Smith and Rawls Share a Room

In particular, it follows that μ*(j) = μ_k+1(j). Hence, μ*(μ*(i)) = μ*(j) = μ_k+1(j) = i.

We now prove that μ* is stable. By definition, μ* is individually rational. Suppose there
is a blocking pair {i,j} with i = j, i.e., j Âi μ*(i) and i Âj μ*(j). Then, i prefers j to at
least k + 1 stable matchings in {μ ₁,..., μ2_k+1}. Similarly, j prefers i to at least k + 1 stable
matchings in {μ ₁,... ,μ2_k+1}. Hence, for at least one stable matching μ ∈ {μ ₁,... ,μ2_k+1},
j Âi μ(i) and i Âj μ(j), contradicting stability.                                             ¥

We can easily extend the result of Theorem 2 to an even number of stable matchings
(Sethuraman and Teo, 2001, Theorem 3.3).

Corollary 1 Smith and Raw ls (almost) share a room

Let μ ₁,... ,μ2_k be an even number of (possibly non-distinct) stable matchings. Then, there
exists a stable matching at which each agent is assigned a match of rank k or k + 1.

Proof By Theorem 2, the median of the first 2k — 1 stable matchings, i.e., μ* =
med{μ ₁,... ,μ2_k-1}, is a well-defined and stable matching. Then, for any i ∈ N,

...      , _{1 1} , * .,_{1 1} . f k-th ranked match if μ* ( i ) °i μ 2 k ( i );

agent i is matched at ^μ with his I (k + 1)-_st ranked match _if μ(i) . _μ,2^(i.         _b

In the next example we calculate the median matching for three stable matchings and
demonstrate that the “median operator” is not closed, i.e., that the resulting median match-
ing is not always one of the stable matchings that were used to calculate it.

Example 2 An odd number of stable matchings and median matchings

Consider the following roommate problem with 8 agents and preferences as listed in the table
below.

There are 5 stable matchings:

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

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

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

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

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

μ₄ is the median matching of {μ ₁ ,μ2 ,μ₃ ,μ₄ ,μ₅ } and of {μ ₁ ,μ₃ ,μ₅}.                       ъ

<<   3   4   5   6   7   8   9   >>

More intriguing information