Generator

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

A generator in the applied library, called 25 times across 4 essays. Below: what it draws at its defaults 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.

At its defaults

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.

`show: "strategy"`

`show: "run"`

`show: "lattice"`

The 4 stable matchings of the instance, ordered by side one's preference. A Hasse diagram of the stable matchings with the best for side one at the top, beside a table giving the join and the meet of every pair.

`show: "blocking"`

One matching that is not stable, and all 24 counted by blocking pairs. An unstable matching with its blocking pair ringed and both members' rankings marked, above an exhaustive census of every matching of the instance by how many blocking pairs it has.

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 ×14
A's ranking of side two ranks all 4 of them exactly once ×4
B's ranking of side two ranks all 4 of them exactly once ×4
the matching drawn as unstable ranks all 4 of them exactly once ×4
C's ranking of side two ranks all 4 of them exactly once ×3
D's ranking of side two ranks all 4 of them exactly once ×2
the member of side two whose lists are searched is a whole number between 0 and 3 ×2
a profitable misreport is profitable under the ranking actually held ×1
a proposer still has a name left to propose to ×1
at least one of the matchings has no blocking pair at all ×1
at the top, every member of side two has its worst stable partner ×1
E's ranking of side two ranks all 5 of them exactly once ×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 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 ranking the participant could submit was formed ×1
every stable matching lies between the two the construction can reach ×1
no member of the proposing side has a profitable misreport ×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 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 meet of two stable matchings is stable ×1
the mode of the match family is one of run, blocking, lattice, strategy ×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 rounds cannot outnumber the proposals available ×1
the settled matching has no blocking pair ×1
the size of each side is a whole number between 2 and 6 ×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

Where it is called

Changing this generator changes every figure on this list. That is what makes the list worth publishing rather than keeping in a check script.

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

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