Smith and Rawls Share a Room



For marriage problems we even have a stronger result. Let μ 1,..., μk be k (possibly non-
distinct) stable matchings for a marriage problem and assume that each agent ranks these
matchings according to his/her preferences. Using linear programming tools, Teo and Sethu-
raman (1998, Theorem 2) showed that the map that assigns to each man his
l-th (weakly)
best match and to each woman her (
k - l + 1)-st (weakly) best match determines a well-
defined and stable matching. We explain and discuss (generalized) medians as compromise
solutions for two-sided matching problems in Klaus and Klijn (2006). Below we provide an
elementary proof of this “generalized median result” for marriage problems.

Consider a marriage problem (MW, (°i)iN). Let μ 1,..., μk be k (possibly non-distinct)
stable matchings. Let each agent rank these matchings according to his/her preferences as
explained before. Formally, for each
i M W there is a sequence of matchings (μi1,..., μzk)
such that
{μi1,..., μzk} = {μ 1,..., μk} and for any l {1,... ,k 1}, μli ( i ) °i μ*i+1( i ). Thus,
for any
l {1,...,k}, at μ*i agent i is assigned to his/her l-th (weakly) best match (among
the
k stable matchings).

For any l {1, . . . , k}, we define the generalized median stable matching αl as the
function
αl : M W M W defined by

αi(i) :=


μli(i)         if i M;

μi(k-l+1) (i) ifiW.

Theorem 3 Marriage and compromise (generalized medians)

Let μ1 , . . . , μk be k (possibly non-distinct) stable matchings for a marriage problem. Then,
for any
l {1, . . . , k}, αl is a well-defined stable matching.

Proof Let l {1, . . . , k}. First, we show that αl is a well-defined matching, i.e., αl is of
order 2. Let
m M with αl (m) = w W. We have to prove that αl (αl (m)) = m. Without
loss of generality,
μ 1(m) °m μ2(m) °m ∙∙∙°m μι(m) °m ∙∙∙°m μk- 1(m) °m μk(m) and
αl(m) = μl(m). Then, μl(m) = αl(m) = w and μl(w) = m. By arguments similar to those
in the first part of the proof of Theorem 2,
6

μ 1 °m ∙∙∙ °m μi- 1 °m μi °m μi+1 °m " ∙ °m μk

{μk, . . . , μl+1 } °w  μl   °w {μl- 1 , . . . , μ 1 }

In particular, μi(w) is the (k l + 1)-st ranked match for woman w and therefore αi (w) =
μi(w). Hence, αi(αi(m)) = αi(w) = μi(w) = m.

We now prove that αi is stable. By definition, αi is individually rational. Suppose there
is a blocking pair
{m, w} with m M and w W, i.e., w Âm αi(m) and m Âw αi(w). Then,
m prefers w to at least kl + 1 stable matchings in {μ1, . . . , μk}. Similarly, w prefers m to at
least
l stable matchings in {μ1 , . . . , μk}. Hence, for at least one matching μ {μ1, . . . , μk},
w Âm μ(m) and m Âw μ(w), contradicting stability.                                    ¥

6Recall that in the first part of the proof of Theorem 2 only the relative rankings of agent i’s mates with
respect to
μk +1 mattered - which exact rank μk+1 had did not play any role in that part of the proof.



More intriguing information

1. The Tangible Contribution of R&D Spending Foreign-Owned Plants to a Host Region: a Plant Level Study of the Irish Manufacturing Sector (1980-1996)
2. The name is absent
3. Name Strategy: Its Existence and Implications
4. ISO 9000 -- A MARKETING TOOL FOR U.S. AGRIBUSINESS
5. Determinants of U.S. Textile and Apparel Import Trade
6. On the estimation of hospital cost: the approach
7. A Study of Prospective Ophthalmology Residents’ Career Perceptions
8. The name is absent
9. A simple enquiry on heterogeneous lending rates and lending behaviour
10. Enterpreneurship and problems of specialists training in Ukraine