All finite lattices are stable matching lattices
This foundational result in matching theory and lattice theory addresses a theoretical gap, with implications for optimization and computational complexity.
The paper proves that all finite lattices can be realized as stable matching lattices with path-independent choice functions, resolving an open question, and introduces new tools like partial representations and distributive closures for lattice optimization.
We show that all finite lattices, including non-distributive lattices, arise as stable matching lattices when all agents have path-independent choice functions. This result answers an open question of Blair~\cite{blair1988lattice}. In the process, we introduce new tools to reason on general lattices for optimization purposes: the \emph{partial representation} of a lattice, which partially extends Birkhoff's representation theorem to non-distributive lattices; the \emph{distributive closure} of a lattice, which gives such a partial representation; and \emph{join constraints}, which can be added to the distributive closure to obtain a representation for the original lattice. Then, we use these techniques to show that the minimum cost stable matching problem under the same standard assumptions on choice functions is NP-hard, by establishing a connection with antimatroid theory.