# 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$.