Thought Exercise: Asymmetry in the Gale-Shapley Algorithm

We proved that the proposers are matched to their top-ranked stable partners. We now want to establish that the algorithm is unfair from the perspective of the proposal recipients. We’d like to do this by showing that each woman is matched to her lowest-ranked stable partner.

A lowest-ranked stable partner for a woman is a partner whom she ranks lowest among all the matches for that woman over all stable matchings.

The task at hand

Argue that each woman is matched to her lowest-ranked stable partner by the Gale-Shapley algorithm. To prove this by contradiction, begin by making the following assumption:

Starting assumption${}^{†}$ ...