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
μ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,... ,μ2kbe 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. Automatic Dream Sentiment Analysis
2. The name is absent
3. The name is absent
4. Indirect Effects of Pesticide Regulation and the Food Quality Protection Act
5. Standards behaviours face to innovation of the entrepreneurships of Beira Interior
6. The Clustering of Financial Services in London*
7. Explaining Growth in Dutch Agriculture: Prices, Public R&D, and Technological Change
8. The name is absent
9. The name is absent
10. The name is absent