matching, for example a stable matching that maximizes the number of matched pairs. It
turns out that no such selection is possible because an agent who is single at one stable match-
ing is also single at all other stable matchings (Gusfield and Irving, 1989, Theorem 4.5.2). In
fact, Gale and Sotomayor (1985, Proposition 1) already proved this “lonely wolf” theorem
for marriage problems. Here we provide an elementary proof.
Theorem 1 The lonely wolf theorem
Let μ and μ' be stable matchings. Then, μ and μ' have the same set of single agents, i.e.,
μ(i) = i ⇔ μ'(i) = i.
Proof Suppose μ(i 1) = i 1 = i2 = μ,(i 1) for some i 1 ,i2 ∈ N. Since preferences are strict
and μ' is individually rational, i2 Âi 1 i 1.
Define i3 := μ(i2). Then, i3 Âi2 i 1 (otherwise {i 1, i2} is a blocking pair for μ) and i3 = i2
(otherwise {i2} is a blocking pair for μ0). Define i4 := μ'(i3). Then, i4 Âi3 i2 (otherwise
{i2,i3} is a blocking pair for μ,) and i4 = i3 (otherwise {i3} is a blocking pair for μ). Next,
define agents i5 , i6 , . . . by
_ ( μ(ip) if p is even;
p++1 : [ μ (ip) if p is odd.
Similarly as before it follows that for all p ≥ 2, ip+1 Âip ip-1 and ip+1 6= ip. Since N is finite,
there is a p0 ≥ 1 with
ip0+1 = il for some l ≤ p0. (1)
Let p be the smallest p0 ≥ 1 that satisfies (1). By showing that this leads to a contradiction,
we prove that μ (i 1) = i 1 implies μ' (i 1) = i 1.
Note that i3 ∈ {i 1 ,i2} and therefore p ≥ 3. In general, for all p ≥ 2, ip+1 ∈ {ip,ip- 1}.
Hence, p ≥ 3 and p > l + 1 for all l ≤ p with ip,+1 = il.
Let l ≤ p with ip,+1 = il. Suppose p is even, i.e., ip,+1 = μ(ip). Then, μ(ip) = il. If l = 1,
then from the definition of i 1, ip = i 1, contradicting that p) is the smallest p0 ≥ 1 that satisfies
(1). If l is odd and l = 1, then il- 1 = μ(il) = ip, contradicting the definition of p). If l is
even, then il+1 = μ(il) = ip, contradicting the definition of p.
Suppose p is odd, i.e., ip+1 = μ'(ip). Then, μ'(ip) = il. If l = 1, then from the definition
of i2, ip = i2, contradicting the definition of p). If l is odd and l = 1, then il+1 = μ'(il) = ip,
contradicting the definition of p). If l is even, then il- 1 = μ'(il) = ip, contradicting the
definition of p). ¥
Since no selection can be based on the set of matched agent, we next try to find a stable
matching that will be perceived as fair by the agents. Imagine that we ask each agent to
rank all stable matchings according to his preferences. For two (stable) matchings μ and μ',
μ °i, μ' ⇔ μ(i) °i μ'(i). Note that since an agent might be matched to the same agent in
several stable matchings, this ranking is not strict. Clearly, we cannot always give the best
match to every agent, but can we implement fairness by finding a matching that matches
each agent with his k-th ranked match? We explain this idea in our next example and
show that this idea of fairness or compromise (at least if there is an even number of stable
matchings) is not always feasible.