IDEAS home Printed from https://ideas.repec.org/a/kap/theord/v96y2024i1d10.1007_s11238-023-09940-0.html
   My bibliography  Save this article

The lattice of envy-free many-to-many matchings with contracts

Author

Listed:
  • Agustin G. Bonifacio

    (Departamento de Matemática, Universidad Nacional de San Luis)

  • Nadia Guiñazú

    (Departamento de Matemática, Universidad Nacional de San Luis)

  • Noelia Juarez

    (Departamento de Matemática, Universidad Nacional de San Luis)

  • Pablo Neme

    (Departamento de Matemática, Universidad Nacional de San Luis)

  • Jorge Oviedo

    (Departamento de Matemática, Universidad Nacional de San Luis)

Abstract

We study envy-free allocations in a many-to-many matching model with contracts in which agents on one side of the market (doctors) are endowed with substitutable choice functions and agents on the other side of the market (hospitals) are endowed with responsive preferences. Envy-freeness is a weakening of stability that allows blocking contracts involving a hospital with a vacant position and a doctor that does not envy any of the doctors that the hospital currently employs. We show that the set of envy-free allocations has a lattice structure. Furthermore, we define a Tarski operator on this lattice and use it to model a vacancy chain dynamic process by which, starting from any envy-free allocation, a stable one is reached.

Suggested Citation

  • Agustin G. Bonifacio & Nadia Guiñazú & Noelia Juarez & Pablo Neme & Jorge Oviedo, 2024. "The lattice of envy-free many-to-many matchings with contracts," Theory and Decision, Springer, vol. 96(1), pages 113-134, February.
    • Handle: RePEc:kap:theord:v:96:y:2024:i:1:d:10.1007_s11238-023-09940-0
    DOI: 10.1007/s11238-023-09940-0
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11238-023-09940-0
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11238-023-09940-0?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to look for a different version below or search for a different version of it.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Bonifacio, Agustín G. & Juarez, Noelia & Neme, Pablo & Oviedo, Jorge, 2022. "Cycles to compute the full set of many-to-many stable matchings," Mathematical Social Sciences, Elsevier, vol. 117(C), pages 20-29.
    2. Klaus, Bettina & Walzl, Markus, 2009. "Stable many-to-many matchings with contracts," Journal of Mathematical Economics, Elsevier, vol. 45(7-8), pages 422-434, July.
    3. Ahmet Alkan, 2002. "A class of multipartner matching markets with a strong lattice structure," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 19(4), pages 737-746.
    4. Bonifacio, Agustín G. & Guiñazú, Nadia & Juarez, Noelia & Neme, Pablo & Oviedo, Jorge, 2022. "The lattice of worker-quasi-stable matchings," Games and Economic Behavior, Elsevier, vol. 135(C), pages 188-200.
    5. Blum, Yosef & Roth, Alvin E. & Rothblum, Uriel G., 1997. "Vacancy Chains and Equilibration in Senior-Level Labor Markets," Journal of Economic Theory, Elsevier, vol. 76(2), pages 362-411, October.
    6. Kominers, Scott Duke, 2012. "On the correspondence of contracts to salaries in (many-to-many) matching," Games and Economic Behavior, Elsevier, vol. 75(2), pages 984-989.
    7. Hatfield, John William & Kominers, Scott Duke, 2017. "Contract design and stability in many-to-many matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 78-97.
    8. Martinez, Ruth & Masso, Jordi & Neme, Alejandro & Oviedo, Jorge, 2004. "An algorithm to compute the full set of many-to-many stable matchings," Mathematical Social Sciences, Elsevier, vol. 47(2), pages 187-210, March.
    9. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    10. 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.
    11. , & ,, 2006. "A theory of stability in many-to-many matching markets," Theoretical Economics, Econometric Society, vol. 1(2), pages 233-273, June.
    12. Eliana Pepa Risma, 2022. "Matching with contracts: calculation of the complete set of stable allocations," Theory and Decision, Springer, vol. 93(3), pages 449-461, October.
    13. Echenique, Federico & Oviedo, Jorge, 2004. "Core many-to-one matchings by fixed-point methods," Journal of Economic Theory, Elsevier, vol. 115(2), pages 358-376, April.
    14. Wu, Qingyun & Roth, Alvin E., 2018. "The lattice of envy-free matchings," Games and Economic Behavior, Elsevier, vol. 109(C), pages 201-211.
    15. Charles Blair, 1988. "The Lattice Structure of the Set of Stable Matchings with Multiple Partners," Mathematics of Operations Research, INFORMS, vol. 13(4), pages 619-628, November.
    16. Adachi, Hiroyuki, 2000. "On a characterization of stable matchings," Economics Letters, Elsevier, vol. 68(1), pages 43-49, July.
    17. Tamás Fleiner, 2003. "A Fixed-Point Approach to Stable Matchings and Some Applications," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 103-126, February.
    18. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    19. Sotomayor, Marilda, 1999. "Three remarks on the many-to-many stable matching problem," Mathematical Social Sciences, Elsevier, vol. 38(1), pages 55-70, July.
    20. Piotr Dworczak, 2021. "Deferred Acceptance with Compensation Chains," Operations Research, INFORMS, vol. 69(2), pages 456-468, March.
    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. Juárez, Noelia & Neme, Pablo & Oviedo, Jorge, 2022. "Lattice structure of the random stable set in many-to-many matching markets," Games and Economic Behavior, Elsevier, vol. 132(C), pages 255-273.
    2. Bonifacio, Agustín G. & Guiñazú, Nadia & Juarez, Noelia & Neme, Pablo & Oviedo, Jorge, 2022. "The lattice of worker-quasi-stable matchings," Games and Economic Behavior, Elsevier, vol. 135(C), pages 188-200.
    3. Klijn, Flip & Yazıcı, Ayşe, 2014. "A many-to-many ‘rural hospital theorem’," Journal of Mathematical Economics, Elsevier, vol. 54(C), pages 63-73.
    4. 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.
    5. Tam'as Fleiner & Zsuzsanna Jank'o & Akihisa Tamura & Alexander Teytelboym, 2015. "Trading Networks with Bilateral Contracts," Papers 1510.01210, arXiv.org, revised May 2018.
    6. Paula Jaramillo & Çaǧatay Kayı & Flip Klijn, 2014. "On the exhaustiveness of truncation and dropping strategies in many-to-many matching markets," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 42(4), pages 793-811, April.
    7. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    8. Wu, Qingyun & Roth, Alvin E., 2018. "The lattice of envy-free matchings," Games and Economic Behavior, Elsevier, vol. 109(C), pages 201-211.
    9. Tamás Fleiner & Zsuzsanna Jankó & Ildikó Schlotter & Alexander Teytelboym, 2023. "Complexity of stability in trading networks," International Journal of Game Theory, Springer;Game Theory Society, vol. 52(3), pages 629-648, September.
    10. Tam'as Fleiner & Zsuzsanna Jank'o & Ildik'o Schlotter & Alexander Teytelboym, 2018. "Complexity of Stability in Trading Networks," Papers 1805.08758, arXiv.org, revised Feb 2019.
    11. Jagadeesan, Ravi, 2018. "Lone wolves in infinite, discrete matching markets," Games and Economic Behavior, Elsevier, vol. 108(C), pages 275-286.
    12. Eliana Pepa Risma, 2022. "Matching with contracts: calculation of the complete set of stable allocations," Theory and Decision, Springer, vol. 93(3), pages 449-461, October.
    13. Hatfield, John William & Kominers, Scott Duke, 2017. "Contract design and stability in many-to-many matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 78-97.
    14. Antonio Romero-Medina & Matteo Triossi, 2023. "Take-it-or-leave-it contracts in many-to-many matching markets," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 75(2), pages 591-623, February.
    15. Echenique, Federico & Yenmez, M. Bumin, 2007. "A solution to matching with preferences over colleagues," Games and Economic Behavior, Elsevier, vol. 59(1), pages 46-71, April.
    16. Adachi, Hiroyuki, 2017. "Stable matchings and fixed points in trading networks: A note," Economics Letters, Elsevier, vol. 156(C), pages 65-67.
    17. Ayşe Yazıcı, 2017. "Probabilistic stable rules and Nash equilibrium in two-sided matching problems," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(1), pages 103-124, March.
    18. Peter Chen & Michael Egesdal & Marek Pycia & M. Bumin Yenmez, 2021. "Quantile Stable Mechanisms," Games, MDPI, vol. 12(2), pages 1-9, May.
    19. Bando, Keisuke, 2014. "A modified deferred acceptance algorithm for many-to-one matching markets with externalities among firms," Journal of Mathematical Economics, Elsevier, vol. 52(C), pages 173-181.
    20. Chen, Peter & Egesdal, Michael & Pycia, Marek & Yenmez, M. Bumin, 2016. "Median stable matchings in two-sided markets," Games and Economic Behavior, Elsevier, vol. 97(C), pages 64-69.

    More about this item

    Keywords

    Matching with contracts; Envy-freeness; Lattice; Tarski operator; Re-equilibration process; Vacancy chain;
    All these keywords.

    JEL classification:

    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D47 - Microeconomics - - Market Structure, Pricing, and Design - - - Market Design

    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:kap:theord:v:96:y:2024:i:1:d:10.1007_s11238-023-09940-0. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.