The roommates problem revisited

Thayer Morrill

Journal of Economic Theory, 2010, vol. 145, issue 5, 1739-1756

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.

Keywords: Matching; Roommates; problem; Market; design; Kidney; exchange; Edmonds'; blossom; algorithm (search for similar items in EconPapers)
Date: 2010
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (19)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0022-0531(10)00025-6
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:jetheo:v:145:y:2010:i:5:p:1739-1756

Access Statistics for this article

Journal of Economic Theory is currently edited by A. Lizzeri and K. Shell

More articles in Journal of Economic Theory from Elsevier
Bibliographic data for series maintained by Catherine Liu ().