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}. ъ
More intriguing information
1. NATURAL RESOURCE SUPPLY CONSTRAINTS AND REGIONAL ECONOMIC ANALYSIS: A COMPUTABLE GENERAL EQUILIBRIUM APPROACH2. The name is absent
3. Retirement and the Poverty of the Elderly in Portugal
4. Fiscal federalism and Fiscal Autonomy: Lessons for the UK from other Industrialised Countries
5. PROFITABILITY OF ALFALFA HAY STORAGE USING PROBABILITIES: AN EXTENSION APPROACH
6. WP 1 - The first part-time economy in the world. Does it work?
7. The name is absent
8. Strategic Investment and Market Integration
9. The name is absent
10. National urban policy responses in the European Union: Towards a European urban policy?