# Proof of the Stable Matching Problem

Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem.

Theorem 1.2.3 - page 12:

In a man-optimal version of stable matching, each woman has worst partner that she can have in any stable matching.

Proof:

Suppose not. Let $M_0$ be the man-optimal stable matching, and suppose there is a stable matching $M’$ and a woman $w$ such that $w$ prefers $m = p_{M_0}(w)$ to $m' = p_{M'}(w)$ . But then $(m,w)$ blocks $M'$ unless $m$ prefers $p_{M'}(m)$ to $w = p_{M_0}(m)$, in contradiction of the fact that $m$ has no stable partner better than his partner in $M_0$.

I'm having trouble visualizing the definition of the problem and the proof (what is the contradiction?).

First, what is the question implying? From what I read and the fact that in most stable matching examples, all the women do not end up with the completely last person on their list ... So I'm a bit confused.

In the proof, here is what I am getting: in $M'$ we suppose $w$ prefers $m$ to $m'$. But then if there is a stable matching containing $(m,w)$ this would leave $w$ with her worst partner and that is a contradiction. Is this correct?

In addition, if $m$ did prefer $w'$ it would contradict that it is not his first pick ?

I'm new to computer science concepts so any help is appreciated.

-

The claim is not that every woman ends with the last man on her list. Rather, consider all stable matchings, and all partners of some woman $w$ in these stable matchings. Among them, pick the worst one (according to her view) $m$. Then in the man-optimal matching, $w$ is matched to $m$.

Now that you understand what they're trying to prove, read the proof again. (It couldn't have made sense before, because the claim as you stated it just isn't true.)

-
ok I see now, that you. In this case, is it true that with the G-S algorithm, there can only be 2 sets of stable matching (with stable matching set 1 with man-optimal and the other one coming from woman-optimal)? –  KJ. Jan 29 '13 at 0:58
Definitely not. There could be exponentially many stable matchings. –  Yuval Filmus Jan 29 '13 at 1:06
You can check the book by Gusfield and Irving, The Stable Marriage Problem: Structure and Algorithms, or the lecture notes by Knuth. –  Yuval Filmus Jan 29 '13 at 1:12
does it depend on the order of men picked to propose? –  KJ. Jan 29 '13 at 1:32
Any implementation of the Gale-Shapley algorithm produces a single stable matching. However, there are lots more stable matchings out there. –  Yuval Filmus Jan 29 '13 at 2:52

There is a very nice lecture video on Youtube which describes all properties. I recommend you to watch is if you are new to the concept.

-
thank you, yes it is new, much appreciated. –  KJ. Jan 29 '13 at 0:59