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 4 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
Everyone points at the house they want. Favourite owners: A→F, B→G, C→H, D→F, E→B, F→G, G→B, H→H, I→G. Cycles: GB; H. Final allocation: A gets F's, B gets G's, C gets A's, D gets I's, E gets D's, F gets C's, G gets B's, H gets H's, I gets E's.

Houses traded in cycles

Everyone owns a house and would rather have someone else's. Let each point at the owner of the house they want most, follow the arrows into a cycle, and trade around it; repeat. The result is the only allocation no group can improve with its own houses, and nobody can gain by lying about what they want — the two guarantees stable matching could not give together.

applied · Stable matching
The trades a buyer and seller cannot make. Uniform private values: efficient surplus 1/6; best incentive-compatible, individually rational, budget-balanced mechanism trades iff b − s ≥ 1/4, surplus 9/64 = 27/32 of the efficient.

Some good trades cannot be made

A seller who values a car at s meets a buyer who values it at b, and neither knows the other's number. Whenever b is larger, a sale would make both better off. Myerson and Satterthwaite proved in 1983 that no way of haggling, auctioning or brokering can guarantee it: some sales worth making are always lost. With values spread evenly the best possible procedure trades only when the buyer's value beats the seller's by a quarter, loses five thirty-seconds of the surplus — and is reached by two people who simply name prices and split the difference.

applied · Fair division

Named alongside it

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

CounterexamplePreference profileStable matchingAuctionBargainingBlocking pairCondorcet cycleDeferred acceptanceExpectationIndependence of irrelevant alternativesKidney exchangeMarket design

All concepts