The deferred-acceptance algorithm always terminates with a stable matching, and the lab checks that by listing the blocking pairs and printing an empty list. The harder fact is what it chose: on the opening instance there are six stable matchings, and the algorithm lands on the one every proposer likes best and every receiver likes worst. Stability is a guarantee. Fairness is not one, and the difference is visible in a single column.
Core ideas
Three ideas: what stability actually forbids, why an empty list is the interesting output, and why the choice among several stable matchings is the real content of the theorem.
A blocking pair is two people, one from each side, who both prefer each other to their current partners. A matching is stable when no such pair exists. That is a local condition: it says nobody can improve by defecting in pairs. It says nothing about totals, nothing about fairness, and nothing about whether a three-way rotation would please everybody.
The panel does not report a boolean. It forms every one of the n(n − 1) ordered pairs — 12 on the opening instance — tests each against the definition, and prints the resulting list, which is empty. A reader can see what was checked. The same test is then applied to all n! matchings, so the count of stable ones comes from the definition rather than from the algorithm.
Six of the 24 matchings on the opening instance are stable. The algorithm returns one of them, and which one is not an accident: every proposer receives the best partner they have in any stable matching, and every receiver the worst. The panel establishes that by reading the list of all stable matchings, not by trusting the algorithm that produced one of them.
The material
The algorithm, the proof that it terminates with a stable matching, the enumeration beside it, and the asymmetry that the same instance makes unmissable.
n proposers and n receivers, each with a complete ranking of the other side. A matching pairs each proposer with exactly one receiver. A blocking pair is a proposer p and a receiver r, not matched to each other, such that p prefers r to their partner and r prefers p to theirs. A matching with no blocking pair is stable.
While some proposer is unengaged and has not yet proposed to everyone, they propose to the highest-ranked receiver they have not yet tried. A receiver who is unengaged accepts; a receiver who is engaged accepts if they prefer the new proposer, releasing the old one, and otherwise rejects. The algorithm stops when everyone is engaged.
The greedy character is in the word deferred. Each proposer works down their own list and never goes back up, which is the commitment; each receiver holds the best offer so far and may release it, which is the part that is not committed. A version in which receivers accepted irrevocably would be fully greedy and would not produce a stable matching.
Deferred acceptance makes at most n² proposals and ends with every proposer matched, and the matching it produces has no blocking pair.
Each proposer proposes to each receiver at most once, so there are at most n² proposals and the process terminates. A receiver, once engaged, stays engaged and only ever trades up, so at the end a proposer who had been rejected by everyone would imply a receiver engaged to nobody while having received a proposal, which is impossible. Hence everyone is matched.
Suppose p and r form a blocking pair: p prefers r to their partner. Then p proposed to r at some point, before proposing to their eventual partner. Either r rejected p outright, which means r was already holding someone better, or r accepted and later released p for someone better. Either way r's partner only improved afterwards, so r ends with someone they prefer to p, and r does not prefer p to their partner. So no blocking pair exists.
□
On the opening instance the algorithm makes 4 proposals, which is well under the bound of 16, and every one of them is accepted immediately. The resulting matching pairs proposer i with receiver i for all four, and the blocking-pair list, built from all 12 ordered pairs, is empty.
All 24 matchings are tested against the blocking-pair definition and 6 of them are stable: 1234, 1243, 2134, 2143, 2341 and 4321, writing each as the partner of proposer 1, 2, 3, 4 in order. Their mean ranks for the proposers are 1, 3/2, 3/2, 2, 5/2 and 7/2. The algorithm returned 1234, the best of the six for every proposer — and 4321, the worst for them, is what the receivers get when they propose instead.
The theorem is that every proposer receives the best partner they have in any stable matching, simultaneously. That is stronger than it sounds: it is not that the outcome is good on average for proposers, but that no proposer can point to another stable matching in which they personally do better. The panel verifies it by computing, for each proposer, their best achievable partner over the enumerated stable matchings, and comparing.
That is the right way round. Reading proposer-optimality off the algorithm would mean trusting the algorithm to describe its own output; reading it off the list of all stable matchings means the claim is checked against objects the algorithm never saw. On the opening instance the proposers' mean rank is 1 and the receivers' is 4, the extreme values in both directions.
When everyone on both sides agrees on the same ranking there is exactly one stable matching, both sides reach it, and proposing buys nothing: the panel reports 6 proposals, 1 stable matching, and mean rank 2 for both sides. When the two sides want opposite things there are 3 stable matchings and the algorithm reaches the one its proposers prefer, mean ranks 1 and 3.
The fourth instance is labelled as having a long chain of rejections, and its caption says one proposal displaces a partner who displaces another. The trace on the page is: 1 proposes to 2, accepted; 2 proposes to 2, rejected; 3 proposes to 1, accepted; 4 proposes to 4, accepted; 2 proposes to 3, accepted. Five proposals, one rejection, and nobody displaced at all — proposer 2 was turned away by a receiver who was already engaged to someone they preferred. The count of 5 exceeds the 4 people for that reason and not for the one the caption gives.
Measured on this page: 4 proposals, 0 blocking pairs from 12 ordered pairs, 6 stable matchings of 24, proposers' mean rank 1 and receivers' 4, and the sides swapped giving 7/2 and 1. Proved on this page: the algorithm always terminates within n² proposals with a stable matching, and that matching is best for every proposer among all stable ones. What no page here proves, because it is false, is that the outcome is fair.
Interactive
An empty blocking-pair list, and every stable matching beside it
Method
Five steps. The last two are where the interesting facts are and where most readers stop too early.
The trace is the algorithm. Each line names who proposed to whom and what happened, and the number of lines is the proposal count — 4 on the opening instance, 6 on the one where everybody agrees, and 5 on the one with a rejection in it.
For every proposer and every receiver not matched to each other, ask whether both would rather swap. That is n(n − 1) questions and the answer should be no every time. An empty list is the output worth printing, because it shows what was asked.
If there is only one, the algorithm had no choice and the asymmetry question does not arise. If there are six, the choice is the whole story. The panel enumerates all n! matchings and filters them with the same blocking-pair test.
On the opening instance the proposers average rank 1 and the receivers rank 4, which on four people is the best and the worst possible. Two numbers, and they say more about the algorithm's character than the stability verdict does.
The same instance with the receivers proposing gives a different stable matching and the mean ranks exchange places. If the two runs agree, as they do when everyone shares a ranking, the stable matching is unique and the algorithm never had a decision to make.
Proposers' rankings, one row each: 1 2 3 4, 2 1 3 4, 3 4 1 2, 4 3 1 2. Receivers' rankings: 4 3 2 1, 3 4 1 2, 2 1 4 3, 1 2 3 4. Each proposer has a different first choice, which is why the run is short.
Every proposer got their first choice and every receiver got their last. Both are visible in the table as the extremes of the mean-rank columns, and the algorithm did not have to do anything clever to get there: all four proposals were accepted at once, because the four proposers wanted four different people.
The six stable matchings form a chain in the mean-rank columns: as the proposers' average rank worsens from 1 to 7/2 the receivers' improves from 4 to 1. That is not a coincidence of this instance either — the stable matchings of any instance form a lattice, with the proposer-optimal one at one end and the receiver-optimal one at the other — but the lattice is not proved anywhere in this library and the table is one instance of it.
For a faded rehearsal, predict the trace on the instance where every row on both sides is 1 2 3. The supplied first move is that proposer 1 takes receiver 1 immediately and proposer 2 is rejected there. Say how many proposals the run takes in total, how many stable matchings exist, and what both mean ranks are — then say why swapping the sides changes nothing.
You should be able to state what a blocking pair is without hedging, reproduce the argument that the output has none, explain why the enumeration of all n! matchings is what makes proposer-optimality checkable, and say what changes when the two sides swap roles.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.