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 (μ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) ifi∈W.
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 k— l + 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.