Symptom

You are assigning interns to teams. Both sides submit ranked preferences, and you write something reasonable: sort by seniority, give each team its top available choice.

The assignment goes out. Within a day, an intern and a team who were not matched to each other discover that they each preferred the other to what they got. They go around the process. Then another pair does. By the end of the week your official assignment has been quietly renegotiated into something else, and the process has no authority left.

The failing is not that your allocation was unfair or low-value. It is that it was unstable: it contained a pair with the motive and the ability to defect. Any allocation with that property will be undone, so the property to design for is not optimality but the absence of such pairs. It turns out one always exists, it is computable in quadratic time, and the algorithm has a bias you need to know about before you choose which side proposes.

Statement

Take $n$ proposers and $n$ receivers, each with a strict total ordering over the other side.

Matching. A bijection between the two sides.

Blocking pair. A pair $(p, r)$ not matched to each other, where $p$ prefers $r$ to its current partner and $r$ prefers $p$ to its current partner. Both would defect, so both can.

Stable matching. One with no blocking pair.

Gale–Shapley (1962).

  1. A stable matching exists for every set of preferences.
  2. The deferred-acceptance algorithm finds one in $O(n^2)$ time.
  3. The matching it produces is proposer-optimal: every proposer gets the best partner it has in any stable matching. It is simultaneously receiver-pessimal: every receiver gets its worst stable partner.
  4. Truth-telling is a dominant strategy for the proposing side. It is not for the receiving side.

The kind tag is compound and both halves are load-bearing. Existence and proposer-optimality are theorems. The algorithm is a construction that shows the guarantee is attainable cheaply, and the mechanism-design consequences are what make it deployed rather than admired.

Argument

The algorithm, which is twenty lines.

while some proposer p is unmatched and has not exhausted its list:
    r = p's highest-ranked receiver not yet proposed to
    if r is unmatched:
        tentatively match (p, r)
    else if r prefers p to its current tentative partner p':
        tentatively match (p, r); p' becomes unmatched
    else:
        r rejects p

The word tentatively is the whole design. A receiver never accepts finally; it holds the best offer so far and trades up. Hence deferred acceptance.

Termination and the $O(n^2)$ bound. A proposer never proposes to the same receiver twice, so there are at most $n^2$ proposals and each is constant work given a rank-lookup table. So it terminates within $n^2$ iterations.

Everyone is matched at termination. Suppose $p$ is unmatched at the end. Then $p$ proposed to all $n$ receivers and was rejected by all. But a receiver, once it holds an offer, never becomes unmatched — it only ever trades up. So all $n$ receivers are matched, hence all $n$ proposers are matched, contradicting $p$ being unmatched.

Stability. Suppose $(p, r)$ is a blocking pair: $p$ prefers $r$ to its partner $r’$, and $r$ prefers $p$ to its partner $p’$. Since $p$ prefers $r$ to $r’$ and proposes in preference order, $p$ proposed to $r$ before settling with $r’$. So $r$ rejected $p$ at some point, which happens only when $r$ held someone it preferred to $p$. And $r$’s partner only ever improves. So $r$’s final partner $p’$ is preferred to $p$, contradicting the assumption that $r$ prefers $p$ to $p’$. No blocking pair exists. $\blacksquare$

Three short paragraphs, and part 1 and part 2 of the statement are done.

Proposer-optimality, which is the surprising part. Call $r$ achievable for $p$ if some stable matching pairs them. Claim: no proposer is ever rejected by an achievable receiver.

Suppose otherwise and consider the first such rejection in the run: $r$ rejects $p$, with $r$ achievable for $p$, because $r$ holds $p’$ whom it prefers. Since this is the first rejection of an achievable partner, $p’$ has not yet been rejected by anyone achievable for it, so $r$ is at least as good as any achievable receiver for $p’$ — that is, $p’$ weakly prefers $r$ to every partner it can have in a stable matching.

Now take a stable matching $M$ pairing $p$ with $r$ (one exists, since $r$ is achievable). In $M$, $p’$ is matched to some $r’’$, and by the previous paragraph $p’$ prefers $r$ to $r’’$. And $r$ prefers $p’$ to $p$. So $(p’, r)$ blocks $M$, contradicting stability.

Therefore no achievable receiver ever rejects a proposer, so each proposer ends up with the best achievable partner: proposer-optimal. The mirror argument gives receiver-pessimality.

So the side that proposes wins, and this is not a small effect. In the canonical worst case, proposers get their first choice and receivers get their last, from the same preferences, purely by swapping who proposes. The lattice structure behind this — the set of stable matchings forms a distributive lattice with proposer-optimal and receiver-optimal matchings as its two extremes — is why there is no neutral choice available: there is no algorithm producing a stable matching that is optimal for both sides, because in general no such matching exists.

Strategy, and where it bites. Truth-telling is dominant for proposers: a proposer cannot do better than its best achievable partner, and that is what it already gets. For receivers it is not. A receiver can sometimes gain by strategically rejecting an acceptable offer early, forcing the rejected proposer to disrupt the run elsewhere and returning a better offer later. Roth proved (1982) that no stable matching mechanism is strategy-proof for both sides, so this is not a defect of deferred acceptance but a limit on the problem.

The deployments, which are why this is a demonstration and not just theory. The National Resident Matching Program has matched US medical graduates to residencies since 1952 — with an algorithm that turned out to be deferred acceptance a decade before it was published — and switched to applicant-proposing in 1998 precisely because of the bias above. New York City and Boston school choice both run it. Roth and Shapley took the 2012 Nobel in economics for the theory and its application, including kidney exchange chains built on the same stability reasoning.

Back to the interns. Run deferred acceptance, and decide deliberately whether interns or teams propose. That choice is the actual policy decision, and it was being made accidentally by the sorting order in the original code.

Forbids

A stable matching that is simultaneously optimal for both sides, in general. The lattice has two extremes and they usually differ. Any process claiming to be best for everyone is either producing an unstable matching or getting lucky on the instance.

A strategy-proof stable mechanism for both sides. Roth’s impossibility. If stability is required, one side has an incentive to misreport.

Expecting an unstable assignment to hold. Blocking pairs are pairs who both gain by defecting. Whether they can defect is a question about your institution, not about the algorithm, but if they can, they will.

Neutrality in choosing who proposes. There is no neutral option. Declining to choose is choosing whichever side your implementation happens to put in the proposing role.

Does not forbid

It does not mean the outcome is unfair to the receiving side, which is the misreading that gets deferred acceptance argued against in exactly the places it should be used. Receiver-pessimal means worst among stable matchings, and every stable matching is better for a receiver than the blocking-pair chaos that replaces an unstable one. The NRMP’s switch to applicant-proposing was estimated to change the assignment for well under 1% of participants, because in practice, with preference lists of realistic length, the lattice is narrow and the extremes nearly coincide. The bias is real, it is worth choosing deliberately, and it is usually small.

It does not require equal-sized sides or complete preference lists. The hospitals/residents generalisation handles quotas, unequal sizes, and truncated lists; unmatched participants and unfilled positions are normal outcomes and stability is defined accordingly.

It does not require preferences to be strict in practice. Ties are broken — randomly, or by a tie-breaking policy — and stability holds with respect to the broken preferences. Finding a maximum stable matching under genuine ties is NP-hard, which is the price.

It does not forbid optimising for other objectives. Among all stable matchings you can minimise total rank sum, or egalitarian cost, in polynomial time via the lattice structure. “Stable” and “good” are compatible; you just optimise inside the stable set rather than over everything.

It does not require centralised trust to be worthwhile. Even a decentralised market benefits from the concept: unravelling — offers made earlier and earlier each year, exploding offers, pressure to accept immediately — is exactly what happens to a market with no stable clearing mechanism, and it is the failure this was invented to fix.

Boundary

  • Couples break it. Residents applying as pairs, needing positions in the same city, can make stable matchings fail to exist, and the NRMP runs a heuristic for these. This is the most important practical caveat and it is not a technicality.
  • Ties make the optimisation hard even though existence survives.
  • Preferences must be known and reportable. The model assumes a complete ranking exists; in many real markets, discovering preferences is the expensive part and the matching is easy by comparison.
  • Only two sides. Three-sided stable matching is NP-hard, and even the one-sided stable roommates problem may have no stable matching at all — Irving’s algorithm decides it in $O(n^2)$ and reports failure when none exists.
  • Stability is not efficiency. A stable matching need not maximise total welfare, and in one-sided markets (kidney exchange) top-trading-cycles targets Pareto efficiency instead, with different guarantees.

The reframing to keep: the question is not who deserves what, it is which pairs can defect. Eliminate those and the assignment survives contact with the people in it.