Nobody has a reason to run away

Two sides, four on each. Side one is lettered A, B, C, D and side two is numbered 1, 2, 3, 4, and every member of each side holds a strict ranking of all four members of the other. A matching pairs them off one to one, and there are twenty-four ways to do that. The question is which of the twenty-four are stable — and the answer has a strange shape, because stability is defined by what it forbids and forbids nothing in particular.

The definition that names nothing to build #

A preference profile is the whole input: for each member of side one, a strict ranking of side two, and for each member of side two, a strict ranking of side one. Nothing else. No numbers are attached to the rankings, no member is more important than another, and no two rankings need have anything to do with each other.

A matching is a one-to-one correspondence between the two sides — a bijection, and for sides of size $n$ there are $n!$ of them. That much is arithmetic.

Stability is not arithmetic. A pair consisting of one member $i$ of side one and one member $j$ of side two is a blocking pair for a matching when both of the following hold:

• $i$ strictly prefers $j$ to the partner the matching gave $i$, and
• $j$ strictly prefers $i$ to the partner the matching gave $j$.

Both halves are needed, and both are strict. A matching is stable when it has no blocking pair at all.

Read that definition again and notice what it does not do. It does not say how to build a stable matching, or what one looks like, or which pairs it contains. It is a filter applied to a finished object, and the filter is a conjunction of $n \times n$ separate refusals — every one of the pairs has to fail to block. On the instance above that is $4 \times 4 = 16$ questions per matching and $24 \times 16 = 384$ questions in total, and the figure asks all of them, including the $n$ questions about pairs the matching already contains, which cannot block and are asked anyway so that the count reported is the number of questions put.

So the natural first question is not how does one find a stable matching but whether there is one to find. Nothing in the definition suggests there should be. The rankings can be set adversarially; the condition quantifies over every pair at once; and a condition that rules things out with that much freedom is exactly the kind that rules everything out.

The smallest instance where the question means anything #

With one member on each side there is one matching and no pair to compare it with, so stability is vacuous. Two on each side is where the question first has content.

Two matchings, and one of them survives. That is the whole of the theorem at this size and it is not yet evidence of anything: with two matchings and a symmetric definition, an instance where neither survives would need both cross pairs to block simultaneously in one arrangement and both diagonal pairs in the other, and a moment’s checking shows that cannot happen. Small cases are agreeable that way, which is precisely why the collection distrusts them.

Three, and a census that comes out even #

At three on each side there are six matchings, and an instance can be built where the two sides’ wishes rotate against each other: A wants 1, B wants 2, C wants 3, while 1 wants B, 2 wants C, and 3 wants A. Every first choice is somebody else’s second or third. Nobody gets what they want first and nobody has an obvious claim.

Half the matchings survive, and the ones that fail all fail in the mildest possible way — one blocking pair each, never two. That is a pleasant census and it is also a warning: the shape of a census is not the theorem. What matters is only that the leftmost column is not empty.

A construction, and the check that it worked #

The proof that the leftmost column is never empty is a construction, and it is worth watching because it is a rare thing: an existence proof that hands over the object it claims exists.

One side proposes. Everybody on the proposing side who is unattached offers themselves to the best name on their list that has not already refused them. Everybody on the receiving side who is holding offers keeps the best one and releases the rest. The released offer again next round, further down their lists. The process stops when nobody is unattached.

The figure does not claim its output is stable because a theorem says the construction produces stable matchings. It puts the finished pairing to the definition, pair by pair, and reports that all sixteen questions came back no. That is the house habit and it matters here more than usual, because the whole essay turns on a definition being satisfied rather than on a procedure being correct.

A word about the number eight, since it is on the page. Eight is a fact about these particular lists, in exactly the register of “four of the twenty-four matchings are stable”: it is what this instance did, not a measurement of anything. How much work a procedure takes, and how that grows, is a question about cost, and cost is another site’s subject in this fleet; nothing here divides eight by anything, compares it to sixteen, or draws a conclusion from it.

Why nobody is left holding a blocking pair #

The argument that the construction cannot fail has two halves, and neither is long.

It stops. Nobody on the proposing side ever offers to the same name twice, because a refusal moves them one place down their own list and they never move back up. So each proposer’s position in their own ranking only increases, and it is bounded by $n$. A quantity in a finite ordered set that only moves one way cannot move for ever — the same device as the infinite descent that shows no square can shrink for ever, and the same one that makes the oldest algorithm terminate. Descent arguments usually appear in number theory and this one is about rankings, but the mechanism is identical: a well-ordered quantity, moved monotonically, with nowhere left to go.

It ends with everybody attached. A member of the receiving side, once holding an offer, is never left empty afterwards — they may swap what they hold for something better, but they never release without replacing. So if some proposer ran out of list, they would have offered to every member of the receiving side, all of whom would then be holding something; and $n$ receivers each holding at most one offer, with one proposer unattached, is more things than boxes run in reverse. The count refuses it.

And the result blocks nowhere. Take any pair not in the final matching. Either the proposer never offered to that receiver — in which case the proposer prefers what they have, since offers go down the list in order and they stopped before reaching this name — or they did offer and were refused, in which case the receiver was holding somebody better at that moment and has only improved since. One of the two halves of the blocking condition fails, whichever pair is chosen. There is no third case, so there is no blocking pair, so a stable matching exists for every preference profile.

That last sentence is the theorem, and it is worth noticing how little of the argument used anything about the instance. Nothing was assumed about the rankings except that they are strict and complete.

As perverse as the lists can be made #

If the theorem is going to fail anywhere, it should fail where the two sides’ wishes conflict most. Take the instance in which every member of side one has the same ranking of side two — 1 first, then 2, then 3, then 4 — and every member of side two has the same ranking of side one, in the opposite lettered order: D first, then C, then B, then A. Total agreement within each side, and everybody’s first choice contested by all three rivals.

One survivor out of twenty-four, and $1 + 3 + 5 + 6 + 5 + 3 + 1 = 24$ accounts for the whole census. This is the instance to keep in mind whenever the theorem starts to sound generous. It promises a non-empty set; it does not promise a large one, and here the set is a single point. Twenty-three of the twenty-four arrangements have somebody with a reason to walk away, and one does not.

Running the construction on the same lists shows why the survivor is the one it is.

The ledger is a picture of the cascade: four offers to the same name in round one, three refusals, and the losers moving down in lockstep. What comes out pairs the most-wanted member of each side with the other — and it is the only thing that can, because any other arrangement leaves the two of them able to improve on each other, which is a blocking pair by definition. The rest follows by the same argument on what is left.

What the census settles, and what it does not #

This needs saying plainly, because the figures are persuasive and they are persuasive about the wrong proposition.

Every census on this page exhausts one instance. It forms all $n!$ matchings of a fixed preference profile, asks all $n \times n$ blocking questions of each, and reports the tally. What it establishes is a statement about that profile: on this profile, four of twenty-four are stable; on that one, exactly one of twenty-four. Each of those is settled beyond argument, in the way a finite check of finitely many cases settles things.

The existence theorem is not a statement about any profile. It is a statement about all of them — every $n$, and every assignment of strict rankings to both sides. There are $(n!)^{2n}$ profiles at each size, and no drawing exhausts that. The census confirms; the argument of the previous section proves. A reader who takes the pattern of the bar charts as the content has read a picture of one instance as a claim about all instances.

Nor is the shape of a census stable across instances. Compare the four-of-twenty-four above with the one-of-twenty-four beside it, and then with five on a side.

Three of a hundred and twenty. The proportion has collapsed and the theorem has not noticed, because the theorem never mentioned a proportion. What the strip at the bottom of that figure shows, and what no smaller drawing shows as well, is how thin the stable set can be inside the space of arrangements while still being non-empty.

Where the two-sidedness is load-bearing #

Two conditions were slipped in at the start and both are doing real work.

The rankings are strict and complete. Ties break the argument at the point where a receiver “keeps the best offer” — with a tie there is no best — and incomplete lists break it where a proposer runs out of names, which the counting argument above forbids only because every name is on every list. Both variants have their own theory and neither is this page’s.

There are two sides. This is the surprising one. Put everybody into a single pool, so that any two participants may be matched and each ranks all the others, and the same definition of blocking pair applies word for word. The existence theorem then fails. There are profiles in that setting with no stable matching at all: whichever pairing is proposed, some two participants prefer each other to what they have, and the counterexample is small enough to check by hand with four participants. Gale and Shapley pointed this out in the same paper that proved the two-sided case.

So the theorem is not a fact about matchings, or about preferences, or about the blocking condition. It is a fact about the bipartite structure — about there being two sides with one side able to propose and the other able only to hold or refuse. Take the sides away and everything else survives except the conclusion. That is an unusually clean example of a hypothesis earning its place, and it is worth setting beside the way a single missing case collapses an otherwise uniform pattern.

Where it came from #

The result is from a short paper of 1962 by David Gale and Lloyd Shapley, whose closing pages make a point of the fact that the whole argument runs without a single piece of mathematical notation. The proof above is theirs, and it is fair to say the claim holds: the two halves of it fit in a paragraph each and nothing in either needs a symbol. Shapley shared the 2012 prize in economic sciences with Alvin Roth for this line of work. Neither the paper’s applications nor the prize’s citation belongs on this page; what belongs is the argument, which is complete without either.

The word “stable” in the definition was theirs too, and it repays attention. It does not mean optimal, or fair, or best by any measure. It means only that no two participants on opposite sides can both do better by abandoning what they were given. That is a low bar, deliberately, and the low bar is what makes the existence theorem possible at all — a stronger condition would be exactly the kind that rules everything out.

Where this anchor goes next #

The census at the top of the page shows four stable matchings, and it draws them as four cells in a band without saying anything about how they relate to each other. They relate to each other a great deal.

Two of the four are incomparable — one is better for some members of side one and worse for others — so the picture is a diamond rather than a chain, and the two extremes are precisely what the construction returns depending on which side does the proposing. That the pointwise better of two stable matchings is again stable is not obvious and is not proved here; it is the subject of the side that proposes wins, which is where this anchor’s second rung sits.

The third rung asks the question this one has carefully not asked. Everything above assumed the rankings submitted are the rankings held. They need not be, and no stable rule is safe from a lie shows what happens when one participant hands in a ranking that is not theirs — searched exhaustively on an instance small enough to search completely, which is the only honest way to exhibit a counterexample to a universal claim.

What survives all three rungs is the fact established here, and it is worth stating one last time in the negative form the definition uses. Given any two sides of the same size and any strict rankings whatever, there is at least one way to pair them off such that nobody has a reason to run away — not because anybody is satisfied, but because nobody can find a partner who would have them.