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 (M∪W, (°_i)i∈N). 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 (μⁱ1,..., μ^z_k)
such that {μⁱ₁,..., μ^z_k} = {μ 1,..., μ_k} and for any l ∈ {1,... ,k — 1}, μ^li ( i ) °_i μ*i+₁( 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

μ_lⁱ(i)         if i ∈ M;

μⁱ(k-l+1) (i) ifi∈W.

Theorem 3 Marriage and compromise (generalized medians)

Let μ₁ , . . . , μ_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,⁶

μ 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 k— l + 1 stable matchings in {μ₁, . . . , μ_k}. Similarly, w prefers m to at
least l stable matchings in {μ₁ , . . . , μ_k}. Hence, for at least one matching μ ∈ {μ₁, . . . , μ_k},
w Âm μ(m) and m Âw μ(w), contradicting stability.                                    ¥

⁶Recall 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.

<<   4   5   6   7   8   9   >>

More intriguing information