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. THE EFFECT OF MARKETING COOPERATIVES ON COST-REDUCING PROCESS INNOVATION ACTIVITY
2. Empirically Analyzing the Impacts of U.S. Export Credit Programs on U.S. Agricultural Export Competitiveness
3. National curriculum assessment: how to make it better
4. The name is absent
5. Visual Perception of Humanoid Movement
6. Behavioural Characteristics and Financial Distress
7. Perfect Regular Equilibrium
8. Credit Market Competition and Capital Regulation
9. STIMULATING COOPERATION AMONG FARMERS IN A POST-SOCIALIST ECONOMY: LESSONS FROM A PUBLIC-PRIVATE MARKETING PARTNERSHIP IN POLAND
10. Optimal Vehicle Size, Haulage Length, and the Structure of Transport Costs