Proof that the Gale-Shapley Algorithm Favors the Proposers

Attempt the following questions to convince yourself that the Gale-Shapley algorithm produces a stable matching in which each proposer is paired with his top-ranked stable partner.

We define a stable partner for an individual to be any partner with whom that individual can be matched in any stable matching.

The proof

We want to start by assuming the opposite of what we want to prove and see where that leads us.

Starting assumption$^\dagger$: Assume that there is at least one proposer who is not partnered with his top-ranked stable partner.

During the execution of the Gale-Shapley algorithm, let $m_0$ be the first man to be rejected by a stable partner $w_1$. This implies that at the time when $m_0$ was rejected by $w_1$, $w_1$ was matched to some other person, say $m_1$.