Smith and Rawls Share a Room *
Bettina Klaust Flip Klijn^
June 2007
Abstract
We consider one-to-one matching (roommate) problems in which agents (students) can
either be matched as pairs or remain single. The aim of this paper is twofold. First, we
review a key result for roommate problems (the “lonely wolf” theorem) for which we
provide a concise and elementary proof. Second, and related to the title of this paper,
we show how the often incompatible concepts of stability (represented by the political
economist Adam Smith) and fairness (represented by the political philosopher John
Rawls) can be reconciled for roommate problems.
JEL classification: C62, C78.
Keywords: roommate problem, stability, fairness.
1 Roommate Markets
We consider one-to-one matching problems in which agents can either be matched as pairs
or remain single. Gale and Shapley (1962, Example 3) introduced these so-called roommate
problems as follows: “An even number of boys wish to divide up into pairs of roommates.”
A very common extension of this problem is to allow also for odd numbers of agents and to
consider the formation of pairs and singletons (rooms can be occupied either by one or by
two agents). The class of roommate problems also include as special cases the well-known
marriage problems (Gale and Shapley, 1962).1
* B. Klaus thanks the Netherlands Organisation for Scientific Research (NWO) for its support under grant
VIDI-452-06-013. F. Klijn’s research was supported through the Spanish Plan Nacional I+D+I (SEJ2005-
01690) and the Generalitat de Catalunya (SGR2005-00626 and the Barcelona Economics Program of XREA).
tDepartment of Economics, Maastricht University, P.O. Box 616, 6200 MD Maastricht, The Netherlands;
e-mail: [email protected]
⅛ Corresponding author : Institute for Economic Analysis (CSIC), Campus UAB, 08193 Bellaterra
(Barcelona), Spain; e-mail: [email protected]
1There is a large literature on the marriage problem; see, for instance, Roth and Sotomayor (1990)
and the two-sided matching bibliography on Al Roth’s game theory, experimental economics, and market
design page. In comparison, relatively few papers and books deal with roommate problems; some of the key
references concerning roommate problems are Chung (2000); Diamantoudi et al. (2004); Gusfield and Irving
(1989); Tan (1991).