The aim of this paper is twofold. First, we review a key result for roommate problems
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 equilibrium or stability (represented
by Adam Smith2) and fairness (represented by John Rawls3) can be reconciled for roommate
problems.
Formally, a roommate problem (Gale and Shapley, 1962) is a pair (N, (°i)i∈N) where N
is a finite set of agents and, for each i ∈ N, °i is a total order over N.4 For each i ∈ N, we
interpret °i as agent i’s preferences over sharing a room with any of the agents in N∖{i}
and having a room for himself (or consuming an outside option such as living off-campus).
Preferences are strict, i.e., k °i j and j °i k if and only if j = k. The strict preference
relation associated with °i is denoted by Âi. A solution to a roommate problem, a matching
μ, is a partition of N in pairs and singletons. Alternatively, we describe a matching by a
function μ : N → N of order two, i.e., for all i ∈ N, μ(μ(i)) = i. Agent μ(i) is agent
i’s match, i.e., the agent with whom he is matched to share a room (possibly himself). If
μ(i) = i then we call i a single.
A marriage problem (Gale and Shapley, 1962) is a roommate problem (N, (°i)i∈N) such
that N is the union of two disjoint sets M and W (men and women), and each agent
in M (respectively W) prefers being alone to being matched with any other agent in M
(respectively W).
A matching μ is blocked by a pair {i,j} ⊆ N (possibly i = j) if j Âi μ(i) and i Âj μ(j). If
{i, j} blocks μ, then {i,j} is called a blocking pair for μ. A matching is individually rational
if there is no blocking pair {i, j} with i = j. A matching is stable if there is no blocking
pair. A roommate problem is solvable if the set of stable matchings is non-empty. Gale and
Shapley (1962) showed that all marriage problems are solvable and provided an unsolvable
roommate problem (Gale and Shapley, 1962, Example 3).
The following is a simplified version of Gale and Shapley’s example with three agents:
2 Â1 3 Â1 1, 3 Â2 1 Â2 2, and 1 Â3 2 Â3 3. Clearly, the matching where all agents are
singles is not stable (any two agents can block). So, assume two agents share a room. Then,
the single agent is the best roommate for one of these two agents and hence a blocking pair
can be formed. Tan (1991) provided a necessary and sufficient condition for the existence of
a stable matching.
Note that for marriage problems, an individually rational matching never matches two
men or two women, i.e., the partition consists of man-woman pairs and singletons.
2 Lonely Wolves, Medians, and Compromise
Our starting point is a solvable roommate problem. Typically there are multiple stable
matchings and with choice comes the opportunity to select a particularly appealing stable
2Adam Smith (1723-1790), a political economist, propagated the view that individuals even though
interested only in their own gains will still advance public interest (Smith, 1796).
3John Rawls (1921-2002), a political philosopher, discussed important aspects of fairness and justice
particularly suited for economic applications (Rawls, 1971).
4 A total order is a binary relation that satisfies reflexivity, antisymmetry, transitivity, and totality or
comparability.