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. Special and Differential Treatment in the WTO Agricultural Negotiations
2. Putting Globalization and Concentration in the Agri-food Sector into Context
3. Modelling the health related benefits of environmental policies - a CGE analysis for the eu countries with gem-e3
4. The Impact of Optimal Tariffs and Taxes on Agglomeration
5. Informal Labour and Credit Markets: A Survey.
6. The name is absent
7. The name is absent
8. Prizes and Patents: Using Market Signals to Provide Incentives for Innovations
9. From music student to professional: the process of transition
10. Self-Help Groups and Income Generation in the Informal Settlements of Nairobi