The people every stable answer leaves out

The first three steps into stable matching all made two assumptions and said so. The sides were the same size, and every member ranked every member of the other side. Nobody has a reason to run away noted that incomplete lists “have their own theory”, and left it there.

That theory turns out to contain one of the most useful facts in the subject, and it is a fact of a different kind from the ones before. The existence theorem said something is always possible. The lattice said the possibilities have a shape. This one says that something about the possibilities cannot vary — that however many stable matchings a market has, and however different they look, certain counts and certain people are the same in all of them.

Short lists, and being left out #

A short list changes one thing about the definitions and nothing about the method.

A member may now leave some of the other side off their list entirely, and a pair is acceptable only when each has named the other. Being unmatched becomes an outcome, and it has a place in every ranking: it is worse than any partner on the list and better than any partner off it. A matching that puts somebody with a partner they did not list is not merely unstable, it is not allowed, and the census in the figure counts only the matchings that respect every list — 1,128 of them here.

Stability gains one clause to match. A pair blocks when both members name each other and each prefers the other to what they have, where “what they have” may be nothing. So an unmatched letter and an unmatched number who have named each other always block: two people each sitting alone who would both accept the other is the plainest possible objection. And a member matched to somebody off their list would block on their own, which is the clause the acceptability rule already removes.

The existence proof survives with one line changed. In deferred acceptance a proposer who has been rejected by everyone on their list simply stops, unmatched, and the argument that the result is stable goes through as before — a blocking pair would need a proposer who preferred someone who had rejected them for a worse offer, and receivers only ever trade up. So stable matchings exist with short lists, and the figure shows four.

What the figure shows beyond existence is the thing to look at. The four stable matchings are visibly different — the edges cross in different patterns, and no two of them agree on more than a couple of pairs. And every one of them leaves out C and 4. Nobody chose that; it is not in the lists in any obvious way; the census simply finds it in all four.

A count that forces it #

The reason is a counting argument short enough to hold in the head, and it runs through the two extreme stable matchings the lattice supplies.

Let $L$ be the stable matching that is best for the letters — the one deferred acceptance returns when the letters propose — and let $M$ be any stable matching at all. Two facts from the lattice:

• Every letter does at least as well in $L$ as in $M$. So a letter matched in $M$ is matched in $L$, since being unmatched is worse than any partner. The letters matched in $M$ are among the letters matched in $L$.
• Every number does at least as badly in $L$ as in $M$. So a number matched in $L$ is matched in $M$. The numbers matched in $L$ are among the numbers matched in $M$.

Now count pairs. Every pair contains one letter and one number, so the number of pairs in a matching is both the number of letters it matches and the number of numbers it matches. Going round:

$$|M| \le (\text{letters matched in } L) = |L| \le (\text{numbers matched in } M) = |M|.$$

The chain starts and ends at $|M|$, so every inequality is an equality. $L$ and $M$ have the same size, the same letters are matched in both, and the same numbers are matched in both. Since $M$ was any stable matching, all stable matchings match exactly the same members. The result is due to McVitie and Wilson, in 1970, and the proof is the same double count that reads one rectangle two ways: the pairs are counted once from each side and the two counts are forced to agree.

The second figure makes a point that is easy to miss. The theorem is not about short lists specifically; it is about anyone who can be left out, and an unequal count of the two sides is enough to leave someone out even when every list is complete. The census finds two stable matchings, and the same letter is surplus in both. Which letter is surplus is decided by the lists, and once decided it is decided for every stable matching at once.

That somebody must be surplus is more things than boxes and nothing deeper: five letters, four numbers, one letter over. What is deeper is which one. The pigeonhole principle says a box must overflow and is silent on which; here the lists name the letter, and the counting argument guarantees that every stable matching names the same one. An arrangement that left out a different letter would not merely be a different answer — it would have to be unstable, because some pair in it would block.

A larger matching that stability forbids #

If the same people are left out every time, a natural question is whether they have to be — whether some matching respecting the lists could place more people.

It could. A matching placing everybody exists, and it is blocked. Stability has a price, and here the price is one pair: the largest matching the lists allow has five couples, and every stable matching has four.

This is worth dwelling on because it inverts an intuition. One might expect that a stable arrangement, being one that nobody would disrupt, would also be one that uses the market fully. It need not. The pairs that block the complete matching are pairs of people who each do better with each other than in it — and letting them have their way breaks up a couple whose members then cannot both be re-placed. The theory of the largest matching asks only whether edges fit together, and answers with Hall’s condition; stability adds preferences, and a matching that is as large as possible can be one that two people would walk out of.

The rural hospitals theorem then says something sharper than “stable matchings can be smaller than the largest”. It says there is no stable way to be larger: every stable matching is exactly the same size, so no amount of searching among stable arrangements finds one that places C or 4.

Several places, one list #

The second relaxation lets one side take several partners. A numbered member now has a number of places, fills them with lettered members it has listed, and ranks the letters as before. Letters still take one number each.

Stability is the natural extension. A letter and a number that name each other block if the letter prefers that number to where it is, and the number either has a place free or prefers this letter to one of the letters it holds. A market like this is many-to-one, and it is the setting the whole subject was built for in practice; the version where a numbered member is a training post with several places is where the theorem below takes its name.

The existence of stable assignments needs no new argument, because a member with several places is several members. Replace a number with $k$ places by $k$ copies, each holding one place and each with the original’s list; let every letter rank the copies of each number in a fixed order, next to one another, where the original was on its list. The stable matchings of the copied market are exactly the stable assignments of the original, one for one, and everything proved for the one-to-one case — existence, the lattice, the best matching for each side — transfers.

The count that does not move, with places #

Apply the copying to the counting argument and it yields the theorem Alvin Roth proved in 1986. In every stable assignment of a many-to-one market:

• each numbered member fills the same number of places;
• the same letters are placed;
• and a numbered member that is left with an empty place in one stable assignment holds exactly the same letters in all of them.

The figure displays all three. Number 1 is short a place in all three stable assignments, and it holds D in all three. Numbers 2 and 3 are full in all three, and the letters filling them move around: C and A in one assignment, B and C in another, E and B in the third. A full member’s holdings can change; a short member’s cannot.

The third clause is the surprising one and its proof is a small refinement of the count. A member that is short in some stable assignment is, by the copying, a set of copies of which some are unmatched — and unmatched copies are unmatched in every stable matching of the copied market, by the one-to-one theorem. So the member is short in all of them, with the same number of empty places. The further claim, that its holders never change, compares the two extreme assignments once more — the one best for the letters and the one best for the numbers — and is a short exercise in the same style as the count above; it is the part of the theorem that is Roth’s own.

The name comes from the market this was first proved about. A post that fails to fill its places in one stable outcome fails in every stable outcome, with the same people — so no rearrangement that keeps the outcome stable can help it, and a member left short by a stable market is left short by the market’s preferences rather than by the choice among stable outcomes.

Checked on four hundred markets of each size #

The theorem is proved, so a census cannot add to its truth. What a census can do is check that the enumeration in the figures reports what the theorem says on markets nobody hand-picked, which guards against a figure that shows the theorem only because its instance was chosen to.

Two numbers in the table deserve a comment. Markets with more than one stable assignment are a minority at these sizes — between one in twenty-four and one in eleven — because short random lists leave few competing arrangements. That makes the theorem easy to satisfy here, which is why the census checks every market rather than only those where it has something to bite on. And a large fraction of markets leave some member short or some letter unplaced, so the clauses about empty places are exercised hundreds of times, not a handful.

The same invariance when partners can be paid #

The theorem has a twin in a setting that looks quite different, and the resemblance is a good sign that the invariance is structural rather than an accident of ranked lists.

Suppose each possible pair produces a value that the two members can split between them however they like — a price is paid from one to the other. Now there are no rankings, only numbers, and a stable outcome is an assignment together with a division of every pair’s value such that no two members could leave their partners and split their own pair’s value to both do better. That is the assignment game of Shapley and Shubik, and a price for every person and task is the linear program underneath it. Its stable outcomes also form a lattice with a best point for each side.

And it has the same kind of fixed part. The assignments that can appear in a stable outcome are exactly the ones that maximise the total value, and a member left unassigned by one such assignment receives nothing in every stable outcome. The payments are free to vary within the lattice; who is left out, and what they are paid for being left out, is not. The ranked version counts people and the priced version counts value, and in both the count at the boundary is the thing that cannot move.

Where the invariance stops #

The invariance is fragile under exactly the extensions practice keeps wanting.

Couples. If two letters apply as a pair and want places close together, the joint preference cannot be written as two independent lists, and the existence theorem itself fails: there are markets with couples that have no stable assignment at all. Roth and Peranson’s redesign of a large clearing house in the 1990s dealt with couples by an algorithm that searches for stability and usually finds it; that “usually” is a statement about the markets that occur, not a theorem.

Ties. If a member is indifferent between two partners, stability splits into weaker and stronger versions, and under the weakest of them stable matchings of different sizes exist. Finding the largest weakly stable matching is then computationally hard, where for strict lists every stable matching is the largest stable one for free. The counting argument above relied on the lattice, and the lattice relied on strict preferences.

Misreporting. Nothing here changes what no stable rule is safe from a lie established. The rural hospitals theorem says a member left short cannot be helped by choosing among stable outcomes; it does not say such a member cannot help itself by submitting a different list, and in some markets it can.

What the pictures cannot show #

The instances are tiny. Every figure enumerates every assignment, which is what makes its claims exact and also what confines it to a handful of members on each side. The theorem is about all markets, and the pictures confirm it on a few; the count argument is what covers the rest.

The copying is described, not drawn. The reduction of places to copies is the step that carries every one-to-one result to the many-to-one case, and it appears in the text only. A figure of a copied market would show the same stable assignments with numbers split into sub-boxes, which is what the place boxes in the fourth figure already suggest without claiming.

The lists are abstract. Members are letters and numbers, and nothing in the pictures carries the weight of the markets the theorem is used about. That is deliberate — an application brings intuitions about fairness that the mathematics does not have — but it means the figures cannot show why a member being left short matters to anybody, which is the reason the theorem is famous.

Still open: how many stable answers a large market has #

The invariance says what every stable matching shares. How many stable matchings there are, and how different they are in the things that can vary, is a different question, and for large random markets it has a surprising answer. When both sides are the same size and lists are complete and random, the expected number of stable matchings grows only like $e^{-1} n \ln n$, a result of Pittel from 1989 — far below the exponential numbers constructed deliberately — and the letter-best and number-best matchings are far apart in the sense that the proposing side is much happier.

That gap closes in a striking way when the sides are unequal. Ashlagi, Kanoria and Leshno showed in 2017 that with even one more letter than numbers, the stable matchings of a large random market become almost identical: the core shrinks to nearly a single outcome, and whoever proposes hardly matters. How that collapse depends on list length, on places and on correlated preferences is an active subject, and the invariance proved here — the one thing about stable matchings that never varies at all — is the fixed point it is measured against. The next question up this path is what happens when there is only one side, where every member could be paired with every other and stability may be impossible.

What stays still when everything else moves #

Stable matchings form a lattice, can be exponentially many, and differ in who gets whom — the preceding essays established all three. Against that background the rural hospitals theorem picks out what cannot move: the size of the matching, the set of people in it, and, for anyone left with room to spare, the very partners they have.

The proof is a single chain of inequalities that begins and ends at the same number, which is the most economical way a mathematical fact can be forced. And it produces a conclusion of practical weight: an outcome that leaves some member short cannot be improved for that member by choosing a different stable outcome, because every stable outcome leaves it short in exactly the same way.