Preference profile
Named by 13 essays across one field — each of them below, with the objects they name alongside it.
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.
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.
Four conditions, and no rule that has all of them
Five reasonable rules can return five different winners on one set of ballots, 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.
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.
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.
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.
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.
The court that contradicts itself
Three judges each answer three questions, and each answers them consistently. Take the majority on each question separately and the answers no longer hang together — the body as a whole endorses a combination no member of it holds, and no rearrangement of the procedure removes the problem.
The people every stable answer leaves out
Let the lists be short and let one side take several partners. Stable matchings still exist and there can be many of them — but every one leaves out exactly the same people, and a member who is left with an empty place holds exactly the same partners in every one. A three-line count proves it.
A ring that no pairing can break
Put everybody in one pool and a stable pairing may not exist. Allow rings as well as pairs and something stable always exists — and the pairs-only answer fails exactly when that stable arrangement contains a ring of odd length. Two sides make every ring even, which is the whole reason the two-sided theorem holds.
How often the majority goes in a circle
Three voters and three candidates give 216 profiles, and 12 of them are cycles. Count every electorate up to 41 voters exactly and the share climbs towards 8.77%, a number Guilbaud found in 1952 as the solid angle where three half-spaces at the tetrahedral angle overlap. Add candidates and a winner goes missing half the time; let voters share one axis and cycles vanish. The number is always a property of the model of how ballots are drawn.
One extra person on one side
In a random market of a thousand a side, whoever proposes gets about their seventh choice and whoever receives gets about their hundred-and-fortieth. Add one person to one side and the advantage of proposing all but disappears: the shorter side does well and the longer side badly, whichever side proposes, and most people are left with exactly one stable partner.
The matching in the middle
List every stable matching of a market, give each member their stable partners sorted from best to worst, and hand each the one in the middle. Nothing says the result should even be a matching — two people might pick the same partner — and yet it always is one, it is always stable, and the other side gets its median partners too.
Named alongside it
The objects these essays reach for when they reach for this one.
Stable matchingBlocking pairCounterexampleCondorcet cycleDeferred acceptanceExhaustive searchPairwise majorityVoting ruleOrder latticeExistence proofIndependence of irrelevant alternativesInvariant