Smith and Rawls Share a Room

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
μ⁰ , 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{μ₁(i), . . . , μ_2k+1(i)}.

Theorem 2 Smith and Rawls share a room

Let μ ₁,... ,μ2_k+ɪ be an odd number of (possibly non-distinct) stable matchings. Then, μ* :
N → N defined by

μ* (i) := med{μ ₁(i),..., μ2_k+₁(i)} for all i ∈ N

is a well-defined stable matching. We call μ* the median matching of μ ₁,... ,μ2_k+ɪ.

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 μ2_k(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,

<<   <   2   3   4   5   6   7   8   >   >>