Priority-Neutral Matching Lattices Are Not Distributive
<|reference_start|>Priority-Neutral Matching Lattices Are Not Distributive: Stable matchings are a cornerstone of market design, with numerous practical deployments backed by a rich, theoretically-tractable structure. However, in school-choice problems, stable matchings are not Pareto optimal for the students. Priority-neutral matchings, introduced by Reny (AER, 2022), generalizes the set of stable matchings by allowing for certain priority violations, and there is always a Pareto optimal priority-neutral matching. Moreover, like stable matchings, the set of priority-neutral matchings forms a lattice.   We study the structure of the priority-neutral lattice. Unfortunately, we show that much of the simplicity of the stable matching lattice does not hold for the priority-neutral lattice. In particular, we show that the priority-neutral lattice need not be distributive. Moreover, we show that the greatest lower bound of two matchings in the priority-neutral lattice need not be their student-by-student minimum, answering an open question. This show that many widely-used properties of stable matchings fail for priority-neutral matchings; in particular, the set of priority-neutral matchings cannot be represented by via a partial ordering on a set of rotations. However, by proving a novel structural property of the set of priority-neutral matchings, we also show that not every lattice arises as a priority-neutral lattice, which suggests that the exact nature of the family of priority-neutral lattices may be subtle.<|reference_end|>
@article{thomas2024priority-neutral,
    title={Priority-Neutral Matching Lattices Are Not Distributive},
    author={Clayton Thomas},
    journal={arXiv preprint arXiv:2404.02142},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.02142},
    primaryClass={econ.TH cs.GT}
}