Smith and Rawls Share a Room

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 Smith²) and fairness (represented by John Rawls³) 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.⁴ 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

²Adam 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).

³John Rawls (1921-2002), a political philosopher, discussed important aspects of fairness and justice
particularly suited for economic applications (Rawls, 1971).

⁴ A total order is a binary relation that satisfies reflexivity, antisymmetry, transitivity, and totality or
comparability.

<<   1   2   3   4   5   >>

More intriguing information