One extra person on one side

The side that proposes wins shows that the stable matchings of a market form a lattice with two ends: the matching produced when side one proposes, which every member of side one likes at least as well as any other stable matching, and the matching produced when side two proposes, which is side two’s favourite in the same strong sense. Stability allows either. What that essay could not say, working with chosen instances of four and five a side, is how far apart the two ends usually are — whether choosing who proposes is a detail or a decision.

The question needs typical markets rather than chosen ones. So draw every list at random: each member of each side ranks the whole other side in an order chosen uniformly from all possible orders, independently of everybody else. Nobody is more popular than anybody else, and all the structure comes from luck. Then run deferred acceptance both ways and compare.

The proposers get their seventh choice #

The first figure grows the market from ten a side to a thousand and records the average rank each side gets in the matching side one’s proposing produces — rank 1 being a first choice.

At a thousand a side the proposers end, on average, with their seventh or eighth choice — inside the top one per cent of a list of a thousand. The receivers end with their hundred-and-fortieth, a little inside the top seventh. The two sides are identical in every respect except who proposes, the matching is stable, and one side does twenty times better than the other. As the market grows the gap grows without limit, because the two averages grow at different rates: the proposers’ like $\ln n$, the receivers’ like $n / \ln n$. Boris Pittel made both rates precise around 1990, and the figure’s dashed curves are those formulas.

The individual ranks inside one market show the same thing member by member.

The proposers’ ranks pile up at the top of their lists and thin out quickly: a hundred and thirty-five get their first choice, and only two in a thousand go beyond their fortieth. The receivers’ ranks are spread almost evenly across the whole list, a few at every position, and three quarters of them end below their fortieth choice. Nobody on either side is unmatched, and no pair would rather be together — the matching is checked against the definition of stability, not taken on trust.

A coupon collector inside the proposals #

The logarithm has a source that is worth tracing, because it is a problem already solved in another setting. A proposer’s final rank is exactly the number of proposals they made: they start at the top of their list and move down one name each time they are turned away. So the proposers’ average rank is the total number of proposals divided by $n$.

The proposing stops at the moment every receiver is holding somebody, since a receiver who holds a proposal never lets go without a better one, and a proposer is only ever turned away by a receiver who already holds someone. With random lists each proposal goes, very nearly, to a receiver chosen at random. So the total number of proposals is roughly the number of random draws needed until every one of $n$ receivers has been drawn at least once — which is the coupon collector’s problem, with its answer $n H_n \approx n \ln n$ — the harmonic sum that never stops growing, turning up inside a matching procedure. Divided by $n$, the proposers’ average rank is about $\ln n$.

The receivers’ side is the mirror image. Each receiver is proposed to about $\ln n$ times over the whole procedure, by proposers arriving in random order from random positions of her list, and she keeps the best of them. The best of $\ln n$ random ranks out of $n$ sits around position $n / \ln n$. That is the receivers’ average, and it is why proposing is worth so much: the proposers each search their lists from the top, while the receivers each choose from a handful of offers that arrived by chance.

The approximation that each proposal goes to a random receiver is not quite right — a proposer never proposes to the same receiver twice — and correcting it is what Pittel’s proof does. The figure shows the correction is small: $7.5$ against $6.9$.

Turning the market round #

Run the same market the other way, with side two proposing, and the roles swap exactly.

With a thousand on each side, side one averages $7.4$ when it proposes and $134.5$ when it receives, and side two the other way round. The two ends of the lattice are about as far apart as two stable matchings could be, and almost everybody is affected: in a balanced market of a thousand, 95 per cent of side one have a different partner in the two extreme matchings. The choice of who proposes decides, for nearly every participant, which of two quite different partners they get.

Between the two ends lie all the other stable matchings, and in a balanced random market there are many of them: each is reached from its neighbour by a rotation, a cycle of members of side one who each trade down to the next stable partner on their list while their counterparts on side two trade up. The two extremes are the endpoints of long chains of such trades, and the members who move along them are nearly everybody. Nothing about stability picks a point on the chain; the procedure that constructs the matching does, by deciding who proposes, and a later essay asks whether some point in the middle has a better claim than either end.

That is the finding the essay on who proposes established as a possibility, now measured as the typical case. It is also why real clearinghouses — the one that assigns doctors to hospital residencies is the famous example — argued for years over which side should propose, and why the argument mattered.

Add one person #

Then comes the finding that turned the subject around. Keep side one at a thousand and give side two one extra member, so that one of side two must end up unmatched. The right-hand half of the figure above is that market. Side one now averages $6.8$ when it proposes and $7.8$ when side two does. The advantage of proposing has almost vanished, and side one — now the shorter side — does well either way.

Sweeping the imbalance from three fewer to three more shows how sharp the effect is. When side two is short by even one, side one is the long side and does badly whichever side proposes, averaging between $36$ and $42$ at two hundred a side. When the sides are equal, the two orders of proposing give $5.5$ and $36.8$. When side two has one more, side one is the short side and does well either way, between $4.8$ and $5.5$. The whole of the proposing advantage lives at exact balance. One person tips it.

Itai Ashlagi, Yash Kanoria and Jacob Leshno proved this in 2017. In a random market with any fixed imbalance, however small, the short side’s average rank is about $\ln n$ and the long side’s about $n / \ln n$, whichever side proposes. The reason is competition rather than procedure. When side two is longer and proposes, its members are turned away again and again as they compete for too few partners, so they propose far down their lists before the one who ends up alone is identified — and every one of those extra proposals is an offer to a member of side one, who therefore has many to choose from. The short side cannot be made to receive few offers, because the long side has to make them.

How far down the long side has to go #

The competition argument can be made quantitative with the same bookkeeping that explained the balanced case, because a proposer’s final rank is still the number of proposals they made.

Suppose side one has $n$ members and side two has $n + 1$, and side two proposes. Its members end, on average, at about rank $n / \ln n$ — that is the long side’s fate whoever proposes — so between them they make about $n \cdot n / \ln n = n^2 / \ln n$ proposals. Every one of those proposals lands on a member of side one. Spread over $n$ receivers, that is about $n / \ln n$ offers each, arriving from random positions of the receiver’s list, and the best of $n / \ln n$ random ranks out of $n$ sits around position $\ln n$. So side one, receiving, ends near rank $\ln n$ — the same as if it had proposed. The advantage of proposing was that the proposers searched their lists while the receivers took what came, and in an unbalanced market so much comes that taking the best of it is as good as searching.

The balanced market escapes this only because its proposers can stop early. When side two proposes and the sides are equal, the procedure ends as soon as every member of side one holds somebody, which happens after only about $n \ln n$ proposals — the coupon collector’s count again — and side one gets about $\ln n$ offers each and rank $n / \ln n$. With one extra member on side two the procedure cannot end until one member of side two has been turned away by everybody, and that takes all the proposals the long side can make. One person’s presence changes the stopping rule, and the stopping rule decides who does well.

Who is left over #

The extra member does not vanish; somebody on side two ends unmatched. It could in principle be a different person in different stable matchings, and the rural hospitals theorem says it cannot: every stable matching leaves out exactly the same people. So each unbalanced market has one specific member of side two who is unmatched whichever side proposes and whichever stable matching is chosen.

That removes one kind of arbitrariness and leaves another. Which member of side two is left out is decided by the lists and by nothing else; the choice of who proposes cannot rescue them, and neither can any other rule that insists on stability. Adding the extra member to side one instead of side two changes nothing in the argument except its direction: then a member of side one is left out, side two becomes the short side, and side two does well however the procedure runs.

So the market’s outcome is organised around an asymmetry nobody chose. In a balanced market the two sides are symmetric and the procedure breaks the symmetry, handing the advantage to whichever side it lets propose. In an unbalanced market the numbers break it first, and the procedure’s choice barely registers. The same deferred-acceptance construction, run on the same kind of random lists, answers to the market’s arithmetic rather than to its own rules — a whole side’s fortunes are decided by one surplus person whom, in the end, nobody takes.

Almost everybody has a choice, or most have none #

The two ends of the lattice measure how much stability leaves undecided. At balance nearly everybody’s partner is undecided; with one extra person it is mostly decided.

In a balanced market the share of side one with two different stable partners climbs with the size of the market — from $39$ per cent at ten a side to $95$ per cent at a thousand — so that in a large balanced market almost every participant’s partner depends on a choice the definition of stability does not make. With one extra member on the other side the share stays between one in nine and one in seven at every size, and most participants have exactly one stable partner. The set of stable matchings, which at balance is a large lattice with nearly everybody moving between its ends, collapses to something close to a single matching.

This has a practical consequence that is the reverse of the balanced story. No stable rule is safe from a lie: a receiver can sometimes do better by misreporting, and the room to do so comes from having more than one stable partner. In an unbalanced market most members have only one, so the room is small — which is part of the reason stable clearinghouses work better in practice than the worst case suggests.

What the pictures cannot show #

The limit. Every number here is an average over a finite number of random markets of a finite size — eight markets at a thousand a side in the first figure. The rates $\ln n$ and $n / \ln n$ are theorems about large $n$; the figure shows the averages tracking them over two orders of magnitude, and cannot show that they keep doing so.

Real preferences. Every list here is uniformly random, which makes every participant equally desirable. Real lists are correlated — some candidates are widely wanted — and correlation shrinks the lattice: if everybody agreed on one ranking of each side, there would be exactly one stable matching and nothing for the choice of proposer to decide. The figures measure the case with the most room for disagreement, not the case any real market is in.

Any single market’s lattice. The census reads only the two ends of each market’s set of stable matchings, and counts who differs between them. It does not draw the matchings in between or count them, so it says nothing about how many stable matchings a typical market has — only about how far apart the extremes lie.

Whether the unbalanced share keeps falling. The census finds between $11$ and $15$ per cent of side one with a choice of stable partners, with no clear trend from thirty a side to a thousand. It cannot say whether that share drifts to nought far beyond a thousand or settles; that is a statement about sizes the figure does not reach.

Still open: a third side #

The two-sided theorem has a natural generalisation that has resisted proof for half a century. Donald Knuth asked in 1976 about markets with three sides — say, groups each made of one member of each of three kinds — with cyclic preferences: members of the first kind rank the second, the second rank the third, and the third rank the first. A grouping is stable if no three people, one of each kind, would all rather be together than in their assigned groups.

The cyclic restriction matters. If each member instead ranks every possible pair from the other two kinds, Ahmet Alkan showed in 1988 that stable groupings can fail to exist, with an instance small enough to check by hand — so the three-sided question is only interesting when the preferences are kept as simple as the two-sided ones, each member ranking one kind of partner and caring about nothing else. With cyclic preferences, whether a stable grouping always exists is not known. Kimmo Eriksson, Jonas Sjöstrand and Pontus Strimling proved in 2006 that it does whenever each kind has at most four members, by an exhaustive argument; Kanstantsin Pashkovich and Laurent Poirrier extended it to five in 2020, with the help of a computer. For larger markets there is neither a proof nor a counterexample, and the deferred-acceptance argument that settles the two-sided case — each proposer moving down a list, each receiver holding the best so far — has no three-sided version, because nobody in a cycle of three is purely a proposer or purely a receiver. No counterexample has turned up in any search; the question is whether some carefully built instance does not, which is exactly the kind of question the one-pool problem answered in the negative for roommates.