The roommates problem revisited |
| |
Authors: | Thayer Morrill |
| |
Affiliation: | Department of Economics, North Carolina State University, Raleigh, NC 27695, United States |
| |
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: | C78 D02 |
本文献已被 ScienceDirect 等数据库收录! |
|