Matpic
mathematics, in pictures
Generator

match

A generator in the applied library, called 24 times across 3 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 testBoth sides' preference tables with every rejected proposal struck through, the round-by-round ledger of proposals, and the matching the construction settles on.side one's rankings, best firstside two's rankings, best firstthe matching it settles on1st2nd3rd4thABCD14324231312413421st2nd3rd4th1234BCADCBDAADCBCDABA1B2C3D4the pair that settledproposed to, then rejectedroundproposals madewhat each name in hand did with them1A→1 B→4 C→3 D→11 holds A; 4 holds B; 3 holds C; 1 keeps A, D rejected2D→33 takes D, C rejected3C→11 takes C, A rejected4A→44 takes A, B rejected5B→22 holds Bside one proposing settles on A4 B2 C1 D3 after 5 roundsall 16 pairs were put the blocking question and none answered yes, so the settled matching is stable8 proposals were made — a fact about these particular lists, not a claim about how long anything takes

show: "strategy"

Every ranking 4 could submit, and the 4 that payOne participant's true ranking, a cell for every ranking they could submit instead labelled with the partner it returns, the profitable misreports listed, and the same search run on the proposing side finding none.4's true ranking of side one, best firstCDAtruthfulBtruthfully: A4 B2 C1 D3one cell per ranking 4 could submit, labelled with the partner it returnsAAAAAABBBBBBAABBADAADDADthe true rankinga ranking that paysthe 4 profitable misreports, submitted ranking and partner obtainedsubmittedpartnertrue rankCDBAD2 of 4DBACD2 of 4DBCAD2 of 4DCBAD2 of 4the control: the same search, every member of both sides, 24 rankings eachside onepaysside twopaysA010B020C030D0444 truly ranks side one CDAB and gets A, its 3rd choiceof the 24 rankings it could submit instead, 4 return a partner it strictly prefersthe same sweep over every member of the proposing side searched 96 rankings and found none, which is whatmakes the 4 a finding

show: "run"

Deferred acceptance on a 4-by-4 instance, and its output put to the testBoth sides' preference tables with every rejected proposal struck through, the round-by-round ledger of proposals, and the matching the construction settles on.side one's rankings, best firstside two's rankings, best firstthe matching it settles on1st2nd3rd4thABCD14324231312413421st2nd3rd4th1234BCADCBDAADCBCDABA1B2C3D4the pair that settledproposed to, then rejectedroundproposals madewhat each name in hand did with them1A→1 B→4 C→3 D→11 holds A; 4 holds B; 3 holds C; 1 keeps A, D rejected2D→33 takes D, C rejected3C→11 takes C, A rejected4A→44 takes A, B rejected5B→22 holds Bside one proposing settles on A4 B2 C1 D3 after 5 roundsall 16 pairs were put the blocking question and none answered yes, so the settled matching is stable8 proposals were made — a fact about these particular lists, not a claim about how long anything takes

show: "lattice"

The 4 stable matchings of the instance, ordered by side one's preferenceA 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.better for side one, worse for side twoM1 A4 B2 C1 D3side one's ranks 2, 2, 2, 2M2 A3 B2 C1 D4side one's ranks 3, 2, 2, 3M3 A4 B1 C2 D3side one's ranks 2, 4, 3, 2M4 A3 B1 C2 D4side one's ranks 3, 4, 3, 3join and meet, on every pairpairjoinmeetM1, M2M1M2M1, M3M1M3M1, M4M1M4M2, M3M1M4M2, M4M2M4M3, M4M3M44 of the 24 matchings are stable, drawn with the best for side one at the topevery one of the 16 ordered pairs was joined and met, and all 32 results were themselves stablethe top A4 B2 C1 D3 is what side one proposing returns; the bottom A3 B1 C2 D4 is what side two proposing returns

show: "blocking"

One matching that is not stable, and all 24 counted by blocking pairsAn 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.a matching that is not stableA1B2C3D4why that pair blocksD13would rather4has now23ADwould ratherChas nowBhow many of the 24 matchings have each number of blocking pairs40315283241516blocking pairsevery matching, sorted — the 4 stable ones first000011122222333333334456A1 B2 C3 D4 has 1 blocking pair: D and 3 would each rather have the otherall 24 matchings were formed and each put all 16 blocking questions; 4 of them came back with nonethe strip holds one cell per matching, sorted by that count with the 4 zeroes at the left

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

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.

The whole library · What the figures prove