Matpic
mathematics, in pictures
Concept

Preference profile

The whole input to a voting rule: one complete ranking of the candidates, submitted by every voter.

Named by 7 essays across one field — each of them below, with the objects they name alongside it.

the majority tournament100 voters, every pair decidedevery profile of the space216 of them, one cell each+34+36+30ABCno Condorcet winner (12)a winner exists (204)the 3 arcs of the ring are the majority in each pair, and following them returns to A: A → B → C → A12 of the 216 profiles of 3 voters over 3 candidates have no Condorcet winner — 5.6% of the space, every oneof them built and tested

The majority that goes in a circle

Every voter hands in a ranking, and a ranking is transitive by construction. Compare the candidates two at a time and let the majority decide each pair, and the verdicts need not fit together into a ranking at all.

applied · voting rules the profileone column per group, size abovethe rulesand what each returns7655221st2nd3rd4th5thDACEACEBDBBEBEBCDACDADCDACEAEBwinnerpluralityBordainstant runoffCondorcetCoombsABCDEthe deciding count8 first places63 points19 of 27 at the end4 of 4 pairs14 of 27 at the endthe candidate that rule returnsthe count it was decided on27 voters in 6 groups over 5 candidates; a majority is more than 13.5the five rules return 5 different winners: plurality A, Borda B, instant runoff C, Condorcet D, Coombs Einstant runoff eliminates B, E, D; Coombs eliminates A, C, D

Five rules and five winners

Twenty-seven ranked ballots, five entirely reasonable ways of counting them, and five different candidates declared the winner. Every count is correct, every rule is defensible, and the answer turns out to be a property of the rule rather than of the ballots.

applied · voting rules first profile4 voters, one column eachsecond profilethe same voters on A and Bv1v2v3v41st2nd3rdAABBBCAACBCCv1v2v3v41st2nd3rdAABBBBACCCCAA 6 · B 5 pointsA 5 · B 6 pointsBorda: A ≻ BBorda: B ≻ AflipsABthe candidates that movedevery voter ranks A against B the same way in both profiles; only the third candidate moves — and Bordareverses its verdictno pair of profiles flips Borda at 3 voters; at 4 voters 3456 of the 104976 ordered pairs inside a class do

Four conditions, and no rule that has all of them

The rung below shows five reasonable rules returning five different winners, which invites the obvious question of which one is right. The answer is that the conditions anybody would write down cannot all hold at once — and here each named rule's own violation is found by search rather than quoted.

applied · voting rules the electoratethe first column is the manipulating voterevery ballot that voter could submitand the winner it producestrue1121st2nd3rdAABCBBCBCCAAelectsfor the voterA ≻ B ≻ CA ≻ C ≻ BB ≻ A ≻ CB ≻ C ≻ AC ≻ A ≻ BC ≻ B ≻ AChonestCno gainBbetterBbetterCno gainCno gainthe honest ballota misreport that paysthe control: the same voters, A and B only0 of 2 ballots payelectsfor the voterA ≻ BB ≻ ABhonestBno gainthe voter's true ranking is A ≻ B ≻ C; the honest ballot elects C under instant runoff2 of the 6 ballots the voter could submit elect somebody the voter ranks higher: B ≻ A ≻ C; B ≻ C ≻ Athe control runs the identical search with only A and B left: 0 of the 2 ballots pay, which is what astrategy-proof contest looks like

A lie that pays

Three rungs of this ladder have read a ballot as a report of a preference. This one reads it as a move, and walks every move one voter has — all six rankings, the winner each produces, and the ones that beat honesty.

applied · voting rules 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

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 · stable matching 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

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.

applied · stable matching 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

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 · stable matching

Named alongside it

The objects these essays reach for when they reach for this one.

CounterexampleCondorcet cyclePairwise majorityVoting ruleBlocking pairDeferred acceptanceStable matchingIndependence of irrelevant alternativesOrder latticeStrategy proofnessArrows theoremBijection

All concepts