IDEAS home Printed from https://ideas.repec.org/p/arx/papers/2404.02142.html
   My bibliography  Save this paper

Characterization of Priority-Neutral Matching Lattices

Author

Listed:
  • Clayton Thomas

Abstract

We study the structure of the set of priority-neutral matchings. These matchings, introduced by Reny (AER, 2022), generalize stable matchings by allowing for priority violations in a principled way that enables Pareto-improvements to stable matchings. Known results show that the set of priority-neutral matchings is a lattice, suggesting that these matchings may enjoy the same tractable theoretical structure as stable matchings. In this paper, we characterize priority-neutral matching lattices, and show that their structure is considerably more intricate than that of stable matching lattices. To begin, we show priority-neutral lattices are not distributive, an important property that characterizes stable lattices and is satisfied by many other lattice structures considered in matching theory and algorithm design. Then, in our main result, we show that priority-neutral lattices are in fact characterized by a more-involved property which we term being a "movement lattice," which allows for significant departures from the order theoretic properties of distributive (and hence stable) lattices. While our results show that priority-neutrality is more intricate than stability, they also establish tractable properties. Indeed, as a corollary of our main result, we obtain the first known polynomial-time algorithm for checking whether a given matching is priority-neutral.

Suggested Citation

  • Clayton Thomas, 2024. "Characterization of Priority-Neutral Matching Lattices," Papers 2404.02142, arXiv.org, revised Dec 2025.
    • Handle: RePEc:arx:papers:2404.02142
    as

    Download full text from publisher

    File URL: http://arxiv.org/pdf/2404.02142
    File Function: Latest version
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Qianfeng Tang & Yongchao Zhang, 2021. "Weak stability and Pareto efficiency in school choice," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(2), pages 533-552, March.
    2. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2025. "School choice with farsighted students," Games and Economic Behavior, Elsevier, vol. 149(C), pages 148-163.
    3. , & , J. & ,, 2011. "Von Neumann-Morgenstern farsightedly stable sets in two-sided matching," Theoretical Economics, Econometric Society, vol. 6(3), September.
    4. Ehlers, Lars, 2007. "Von Neumann-Morgenstern stable sets in matching problems," Journal of Economic Theory, Elsevier, vol. 134(1), pages 537-547, May.
    5. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-proofness versus Efficiency in Matching with Indifferences: Redesigning the New York City High School Match," NBER Working Papers 14864, National Bureau of Economic Research, Inc.
    6. Linda Cai & Clayton Thomas, 2019. "Representing All Stable Matchings by Walking a Maximal Chain," Papers 1910.04401, arXiv.org.
    7. Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
    8. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," American Economic Review, American Economic Association, vol. 99(5), pages 1954-1978, December.
    9. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    10. Troyan, Peter & Delacrétaz, David & Kloosterman, Andrew, 2020. "Essentially stable matchings," Games and Economic Behavior, Elsevier, vol. 120(C), pages 370-390.
    11. Gul, Faruk & Stacchetti, Ennio, 1999. "Walrasian Equilibrium with Gross Substitutes," Journal of Economic Theory, Elsevier, vol. 87(1), pages 95-124, July.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Rodríguez-Álvarez, Carmelo & Romero-Medina, Antonio, 2024. "School choice with transferable student characteristics," Games and Economic Behavior, Elsevier, vol. 143(C), pages 103-124.
    2. Zhang, Luosai, 2025. "The properness of weak stability notions," Economics Letters, Elsevier, vol. 247(C).
    3. Ata Atay & Ana Mauleon & Vincent Vannetelbosch, 2025. "Limited Farsightedness in Priority‐Based Matching," Journal of Public Economic Theory, Association for Public Economic Theory, vol. 27(4), August.
    4. Lars Ehlers & Bettina Klaus, 2012. "Strategy-Proofness Makes the Difference : Deferred-Acceptance with Responsive Priorities," Cahiers de recherche 15-2012, Centre interuniversitaire de recherche en économie quantitative, CIREQ.
    5. Troyan, Peter & Delacrétaz, David & Kloosterman, Andrew, 2020. "Essentially stable matchings," Games and Economic Behavior, Elsevier, vol. 120(C), pages 370-390.
    6. Julien Combe, 2023. "Reallocation with priorities and minimal envy mechanisms," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(2), pages 551-584, August.
    7. Ata Atay & Sylvain Funck & Ana Mauleon & Vincent Vannetelbosch, 2025. "Matching markets with farsighted couples," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 64(3), pages 465-481, May.
    8. Battal Dogan & Lars Ehlers, 2020. "Blocking pairs versus blocking students: Stability comparisons in school choice," Cahiers de recherche 2020-02, Universite de Montreal, Departement de sciences economiques.
    9. Qianfeng Tang & Yongchao Zhang, 2021. "Weak stability and Pareto efficiency in school choice," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(2), pages 533-552, March.
    10. Kang Rong & Qianfeng Tang & Yongchao Zhang, 2024. "The core of school choice problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 77(3), pages 783-800, May.
    11. Abdulkadiroglu, Atila & Andersson, Tommy, 2022. "School Choice," Working Papers 2022:4, Lund University, Department of Economics.
    12. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2025. "School choice with farsighted students," Games and Economic Behavior, Elsevier, vol. 149(C), pages 148-163.
    13. Franz Diebold & Haris Aziz & Martin Bichler & Florian Matthes & Alexander Schneider, 2014. "Course Allocation via Stable Matching," Business & Information Systems Engineering: The International Journal of WIRTSCHAFTSINFORMATIK, Springer;Gesellschaft für Informatik e.V. (GI), vol. 6(2), pages 97-110, April.
    14. Lars Ehlers & Bettina Klaus, 2014. "Strategy-Proofness Makes the Difference: Deferred-Acceptance with Responsive Priorities," Mathematics of Operations Research, INFORMS, vol. 39(4), pages 949-966, November.
    15. Claudia Cerrone & Yoan Hermstrüwer & Onur Kesten, 2024. "School Choice with Consent: an Experiment," The Economic Journal, Royal Economic Society, vol. 134(661), pages 1760-1805.
    16. Michel Callon & Alvin E. Roth, 2021. "The design and performation of markets: a discussion," AMS Review, Springer;Academy of Marketing Science, vol. 11(3), pages 219-239, December.
    17. Chao Huang, 2021. "Stable matching: an integer programming approach," Papers 2103.03418, arXiv.org, revised Apr 2022.
    18. Diebold, Franz & Bichler, Martin, 2017. "Matching with indifferences: A comparison of algorithms in the context of course allocation," European Journal of Operational Research, Elsevier, vol. 260(1), pages 268-282.
    19. Alvin E. Roth, 2010. "Marketplace Institutions Related to the Timing of Transactions," NBER Working Papers 16556, National Bureau of Economic Research, Inc.
    20. Ortega, Josué & Klein, Thilo, 2022. "Improving Efficiency and Equality in School Choice," QBS Working Paper Series 2022/02, Queen's University Belfast, Queen's Business School.

    More about this item

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:arx:papers:2404.02142. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: arXiv administrators (email available below). General contact details of provider: http://arxiv.org/ .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.