Proof that the Gale-Shapley Algorithm Favors the Proposers
Understand how the Gale-Shapley algorithm ensures that each proposer is paired with their highest-ranked partner among all stable matchings. This lesson guides you through the proof by contradiction approach, demonstrating why proposers benefit from the algorithm's design and how stability in matchings is maintained.
We'll cover the following...
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: 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, ...