= 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'$. Every partner $\ell'$ prefers to $r$ has already rejected it, so none can be its partner in $S$. If $S(r)=\ell$, then $\ell'$ prefers $r$ to $S(\ell')$, while $r$ prefers $\ell'$ 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.
Back to article page
