THE ROOMMATES PROBLEM REVISITED

Abstract. One of the oldest but least understood 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, the traditional notion of stability ignores the key physical constraint that roommates require a room, and it is therefore too restrictive. Recognition of the scarcity of rooms motivates replacing stability with Pareto optimality as the relevant solution concept. This paper proves that a Pareto optimal assignment always exists in the roommates problem, and it provides an efficient algorithm for finding a Pareto improvement starting from any status quo. In this way, the paper reframes a classic matching problem, which previously had no general solution, to become both solvable and economically more meaningful