Generator

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

A generator in the applied library, called 47 times across 8 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

6 roommates and no stable pairing

A two-sided market is a special roommates problem

How often a room assignment can be stable

Every ranking 4 could submit, and the 4 that pay

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.

1's ranking of side one ranks all 4 of them exactly once ×20
A's ranking of side two ranks all 4 of them exactly once ×5
B's ranking of side two ranks all 4 of them exactly once ×5
column 1 gives every member of side two exactly one partner ×5
column 1 is itself a stable matching ×5
hospital 1's list names distinct residents ×5
side two's 5-th column is side one's 1-th ×5
the 1-th generalised median is one of the stable matchings ×5
with one extra the share stays a small minority at 10 a side ×5
C's ranking of side two ranks all 4 of them exactly once ×4
enough instances with an odd number of stable matchings at 6 a side ×4
the matching drawn as unstable ranks all 4 of them exactly once ×4
the median is stable in every instance at 6 a side ×4
D's ranking of side two ranks all 4 of them exactly once ×3
the size of each side is a whole number between 2 and 6 ×3
E's ranking of side two ranks all 5 of them exactly once ×2
the member of side two whose lists are searched is a whole number between 0 and 3 ×2
the number of markets is a whole number between 4 and 60 ×2
the size of side one is a whole number between 20 and 2000 ×2
a hospital left short holds the same residents in each ×1
a profitable misreport is profitable under the ranking actually held ×1
a proposer still has a name left to propose to ×1
A ranks every other person once ×1
a stable pairing exists exactly when there is no odd ring ×1
a stable partition exists ×1
a third or more of the receivers are matched beyond the fortieth name ×1
A's list names distinct hospitals ×1
an even number of people, four to ten ×1
an odd number of stable matchings, at least five ×1
an odd number of stable matchings, at least three ×1
and is one of the market's stable matchings ×1
and matches the same residents ×1
at balance the share with two stable partners climbs towards all ×1
at balance, side one does far worse when side two proposes ×1
at every size most instances, but not all, have a stable pairing ×1
at least one of the matchings has no blocking pair at all ×1
at least three stable matchings ×1
at the top, every member of side two has its worst stable partner ×1
B ranks every other person once ×1
B's list names distinct hospitals ×1
between one and fifteen pairings to draw ×1
C ranks every other person once ×1
C's list names distinct hospitals ×1
D ranks every other person once ×1
D's list names distinct hospitals ×1
E ranks every other person once ×1
E's list names distinct hospitals ×1
each annotation fits inside its own cell with a gap to the cell beside it ×1
each member of side one settles on the last name it proposed to ×1
every hospital has between one and four places ×1
every matching found is stable ×1
every matching of the two sides was formed ×1
every ordered pair of stable matchings was joined and met ×1
every pair of the two sides is put the blocking question ×1
every proposer ends the construction matched ×1
every random market has a stable assignment ×1
every ranking the participant could submit was formed ×1
every stable assignment fills each hospital to the same count ×1
every stable matching lies between the two the construction can reach ×1
every stable pairing pairs across the two sides ×1
every stable partition has the same odd rings ×1
F ranks every other person once ×1
F's list names distinct hospitals ×1
F's ranking of side two ranks all 6 of them exactly once ×1
far more proposers than receivers get their first choice ×1
G ranks every other person once ×1
G's list names distinct hospitals ×1
H ranks every other person once ×1
I ranks every other person once ×1
instances counted per size is a whole number between 20 and 1000 ×1
J ranks every other person once ×1
most members have two stable partners at balance and few do with one extra on either side ×1
no member of the proposing side has a profitable misreport ×1
no pair blocks the constructed matching ×1
no sampled pair blocks the constructed matching ×1
no stable matching beats an extreme for the side it favours ×1
no stable matching is larger than the largest matching ×1
nobody proposes to the same name twice ×1
nothing with a blocking pair is anything the construction returns ×1
side one has one ranking per member ×1
side two has one ranking per member ×1
submitting the true ranking returns the truthful matching ×1
the bottom of the order is what the construction returns with side two proposing ×1
the construction returns a one-to-one pairing ×1
the count of pairs put the blocking question ×1
the instance has a matching that stability excludes, or there is nothing to draw ×1
the instance has at least one stable matching ×1
the join of two stable matchings is stable ×1
the market has a stable assignment ×1
the matching side one proposing returns is in the zero band of the census ×1
the matching side two proposing returns is in the zero band of the census ×1
the matching this mode draws is one stability actually excludes ×1
the median is one of the stable matchings ×1
the meet of two stable matchings is stable ×1
the mode of the match family is one of run, blocking, lattice, strategy, seats, rural, partial, roommates, roomcensus, partition, twosided, market, marketflip, marketimb, marketmulti, marketspread, mediantable, mediangen, medianscatter, mediancensus ×1
the pairings number (n − 1)!! ×1
the pointwise better of two stable matchings is a matching ×1
the pointwise worse of two stable matchings is a matching ×1
the proposals counted and the proposals drawn are the same proposals ×1
the proposers' average rank is near ln n ×1
the receivers' average rank is near n / ln n ×1
the roommates instance has exactly as many stable pairings as the market has stable matchings ×1
the rounds cannot outnumber the proposals available ×1
the seed is a whole number between 0 and 1000000 ×1
the settled matching has no blocking pair ×1
the tally accounts for every matching exactly once ×1
the top is at least as good as every stable matching for side one ×1
the top of the order is what the construction returns with side one proposing ×1
the true ranking is one of the rankings searched ×1
the whole strategy space of both sides was searched ×1
the zero column of the tally is the stable set ×1
three to six increasing market sizes up to 2,000 ×1
two to eight residents ×1
two to four sizes between 4 and 14 ×1
two to six hospitals ×1
with one extra receiver, side one does about as well either way ×1

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

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 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