Deferred acceptance
Named by 6 essays across one field — each of them below, with the objects they name alongside it.
Nobody has a reason to run away
A matching is stable when no two people on opposite sides would both rather have each other than what they have — a condition that names nothing to build and everything to rule out. The surprise is that something always satisfies it, however perverse the rankings are made.
The side that proposes wins
An instance usually has several stable matchings, and the set of them is not a heap — it is a lattice, closed under taking the better partner and under taking the worse. The two ends of that lattice are exactly what deferred acceptance returns from the two sides, so whoever proposes decides which end the instance lands on.
No stable rule is safe from a lie
A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the story with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.
The people every stable answer leaves out
Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.
One extra person on one side
In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.
A third kind of member
Two sides always have a stable matching, and the proof is a procedure. Add a third kind of member — capitals who rank numbers, numbers who rank letters, letters who rank capitals — and every market small enough to check still has a stable grouping. Ten million markets of three have at least ten each. Nobody can prove it continues, because the structure the two-sided proof stands on is gone.
Named alongside it
The objects these essays reach for when they reach for this one.
Preference profileStable matchingBlocking pairOrder latticeCounterexampleExhaustive searchExistence proofBijectionConjectureConstructive proofCounting two waysCoupon collector