IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v16y2008i4d10.1007_s10878-008-9153-1.html
   My bibliography  Save this article

Stable matching problems with exchange restrictions

Author

Listed:
  • Robert W. Irving

    (University of Glasgow)

Abstract

We study variants of classical stable matching problems in which there is an additional requirement for a stable matching, namely that there should not be two participants who would prefer to exchange partners. The problem is motivated by the experience of real-world medical matching schemes that use stable matchings, where cases have arisen in which two participants discovered that each of them would prefer the other’s allocation, a situation that is seen as unfair. Our main result is that the problem of deciding whether an instance of the classical stable marriage problem admits a stable matching, with the additional property that no two men would prefer to exchange partners, is NP-complete. This implies a similar result for more general problems, such as the hospitals/residents problem, the many-to-one extension of stable marriage. Unlike previous NP-hardness results for variants of stable marriage, the proof exploits the powerful algebraic structure underlying the set of all stable matchings. In practical matching schemes, however, applicants’ preference lists are typically of short fixed length, and we describe a linear time algorithm for the problem in the special case where all of the men’s preference lists are of length ≤3.

Suggested Citation

  • Robert W. Irving, 2008. "Stable matching problems with exchange restrictions," Journal of Combinatorial Optimization, Springer, vol. 16(4), pages 344-360, November.
    • Handle: RePEc:spr:jcomop:v:16:y:2008:i:4:d:10.1007_s10878-008-9153-1
    DOI: 10.1007/s10878-008-9153-1
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-008-9153-1
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10878-008-9153-1?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 search for a different version of it.

    References listed on IDEAS

    as
    1. 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.
    2. José Alcalde, 1994. "Exchange-proofness or divorce-proofness? Stability in one-sided matching markets," Review of Economic Design, Springer;Society for Economic Design, vol. 1(1), pages 275-287, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kolos Csaba Ágoston & Péter Biró & Iain McBride, 2016. "Integer programming methods for special college admissions problems," Journal of Combinatorial Optimization, Springer, vol. 32(4), pages 1371-1399, November.
    2. Vergote, W., 2015. "One-to-One Matching Problems with Location Restrictions," LIDAM Discussion Papers CORE 2015054, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. Wouter Vergote, 2019. "Revisiting stability in one-to-one matching problems," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(1), pages 59-75, May.
    4. Pittel, Boris, 2018. "On random exchange-stable matchings," Mathematical Social Sciences, Elsevier, vol. 93(C), pages 1-13.

    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. Peter Coles & John Cawley & Phillip B. Levine & Muriel Niederle & Alvin E. Roth & John J. Siegfried, 2010. "The Job Market for New Economists: A Market Design Perspective," Journal of Economic Perspectives, American Economic Association, vol. 24(4), pages 187-206, Fall.
    2. 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.
    3. Muriel Niederle & Alvin E. Roth, 2009. "The Effects of a Centralized Clearinghouse on Job Placement, Wages, and Hiring Practices," NBER Chapters, in: Studies of Labor Market Intermediation, pages 235-271, National Bureau of Economic Research, Inc.
    4. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    5. Parag A. Pathak & Alex Rees-Jones & Tayfun Sönmez, 2020. "Immigration Lottery Design: Engineered and Coincidental Consequences of H-1B Reforms," NBER Working Papers 26767, National Bureau of Economic Research, Inc.
    6. Du, Qingyuan & Wei, Shang-Jin, 2013. "A theory of the competitive saving motive," Journal of International Economics, Elsevier, vol. 91(2), pages 275-289.
    7. 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.
    8. Marco LiCalzi, 2022. "Bipartite choices," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 45(2), pages 551-568, December.
    9. Jiang, Zhishan & Tian, Guoqiang, 2013. "Matching with Couples: Stability and Algorithm," MPRA Paper 57936, University Library of Munich, Germany, revised Jul 2014.
    10. Akahoshi, Takashi, 2014. "Singleton core in many-to-one matching problems," Mathematical Social Sciences, Elsevier, vol. 72(C), pages 7-13.
    11. Roth, Alvin E & Xing, Xiaolin, 1997. "Turnaround Time and Bottlenecks in Market Clearing: Decentralized Matching in the Market for Clinical Psychologists," Journal of Political Economy, University of Chicago Press, vol. 105(2), pages 284-329, April.
    12. TANAKA Mari & NARITA Yusuke & MORIGUCHI Chiaki, 2020. "Meritocracy and Its Discontent: Long-run Effects of Repeated School Admission Reforms," Discussion papers 20002, Research Institute of Economy, Trade and Industry (RIETI).
    13. Matilde P. Machado & Ricardo Mora & Antonio Romero-Medina, 2012. "Can We Infer Hospital Quality From Medical Graduates’ Residency Choices?," Journal of the European Economic Association, European Economic Association, vol. 10(6), pages 1400-1424, December.
    14. Gary Charness & Francesco Feri & Miguel A. Meléndez‐Jiménez & Matthias Sutter, 2014. "Experimental Games on Networks: Underpinnings of Behavior and Equilibrium Selection," Econometrica, Econometric Society, vol. 82(5), pages 1615-1670, September.
    15. van Damme, E.E.C., 1995. "Game theory : The next stage," Other publications TiSEM 7779b0f9-bef5-45c7-ae6b-7, Tilburg University, School of Economics and Management.
    16. Kóczy Á., László, 2009. "Központi felvételi rendszerek. Taktikázás és stabilitás [Central admission systems. Stratagems and stability]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(5), pages 422-442.
    17. Jeremy Bulow & Jonathan Levin, 2006. "Matching and Price Competition," American Economic Review, American Economic Association, vol. 96(3), pages 652-668, June.
    18. James Boudreau & Vicki Knoblauch, 2013. "Preferences and the price of stability in matching markets," Theory and Decision, Springer, vol. 74(4), pages 565-589, April.
    19. Echenique, Federico & Galichon, Alfred, 2017. "Ordinal and cardinal solution concepts for two-sided matching," Games and Economic Behavior, Elsevier, vol. 101(C), pages 63-77.
    20. Michael Vlassopoulos, 2017. "‘Putting a Foot in the Door’: Volunteer Hiring and Organizational Form," Manchester School, University of Manchester, vol. 85(2), pages 133-162, March.

    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:spr:jcomop:v:16:y:2008:i:4:d:10.1007_s10878-008-9153-1. 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.