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. Gianluigi Zenti, President, Academia Barilla SpA - The Changing Consumer: Demanding but Predictable2. Empirically Analyzing the Impacts of U.S. Export Credit Programs on U.S. Agricultural Export Competitiveness
3. Strategic Policy Options to Improve Irrigation Water Allocation Efficiency: Analysis on Egypt and Morocco
4. The name is absent
5. Quelles politiques de développement durable au Mali et à Madagascar ?
6. Biologically inspired distributed machine cognition: a new formal approach to hyperparallel computation
7. Non-causality in Bivariate Binary Panel Data
8. An institutional analysis of sasi laut in Maluku, Indonesia
9. FUTURE TRADE RESEARCH AREAS THAT MATTER TO DEVELOPING COUNTRY POLICYMAKERS
10. Anti Microbial Resistance Profile of E. coli isolates From Tropical Free Range Chickens