Deferred acceptance on a 4-by-4 instance, and its output put to the test
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
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
Three kinds of member, and a triple that breaks a 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.
- 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
- a sampled market of 4 has a stable grouping ×3
- 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
- 100 to 1,000 markets a size ×1
- 100 to 1,000 markets at each size ×1
- a grouping best for every capital at once exists in exactly two markets in nine ×1
- a hospital left short holds the same residents in each ×1
- a market with 12 to 30 stable matchings is found ×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
- allowing longer cycles never covers fewer pairs ×1
- allowing three-way exchanges helps substantially at moderate compatibility ×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
- eight to sixteen a side ×1
- every grouping of the drawn market is broken ×1
- every hospital has between one and four places ×1
- every market of three has a stable grouping ×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
- fifty or a hundred a side, 500 to 4,000 markets ×1
- following the pointers always leads into a cycle ×1
- from 40 a side to 1,000 the measured mean stays between 0.28 and 0.45 of e⁻¹ n ln n ×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
- in every market of three each capital gets its first choice in some stable grouping ×1
- in every market the strict core is a single allocation, and it is the cycles' allocation ×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 ends with a house worse than their own ×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 census supplies a market with the fewest stable groupings ×1
- the construction returns a one-to-one pairing ×1
- the count of pairs put the blocking question ×1
- the first round's traders number about √(πn/2) ×1
- the grouping drawn on the right is stable, checked triple by triple ×1
- the histogram fits inside the figure with room for its labels ×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 mean lies above the median: the tail runs to the right ×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, trimarket, tricensus, trishrink, trioptimal, tripairs ×1
- the option is one this view reads ×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 rotation search finds exactly the stable matchings that trying every matching finds ×1
- the rounds cannot outnumber the proposals available ×1
- the search finds a market with no stable grouping ×1
- the seed is a whole number between 0 and 1000000 ×1
- the settled matching has no blocking pair ×1
- the share of side one with a single stable partner falls as the market grows ×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
- under the smallest-total-rank rule some agent often gains ×1
- under top trading cycles no agent in any market gains by lying ×1
- with one extra receiver, side one does about as well either way ×1
- with two of each kind no grouping can be broken ×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.
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.
AppliedA 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.
AppliedHouses 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.
AppliedHow 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.
AppliedNo 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.
AppliedNobody 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.
AppliedOne 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.
AppliedThe 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.
AppliedThe 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.
AppliedThe 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.
AppliedThe 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.
ProbabilityWhen 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.