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 {μ 1,..., μ2k+1}. Similarly, j prefers i to at least k + 1 stable
matchings in {μ 1,... ,μ2k+1}. Hence, for at least one stable matching μ ∈ {μ 1,... ,μ2k+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 μ 1,... ,μ2k 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{μ 1,... ,μ2k-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.
|
Â1 |
Â2 |
Â3 |
Â4 |
 5 |
Â6 |
Â7 |
Â8 |
|
4 |
7 |
2 |
6 |
2 |
1 |
4 |
7 |
|
2 |
4 |
8 |
2 |
6 |
2 |
6 |
2 |
|
5 |
6 |
5 |
5 |
4 |
8 |
1 |
5 |
|
3 |
8 |
4 |
8 |
7 |
3 |
3 |
1 |
|
8 |
1 |
6 |
3 |
8 |
4 |
5 |
4 |
|
7 |
5 |
1 |
1 |
3 |
5 |
2 |
6 |
|
6 |
3 |
7 |
7 |
1 |
7 |
8 |
3 |
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
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}}
μ4 is the median matching of {μ 1 ,μ2 ,μ3 ,μ4 ,μ5 } and of {μ 1 ,μ3 ,μ5}. ъ