Try
Three volunteers A, B and C seek one of two placements X and Y. Each placement can hold one volunteer. Everyone finds every opposite-side participant acceptable and prefers any partner to remaining unmatched. Preferences are strict: there are no ties.
A prefers X to Y; B prefers X to Y; C prefers Y to X. Placement X ranks B above A above C. Placement Y ranks A above C above B. Two volunteers can be placed, but a proposal need not be final. Which volunteer would you expect to remain unmatched? Explain your prediction from the lists rather than from arrival order alone.
We study a matching, meaning disjoint pairs. A blocking pair is a volunteer and placement not paired together who both prefer each other to their current situation. An unmatched participant regards every opposite-side participant as better. The theorem concerns this explicitly complete preference model; later we will change that assumption.
Predict
Imagine A first proposes to X. Should X commit permanently, or retain A provisionally while remaining willing to replace A by a preferred volunteer? Deferred acceptance uses the second rule. A receiver always retains its best proposal so far.
Predict what should happen to a free volunteer who has already proposed to both placements. There is no new legal proposal. Repeating the first proposal would destroy the argument that each pair is tried only once. A free participant may therefore be exhausted, even though another free participant could still have a proposal left.
Experiment
Use the alphabetically first free volunteer who still has an untried placement. Propose to that volunteer’s most preferred untried placement. A placement holds the better of its current volunteer and the new proposer, rejecting the other. An empty placement accepts. Mark every proposed pair as tried, including rejected proposals.
| Step | Proposal | Decision | X holds | Y holds | Free volunteers afterward |
|---|
| 0 | None | Start | Nobody | Nobody | A, B, C |
| 1 | A to X | X accepts | A | Nobody | B, C |
| 2 | B to X | X prefers B; A is displaced | B | Nobody | A, C |
| 3 | A to Y | Y accepts | B | A | C |
| 4 | C to Y | Y prefers A; rejects C | B | A | C |
| 5 | C to X | X prefers B; rejects C | B | A | C, now exhausted |
Cover the last two rows and predict them from the rankings. At the end, the pairs are B–X and A–Y. C is unmatched, but has no untried placement. The held pairs remain provisional during execution; they constitute the final matching only when no free participant can make a new proposal.
Audit the unpaired pairs. A prefers X to Y, but X prefers B to A. C wants either placement, but X prefers B and Y prefers A. B is already at its first choice X. No pair blocks. Five proposals were used, within the bound of three times two, or six. A finite trace verifies this example; the proof below handles arbitrary finite side sizes.
Understand
Let p be the number of proposers and r the number of receivers. The algorithm only chooses a free proposer with an untried receiver. Each of the pr possible proposer-receiver pairs is proposed at most once, so execution ends after at most pr proposals. This counts proposals, not every comparison or implementation operation.
Two receiver facts drive the proof. First, after a receiver holds anyone, it never becomes empty: a replacement happens immediately when a better proposal arrives. Second, its held partner can only improve in its strict ranking. Rejection is therefore durable evidence that the receiver’s eventual partner will be preferred to the rejected proposer.
To prove stability, suppose proposer a and receiver x would block the terminal matching. If a is matched but prefers x to its final partner, it proposed to x earlier because it follows its list in order. If a is unmatched, termination says it exhausted its complete list; otherwise it would still be eligible. Thus it proposed to x in this case too. Since they are not paired at the end, x rejected a immediately or displaced it later. At that moment x held a better proposer and could only improve afterward. Its final partner is therefore preferred to a, contradicting the alleged block.
Now prove exactly min(p,r) pairs. No matching can contain more than the smaller side. If a stable matching contained fewer, there would be an unmatched participant on each side. Under complete acceptable lists they would prefer each other to being unmatched and would block. Thus every stable matching in this model saturates the smaller side.
There is a separate algorithmic argument: an unmatched terminal proposer has tried every receiver. If a receiver were also unmatched, that earlier proposal would have made it hold someone, after which it could never become empty. This contradiction uses both complete lists and the receiver invariant. Stability and saturation are related conclusions, but their proof obligations are worth distinguishing.
If either side is empty, no proposals occur and the matching is empty. There are no cross-side pairs to block, and min(p,r)=0. In particular an empty receiver list is legitimate for everyone when there are no receivers; it is not an error in this boundary case.
These arguments determine the number of pairs. They do not prove that an arbitrarily chosen participant can be left unmatched, or identify the unmatched set across all stable matchings. Such stronger claims would require their own proofs. Reversing the proposing side still gives the same saturation count under these assumptions, but the pairs need not be the same.
Apply
Change the preferences: A ranks X above Y, B ranks Y above X and C ranks X above Y; X ranks B above A above C, while Y ranks A above B above C. Run the volunteer-proposing algorithm, then let placements propose using exactly these same rankings. Predict whether the number of pairs or their identities change before opening the check.
Compare the reversed roles
With volunteers proposing, A–X and B–Y form; C is rejected by both receivers. With placements proposing, X proposes to B and Y to A, producing B–X and A–Y. There are two pairs in both runs, but different pairs. This example leaves C unmatched in both; it does not prove a general statement about unmatched identities.
Finally allow incomplete lists. Suppose all three volunteers list only X, X accepts all three with A preferred, and Y accepts nobody. The procedure ends with only A–X. The result is stable among acceptable pairs, although two volunteers and one placement remain free. They cannot block if they do not find each other acceptable. Locate the precise use of completeness that no longer applies in each saturation argument.
Continue
Return to deferred acceptance with equal sides for the original proposal and receiver invariants. The new feature here is an exhausted free proposer and a cardinality conclusion under explicitly complete lists. In practice, write the preference contract before the trace, keep tried pairs even after rejection, and prove stability separately from the number matched. Neither the proposal bound nor a full-looking matching alone rules out a blocking pair.
