The roommates problem revisited

• 成果类型: Article
• 署名作者: Morrill, Thayer
• 署名单位: North Carolina State University
• 刊物名称: JOURNAL OF ECONOMIC THEORY
• ISSN/ISSBN: 0022-0531
• DOI: 10.1016/j.jet.2010.02.003
• 发表日期: 2010
• 页码: 1739-1756
• 关键词: Matching; Roommates problem; market design; kidney exchange; Edmonds' blossom algorithm

摘要

One of the oldest matching problems is Gale and Shapley's (1962) [81 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. (C) 2010 Elsevier Inc. All rights reserved.