How many stable matchings a market has

The side that proposes wins showed that the stable matchings of a market are not a heap but a lattice, with one end best for each side, and one extra person on one side measured how far apart those two ends are in a random market: in a balanced market of a thousand, almost everybody has a different partner at the two extremes. That essay said plainly what it had not done. Its census read only the two ends, and “it says nothing about how many stable matchings a typical market has”.

This essay counts them. Give each of $n$ members on one side a random ranking of the other side, and each member of the other side a random ranking of the first; find every matching in which no two people on opposite sides would both rather have each other than their partners; and count. The answer is that a random market has many stable matchings, more as it grows, and that the count grows in a way that has been proved for forty years and that the computer still cannot see.

Finding them all without trying them all #

There are $n!$ ways to pair two sides of $n$, so trying every matching is hopeless beyond a dozen. The count is possible because the stable matchings have structure. Run deferred acceptance with side one proposing and it produces the matching best for side one, the top of the lattice. Every other stable matching is below it, and the steps down are rotations, a notion Robert Irving and Paul Leather made precise in 1986.

Take a stable matching and, for each member $m$ of side one, look down $m$’s list past the current partner for the first member of side two who would rather have $m$ than her own partner. Call her $s(m)$, and call her present partner $\mathrm{next}(m)$. Following $m \mapsto \mathrm{next}(m)$ from member to member must eventually loop, and a loop is a rotation: a cycle of side-one members, each of whom can move down to $s(m)$ — the partner of the next member in the cycle — at the same moment. Moving every member of a rotation at once gives another stable matching, one step down the lattice, and Irving and Leather proved that every matching immediately below a given one arises this way.

So a search that starts at the top and follows every rotation available at every matching it reaches, keeping a record of the matchings already seen, visits every stable matching exactly once. At a hundred a side that takes a few milliseconds, where trying every matching would take longer than the age of the universe. The hero runs it on hundreds of random markets at each size from 10 to 300 a side, and on dozens at 500, 700 and 1,000.

The search against every matching #

An algorithm that skips most of the matchings has to be checked against one that skips none, and for small markets the check is cheap. The figure takes random markets of three to seven a side — two thousand each for the smaller sizes, a hundred and fifty at seven — and in each one counts the stable matchings twice: by the rotation search, and by testing every one of the $n!$ ways to pair the sides, from 6 at three a side to 5,040 at seven, for a blocking pair. The two counts agree in every market.

The table also starts the story. With three a side a random market has 1.285 stable matchings on average, already more than one; with seven a side it has 2.273, and the most found in a hundred and fifty markets is eight. These small averages can be checked a third way, because Donald Knuth showed in 1976 that the expected number of stable matchings is an integral, $n!$ times the integral of $\prod_{i \ne j}(1 - x_i y_j)$ over the unit cube in $2n$ dimensions — the chance that a fixed matching is stable, multiplied by the number of matchings. Evaluated by sampling, the integral gives 1.126 at two a side and 1.292 at three against the searches’ 1.135 and 1.282, the differences being sampling error.

One market’s lattice #

The figure draws the whole set for one market of twelve a side. Its 21 stable matchings are dots, arranged in rows by how many rotations separate each from side one’s best, and a line joins two matchings when one rotation turns the first into the second. At the top, side one’s ranks of its partners add up to 18 and side two’s to 62; at the bottom the totals are 80 and 19. Every matching between gives side one something worse and side two something better, as the lattice requires.

The picture has more order than it first appears to. Every route from top to bottom passes through the same number of rows, nine, because it makes the same nine rotations, each exactly once, in some order. The rotations are partly ordered among themselves — some can be made only after others have been — and the stable matchings are exactly the ways of choosing a set of rotations that is closed under that order: if a rotation is in the set, so is everything that must precede it. Twenty-one matchings are encoded by nine rotations and the order among them.

That is why counting is hard in general and easy here. Irving and Leather also proved that counting the stable matchings of an arbitrary market is #P-complete, as hard as computing the sum without its minus signs, because counting the closed sets of an arbitrary partial order is. But a random market has only a few hundred stable matchings even at a thousand a side, and listing them one at a time is fast. The difficulty is a statement about the worst markets, which can have exponentially many.

A slope that will not arrive #

The hero’s means climb steadily: 3.0 at ten a side, 55 at a hundred, 240 at three hundred, about 1,050 at a thousand. The bands are wide — at a hundred a side the middle eighty per cent of markets have between 26 and 90 — but the means rise smoothly, and they rise slightly faster than $n$.

Boris Pittel proved in 1989 what they rise towards: the expected number of stable matchings is asymptotic to $e^{-1} n \ln n$. His proof starts from Knuth’s integral and evaluates it, by a delicate analysis of where the integrand is large, as $n$ goes to infinity. It is a theorem, and its leading term is the dashed line.

The measured means do not follow it. At every size from forty a side to a thousand they sit between 0.28 and 0.45 of Pittel’s line, and the ratio shows no sign of climbing towards one: about a third at a hundred, about a third at a thousand. They track the dotted curve, $e^{-2} n \ln n$, rather closely — 935 at a thousand against a measured 1,053 from ten markets, 420 at five hundred against 410 — and that fit is an observation about these sizes, not a rival theorem. Both can be true at once only if the approach to Pittel’s limit is extraordinarily slow, with corrections that remain a large fraction of the leading term at a thousand a side and far beyond.

The discrepancy is not new. Michael Dzierzawa and Marie-José Omero pointed out in 2000 that simulations of the average fall far short of Pittel’s asymptotic at every size simulated, and later physicists’ reviews have repeated the comparison and proposed corrected formulas. Here it appears simply as the gap between two curves. An asymptotic formula is a statement about a limit, and nothing in it promises that the limit has been reached by any size anyone will ever build. A market of a thousand is large by the standards of any real clearing house, and at that size the theorem’s prediction is too high by a factor of about two and a half.

Most markets have dozens, a few have hundreds #

One more reason to be wary of an average is visible in the distribution. At a hundred a side, two thousand markets have a median of 48 stable matchings and a mean of 53.7, and the histogram is skewed, with a tail stretching out to one market with 332. The tail is what one would expect from the lattice. If a market’s rotations fall into two groups that do not constrain each other, the stable matchings are every combination of a closed set from the first group with a closed set from the second, so the counts multiply — two groups of size ten can give a hundred matchings. A few markets happen to split that way, or nearly, and they carry counts several times the typical one.

The skew matters for what a single market can say. A clearing house running deferred acceptance on its own preferences learns nothing about the size of its own lattice from the average; the count for one market can be a fifth or five times the mean. The search above answers the question for any particular market in milliseconds, and the honest summary of a random one is a band, not a number.

Who has a choice of partner #

The count of matchings hides who they differ for. The final figure asks, for each member of side one, how many different partners that member has across all the stable matchings of the market. In small markets most people are settled: at ten a side about three in five have the same partner in every stable matching, and the average member has 1.46 stable partners, so the market’s several stable matchings differ in a few pairs only. As the market grows the settled share falls — under one in two at forty a side, 12% at 320 — and the average number of stable partners rises to 3.13.

That is the census of extremes seen from inside. The people every stable answer leaves out proved that, with unequal sides, every stable matching leaves out the same people; here the sides are equal, nobody is left out, and what varies is the partner. The more members with several stable partners, the more the choice of a stable matching is a choice about who gets their better partner — the question the matching in the middle answered by giving every member the median of their stable partners. In a large random market that choice is real for most of the people in it.

Room to lie, and a pool with almost none #

The size of the lattice has a practical reading. No stable rule is safe from a lie proved that whenever a market has more than one stable matching, some member can gain by misreporting a ranking: deferred acceptance with side one proposing gives side two its worst stable partners, and a member of side two who truncates its list — declares everyone below its best stable partner unacceptable — can push the outcome towards its own end of the lattice. A market with one stable matching offers nobody that room. The counts above say that a random balanced market almost never has only one: already at ten a side the median is three, and the settled share of the last figure falls with size. So the room to gain by strategy is the normal condition of a large balanced market, not a pathology of contrived ones, and its size grows with the lattice.

It shrinks again in two ways. Unequal sides collapse the lattice, which is the finding one extra person on one side reported and the reason the large clearing houses that run deferred acceptance see little manipulation in practice: real markets are rarely exactly balanced. And dropping the two sides altogether changes the count completely. In a single pool where anybody may pair with anybody — the roommates problem that a ring that no pairing can break studied — a stable pairing may not exist at all, and Pittel showed in 1993 that when random preferences are used the expected number of stable pairings tends to $e^{1/2} \approx 1.65$, a constant, however large the pool. Two sides with opposed interests give a lattice that grows like $n \ln n$; one pool gives at most a handful. The difference is the lattice itself, which exists because what one side gains the other loses, and which has no counterpart when every member is on both sides at once.

Pittel’s limit is not visible by a thousand a side #

The counts are exact for each market searched: the rotation search finds every stable matching, as the check against brute force confirms at small sizes and Irving and Leather’s theorem guarantees at all. What is sampled is the markets. The means at small sizes come from four hundred markets each and are good to a few per cent; at 500, 700 and 1,000 a side they come from forty, sixteen and ten markets, and at a thousand the standard error is about a fifth of the mean — still far too small for the mean to be anywhere near Pittel’s line, which is more than six standard errors above it.

Nothing here contradicts Pittel’s theorem, and nothing could: a finite computation says nothing about a limit. What the figures show is that the limit is not visible at any size up to a thousand, which is a fact about the approach and not about the destination. Whether the ratio of the true expectation to $e^{-1} n \ln n$ is creeping upward too slowly to see, or the expectation is dominated at these sizes by a part of the distribution that a few hundred samples miss, is a question the sampling cannot settle on its own.

The model is also the most symmetric one available — every ranking equally likely, independently, on both sides. Real markets have correlated preferences, with some hospitals or schools wanted by nearly everyone, and correlation shrinks the lattice sharply: one extra person on one side already found that a single extra member nearly collapses it. The counts here are an upper benchmark for markets with no shared tastes, not a prediction for any actual one.

Still open: the worst market and the typical one #

The worst case is not settled. Irving and Leather built markets with at least $2.28^n$ stable matchings, and Anna Karlin, Shayan Oveis Gharan and Robbie Weber proved in 2018 that no market has more than $c^n$ for some fixed $c$, but the true base of the exponential is unknown, with a wide gap between the constructions and the bound. The lattice’s structure makes it a question about partial orders of rotations — how many closed sets the rotation order of a market of size $n$ can have — and the markets that achieve large counts have a recursive, nearly self-similar construction that nobody has shown to be optimal.

The typical case has its own gap, the one the hero draws. Pittel later showed, with Craig Lennon, that the number of stable matchings is at least a power of $n$ with high probability, and its distribution beyond that is understood only roughly. A description of the typical count precise enough to predict the hero’s dots — a second term in the asymptotic expansion, or a proof that the median and mean behave differently enough to explain the gap — would say why a market of a thousand looks so unlike the limit it is approaching, and nobody has written one down.

Many stable answers, and slowly more #

A random market of $n$ a side has many stable matchings — 1.3 at three a side, about 55 at a hundred, about a thousand at a thousand — and all of them are found from the proposers’ best by following rotations, which a search can do in milliseconds where trying every matching would take forever. The matchings form a lattice whose routes from top to bottom all make the same rotations, and the counts are skewed, with a few markets holding several times the typical number. Pittel proved the expected count grows like $e^{-1} n \ln n$; the measured means sit at about a third of that line at every size up to a thousand, closer to $e^{-2} n \ln n$, which is a reminder that a theorem about the limit and the markets anyone can build are different things.