The next lemma, which appeared in Gusfield and Irving (1989, Lemma 4.3.9), facilitates
the proof of our main result.
Lemma 1 Let μ and μ' be stable matchings. Let i ∈ N. Suppose μ'(i) = μ(i) = j for some
j ∈ N. Then, j,μ'(i) = i. Moreover, μ(i) Âi μ'(i) implies μ'(j) Âj μ(j).
Proof By Theorem 1, j,μ'(i) = i. Suppose μ(i) Âi μ,(i) and μ(j) °j μ,(j). Since
preferences are strict and μ(j) = i = μ'(j), μ(j) Âj μ,(j). Hence, {i, j} is a blocking pair for
μ0 , contradicting stability. ¥
Our main result, Theorem 2, extends Theorem 4.3.5 in Gusfield and Irving (1989) from
three to any odd number of stable matchings.
Let μ1 , . . . , μ2k+1 be an odd number of (possibly non-distinct) stable matchings. Let each
agent rank these matchings according to his preferences as explained before (Example 1).
We denote agent i’s (k + 1)-st ranked match by med{μ1(i), . . . , μ2k+1(i)}.
Theorem 2 Smith and Rawls share a room
Let μ 1,... ,μ2k+ɪ be an odd number of (possibly non-distinct) stable matchings. Then, μ* :
N → N defined by
μ* (i) := med{μ 1(i),..., μ2k+1(i)} for all i ∈ N
is a well-defined stable matching. We call μ* the median matching of μ 1,... ,μ2k+ɪ.
In the context of the linear programming approach to so-called bistable matching problems,
Sethuraman and Teo (2001, Theorem 3.2) mentioned this result (without proof) as an in-
teresting structural property of stable roommate matchings. Here we provide an elementary
proof.
Proof First, we show that μ* is a well-defined matching, i.e., μ* is of order 2. Let i ∈ N
with μ*(i) = i. We have to prove that μ*(μ*(i)) = i. Let j := μ*(i). Without loss of
generality, μɪ(i) °i μ2(i) °i ■■■ °i μ2k(i) °i μ2k+ι(i). Then, μ*(i) = μk+ι(i) = j and
μk+1(j) = i. Let S = {μ1, . . . , μ2k+1}. Define
Bi := {μ ∈ S I μ °i μk+ɪ},
wi := {μ ∈ s i μ ^i μk+ɪ}
Bj := {μ ∈ S I μ Âj μk+ɪ}, and
wj := {μ ∈ s i μ ^j μk+ɪ}.
Clearly, {Bi, Wi} and {Bj,Wj} are partitions of S, where possibly Wi = 0 or Bj = 0.
By Lemma 1, Wi ⊆ Bj. Suppose there exists μ ∈ Bj \ Wi. Since Bi U Wi = S, μ ∈ Bi.
Thus, μ ∈ Bi ∩ Bj. Since μ ∈ Bj, μ Âj μk+ɪ. In particular, since μk+ɪ(j) = i, μ(j) = i.
Then, since μ ∈ Bi, μ Âi μk+ɪ. Hence, {i,j} is a blocking pair for μk+ɪ, contradicting
stability. So, Wi = Bj. Since {Bi,Wi} and {Bj,Wj} are partitions of S, Bi = Wj. Hence,
Bi
z---------------------------------}|--------------------------
μɪ °i μ2 °i ■ ■ ■ °i μk+ɪ ~i
Wi
Âi
Âj
Wi
■ ■ ■ ~j μk+ɪ °j {μɪ,..., μk}
|--------------------{z---------------------}
Bi
More intriguing information
1. Cyber-pharmacies and emerging concerns on marketing drugs Online2. Ex post analysis of the regional impacts of major infrastructure: the Channel Tunnel 10 years on.
3. The name is absent
4. The name is absent
5. Endogenous Determination of FDI Growth and Economic Growth:The OECD Case
6. Forecasting Financial Crises and Contagion in Asia using Dynamic Factor Analysis
7. Death as a Fateful Moment? The Reflexive Individual and Scottish Funeral Practices
8. The name is absent
9. Reputations, Market Structure, and the Choice of Quality Assurance Systems in the Food Industry
10. The name is absent