The market with the most stable matchings

How many stable matchings a market has measured the typical market, drawing its preferences at random and counting what it found. That answer is modest: a few at ten a side and about a thousand at a thousand. It grows barely faster than the size of the market. The same essay ended with a different question, which random sampling can never touch. How many stable matchings can a market have if its preferences are arranged on purpose?

There are $n!$ ways of pairing $n$ people with $n$ others, so $n!$ is a ceiling. For a long time it was not known whether the true maximum grew like a factorial or like something much smaller. It is now known to be plainly exponential, with a base between 2.28 and 3.55. The lower end of that gap is a single construction, a market nested inside itself, which is simple enough to draw and which every later search has failed to beat. The upper end took until 2018 even to reach the form $c^n$.

Ten at four a side #

A stable matching, as Gale and Shapley’s proposal procedure showed, always exists, and the proposers’ best and the receivers’ best are its two extremes. Everything else lies between them. Starting from the proposers’ best, each stable matching can be reached by a chain of rotations, each one a cycle of men who all move down to the next woman who would have them. So listing all stable matchings is a search on a graph, and it is cheap for each one found.

The market in the first figure has four men and four women. The lists have a pattern that is hard to see at first and obvious once it is pointed out: the first two men want women A and B first, in opposite orders, and the last two want C and D first, again in opposite orders. The women’s lists run the other way. The stable matchings form the picture on the right. Two independent choices at the top, one rotation to merge them, then two more independent choices, then one final rotation, and then two more: the structure is a distributive lattice, as every stable matching structure is, and it has ten elements.

All 24 possible pairings were also tested directly for blocking pairs, and exactly ten pass, so the search through rotations misses nothing. Ten turns out to be the maximum at this size. That is a quoted result. The search here does not establish it, because a complete run over all preference lists would mean trying about $24^7$ profiles, nearly five billion, after renaming the women. At three a side the full run is easy: with one list fixed there are 7,776 profiles, and none has more than three stable matchings.

The natural next step is to search further by climbing, which swaps two entries of one list at a time and keeps the change if the count does not fall. This was done from dozens of random starts at each size. It finds 8 at four a side and 60 at eight, and those fall well short. At four it misses the known 10, and at eight it misses the known 268 by a factor of more than four. The searches are not weak: each ran for many thousand counts. The landscape simply has no slope leading up to the good markets, since the structure that produces very many matchings has every list cooperating at once, and a market that is half-arranged is scarcely better than a random one. It is much the same failure as with greedy approaches to other extreme structures. A structure was needed, and it had to come from thought.

Nesting a market inside itself #

The construction is by Robert Irving and Paul Leather, in 1986. Given two markets of sizes $a$ and $b$, form one of size $ab$. Each man is a pair (outer label, inner label), and so is each woman. A man ranks women first by his outer list, applied to their outer labels, and then within each block by his inner list, applied to their inner labels. Women do the same on their side.

The table of ranks shows what that means. The smallest market that can be nested has two a side: two men and two women, with the men preferring opposite women, and the women preferring the men who do not prefer them. It has exactly two stable matchings. Multiplying it into itself gives the four-a-side market in the first figure. Doing it again gives eight, with 268 stable matchings. Doing it once more gives sixteen, with 195,472.

Those are not formulas taken on trust. All 195,472 were produced, one at a time, by the rotation search, and they are all different. They agree with the value that Irving and Leather’s recurrence gives. Donald Knuth had asked in his lectures of 1976 how large the count could be, and this is the first strong answer. Why does it give so many? Consider a stable matching of the outer market, so that each outer man is assigned an outer woman. In every assigned block, an inner market of $b$ men and $b$ women is now free to be matched in any of its stable ways, independently of all other blocks. So a single outer matching contributes the count of the inner market raised to the power $a$. That is the source of the exponential growth, and the rest of the count comes from combinations that mix between the outer matchings.

For doubling, the counts obey an exact recurrence:

$$f_{k+1} = 3 f_k^2 - 2 f_{k-1}^4, \qquad f_0 = 1,\ f_1 = 2.$$

Here $f_k$ is the count for $2^k$ a side. Three times $f_k^2$ has the shape of a sum over three types of the smallest market’s states, and the subtraction removes those counted twice. It predicts 10, 268 and 195,472, each of which was verified by listing, and then 104,310,534,400 at thirty-two a side, which agrees with the published value and is far too large to list.

The base of the exponential #

Each doubling roughly squares the count, which keeps the $n$-th root nearly constant. So the natural measure is $f_k^{1/2^k}$, and it rises to a limit.

The root is 1.4142 at two a side, 1.7783 at four, 2.0115 at eight, 2.1414 at sixteen, and 2.2779 at a thousand and twenty-four, by which point it has very nearly stopped. That number is the 2.28 in the literature. Matthew Thurber showed in 2002 that this construction is the best known for general sizes, by extending it to sizes other than powers of two, at the cost of a slightly smaller base.

Sizes that are not powers of two need a little more care, since the product of an eight with a three is a market of twenty-four whose count depends on both factors. Starting the nesting from a different seed gives a family with its own base, and the seed of two gives the largest base anyone has found. An exponential base is a very different statement from a factorial. It means that a typical pairing is unstable by a vast margin, as $n!$ grows faster than $c^n$ for any fixed $c$. And for a long time, this difference was not known. The best upper bound before 2018 had a form close to $n!$ itself, although it was widely believed that the truth should be exponential. Anna Karlin, Shayan Oveis Gharan and Robbie Weber proved in 2018 that the count is at most $c^n$ for a fixed $c$, and their constant was $2^{17}$, or 131,072. In the next few years Cory Palmer and Dömötör Pálvölgyi brought this down dramatically, using an entropy bound, to $3.55^n$. This is the dashed line in the figure. So at the time of writing, the base lies somewhere in the interval from 2.28 to 3.55.

It is unusual for a problem of this type that the lower bound has stayed still while the upper bound fell by five orders of magnitude. Often the opposite is true. And it raises a suspicion that the nested market may simply be right. That suspicion is unproved, and the climbing searches above certainly say nothing about it, since they cannot even recover the nested market when it is known to exist.

The shape of a very large set #

The whole list of 195,472 can be examined. For each stable matching, add up the ranks that the men give to their partners. That total runs from nought, where every man has his first choice, to 240, where they are at their worst and the women are at their best.

The picture has three humps of equal height, and it is the recurrence made visible. The outermost level of the construction is the smallest market, and it has three ways to settle: entirely in one direction, entirely in the other, or in a mixed way that the $3f^2$ term counts. Each hump is a copy of a spread produced by the smaller markets within it. The most common total is 56, held by 2,920 matchings, and there are peaks of about the same height at the centre and close to the other end. That is a little surprising, since a picture of many independent choices would suggest a single bell, and a sum of independent parts usually gives one. These parts are not independent at the outer level, and one coarse decision splits the whole list into three.

That spread matters to anyone who has to use one of these. A stable procedure returns an extreme, and the side that proposes gets the best of it. In this market, the outcome chosen can make a difference of 240 rank places in total between the two sides, on sixteen people each, with every intermediate value achievable. A fair choice in the middle is therefore not implied by stability at all. Robert Irving, Paul Leather and Dan Gusfield showed in 1987 how to choose the stable matching that minimises the total of everyone’s ranks, in polynomial time, even though the list is exponentially long, since the rotations can be treated as a small graph with a minimum cut. The same structure is what makes counting them hard in general while particular tasks remain easy. Counting is #P-complete, and optimising is not.

What the typical market does not show #

The contrast with random markets is extreme. Two thousand random markets of sixteen a side give a mean of 4.99 stable matchings, a median of 4, and a largest of 24, and they do not approach what is possible. The nested market has 39,161 times the mean. The earlier measurement found the mean growing like about $e^{-2} n \ln n$ in the range it could reach, while Boris Pittel’s limit is $e^{-1} n \ln n$. For sixteen, $e^{-2} n \ln n$ is about 6, so these numbers are consistent with it, and the worst case is on a different scale altogether.

Nothing in the random picture hints at that. It is a case in which the distribution of a quantity gives no information about its extreme, and a sample of any feasible size would say that the largest count at sixteen a side is about 30 or 50. The reason is that the large values need so much agreement among the lists that they have a negligible probability under random preferences. Real markets are not random, and they are not nested either. The residency-matching data that Roth and Peranson studied in the 1990s showed few stable matchings in practice, for yet another reason, since people in large markets have short lists. So neither extreme is a good model of any real market, and each of them is useful as a limit.

What a table of counts leaves unsaid #

Listing proves a lower bound only. A list of 195,472 stable matchings at sixteen a side says that the maximum at sixteen is at least that, and it says nothing about whether another market does better. The maximum is known exactly only at small sizes. The value 10 at four is proved, but no proof by exhaustion is feasible beyond a very few people on each side. At five a side, the space is $120^9$ profiles after renaming, and no symmetry reduction brings that within reach of a direct search.

The figures do not prove the upper bound either. The dashed line in the root figure comes from a paper, and it has no connection with anything computed here. The lattice of the first figure is exact and small, and it can be read in full, but already at sixteen a side no drawing would be useful.

What was computed and what was quoted #

The rotation search was run on the nested markets and gives 10, 268 and 195,472, each stable matching produced explicitly. At four a side, the ten were confirmed by testing all 24 pairings. The maximum of 3 at three a side was found by trying all 7,776 profiles with one list fixed. The climbing used seeded restarts at sizes from four to eight, and its values are lower bounds only. The recurrence was iterated exactly with integers beyond what could be listed, and it matches the listing where both exist. The random sample used 2,000 seeded markets.

Quoted: the maximum 10 at four a side, Thurber’s extensions, the theorems of Karlin, Oveis Gharan and Weber, and of Palmer and Pálvölgyi, the complexity results, and Irving, Leather and Gusfield’s optimisation. The reading of the recurrence’s three terms as states of the smallest market is an interpretation that fits the three humps. It was not derived in full here.

Still open: whether 2.28 is the truth #

What is the exact base of the exponential? It lies between 2.28 and 3.55, and the question is whether the nested market is optimal. Nothing better has been found in forty years, by construction or search, and no known argument rules one out. A cleverly chosen market might be found to beat it at a small size, and then nesting that market would give a larger base at once, since the construction works with any starting point. That makes the question particularly crisp: a single example at modest size with a larger count than the nested market would raise the lower bound for all powers of that size. Searches at small sizes have not overturned it, though none of them is exhaustive, and the climbing here shows how little a failed search of that kind can mean.

A related question concerns the stable roommates problem, with one set of people instead of two sides. There the matchings have less structure, and they may not exist at all. Palmer and Pálvölgyi’s bound also covers that case, and whether its true base equals that of the two-sided problem is not known. The rotation poset also raises an open combinatorial question. Every finite distributive lattice arises from some market, as Blair showed, and so the question is one about which posets can be realised by few people. Since counting stable matchings amounts to counting closed subsets of a poset, the bound becomes an extremal problem about posets that can be drawn with a limited number of men.

A market built from markets #

The most stable matchings known come from nesting a market inside itself, so that every block is free to choose independently: 10 at four a side, 268 at eight, 195,472 at sixteen, and a growth rate of $2.28^n$. The bound from above reached a simply exponential form only in 2018 and now stands at $3.55^n$.

The gap between those is the question. What makes it attractive is how direct it is, since a single better market at any size would settle the lower half, and that market would be an ordinary table of numbers. What makes it hard is shown by the climbing runs, which started from random tables and could not even find the market that was already known. Random preferences never look like this, and small changes do not lead here. It had to be built, by someone asking what structure might make every choice independent.