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. No reasonable voting rule over three or more candidates has it, which is the Gibbard-Satterthwaite theorem.

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

Every ballot one voter could submit under instant runoff. One voter's true ranking beside every ranking that voter could submit instead, with the winner each produces and the profitable misreports marked.

A lie that pays

A ballot is usually read 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 Every ranking 4 could submit, and the 4 that pay. One 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.

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

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