 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.