Generator

Deferred acceptance on a 4-by-4 instance, and its output put to the test

A generator in the applied library, called 69 times across 12 essays. Below: what it draws with nothing chosen and at each mode an essay asks for, what it checks while drawing, and everywhere it is used.

match is one function. Everything below came out of it during this build, at parameters taken from the essays rather than invented for this page — so a figure here is the same figure a reader meets in an essay, and if the generator changes, this page changes with it.

With nothing chosen

Deferred acceptance on a 4-by-4 instance, and its output put to the test. Both sides' preference tables with every rejected proposal struck through, the round-by-round ledger of proposals, and the matching the construction settles on.

The odd ring that forbids a stable pairing

The odd ring that forbids a stable pairing. The ranked lists of 6 people and a stable partition of them drawn on a circle: pairs as plain chords, a ring of three or more as arrows from each person to the one they hold. An odd ring is present, as it is in every stable partition of this instance.

6 roommates and no stable pairing

6 roommates and no stable pairing. The ranked lists of 6 people, and all 15 ways of pairing them drawn as chords on a circle, with blocking pairs dashed. 0 pairings are stable.

A two-sided market is a special roommates problem

A two-sided market is a special roommates problem. The 4 stable pairings of 8 people who each rank the other side first, drawn on circles with the lettered side on the left and the numbered side on the right. Each is a stable matching of the two-sided market.

How often a room assignment can be stable

How often a room assignment can be stable. Bars for group sizes 4, 6, 8, 10: the share of 600 random instances with at least one stable pairing, 95%, 94%, 91%, 88%, against a line at 100%.

Three kinds of member, and a triple that breaks a grouping

Three kinds of member, and a triple that breaks a grouping. Two copies of one market with three members of each of three kinds and cyclic preferences: on the left a grouping blocked by the triple B, 1, p; on the right a stable grouping.

What it checks while it draws

Collected by running the family and recording what it asserted, not written here. The count is how many separate times the claim was put to the test while these drawings were made.

Where it is called

Every figure on this list is drawn by the same rule, so a change to the rule changes all of them at once. That is why the list is published.

Applied

A ring that no pairing can break

Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.

Applied

A third kind of member

Two sides always have a stable matching, and the proof is a procedure. Add a third kind of member — capitals who rank numbers, numbers who rank letters, letters who rank capitals — and every market small enough to check still has a stable grouping. Ten million markets of three have at least ten each. Nobody can prove it continues, because the structure the two-sided proof stands on is gone.

Applied

Houses traded in cycles

Everyone owns a house and would rather have someone else's. Let each point at the owner of the house they want most, follow the arrows into a cycle, and trade around it; repeat. The result is the only allocation no group can improve with its own houses, and nobody can gain by lying about what they want — the two guarantees stable matching could not give together.

Applied

How many stable matchings a market has

A market with random preferences on both sides has not one stable matching but many — a few at ten a side, a few dozen at a hundred, about a thousand at a thousand — and all of them are reached from the proposers' best by a chain of rotations. Boris Pittel proved that the average grows like n ln n / e. The averages measured here sit at a third of that at every size a computer can reach.

Applied

No stable rule is safe from a lie

A stable matching always exists, and the side that proposes gets the best one it could hope for. This essay closes the story with the result that spoils it — one participant's whole strategy space searched, four submissions found that beat the truth, and a theorem saying no rule anywhere escapes.

Applied

Nobody has a reason to run away

A matching is stable when no two people on opposite sides would both rather have each other than what they have — a condition that names nothing to build and everything to rule out. The surprise is that something always satisfies it, however perverse the rankings are made.

Applied

One extra person on one side

In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.

Applied

The market with the most stable matchings

Random preferences give a sixteen-a-side market about five stable matchings. Nesting a two-a-side market inside itself gives the same size 195,472, every one of them listed. That construction is forty years old and nothing has beaten it, while the ceiling above it has fallen from 2¹⁷ⁿ to 3.55ⁿ. The truth lies somewhere between 2.28ⁿ and that.

Applied

The matching in the middle

List every stable matching of a market, give each member their stable partners sorted from best to worst, and hand each the one in the middle. Nothing says the result should even be a matching — two people might pick the same partner — and yet it always is one, it is always stable, and the other side gets its median partners too.

Applied

The people every stable answer leaves out

Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.

Applied

The side that proposes wins

An instance usually has several stable matchings, and the set of them is not a heap — it is a lattice, closed under taking the better partner and under taking the worse. The two ends of that lattice are exactly what deferred acceptance returns from the two sides, so whoever proposes decides which end the instance lands on.

Probability

When to stop looking

Candidates arrive one at a time in a random order. Each must be accepted or rejected on the spot, with no going back and no way to know what is still to come. The best possible rule is to look at about a third of them and then take the first one that beats everything seen — and it works about a third of the time, however many there are.

The whole library · What the figures prove