= Receiver-pessimal stable matching
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.
Back to article page
