IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v145y2010i5p1739-1756.html
   My bibliography  Save this article

The roommates problem revisited

Author

Listed:
  • Morrill, Thayer

Abstract

One of the oldest matching problems is Gale and Shapley's (1962) [8] "roommates problem": is there a stable way to assign 2N students into N roommate pairs? Unlike the classic marriage problem or college admissions problem, there need not exist a stable solution to the roommates problem. However, stability ignores the key physical constraint that roommates require a room and is therefore too restrictive. This motivates a new matching problem: matching agents subject to an initial assignment. A particularly important example is kidney exchange where after an assignment has been made, subsequent tests may determine that a patient and donor are incompatible. This paper introduces an efficient algorithm for finding a Pareto improvement starting from any status quo roommates assignment.

Suggested Citation

  • Morrill, Thayer, 2010. "The roommates problem revisited," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1739-1756, September.
    • Handle: RePEc:eee:jetheo:v:145:y:2010:i:5:p:1739-1756
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022-0531(10)00025-6
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Tayfun Sönmez & Alvin E. Roth & M. Utku Ünver, 2007. "Efficient Kidney Exchange: Coincidence of Wants in Markets with Compatibility-Based Preferences," American Economic Review, American Economic Association, vol. 97(3), pages 828-851, June.
    2. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    3. Atila Abdulkadiroğlu & Parag A. Pathak & Alvin E. Roth, 2005. "The New York City High School Match," American Economic Review, American Economic Association, vol. 95(2), pages 364-367, May.
    4. Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
    5. 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.
    6. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    7. Parag A. Pathak & Tayfun Sonmez, 2008. "Leveling the Playing Field: Sincere and Sophisticated Players in the Boston Mechanism," American Economic Review, American Economic Association, vol. 98(4), pages 1636-1652, September.
    8. Zenios, Stefanos & Woodle, E. Steve & Ross, Lainie Friedman, 2001. "Primum Non Nocere: Avoiding Harm to Vulnerable Wait List Candidates in an Indirect Kidney Exchange," Research Papers 1684, Stanford University, Graduate School of Business.
    9. 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.
    10. 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.
    11. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    12. Alvin E. Roth & Tayfun Sönmez, 2005. "A Kidney Exchange Clearinghouse in New England," American Economic Review, American Economic Association, vol. 95(2), pages 376-380, May.
    13. Aytek Erdil & Haluk Ergin, 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice," American Economic Review, American Economic Association, vol. 98(3), pages 669-689, June.
    14. Alvin E. Roth, 1982. "The Economics of Matching: Stability and Incentives," Mathematics of Operations Research, INFORMS, vol. 7(4), pages 617-628, November.
    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. Niclas Boehmer & Edith Elkind, 2020. "Stable Roommate Problem with Diversity Preferences," Papers 2004.14640, arXiv.org.
    2. 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.
    3. Peng, Zixuan & Shan, Wenxuan & Guan, Feng & Yu, Bin, 2016. "Stable vessel-cargo matching in dry bulk shipping market with price game mechanism," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 95(C), pages 76-94.
    4. Justin Burkett & Francis X. Flanagan & Amanda L. Griffith, 2018. "Allocating group housing," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(4), pages 581-596, April.
    5. Kong, Qianqian & Peters, Hans, 2023. "Power indices for networks, with applications to matching markets," European Journal of Operational Research, Elsevier, vol. 306(1), pages 448-456.
    6. Duygu Nizamogullari & İpek Özkal-Sanver, 2022. "A note on roommate problems with a limited number of rooms," Review of Economic Design, Springer;Society for Economic Design, vol. 26(4), pages 553-560, December.
    7. Aziz, Haris & Brandt, Felix & Harrenstein, Paul, 2013. "Pareto optimality in coalition formation," Games and Economic Behavior, Elsevier, vol. 82(C), pages 562-581.
    8. Hakan İnal, 2014. "A Generalization of the Lone Wolf Theorem," Metroeconomica, Wiley Blackwell, vol. 65(4), pages 541-547, November.
    9. Andreas Darmann, 2018. "Stable and Pareto optimal group activity selection from ordinal preferences," International Journal of Game Theory, Springer;Game Theory Society, vol. 47(4), pages 1183-1209, November.
    10. Edith Elkind & Angelo Fanelli & Michele Flammini, 2020. "Price of Pareto Optimality in hedonic games," Post-Print hal-02932135, HAL.
    11. Azar Abizada, 2019. "Exchange-stability in roommate problems," Review of Economic Design, Springer;Society for Economic Design, vol. 23(1), pages 3-12, June.
    12. Peter Biro & Elena Iñarra & Elena Molis, 2014. "A new solution for the roommate problem. The Q-stable matchings," ThE Papers 14/04, Department of Economic Theory and Economic History of the University of Granada..
    13. Combe, Julien, 2022. "Matching with ownership," Journal of Mathematical Economics, Elsevier, vol. 98(C).
    14. Agnes Cseh & Tamas Fleiner & Petra Harjan, 2020. "Pareto optimal coalitions of fixed size," CERS-IE WORKING PAPERS 2005, Institute of Economics, Centre for Economic and Regional Studies.
    15. Biró, Péter & Iñarra, Elena & Molis, Elena, 2016. "A new solution concept for the roommate problem: Q-stable matchings," Mathematical Social Sciences, Elsevier, vol. 79(C), pages 74-82.
    16. Greg Leo & Yevgeniy Vorobeychik & Myrna Wooders, 2023. "Subgame Perfect Coalition Formation," Dynamic Games and Applications, Springer, vol. 13(2), pages 510-524, June.
    17. Kondor, Gábor, 2022. "Egyoldali párosítási piacok nehézségi eredményei magasabb dimenzióban [Hardness results of one-sided matching markets in higher dimensions]," 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(7), pages 825-840.

    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. 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.
    2. Alvin E. Roth, 2009. "What Have We Learned from Market Design?," Innovation Policy and the Economy, University of Chicago Press, vol. 9(1), pages 79-112.
    3. Morrill, Thayer & Roth, Alvin E., 2024. "Top trading cycles," Journal of Mathematical Economics, Elsevier, vol. 112(C).
    4. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers 1327, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
    5. Chen, Yan & Jiang, Ming & Kesten, Onur & Robin, Stéphane & Zhu, Min, 2018. "Matching in the large: An experimental study," Games and Economic Behavior, Elsevier, vol. 110(C), pages 295-317.
    6. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers halshs-00860931, HAL.
    7. Roth, Alvin E. & Sonmez, Tayfun & Utku Unver, M., 2005. "Pairwise kidney exchange," Journal of Economic Theory, Elsevier, vol. 125(2), pages 151-188, December.
    8. Alvin E. Roth, 2010. "Marketplace Institutions Related to the Timing of Transactions," NBER Working Papers 16556, National Bureau of Economic Research, Inc.
    9. 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.
    10. Zhu, Min, 2014. "College admissions in China: A mechanism design perspective," China Economic Review, Elsevier, vol. 30(C), pages 618-631.
    11. José Alcalde & Antonio Romero-Medina, 2017. "Fair student placement," Theory and Decision, Springer, vol. 83(2), pages 293-307, August.
    12. Kesten, Onur & Kurino, Morimitsu, 2019. "Strategy-proof improvements upon deferred acceptance: A maximal domain for possibility," Games and Economic Behavior, Elsevier, vol. 117(C), pages 120-143.
    13. Ehlers, Lars, 2014. "Top trading with fixed tie-breaking in markets with indivisible goods," Journal of Economic Theory, Elsevier, vol. 151(C), pages 64-87.
    14. Abdulkadiroglu, Atila & Andersson, Tommy, 2022. "School Choice," Working Papers 2022:4, Lund University, Department of Economics.
    15. 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.
    16. Featherstone, Clayton R. & Niederle, Muriel, 2016. "Boston versus deferred acceptance in an interim setting: An experimental investigation," Games and Economic Behavior, Elsevier, vol. 100(C), pages 353-375.
    17. 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.
    18. Onur Kesten, 2012. "On two kinds of manipulation for school choice problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 51(3), pages 677-693, November.
    19. 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.
    20. Troyan, Peter, 2012. "Comparing school choice mechanisms by interim and ex-ante welfare," Games and Economic Behavior, Elsevier, vol. 75(2), pages 936-947.

    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:eee:jetheo:v:145:y:2010:i:5:p:1739-1756. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/inca/622869 .

    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.