A ring that no pairing can break

The existence theorem for stable matchings was careful about its hypotheses, and it named the one that surprises people. The theorem needs two sides. Put everybody in a single pool, let any two be paired, let each rank all the others, keep the same definition of a blocking pair — and there are instances with no stable pairing at all. The smallest has four people, and that essay checks it by hand: three of them prefer each other in a cycle, the fourth is everybody’s last choice, and each of the three pairings is broken up by somebody escaping the fourth.

That settles whether the one-pool version can fail. It does not say why it fails, or which instances fail, or what a failed instance still has in it. Those questions have an answer, found by Jimmy Tan in 1991, and it is a picture: the obstruction is always a ring of odd length, and the ring is a genuine feature of the preferences that every stable arrangement contains.

Six people and fifteen pairings #

Before the rings, the plain question for a larger instance. Six people can be paired off in $5 \times 3 \times 1 = 15$ ways, few enough to check every one against every possible objection.

Every one of the fifteen is blocked, some by a single pair and some by five. That is the claim “no stable pairing exists” in its most direct form, a census with no gaps, and it is also completely uninformative about the reason. Fifteen panels of dashed lines show that each pairing fails; they do not show that the failures have a common cause, and the four-person example had a cause that could be named — a cycle of three people who each wanted the next.

Here the lists invite exactly that explanation and it turns out to be wrong. E ranks C first, C ranks F first, and F ranks E first — a cycle of first choices among three people, just like the four-person example. The natural guess is that these three are the trouble, that some pairing of the others fails because of them, and that the obstruction is a ring of three.

It is not. The ring that every stable arrangement of this instance contains has five members, A, F, E, C and B, and it holds E and C and F in a different order from their first choices: F holds E, E holds C, and C holds B rather than F. The obvious triangle of first choices is not a stable arrangement at all: the census of all 720 arrangements rejects every one that contains it. An odd ring is not something that can be spotted in the lists; it is a property of the whole preference structure, found by asking which arrangements survive every objection. What prevents pairing is the ring in the first figure, and to see why it has to be a ring, the arrangement has to be allowed to be one.

Letting the arrangement be a ring #

A pairing is a way of making everybody hold someone and be held by the same person. Relax that: let each person hold one other person and be held by one, but not necessarily the same one. The people then fall into rings — cycles in which each holds the next and is held by the previous. A ring of two is an ordinary pair; a ring of one is somebody alone; a ring of three or more is new.

Tan’s definition of a stable partition asks two things of such an arrangement:

• Nobody is held by someone they prefer to whom they hold. Each person in a ring of three or more likes the person they hold strictly better than the person who holds them. (In a pair the two coincide and the condition is empty.)
• No two people would both rather be together. Measure each person’s satisfaction by who holds them — the worse of their two ring neighbours — and forbid any two people who each prefer the other to their holder.

The second condition is the old blocking-pair condition, with the holder standing in for the partner. So a stable partition consisting only of pairs is exactly a stable pairing, and stable partitions are a generalisation that includes the thing being sought.

The first figure was found by trying all $6! = 720$ ways of arranging six people in rings and keeping those that meet both conditions. Exactly one does. It puts five people in a ring and leaves D alone.

Every instance has one, and they all share the same odd rings #

Tan proved two facts about stable partitions, and they are the whole explanation.

First, every instance has a stable partition. The relaxation is exactly enough to make existence unconditional, just as two sides were enough for pairings. The proof is a construction extending Irving’s procedure for pairings, with proposals that can go round in cycles, and a cycle that cannot be resolved is simply kept as a ring.

Second, the odd rings are the same in every stable partition. An instance may have several stable partitions, differing in how the even rings and pairs are arranged; the rings of odd length — three, five, seven people — appear in all of them, with the same members.

From those two facts the criterion follows in a line. A stable pairing exists exactly when a stable partition has no odd ring. If there is no odd ring, every ring has even length, and an even ring can be cut into pairs — alternate members pair with the person they hold — in a way that inherits stability; the result is a stable pairing. If there is an odd ring, it is in every stable partition, including any stable pairing, which is a stable partition with no rings at all — a contradiction, so no stable pairing exists.

That is the reason the census of fifteen pairings found nothing. There are five people in a ring of odd length, and an odd number of people cannot be split into pairs. The ring is not an artefact of how the search was organised; it is present in the preferences, it is present in every stable arrangement, and parity forbids pairing it off.

An instance that can be paired #

The criterion works in the other direction too, and the contrast is worth seeing.

This instance has three stable pairings, so by the criterion its stable partitions have no odd ring. They may still have rings — a ring of four, cut two ways into pairs, is the typical source of several stable pairings — but every ring is even, and every even ring can be broken into pairs without anybody objecting.

The five stable partitions of this instance include the three stable pairings and two arrangements that keep a ring of four intact rather than cutting it. That is the general shape: an even ring is a pairing that has not yet been chosen between its two ways of being cut, and an odd ring is one that cannot be cut at all.

Proposals in one pool, and where they go round #

The rings are not only a way of describing failure after the fact. They are what a proposal procedure produces when it is run in one pool, and seeing how makes the connection to the two-sided case direct.

Run the familiar construction with everybody both proposing and receiving. Each person proposes to the first name on their list; each person holds the best proposal they have received and rejects the rest; the rejected propose to their next name. In a two-sided market this stops with everybody holding exactly the person holding them, which is the stable matching. In one pool it stops with everybody holding somebody and held by somebody, but the two need not coincide. What the first round of proposals produces is already an arrangement in rings.

Irving’s procedure takes it from there. Each person’s list is trimmed to the names between the one they hold and the one holding them, since anything better has rejected them and anything worse cannot be stably theirs. Then the procedure looks for a particular kind of cycle among the trimmed lists — called a rotation, the same word and nearly the same object as the moves that step through the lattice of two-sided stable matchings — and eliminates it, trimming further. If trimming ever empties somebody’s list, no stable pairing exists; if every list shrinks to a single name, those names are the stable pairing.

Tan’s refinement is to keep what Irving’s procedure throws away. When a list would empty, the cycle responsible is an odd ring, and instead of reporting failure the procedure records the ring and carries on with everybody else. What it ends with is a stable partition. So the odd ring in the first figure is not a separate discovery; it is the exact point at which the pairing procedure runs out of room, and it is the thing any correct procedure for pairings has to detect in order to say “none”.

Why two sides make every ring even #

The original theorem now has a one-line explanation that its own proof never gives.

With two sides, a lettered member can only hold a numbered one and vice versa, so every ring alternates letter, number, letter, number. A ring that alternates between two kinds must have even length — it has to come back to a letter after a number, so its letters and numbers are equal in count. In a two-sided market an odd ring is impossible, so no stable partition has one, so a stable pairing always exists.

The figure makes the embedding concrete. Treat a two-sided market as a one-pool instance in which everybody ranks the whole other side first and their own side after. Then any pairing that puts two same-side people together is blocked — two people who would each rather cross — so every stable pairing crosses, and the stable pairings are exactly the stable matchings. The existence theorem for two sides is the special case of Tan’s criterion in which parity has already been fixed.

The same parity governs graphs directly, and the resemblance is not a metaphor. A graph can be coloured with two colours so that every edge joins different colours exactly when it has no cycle of odd length — the standard test, which the four-colour essay notes is the one easy case of colouring. Two colours are two sides. A two-sided market is a two-coloured graph of acceptable pairs, it has no odd cycles, and the rings that stability can force are cycles in that graph; so the two-sided theorem is the two-colour test in another setting. The five-cycle that defeats bipartiteness among triangle-free graphs is the graph-theoretic cousin of the five-person ring above.

This is a pleasing kind of explanation, and it has a familiar shape. The handshake count that settled the bridges of Königsberg is a parity of the same kind: the ends of edges come in pairs, so odd-degree places come in pairs, and no route can change that. The fifteen-puzzle has half its positions unreachable because a move changes a parity that the solved position fixes; the crossings of a permutation have a parity that no rearrangement by swaps can change. Here the parity is of a ring’s length, and the bipartite structure fixes it before any preference is written down.

How often a random pool can be paired #

Tan’s criterion says which instances fail. How many do is a separate question, and it has a surprisingly slow answer.

At every size most random instances can be paired, and the share falls only slowly. The four-person figure is close to the exact value, which can be counted outright. Four people have $6^4 = 1{,}296$ possible sets of lists, and an instance fails exactly when three of them form a cycle of first choices with the fourth last on all three lists. That leaves four choices of the unwanted person, two directions for the cycle and six lists for the outsider — $48$ failing instances, so the exact share that can be paired is $1{,}248/1{,}296 = 26/27$, about $96.3\%$. As the pool grows, odd rings have more ways to form and the share drifts down.

Where it goes in the limit is the open part. Pittel and Irving proved in 1994 that the share cannot tend to one — for large pools it is at most $\sqrt{e}/2$, about $0.82$ — so failure becomes common rather than exceptional. Simulations by Mertens and others suggest it falls towards zero, roughly like $n^{-1/4}$ — so slowly that a pool of ten thousand would still be solvable perhaps one time in six, and a pool of a million not much less often than one in twenty. The decay is slow enough that no feasible census will display it convincingly; the fourth figure shows the first few percent of the fall and nothing of its eventual shape.

What the pictures cannot show #

Whether a stable pool can be manipulated. The two-sided theory showed that no stable rule is safe from a lie; a one-pool rule inherits the same impossibility, since two-sided markets are a special case of it, and adds a question of its own — whether somebody in an odd ring could, by submitting a different list, make a stable pairing exist where none did. None of the figures considers any list but the true one.

How the stable partition is found. Every stable partition drawn here was found by trying all $n!$ arrangements, which is fine for six people and hopeless for sixty. Tan’s existence proof and Irving’s 1985 procedure for pairings both run in polynomial time, by cleverly organised rounds of proposals and eliminations; nothing in the figures depicts them, and nothing here claims anything about their cost.

That the odd rings are shared. Each instance drawn happens to have a single stable partition or, in the solvable case, several with no odd rings. The theorem that odd rings are common to all stable partitions is checked on these instances and is not illustrated by any of them, since none of them has two stable partitions containing an odd ring. An instance with several such partitions would need more people than an exhaustive search over rings can comfortably handle.

Why the share falls. The census measures the share at four sizes. The reason it declines — the growing number of places an odd ring can form, against the growing number of pairings available to avoid one — is an asymptotic argument of real difficulty, and the bars are consistent with many different rates of decline.

Still open: rings, and how they are counted #

Tan’s criterion is complete for strict rankings, and the natural extensions each reopen it. With ties in the rankings, deciding whether a stable pairing exists becomes NP-complete in some versions, where for strict rankings Irving’s procedure settles it quickly, so a small relaxation of the input moves the problem across the boundary of efficient solvability. With incomplete lists, stable partitions still exist but the relation between odd rings and unpaired people gains a clause, since somebody may now be unpaired because nobody listed them.

The counting questions are open in the ordinary sense. The limiting share of solvable random instances is conjectured and not proved; so is the expected number of stable pairings when one exists, and the typical size of the odd rings when one does not. The analogy with the rural hospitals theorem is close: there, every stable matching leaves out the same people; here, every stable partition contains the same odd rings, and the people in them are the ones a stable pairing would have to separate and cannot. In both settings the invariant is what stability cannot move, and in both it is found by comparing all stable outcomes at once rather than by inspecting one. What is settled is the thing the pictures show: when a pool of people cannot be paired stably, it is because some of them are locked in a ring of odd length that every stable arrangement contains, and an odd number of people will not split into pairs.

An obstruction with a shape #

The one-pool failure first appeared as a curiosity, four people and three blocked pairings, a warning that the two-sided theorem’s hypothesis was doing real work. With rings allowed, the curiosity becomes a theory. Every instance has a stable arrangement; the stable arrangements share their odd rings; and a stable pairing exists precisely when there are none.

That turns a negative census — fifteen pairings, each blocked — into a positive object: five named people holding one another in a cycle that cannot be cut. And it gives the original theorem the explanation its proof never offered. Two sides guarantee a stable matching not because proposing is clever, but because a ring that alternates between two kinds of people always has even length.