Proof the correctness of Gale-Shapley algorithm

Observation 1. men propose to women in decreasing order of preference.
Observation 2. Once a woman is matched, the woman never becomes unmatched; only move on for better.

Proof of correctness: perfect matching

Claim: In Gale-Shapley matching, all men get matched.

Proof : [by contradiction]

Suppose for sake of contradiction, that some man $LaTeX: m\subset M$ is unmatched upon termination of Gale-Shapley algorithm.

Then some women $LaTeX: w\subset W$ , is unmatched upon termination.

- By observation 2, w was never proposed to.
- But, m proposes to every w, since m ends up unmatched.

Theses two are contradict with each other

Claim: in Gale-Shapley matching, all women get matched.

proof : [by counting]

By previous claim, all n men get matched.

Thus, all n women get matched.

Claim: in Gale-Shapley matching $LaTeX: M^{\ast}$ , there are no unstable pairs.

Proof : Consider any pair m — w that is not in $LaTeX: M^{\ast}$

m prefers his Gale-Shapley partner w' to w.

m — w is not unstable.

w rejected m

w prefers her Gale-Shapley Partner m' to m.

m — w is not unstable.

In either case, the pair m —w is not unstable

Proof of correctness: termination

Claim: The Gale-Shapley algorithm terminates after at most LaTeX: n^2 iterations of WHILE loop.

Proof : Each time through the WHILE loop, a men proposes to a new women.

Thus, there are at most LaTeX: n^2 possible proposals.