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

Priority-Neutral Matching Lattices Are Not Distributive

Author

Listed:
  • Clayton Thomas

Abstract

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.

Suggested Citation

  • Clayton Thomas, 2024. "Priority-Neutral Matching Lattices Are Not Distributive," Papers 2404.02142, arXiv.org.
    • 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. Atay, Ata & Mauleon, Ana & Vannetelbosch, Vincent, 2022. "School Choice with Farsighted Students," LIDAM Discussion Papers CORE 2022025, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    2. , & , J. & ,, 2011. "Von Neumann-Morgenstern farsightedly stable sets in two-sided matching," Theoretical Economics, Econometric Society, vol. 6(3), September.
    3. Ehlers, Lars, 2007. "Von Neumann-Morgenstern stable sets in matching problems," Journal of Economic Theory, Elsevier, vol. 134(1), pages 537-547, May.
    4. 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.
    5. Linda Cai & Clayton Thomas, 2019. "Representing All Stable Matchings by Walking a Maximal Chain," Papers 1910.04401, arXiv.org.
    6. 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.
    7. 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.
    8. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    9. Troyan, Peter & Delacrétaz, David & Kloosterman, Andrew, 2020. "Essentially stable matchings," Games and Economic Behavior, Elsevier, vol. 120(C), pages 370-390.
    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. Ata Atay & Ana Mauleon & Vincent Vannetelbosch, 2022. "Limited Farsightedness in Priority-Based Matching," Papers 2212.07427, arXiv.org.
    2. 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.
    3. 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.
    4. Troyan, Peter & Delacrétaz, David & Kloosterman, Andrew, 2020. "Essentially stable matchings," Games and Economic Behavior, Elsevier, vol. 120(C), pages 370-390.
    5. 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.
    6. Ata Atay & Sylvain Funck & Ana Mauleon & Vincent Vannetelbosch, 2023. "Matching markets with farsighted couples," UB School of Economics Working Papers 2023/445, University of Barcelona School of Economics.
    7. 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.
    8. 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.
    9. Abdulkadiroglu, Atila & Andersson, Tommy, 2022. "School Choice," Working Papers 2022:4, Lund University, Department of Economics.
    10. 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.
    11. 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.
    12. 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.
    13. 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.
    14. Alvin E. Roth, 2010. "Marketplace Institutions Related to the Timing of Transactions," NBER Working Papers 16556, National Bureau of Economic Research, Inc.
    15. 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.
    16. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    17. Yasushi Kawase & Keisuke Bando, 2021. "Subgame perfect equilibria under the deferred acceptance algorithm," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(2), pages 503-546, June.
    18. Minoru Kitahara & Yasunori Okumura, 2021. "Improving efficiency in school choice under partial priorities," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(4), pages 971-987, December.
    19. Andrew McLennan & Shino Takayama & Yuki Tamura, 2024. "An Efficient, Computationally Tractable School Choice Mechanism," Discussion Papers Series 668, School of Economics, University of Queensland, Australia.
    20. John Kennes & Daniel Monte & Norovsambuu Tumennasan, 2015. "Dynamic Matching Markets and the Deferred Acceptance Mechanism," Economics Working Papers 2015-23, Department of Economics and Business Economics, Aarhus University.

    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.