Proposer-optimal stable matching

For fixed strict preferences, a proposer-optimal stable matching gives each proposer its best partner obtainable in any stable matching, with unmatched ranked last. The Gale-Shapley algorithm achieves all these individual optima simultaneously. In the worked example, $M_L$ gives $A,B,C$ partners ranked $1,2,2$, respectively; the alternative $M_R$ gives them ranks $2,3,3$.

Suppose a first rejection of a pair belonging to some stable matching $S$ occurs when $r$ rejects $\ell$ for ${\ell }^{\prime }$. Every partner ${\ell }^{\prime }$ prefers to $r$ has already rejected it, so none can be its partner in $S$. If $S(r)=\ell$, then ${\ell }^{\prime }$ prefers $r$ to $S({\ell }^{\prime })$, while $r$ prefers ${\ell }^{\prime }$ to $\ell$: a blocking pair in stable matching, a contradiction. Hence no rejected pair is stable, and each proposer receives its best stable partner. Under strict preferences this also makes the outcome independent of proposal order.

For fixed strict preferences, the same output of the Gale-Shapley algorithm gives each receiver its worst partner obtainable in any stable matching, treating unmatched as last. "Worst" is restricted to stable possibilities: a receiver might still receive its favourite acceptable partner if every stable matching assigns it that partner. Reversing the proposing side gives receivers their best stable partners instead.

For a short proof, let $M$ be a proposer-optimal stable matching and $S$ any other stable matching. If a receiver $r$ preferred $M(r)=\ell$ to $S(r)$, then proposer optimality would make $\ell$ prefer $r=M(\ell )$ to $S(\ell )$, since the partners differ and preferences are strict. The pair $(\ell ,r)$ would block $S$. Therefore no receiver prefers its partner in $M$ to its partner in $S$. In the worked example, right-side ranks in $M_L$ are $2,2,3$ for $X,Y,Z$, whereas $M_R$ gives them $1,1,2$. Neither outcome is universally best for both sides.