All Finite Lattices Are Stable Matching Lattices

We show that all finite lattices, including nondistributive lattices, arise as stable matching lattices when all agents have path-independent choice functions. This result answers an open question of Blair. In the process, we introduce new tools to reason on general lattices for optimization purposes: the partial representation of a lattice, which partially extends Birkhoff’s representation theorem to nondistributive lattices; the distributive closure of a lattice, which gives such a partial representation; and 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.

Funding: This work was supported by the Division of Computing and Communication Foundations, NSF [Grant 2046146]; by the Air Force Office of Scientific Research [Grant FA9550-23-1-0697]; and by a Cheung-Kong Innovation Doctoral Fellowship.