Proof of the Stable Matching Problem

Problem Detail: 

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.

Asked By : KJ.

Answered By : Yuval Filmus

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.)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9196