I have this confusion related to Gale and Shapley algorithm
Claim. GS finds woman-pessimal stable matching S*.
Proof
Suppose A-Z matched in S*, but Z is not worst valid partner for A.
There exists stable matching S in which A is paired with a man, say
Y, whom she likes less than Z.
Let B be Z's partner in S.
Z prefers A to B.
Thus, A-Z is an unstable in S.
Now, I find it really strange how it is proved here. I didn't get what they are trying to do here and how they are proving the claim. Can anyone provide some insights?
Best Answer
This is a proof by contradiction. It assumes that there is a stable matching $S$ in which $A$ has a worse partner than in the stable matching $S^*$ produced by the Gale–Shapley algorithm, and derives a contradiction.
"$Z$ is not the worst valid partner for $A$": That such a pair exists follows from the assumption that $S^*$ is not "woman-pessimal" (never heard that term before :-). Here $A$ is a woman and $Z$ is a man.
The next sentence just explicates this: a "valid" partner of a woman here is one that can be her partner in a stable matching, so if $Z$ is not $A$'s worst valid partner, there is a stable matching $S$ in which $A$ is paired with a worse partner, say $Y$.
"$Z$ prefers $A$ to $B$": This is the clue. This follows from the man-optimality of $S^*$. (If you haven't proved this yet, you can find a proof of it in these slides, on the slide titled "Proof of Fact $3$".) Since $Z$ is married to $A$ in $S^*$, $S^*$ is man-optimal among all stable matchings, and both $S$ and $S^*$ are stable, $Z$ prefers $A$ to $B$.
"Thus, $A$-$Z$ is unstable in $S$.": This now follows because $Z$ prefers $A$ to $B$ and $A$ prefers $Z$ to $Y$.