A third kind of member

Every two-sided market has a stable matching, and the proof is a procedure that finds one. Members of one side propose down their lists, members of the other side hold the best proposal received so far and reject the rest, and the process can only end in a matching no two people would both abandon. The theorem is from 1962, and it is as settled as anything in the subject.

In 1976 Donald Knuth asked what happens with three sides. The simplest version that is not trivially false keeps each member’s preferences as simple as they are with two sides — one ranked list of one kind of partner — and arranges the kinds in a cycle. Here they are capitals, numbers and lower-case letters. Each capital ranks the numbers, each number ranks the lower-case letters, and each lower-case letter ranks the capitals. A grouping splits everybody into triples, one member of each kind in each. It is stable when there is no triple outside it whose three members would each rather be in it: a capital who prefers that triple’s number to the one it was given, a number who prefers that triple’s letter, a letter who prefers that triple’s capital.

Whether every such market has a stable grouping is not known. It has been checked for markets with up to five members of each kind, and in every one of them a stable grouping exists. Beyond five there is neither a proof nor a counterexample, and the obstacle is not a lack of effort; it is that the two-sided proof’s engine has nothing to run on.

What breaks a grouping #

The left-hand panel of the figure shows the definition at work. In the market drawn, every capital ranks the numbers in the same order, $1, 2, 3$; every number ranks the letters $p, q, r$; every letter ranks the capitals $A, B, C$. The grouping on the left gives capital $B$ the number $2$, gives number $1$ the letter $q$, and gives letter $p$ the capital $C$. The triple $B, 1, p$ is outside the grouping, and all three of its members would gain by forming it: $B$ ranks $1$ above $2$, number $1$ ranks $p$ above $q$, and letter $p$ ranks $B$ above $C$. The grouping is broken.

The right-hand panel gives $A$ to $1$ to $p$, $B$ to $2$ to $q$, and $C$ to $3$ to $r$, and nothing breaks it. Capital $A$, number $1$ and letter $p$ already have their first choices and cannot gain, so no breaking triple can contain any of them. A breaking triple would therefore be made of $B$ or $C$, $2$ or $3$, and $q$ or $r$. Its capital must gain, so it is $C$ moving from $3$ to $2$ — $B$ already holds the best number left. Its number is then $2$, which must gain a letter better than $q$, and the only one is $p$, which is excluded. Nothing is left. In a market where everybody agrees, matching first with first, second with second and third with third is stable for the same reason a two-sided market with identical lists has exactly one stable matching.

Two things about the definition deserve attention before counting anything. First, the breaking triple needs all three of its members to gain strictly. A triple in which two would gain and one would be indifferent breaks nothing. Second, a member’s preferences concern one partner only: a capital does not care which letter comes with its number. Both choices are the ones that make the question interesting rather than easy. With weaker blocking — any triple in which some member gains and none loses — stable groupings often fail to exist for reasons that have nothing to do with the third side; with richer preferences, the subject of the last section, they fail to exist outright.

Every market of three #

With three members of each kind, a market is nine lists, each an ordering of three things, so there are $6^9 = 10{,}077{,}696$ markets. Relabelling the numbers so that capital $A$’s list reads $1, 2, 3$ and the letters so that number $1$’s list reads $p, q, r$ changes nothing about stability, and it reduces the count to 279,936 markets each standing for 36. Each market has $(3!)^2 = 36$ groupings, and each grouping can be tested for every one of the 27 possible triples.

The census answers the question for three members of each kind, and the answer is emphatic. Not only does every market have a stable grouping; every market has at least ten. The fewest occur in markets like the one in the hero figure, where everybody agrees, and the typical market has seventeen of its thirty-six groupings stable.

That the answer is yes for three was known before this census: Endre Boros, Vladimir Gurvich and their coauthors proved it in 2004, and the census confirms it by exhaustion. The useful information in the histogram is the shape. Existence at size three is not a near thing that happens to work out — it holds with a wide margin. That is the kind of evidence that tends to make people believe a conjecture, and it is worth asking what happens to the margin as markets grow.

Why two of each can never break #

The smallest case is worth a paragraph, because the reason it is empty shows what a breaking triple needs.

With two members of each kind, a grouping is two triples. Suppose a triple $a, b, c$ outside the grouping breaks it. Capital $a$ must gain a number, so its current number is the other one and $b$ sits in the other triple of the grouping, with the other capital. Number $b$ must gain a letter, so its current letter is not $c$, which puts $c$ in $a$’s triple — and then letter $c$’s current capital is $a$ itself, which it cannot strictly prefer to $a$. The ring cannot close. Every one of the sixty-four markets of two is stable in all four of its groupings, and the census in the next figure includes them as its first column.

The argument generalises in one direction only. A breaking triple’s three members must come from three different triples of the grouping — any two of them sharing a triple would make one of the three gains impossible — and with two triples there are not three to draw from. With three of each kind there are, and the question becomes real.

A margin that shrinks and does not reach nought #

A market with $n$ members of each kind has $(n!)^2$ groupings, a number that grows very fast, and the natural measure of the margin is the share of those groupings that are stable.

With two of each kind the question is empty: a short argument shows no triple can ever break a grouping, and the census of all sixty-four markets confirms that every grouping is stable. From three upward the share falls by roughly a factor of five or seven with each extra member of each kind. The median market with six of each kind has fewer than three stable groupings in a thousand.

And yet the count itself, rather than the share, is still large. With six of each kind there are 518,400 groupings, and 0.13% of them is several hundred. Every one of the sixty sampled markets of six had stable groupings — not one, but hundreds. The share shrinking is what any condition with many clauses does as the number of clauses grows; it says nothing by itself about whether the count can reach nought.

The honest summary of the evidence is therefore mixed. Every market anybody has examined has stable groupings, typically many. The share is falling fast enough that extrapolation is not obviously safe, and there is no theoretical reason in sight for the decline to stop at a positive number of groupings rather than at nought. This is exactly the situation in which small cases are least trustworthy: plentiful examples, a quantity heading towards zero, and no mechanism. Latin squares give the cautionary precedent in the other direction, where an orthogonal mate is rare in every small square and common from order ten — a share that looked like it was heading to nought and turned round.

Where the two-sided proof’s engine was #

The two-sided proof does more than show existence. It shows that the stable matchings have a structure, and the structure is what the proof uses.

With two sides, the stable matchings form a lattice: given any two, there is a stable matching that gives every member of one side the better of its two partners, and another that gives the worse. In particular there is a stable matching that gives every member of the proposing side its best possible stable partner at once — and deferred acceptance finds it. The procedure works because proposers only ever move down their lists and receivers only ever move up theirs, and the lattice guarantees the two movements meet.

With three sides the structure dissolves, and the census shows exactly how. In every market of three, each capital gets its very first choice in at least one stable grouping — a remarkable regularity, and one the census establishes for all ten million markets. But “each capital is best served by some stable grouping” does not combine into “some stable grouping serves every capital best”. When two capitals want the same number first, the groupings that give it to one cannot give it to the other, and there is no capital-optimal stable grouping at all. That happens whenever the capitals’ first choices collide, which is seven markets in nine.

So a proposal procedure run from the capitals’ side cannot have the property it has with two sides: there is no single best outcome for the capitals for it to converge to. The engine of the existence proof — a monotone search that lands on an extreme point of a lattice — has no lattice to land on. Every existence proof known for small markets works instead by case analysis or by exhaustive computer search, which is how Kimmo Eriksson, Jonas Sjöstrand and Pontus Strimling settled markets of four in 2006 — a search that finds nothing is a proof, as it is for clauses, provided it is shown to have looked everywhere — and how Kanstantsin Pashkovich and Laurent Poirrier settled markets of five in 2020.

The surprising thing: the trouble is the cycle, not the number three #

It is tempting to think three sides are hard because three is more than two. The census suggests a different reading.

A cyclic market is, from each member’s point of view, a two-sided market: a capital chooses among numbers and nothing else matters to it. What makes the problem new is that the three two-sided markets are chained in a ring, so that a number’s satisfaction depends on a letter whose satisfaction depends on a capital whose satisfaction depends on the number. Breaking a grouping requires all three links of the ring to improve at once. That is why the condition is so hard to violate in small markets — a single dissatisfied member cannot break anything — and why the share of stable groupings is so high at size three.

This is the same structure that decided existence in the one-pool problem, where people are paired from a single pool and stable pairings fail to exist exactly when the preferences contain a ring of odd length. There the ring was a cycle of preferences among individuals; here it is a cycle among kinds. Two sides make every ring even and every instance solvable. A ring of three kinds is odd, and whether that oddness can ever be turned into a market with no stable grouping, as it can in the one-pool problem, is the open question in a sentence.

When members rank pairs #

There is a version of the three-sided question whose answer is known, and it shows how fragile existence is.

Let each member care about both partners: a capital ranks the pairs (number, letter), rather than the numbers alone. A triple breaks a grouping when each of its members prefers its pair in the triple to the pair it was given. This is a more realistic model of, say, forming project teams, where a person cares about both colleagues.

With only two members of each kind, there are four groupings, and the figure shows a market in which every one of them is broken. Ahmet Alkan published the first example of this kind in 1988. The search behind the figure found such markets about one time in two hundred, so they are not rare curiosities; they are a steady fraction of all small markets. The cyclic markets, by contrast, never failed once in any census here.

The difference is the size of each member’s world. When preferences range over pairs, a member can be made unhappy by a change in either partner, so far more triples have all three members improving, and the condition that a grouping survives every triple becomes far more demanding. With cyclic preferences each member watches one partner, the ring has to close for anything to break, and stability is cheap. That is why Knuth’s question is posed in the cyclic form: it is the version where a positive answer is plausible.

Markets of six say nothing about markets of seven #

Every census here is finite, and the question is about all sizes. The figures establish that every cyclic market of three has at least ten stable groupings, that sampled markets of four, five and six all have some, and that markets ranking pairs can have none. None of that bears logically on markets of seven, or of a hundred. The proofs that exist for four and five are themselves exhaustive in character, and their method does not extend.

The samples are samples. For four, five and six members of each kind, the figures test random markets drawn with every list equally likely. A market built adversarially — the kind a counterexample would be — might look nothing like a random one. Every sampled market of six had hundreds of stable groupings, and a market with none, if it exists, could still be a vanishing fraction of all markets of some size, invisible to any sample.

The cost of finding a stable grouping is not drawn. This essay asks whether stable groupings exist and what the set of them looks like. How hard they are to find, in a market where they exist, is a different question with its own literature; the figures count groupings by testing all of them, which says nothing about better methods.

Still open: Knuth’s question #

Whether every cyclic three-sided market has a stable grouping is open for markets with six or more members of each kind, fifty years after Knuth asked it. The known facts point both ways. Stable groupings are plentiful in every case computed, and the share of them falls fast. Two-sided markets have a lattice and a procedure; three-sided markets have neither, and the census shows the lattice failing in seven markets of nine. Markets with incomplete lists — members willing to be grouped only with some partners — are known to have instances with no stable grouping at all, found by Péter Biró and Eric McDermid in 2010, so any proof for complete lists must use completeness essentially.

The two-sided theory came with surprises nobody had looked for: that every stable matching leaves out the same people, that one extra member changes everything, that nobody’s strategy is safe. What the three-sided theory would look like, if existence were proved, is unknown, because the proof would have to supply the structure that the census shows is missing — some ordering of groupings, or some invariant of the ring, that a procedure could climb. Finding it, or finding the market with nothing stable in it, would settle the question either way.