Non-distributive Lattices, Stable Matchings, and Linear Optimization

Christopher En and Yuri Faenza

Papers from arXiv.org

Abstract: We show that all finite lattices, including non-distributive lattices, arise as stable matching lattices under standard assumptions on choice functions. 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 non-distributive 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.

Date: 2025-04
New Economics Papers: this item is included in nep-dcm and nep-des
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://arxiv.org/pdf/2504.17916 Latest version (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:arx:papers:2504.17916

Access Statistics for this paper

More papers in Papers from arXiv.org
Bibliographic data for series maintained by arXiv administrators ().