The roommates problem revisited
AbstractOne of the oldest matching problems is Gale and Shapley's (1962)  "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.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Bibliographic InfoArticle provided by Elsevier in its journal Journal of Economic Theory.
Volume (Year): 145 (2010)
Issue (Month): 5 (September)
Contact details of provider:
Web page: http://www.elsevier.com/locate/inca/622869
Matching Roommates problem Market design Kidney exchange Edmonds' blossom algorithm;
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Alvin E. Roth & Tayfun Sonmez & M. Utku Unver, 2004.
"Pairwise Kidney Exchange,"
122247000000000350, UCLA Department of Economics.
- Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Pairwise Kidney Exchange," Game Theory and Information 0408001, EconWPA, revised 16 Feb 2005.
- Alvin E. Roth & Tayfun Sonmez & M. Utku Unver, 2004. "Pairwise Kidney Exchange," NBER Working Papers 10698, National Bureau of Economic Research, Inc.
- Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Pairwise Kidney Exchange," Boston College Working Papers in Economics 620, Boston College Department of Economics.
- Roth, Alvin & Ãœnver, M. Utku & SÃ¶nmez, Tayfun, 2005.
"A Kidney Exchange Clearinghouse in New England,"
2562810, Harvard University Department of Economics.
- Chung, Kim-Sau, 2000. "On the Existence of Stable Roommate Matchings," Games and Economic Behavior, Elsevier, vol. 33(2), pages 206-230, November.
- Pathak, Parag A. & Abdulkadiroglu, Atila & Roth, Alvin, 2005.
"The New York City High School Match,"
2562765, Harvard University Department of Economics.
- Aytek Erdil & Haluk Ergin, 2007.
"What`s the Matter with Tie-breaking? Improving Efficiency in School Choice,"
Economics Series Working Papers
349, University of Oxford, Department of Economics.
- 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-89, June.
- 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.
- S. Illeris & G. Akehurst, 2001. "Introduction," The Service Industries Journal, Taylor & Francis Journals, vol. 21(1), pages 1-4, January.
- 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.
- 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-78, December.
- Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
- 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.
- Ãœnver, M. Utku & SÃ¶nmez, Tayfun & Roth, Alvin, 2007. "Efficient Kidney Exchange: Coincidence of Wants in a Markets with Compatibility-Based Preferences," Scholarly Articles 2562809, Harvard University Department of Economics.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Zhang, Lei).
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 references are entirely missing, you can add them using this form.
If the full references list an item that is present in RePEc, but the system did not link 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 profile, as there may be some citations waiting for confirmation.
Please note that corrections may take a couple of weeks to filter through the various RePEc services.