Cannot understand the proof for why the Gale – Shapley Algorithm marries every woman to her PESSIMAL spouse.

algorithmsgame theorygraph theorymatching-theory

I'm new here. This is my first post!

Almost all proofs for this theorem use proof by contradiction and they assume that "there must be a stable set of marriages $\mathcal M$ where some woman is married to a man that she likes LESS than her spouse in The Mating Ritual."

My question is; for the purpose of contradiction shouldn't we assume that "there must be a stable set of marriages $\mathcal M$ where some woman is married to a man that she likes MORE than her spouse in The Mating Ritual."

Because in my head it seems like we want to show that every woman is NOT married to her optimal spouse. Seems like all we've shown in the proof below is that a woman can do no worse than her pessimal spouse. I'm sure I'm missing something here!

The full proof for this theorem in MIT's "Mathematics for Computer Science" textbook is below (it's just the above part that's not clear to me, everything else makes sense):

Theorem: The Mating Ritual marries every woman to her pessimal spouse.

Proof. By contradiction. Assume that the theorem is not true. Hence there must be a stable set of marriages $\mathcal M$ where some woman (call her Nicole) is married to a man (call him Tom) that she likes less than her spouse in The Mating Ritual (call him Keith). This means that:

Nicole prefers Keith to Tom.

We know that The Mating Ritual marries every man to his optimal spouse and the fact that Nicole and Keith are married in the Mating
Ritual, we know that

Keith prefers Nicole to his spouse in $\mathcal M$.

This means that Keith and Nicole form a rogue couple in $\mathcal M$, which contradicts the stability of $\mathcal M$. $\blacksquare$

Help is much appreciated!

Best Answer

If our claim is "the Gale-Shapley algorithm assigns every woman her pessimal spouse", and we want to prove it by contradiction, then we want to negate this statement.

The negation of this statement is that not every woman is assigned her pessimal spouse under Gale-Shapley. In other words, there is some woman who is not assigned her pessimal spouse (in the the Gale-Shapley matching I'll call $\mathcal G$).

Following the proof, call the woman who is not assigned her pessimal spouse in $\mathcal G$ "Nicole", and call her spouse in $\mathcal G$ "Keith".

What does it mean that Keith is not her pessimal spouse? It means that some other man, call him "Tom", is her pessimal spouse. And what does being a pessimal spouse mean? It does not mean that Nicole likes Tom least of everyone. It means that Nicole likes Tom least of everyone she could possibly marry in any stable matching. In particular:

  • There has to be some stable matching $\mathcal M$ which matches Nicole and Tom; that's why Tom is a potential spouse.
  • In any stable matching, Nicole either marries Tom or someone else she likes more: that's why Tom is the pessimal spouse.
  • In particular, in $\mathcal G$ (the Gale-Shapley stable matching), Nicole likes the person she marries (Keith) more than Tom.

This covers all the conclusions made in the first paragraph of the proof.

Related Question