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. Regional dynamics in mountain areas and the need for integrated policies
2. The Functions of Postpartum Depression
3. The name is absent
4. Trade Liberalization, Firm Performance and Labour Market Outcomes in the Developing World: What Can We Learn from Micro-LevelData?
5. The name is absent
6. Human Rights Violations by the Executive: Complicity of the Judiciary in Cameroon?
7. The name is absent
8. How do investors' expectations drive asset prices?
9. The name is absent
10. The name is absent
11. The Making of Cultural Policy: A European Perspective
12. The name is absent
13. Critical Race Theory and Education: Racism and antiracism in educational theory and praxis David Gillborn*
14. Internationalization of Universities as Internationalization of Bildung
15. TOWARDS THE ZERO ACCIDENT GOAL: ASSISTING THE FIRST OFFICER MONITOR AND CHALLENGE CAPTAIN ERRORS
16. The name is absent
17. Reversal of Fortune: Macroeconomic Policy, International Finance, and Banking in Japan
18. Performance - Complexity Comparison of Receivers for a LTE MIMO–OFDM System
19. The name is absent
20. Regionale Wachstumseffekte der GRW-Förderung? Eine räumlich-ökonometrische Analyse auf Basis deutscher Arbeitsmarktregionen