An early promise need not be a final assignment. In deferred acceptance, a receiver holds its favorite proposal so far but may replace that hold when a preferred proposer arrives. Rejected proposers move down their lists instead of repeatedly asking the same receiver. All preferences remain fixed during the process.
Use this three-per-side synthetic profile, with preferences from best to worst:
Proposer
Receivers in preference order
Receiver
Proposers in preference order
A
X, Y, Z
X
C, B, A
B
X, Z, Y
Y
A, C, B
C
Y, X, Z
Z
B, A, C
A first approaches X, which has nobody held and therefore holds A. B next approaches X. X prefers B to A, so it holds B and releases A. This is not a violation of the algorithm: holds are provisional. The history that A already approached X is permanent.
A now approaches Y and is held. Predict what happens when C approaches Y. C’s first choice is not enough to guarantee acceptance: Y prefers its existing A, so C is rejected.
Predict
What should C do after this rejection? Its next untried receiver is X. X prefers C to its current B, so B becomes free. B next approaches Z, completing A–Y, B–Z, C–X. Notice that C visited two receivers, A visited two, and B visited two. Six proposals were used, fewer than the nine possible proposer–receiver pairs.
Predict whether a receiver can become empty after having received a proposal. Under this algorithm it cannot: a receiver either retains its current hold or replaces it immediately. Predict whether its held partner can get worse in its own ranking. It cannot, because replacement occurs only for a preferred newcomer. These two observations will become the key invariant.
Also identify a tempting but invalid progress measure: the number of held pairs. A rejection or replacement need not change that number. We need a quantity that changes at every proposal, not only when someone first finds a partner.
Experiment
The tool initially opens a different two-per-side profile. Select Three by three: follow a rejection chain, leave A, B, C propose selected, and predict each next step before choosing Reveal next proposal. Its fixed choice rule selects the first free proposer in displayed order, matching this worked trace:
Step
Proposal
Receiver decision
Free proposer caused by this step
1
A to X
Hold A
none
2
B to X
Replace A with B
A
3
A to Y
Hold A
none
4
C to Y
Keep A; reject C
C
5
C to X
Replace B with C
B
6
B to Z
Hold B
none
After the last step, independently test the unpaired pairs. A would rather have X than Y, but X prefers C. B would rather have X than Z, but X prefers C. C would rather have Y than X, but Y prefers A. Each proposer’s less-preferred alternatives cannot block either. This checks the final matching using the definition, separately from trusting the procedure.
Predict a proposal, then reveal one step
Each person ranks every person on the other side, strictly from best to worst. Preferences stay fixed. A free proposer tries their highest-ranked receiver not yet approached. The receiver holds their preferred proposal so far; a held pair is provisional.
The trace chooses the first free proposer in the displayed proposer order. This fixes a reproducible trace; a different choice order can produce a different proposal sequence. Switching sides changes who proposes, not anyone's preference ranking.
Rankings: leftmost name is most preferred. Both sides' full lists remain visible.
Role
Person
Best → worst
Proposer
A
X → Y
Proposer
B
Y → X
Receiver
X
B → A
Receiver
Y
A → B
Use the current held pairs and earlier proposals below to make your prediction before revealing. Compare it with the revealed decision; this tool does not grade your text. Revealing a step clears the prediction field for the next step.
No proposals revealed. Everyone is free.
Provisional held pairs. 0 proposals revealed; at most 2² = 4 distinct proposer–receiver proposals under these assumptions. This is an upper bound, not the expected count.
A: free.
B: free.
The complete-matching checker has not run on these provisional pairs. Some people may still be free; later proposals can displace a currently held proposer.
Fixed complete, strict, equal-size examples only. No ties, unacceptable partners or capacity constraints are modeled. Work here counts proposals, not all implementation operations. This temporary experiment saves no answers and awards no mastery.
Restart the profile to reconstruct the history, or switch the proposing side and predict before revealing. For this three-per-side profile the reversed run reaches the same named pairs with three proposals. That observation alone does not prove reversal always preserves the outcome; the tool’s two-per-side profile supplies a contrasting case for the next lesson. These temporary traces do not award proof credit or assess the quality of prediction text.
Understand
State the algorithm precisely. Initially everyone is free. Choose a free proposer with an untried receiver and send it to its highest-ranked untried receiver. A free receiver holds it. An occupied receiver compares the newcomer with its current hold, keeps its preferred one and rejects the other. A rejected proposer becomes or remains free. Only free proposers may make proposals, and no proposer–receiver pair is tried twice.
Assume both sides have the same finite size n, with complete strict lists and every partner preferable to being unmatched. We prove three different conclusions: termination, perfect completion and stability.
Receiver invariant. After every step, a receiver that has seen proposals holds its favorite among all proposers who approached it. Initially the claim is vacuous. At an update it chooses the better of its previous favorite and the newcomer, exactly the favorite of the enlarged set. Other receivers do not change. Thus an occupied receiver stays occupied, and its hold never worsens. Any proposer rejected earlier is strictly less preferred than every later hold, including the final partner. This includes a proposer first held and later displaced.
Termination. There are n² possible proposer–receiver pairs. Each step uses one previously untried pair, so the number of untried pairs decreases by exactly one and is bounded below by zero. At most n² proposals can occur, regardless of which free proposer acts next. This is an upper bound, not a prediction that every run uses all pairs. For n=0 the empty matching is already complete.
Perfect completion. Could a free proposer have exhausted its entire list? Then every receiver would have received a proposal. By persistent occupancy, all n receivers would hold someone. Those n held proposers are distinct because only a free proposer can approach a new receiver. Equal side sizes would leave nobody free, a contradiction. Completeness of the lists ensures that exhausting a list really means approaching every receiver. Therefore a free proposer always has a next step, and termination can occur only when everyone is paired.
Stability. Consider any unpaired proposer p and receiver r at termination. If p prefers its assigned partner to r, they do not block. Otherwise p approached r before reaching its less-preferred final partner. Receiver r must have rejected p, immediately or later. The invariant says r’s final partner is strictly preferred to p, so again the pair does not block. These cases cover every unpaired pair and prove stability generally, rather than just for the six-step example.
Apply
Diagnose a broken implementation that discards a rejected proposer’s history. If two proposers both prefer X, X keeps its favorite, and the other repeatedly approaches X again, the process can loop forever while another receiver stays free. The n² termination proof no longer applies: the same pair is tried repeatedly, so the claimed measure does not decrease. Repair the state by retaining each proposer’s next untried position or a permanent record of attempted receivers.
Distinguish this implementation bug from an assumption failure. With incomplete lists, a free proposer can legitimately exhaust all acceptable receivers; a perfect matching need not exist. A version allowing unmatched outcomes can still be studied, but the counting argument above cannot be reused without modification. With ties, “keeps its preferred one” also needs a declared policy and a specified stability notion.
Finally, explain why the trace itself is not the general proof. Six decisions verify this profile. The favorite-so-far invariant, finite proposal measure and blocking-pair argument cover every profile under the stated hypotheses. Written tasks ask you to reconstruct those logical steps and repair a changed process.
Continue
Continue to the question of whose best stable outcome the algorithm finds. Changing the order of free proposers and changing which side proposes are different operations. The next proof will show that for fixed complete strict preferences and a fixed proposing side, the final matching does not depend on the first choice; reversing the side may change it.
If the proof structure is unfamiliar, revisit state models and invariant discovery. Keep the invariant, termination measure and exit conclusion distinct. Here none can replace the other two.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Proposers rank A:Y>X>Z, B:Y>Z>X, C:Z>Y>X. Receivers rank X:A>B>C, Y:C>B>A, Z:B>C>A. Run deferred acceptance with the alphabetically first free proposer acting each time; a free proposer proposes to its highest-ranked receiver not yet approached. List every proposal and hold/rejection, then independently check the final matching for blocking pairs.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove that after every proposal, each receiver holds at most one proposer and, if it has received any proposals, holds its favorite among all proposers who have approached it. Deduce a statement about a proposer whom it rejected earlier, including when that proposer was once held.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
For equal sides of size n with complete strict lists, prove that a free proposer cannot have exhausted its list during deferred acceptance. Deduce that termination leaves everyone paired. State explicitly where equal sizes and complete acceptability enter.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Give a termination measure for deferred acceptance with n participants per side, and prove at most n² proposals occur, for any choice of free proposer. Handle n=0. Explain why counting only the currently held pairs is not a strict progress measure.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Prove the final matching produced by deferred acceptance has no blocking pair. Start from an arbitrary unpaired proposer p and receiver r; distinguish whether p prefers r to its final partner. Do not assume the desired conclusion as an invariant.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
A faulty implementation lets a rejected free proposer try its first choice again, forgetting which receivers already rejected it. Construct a complete strict two-per-side example and an allowed infinite execution. Explain exactly why the n² argument fails and how to repair the state.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
