Try
A stable outcome need not be unique. Consider this complete strict two-per-side profile, different from the first lesson’s worked profile:
| Participant | First choice | Second choice |
|---|
| A | X | Y |
| B | Y | X |
| X | B | A |
| Y | A | B |
If A and B propose, their first proposals go to different receivers. The result is A–X and B–Y, with both proposers receiving first choices. If X and Y propose instead, the result is X–B and Y–A, with those proposers receiving first choices. Everyone’s preference list stayed unchanged; only the direction of proposals changed.
Both outcomes are stable. In the first, neither A nor B prefers a switch; in the second, neither X nor Y prefers a switch. Write down the rank received by each participant in both outcomes. The original proposers improve from rank two to rank one in the first outcome, while the original receivers improve in the second. Stability alone does not select a unique outcome or resolve whose interests should take priority.
Predict
The algorithm seems to give receivers power: they decide whom to keep and their held partners never get worse. Predict which side receives its best achievable partners among stable matchings. Surprisingly, it is the proposing side.
The italicized restriction matters. A proposer might prefer a receiver who could never be its partner in any stable matching. Getting one’s best stable partner does not mean getting one’s first choice on the original list. Nor does it maximize the total of some invented happiness scores.
Here is a sharper prediction to test. Can the algorithm ever reject a pair that appears together in some stable matching? If it cannot, then every rejection eliminates an impossible stable partner. When a proposer finally settles, every receiver it likes better has already been eliminated for this specific reason. The next argument proves that rejection claim.
Experiment
Return to the two-per-side profile in the deferred-acceptance experiment. Select Two by two: reverse the proposing side and predict the outcome for each proposing side before revealing proposals. Record the partners and ranks, not just whether the final blocking count is zero.
| Fixed preference profile | A's partner | B's partner | Original applicants' ranks | Original hosts' ranks |
|---|
| A and B propose | X | Y | 1, 1 | 2, 2 |
| X and Y propose | Y | X | 2, 2 | 1, 1 |
For this two-per-side profile, these are all possible perfect matchings, so you can verify that each proposer gets its best stable partner in its own run. The finite enumeration motivates the theorem, but it is not a proof for arbitrary n.
Next consider the three-per-side rejection-chain profile from the preceding lesson. A–X was rejected before A–Y became final. To refute the rejection theorem you would need to produce an entire stable matching containing A–X, not merely observe that A prefers X. Use the rejection trace to explain why the required alternative partners would create a blocking pair.
Understand
Maintain the same hypotheses: equal finite sides, complete strict preferences, every partner acceptable, and the deferred-acceptance process already proved to terminate in a stable perfect matching. A stable partner for a proposer is a receiver paired with it in at least one stable matching. The algorithm’s own final matching shows each proposer has at least one stable partner.
We prove that no pair belonging to any stable matching is ever rejected. Suppose otherwise and choose the earliest rejection of such a pair in the proposal sequence. Let receiver r reject proposer p, and choose a stable matching M containing p–r. At that rejection, r keeps a proposer q that it strictly prefers to p. This may be a new arrival replacing p or an existing hold causing p’s immediate rejection.
In M, proposer q has a partner s different from r, because r is already paired with p. What can q’s preferences be? If q preferred s to r, q would have proposed to s before it could approach r. To move on from s, q must have been rejected there. But q–s is a pair in the stable matching M. That would be an earlier rejection of a stable pair, contradicting our choice of the first event. Therefore, since the lists are strict, q prefers r to s.
Now compare M’s assigned pairs with the proposed deviation:
| Participant | Assigned partner in M | Preferred alternative just established |
|---|
| q | s | r |
| r | p | q |
Thus q and r block M, contradicting its stability. Both possibilities led to contradiction, so the first rejected stable pair cannot exist. Choosing the first such rejection is essential: we did not assume that all earlier rejections were valid without explaining why that follows from the choice.
The proposer-optimality theorem follows. A proposer approaches receivers in order from best to worst. Every receiver it prefers to its final partner must have rejected it earlier. The rejection theorem says none of those preferred pairs occurs in any stable matching. Its final partner is therefore its highest-ranked stable partner.
This also proves order independence for a fixed proposing side. Each proposer has a unique highest-ranked stable partner because preferences are strict. Every legal execution returns that same partner for every proposer. Choosing a different free proposer next can change the proposal sequence, but not the final matching. Each proposer’s number of proposals is also fixed: it approaches exactly the prefix of its list ending at its final partner. Therefore the total proposal count is fixed too, even when the chronological trace differs. Reversing the proposing side is a different operation and can change both outcome and count.
There is a corresponding receiver statement. Let M be the proposer-optimal outcome and N any other stable matching. Suppose a receiver r preferred its M-partner p to its different N-partner. Proposer-optimality makes p prefer its M-partner r to its different N-partner as well. Then p–r would block N. Consequently each receiver weakly prefers its partner in every other stable matching to its partner in M. This is a comparison between stable outcomes, not a contradiction of improving holds during one run.
Apply
Repair the statement “Everyone proposing gets their first choice.” Let both A and B rank X above Y, let X rank A above B, and let Y rank B above A. Deferred acceptance yields A–X, B–Y. The alternative perfect matching is blocked by A–X, so no stable outcome can give B its first choice X. B receives its best stable partner Y, even though that partner is second on its full list.
Also repair “The algorithm is fair because it is stable.” Stability excludes a particular two-party deviation under stated rankings. Fairness might concern access, distribution, strategic reporting or goals not encoded in those rankings. The theorem does not choose among those criteria, and ordinal ranks from different people are not automatically comparable numerical utilities. Treat truthful fixed preferences as a modeling input, not a proven consequence of the algorithm.
Finally, allow every participant to be indifferent between both possible partners. Under weak stability, which requires both participants to strictly prefer a deviation, both perfect matchings are stable. There is no unique highest-ranked partner. The strict-preference step proving unique output therefore cannot be imported unchanged. Breaking ties supplies a new strict profile to which the theorem applies, but the chosen refinement is additional information; the original tied profile did not uniquely dictate it.
Continue
Use the practice to reconstruct the first-rejection argument, derive its consequences and identify where strictness enters. A complete proof names the alternative stable matching, both assigned partners, the earlier rejection that would follow, and the final blocking pair. Saying “receivers only improve” alone does not prove proposer-optimality.
These lessons establish a finite matching theorem under explicit hypotheses. They do not certify a deployment policy, incentives for truthful reporting, or general fairness. For a different notion of optimality, revisit maximum matchings and vertex-cover certificates, and state which objective a proposed certificate actually proves.
