Matpic
mathematics, in pictures
Concept

Strategy proofness

The property that submitting one's true ranking is never beaten by submitting any other, whatever everybody else does.

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

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

CounterexamplePreference profileBlocking pairCondorcet cycleDeferred acceptanceIndependence of irrelevant alternativesOrder latticePairwise majorityQuantifier orderStable matchingStrategic votingVoting rule

All concepts