Smith and Rawls Share a Room

Example 1 An even number of stable matchings and no compromise

Consider the following roommate problem with 8 agents and preferences as listed in the table
below. The first column, for instance, means that 8 Â1 2 Â1 7 Â1 4 Â1 1 Â1 5 Â1 3 Â1 6.

μi = {{1, 2},{3,4},{5,6},{7, 8}}
μ 2 = {{1,2},{3,4},{5,8},{6,7}}

μз = {{1,4},{2,3},{5, 6}, {7, 8}}

μ 4 = {{1,4},{2,3},{5,8},{6,7}}

The following (weak) rankings on matchings are induced (~ denotes indifferences):

μ 1 ~ 1 μ 2 Â 1 μ з ~ ι μ 4

μ 3 ~ 2 μ 4 Â 2 μ ι ~ 2 μ 2

μ 1 ~ 3 μ 2 Â 3 μ з ~ з μ 4

μ з ~ 4 μ 4 Â 4 μ 1 ~ 4 μ 2

μ 1 ~ 5 μ з Â 5 μ 2 ~ 5 μ 4

μ 2 ~ 6 μ 4 Â 6 μ 1 ~ 6 μ з

μ 1 ~ 7 μ з Â 7 μ 2 ~ 7 μ 4

μ 2 ~ 8 μ 4 Â 8 μ 1 ~ 8 μ з

Agents 1, 2, and 4 order their matches at the 4 stable matchings as 2, 2, 4, 4; 3, 3, 1, 1; and
1, 1, 3, 3 respectively. If agent 1 is given his first or second choice, then he is matched with
agent 2 who then receives his third or fourth choice. If agent 1 is given his third or fourth
choice, then he is matched with agent 4 who then receives his first or second choice. It
follows that matching all agents with a k-th ranked match is not possible.               0

The impossibility result exhibited in the example is due to the fact that there is an even
number of (distinct) stable matchings. Next, we show that for roommate problems with an
odd number of stable matchings a compromise matching where each agent is matched to a
match of the same rank is possible. In fact, we prove that for any odd number of stable
matchings, a stable matching at which each agent is matched to his “median” match always
exists. Thus, for roommate problems with an odd number of stable matchings Adam Smith
(who stands for stability) and John Rawls (who stands for fairness) represent compatible
criteria and hence “can share a room.”⁵

⁵Example 1 is an example where the equilibrium and the fairness principles represented by Adam Smith
and John Rawls are incompatible: there they will never be able to share a room.

<<   <   1   2   3   4   5   6   7   >   >>