The matching in the middle

A market’s stable matchings form a lattice with two ends: one end is the best stable matching for side one and the worst for side two, the other end the reverse, and every stable matching lies between them. In a random balanced market the ends are far apart — at a thousand a side, the proposers average their seventh choice and the receivers their hundred-and-fortieth, and nearly every participant has a different partner at the two ends. Choosing an end means choosing a side to favour.

So a natural question is whether the lattice has a middle with a claim of its own: a stable matching that treats both sides even-handedly, defined without first deciding who proposes. There is one, and its definition is so simple that it looks like it should not work. Take every stable matching of the market. For each member, collect the partners they have across all of them and sort those partners from the member’s best to their worst. Give each member the one in the middle.

Each member’s stable partners, sorted #

The first figure does this for one instance of six a side with five stable matchings.

Each row lists one member’s partners in the five stable matchings, repetitions included, in that member’s order of preference. Member A has partner 4 in two of the five matchings, partner 2 in two and partner 6 in one, so A’s row reads $4, 4, 2, 2, 6$ and A’s median is 2. Member D has partner 5 in all five and the row is constant. Member E has partner 6 four times and partner 2 once.

The middle column reads A2, B1, C4, D5, E6, F3. Look at what the definition did not promise. Each member of side one chose their median independently of the others, by consulting only their own partners and their own preferences. Nothing stops two of them choosing the same member of side two, in which case the column would not even be a matching. It is one — the six entries in the middle column are six different members of side two — and it is stable: checked pair by pair against the definition, no member of side one and member of side two would both rather be with each other. The same holds for every column of the table, not only the middle one.

And there is a second surprise in the reading from the other side. Do the same construction for side two — each member of side two’s stable partners, sorted by their preferences — and the middle column there is the same matching. Side one’s median is side two’s median. The compromise is not a compromise imposed on one side from the other’s point of view; each side gets its middle, simultaneously, in one matching.

Where the median sits among the five #

Drawing the instance’s lattice shows where the median lands, and the answer is not the obvious one.

The five stable matchings make a diamond with a tail: M1 at the top, M2 and M3 side by side, M4 where they meet, and M5 below. M2 and M3 are incomparable — some members of side one prefer one, some the other — which is exactly what makes the lattice more than a list. A reader looking for “the middle” of this picture would point at M2 or M3, or at the level between them. The median is neither. It is M4, the meet of M2 and M3: the matching that gives each member of side one the worse of their partners in M2 and M3.

That is less arbitrary than it looks. A member’s median partner is the one that at least three of the five matchings rate at least as good for that member and at least three rate at least as bad. For A that is partner 2, which M1 and M2 beat and M5 falls short of; for B it is partner 1, and so on down the column — and the column is M4 because M4 is the only stable matching in which every member of side one sits at their own middle at once. In totals of rank, side one pays $9, 11, 12, 14, 19$ across the five matchings from top to bottom and side two pays $22, 18, 18, 14, 9$; the median gives 14 to each, the one matching of the five that splits the ranks exactly evenly.

Every column is a stable matching #

The middle column is the famous one, but the figure’s first claim was stronger: every column of the sorted table is a stable matching. The next figure says which.

The first column, everybody’s best stable partner, is M1 — that is the lattice’s top, which the essay on who proposes identifies as the matching side one’s proposing produces. The last column is M5, the bottom. In between, the second column is M1 again and the third and fourth are both M4. The two matchings that the definition of “middle” would have pointed at, M2 and M3, are never a column at all.

Chung-Piaw Teo and Jay Sethuraman proved in 1998 that this always happens: for any market with $k$ stable matchings, the $i$-th column of the sorted table is a stable matching for every $i$, and it is the $(k + 1 - i)$-th column read from side two. They are called the generalised medians, and they give a whole scale of compromises, from side one’s favourite through the median to side two’s, each defined by a position in everybody’s sorted list rather than by a procedure.

The reversal between the sides is the lattice’s opposition of interests carried down to individual members. A stable matching that is better for one member of side one is worse for that member’s partner, and the sorted lists record that trade member by member: side one’s second-best column is side two’s second-worst.

Why sorting stays stable: rounding an average #

The proof is a piece of geometry, and the geometry is the same that makes a table of shares a lottery over whole assignments.

Average the $k$ stable matchings: give each pair of members a weight equal to the fraction of the stable matchings in which they are partners. The result is a fractional matching, a table in which every member’s weights add to one. It satisfies a fractional version of stability: for every pair of members from the two sides, the weight they give each other, plus the weight each gives to partners they like better than the other, adds to at least one — a pair that would block has too little of either. John Vande Vate in 1989 and Uriel Rothblum in 1992 proved that the fractional stable matchings form a polytope whose corners are exactly the stable matchings, in the same way the corners of the assignment polytope are the whole assignments.

Teo and Sethuraman’s step is a way of rounding a point of that polytope. Choose a threshold $\alpha$ between nought and one. Each member of side one reads down their own list, adding up the weights, and takes the partner at which the running total first passes $\alpha$. They proved the result is always a stable matching — the fractional stability inequalities are exactly what stop two members of side one claiming the same partner, and what stop any pair from blocking. At $\alpha$ just above $i/k$ the rounding of the average of all $k$ stable matchings is the $(i+1)$-th column of the table, and at $\alpha = \tfrac12$ it is the median. From side two’s side the running totals are read in the opposite order, which is why side two’s median is the same matching.

So the median is not a clever choice among the stable matchings; it is the average of all of them, rounded. The lattice’s middle is its centre of mass.

The same geometry explains why this is special to two sides. When everybody is in one pool, as in the roommates problem, the fractional stable matchings still form a polytope, but its corners are no longer all whole: some put weight one half on each of two partners, which is exactly the odd ring that no pairing can break, seen as a point of the polytope. A rounding of an average can then land on a half, and the median argument has nothing to stand on. Two sides make the corners whole, and whole corners are what let every column of the table be a matching.

A larger market: fifteen stable matchings #

Six a side is enough to show the definition and too small to show how the median relates to other ideas of fairness. The next figure takes one random instance of twelve a side, which happens to have fifteen stable matchings, and places each by the total rank the two sides pay in it.

The fifteen matchings run from side one’s best at $(23, 64)$ to side two’s at $(73, 22)$, roughly along a line: what one side gains the other loses. The median sits at $(52, 32)$ — favourable to side two, in this instance, by twenty ranks. Two other stable matchings have a claim to be the fairest. The egalitarian one, with the least total rank, is at $(32, 47)$, costing $79$ in all against the median’s $84$. The most even one splits the ranks $42$ against $43$. The median is neither.

That is not a defect in the median. The three are answers to three different questions. The egalitarian matching minimises the sum of everybody’s ranks, treating a rank lost by one person as recoverable by a rank gained by another. The even matching equalises the two sides’ totals, treating each side as a single party. The median gives each member the middle of what stability allows them, which is a statement about individuals and says nothing about totals. In the six-a-side instance all three coincided; in this one they come apart.

How often the three agree #

Running the comparison over many random markets measures how often the median also wins by the other two standards.

Across eight hundred random markets the median was stable every time, as the theorem requires — the census is a check on the construction as much as on the markets. It was also the least-total matching in about half of the small markets and fewer of the larger ones, falling from $49$ to $38$ per cent between six and twelve a side, and the most even in three quarters of the smallest markets falling to a half. As markets grow and their lattices lengthen, there are more stable matchings for the three notions of fairness to disagree about, and they agree less often.

Two things in the census are worth separating. The first column is a theorem being confirmed: the count is 800 of 800 because it could not be anything else, and the only thing it tests is that the search found every stable matching and sorted the lists correctly — had it missed one, a column could easily have failed to be a matching. The other two columns are measurements with no theorem behind them. They say that in random markets of these sizes the median is a reasonable proxy for the two other notions of fairness about half the time, and they say it with the uncertainty of two hundred instances a row: a difference of five points between neighbouring rows is inside the noise, and the downward drift across all four rows is the only thing the table can be trusted to show.

What the median guarantees each member #

The median’s claim to fairness is a guarantee made to every individual, and it can be stated without totals. In the median matching each member of either side has a partner at least as good as the one they get in half of the stable matchings, and at least as bad as the one they get in the other half. Nobody is at the bottom of what stability allows them unless all their stable partners are the same, and nobody is at the top on the other side’s account.

Neither end of the lattice can say that. At the top, every member of side one has their best stable partner and every member of side two their worst, by construction; at the bottom, the reverse. Stability itself is indifferent between them, in the same way that it is indifferent to which people it leaves unmatched in an unbalanced market, since every stable matching leaves out the same ones — the choice between the ends is not one stability makes. The egalitarian matching cannot say it either: minimising the total can leave a particular member at their worst stable partner, provided the ranks saved elsewhere add up to more. A third standard, the matching that minimises the worst rank anybody gets, goes the other way and protects the worst-off individual at the cost of everybody else. The median is the one of the four that promises each member the same thing, a middle position, and keeps the promise to all of them at once.

What the median does not do is remove the incentive to misreport. No stable rule is safe from a lie, and a rule that returns the median is a stable rule: a member who can change the set of stable matchings by submitting a different list can change which one sits in the middle. The median settles the argument about which side a procedure should favour, and leaves the argument about truthful reports where it was.

A majority vote in disguise #

The median has a description that ties it to a much older idea. In any distributive lattice — and the lattice of stable matchings is distributive — the median of three elements $x$, $y$, $z$ is

$$(x \wedge y) \vee (y \wedge z) \vee (z \wedge x),$$

which is the majority function: for any single member, it picks the partner that at least two of the three matchings agree is good enough. For bits the same formula is the majority vote of three bits, the three-input gate that returns whatever at least two inputs say — the function that a single connective can build and that error-correcting circuits use to outvote a faulty component.

So the median stable matching is a majority vote among the stable matchings, taken member by member, and the theorem says the vote never produces a conflict: members voting independently never elect the same partner twice, and the elected pairs never block. That is the same reason a majority of three bits is always a bit. Distributivity is exactly the property that makes coordinate-wise voting land back inside the structure. In a lattice that is not distributive the majority formula can be written down just the same and simply fails to pick out a well-defined middle, because the two ways of combining meets and joins give different answers; Conway’s observation that the stable matchings form a distributive lattice, made in the 1970s as a structural curiosity, is what licenses the vote.

What the pictures cannot show #

The theorem. Every figure checks the median, and every generalised median, on particular instances — six a side in three figures, twelve a side in one, eight hundred random markets in the census. The statement that it holds for every market is Teo and Sethuraman’s, and it rests on the rounding argument, which no table can carry. A census of eight hundred confirmations is still eight hundred and not all.

How the stable matchings were found. Every figure lists all the stable matchings of its instance, found by a search that tries partners between each member’s best and worst stable partner and discards any that create a blocking pair. That works for twelve a side and would not for a market of any real size, where the stable matchings can be far too many to list, and nothing here addresses how the median might be found in a market too large to list.

Even numbers. With an even number of stable matchings there is no single middle column but two, both stable; the figures chose instances with an odd count to avoid the choice, and the choice between the two middle columns is a real one that the definition does not make.

Still open here: where the median goes in a large market #

For the egalitarian matching there is an asymptotic answer. Boris Pittel showed that in a large balanced random market the least total rank over all stable matchings is about $2n^{3/2}$, shared roughly equally between the sides — each side averaging about $\sqrt n$ per member, far better for the worse-off side than either end of the lattice, where one side averages $n / \ln n$.

For the median the census here stops at twelve a side, and its percentages are still moving: the median coincides with the egalitarian matching less often as the market grows, and nothing drawn here says whether it ends up near that balanced point at $\sqrt n$ per member, or drifts towards one end, or wanders. The median is defined member by member and the egalitarian matching by a total, and a large random market is exactly where statements about typical members and statements about totals come apart. Where, along the long lattice of a large random market, everybody’s middle partner puts the market as a whole is not something this essay can answer. A census that could would need to list the stable matchings of markets of hundreds a side, and those can number in the thousands; what it would find is a question about typical members of large random structures, of the kind that usually turns out to have a clean answer once somebody finds the right way to average.