A lie that pays

Everything on this ladder so far has treated a ballot as a report. A voter has a ranking, the ballot says what it is, and the voting rule is a machine that reads a preference profile and returns a name. The interesting question was what the machine does. Here the ballot becomes a move instead, the voter becomes somebody with an outcome to steer, and the question is whether the honest report is ever the wrong move.

What the sweep reports #

The electorate is five voters over three candidates. One of them — the first column of the table — genuinely holds A ≻ B ≻ C. The other four are fixed and are not lying about anything; they are scenery.

Instant runoff on the honest profile eliminates B, whose single first place is the fewest, and the ballot that had B on top transfers to C. C ends with three of five and wins. So honesty hands this voter their last choice.

Now the sweep. There are six rankings of three candidates, the voter can submit any of them, and the figure runs the rule on all six with the rest of the electorate untouched. Four produce C again. Two — B ≻ A ≻ C and B ≻ C ≻ A — produce B. Both of those are lies, both elect somebody the voter genuinely prefers to C, and the figure marks them.

That is the whole finding, and it is worth being precise about how small it is. It is not that instant runoff is a bad rule, and it is certainly not that any voter should do anything. It is that on this profile, under this rule, the map from submitted ballot to outcome has the property that the honest input is not the input the voter would choose if choosing were the point. A rule for which that can never happen is called strategy-proof, and this profile is a counterexample to instant runoff being one.

The control, and why the 2 means anything #

A search that always finds something has not been tested. That is a standing rule on this site, and it is the reason the picture has a second half.

Underneath the sweep, the identical machinery runs again on the same five voters with everything but A and B struck from every ballot. Six submissions become two, and the count of profitable ones comes back 0 of 2. Nothing was rigged to produce that zero: it is the same rule, the same electorate, the same comparison, with one candidate removed.

The zero is not an accident of the example either. With two candidates the eliminating rules collapse to counting first places, the voter’s ballot contributes one vote to one of them, and moving that vote can only move the winner away from the voter’s favourite. So the control is a genuine instance of a strategy-proof contest — and the boundary it marks is exactly the boundary of the theorem this essay is named after. Gibbard and Satterthwaite need three possible winners. With two, there is nothing to find, and the search that found two things a moment ago finds nothing.

Without that half of the picture, the 2 would be a number a search produced. With it, the 2 is a difference between two runs of the same search, which is a different kind of fact.

The same electorate, three other rules #

The obvious next question is whether the other rules of the second rung do better on this electorate. They do, and the way they do it is instructive rather than reassuring.

Borda gives the voter a great deal of power and none of it is useful. Strip out the manipulating voter and the other four leave A on two points, B on five and C on five. B and C are exactly level, so this one voter decides between them single-handed: whichever of B and C sits higher on the submitted ballot wins. Three of the six submissions elect B and three elect C. A, three points behind, is out of reach whatever happens.

So the voter is a dictator over the pair that is actually in contention — and the honest ballot already puts the better of that pair on top. Power without profit.

Plurality is not shown, because on this electorate the figure refuses to draw it. Two candidates are level at two first places each, so several of the six submissions leave the count tied at the top and there is no winner to report. That refusal is not squeamishness and it is not a gap in the drawing; it turns out to be the most important thing on the page, and the next two sections are about it.

Why a scoring rule can show nothing here #

Borda’s zero and plurality’s refusal are the same fact wearing two costumes, and the fact is exact.

A scoring rule hands out a fixed list of points by rank — $(1, 0, 0)$ for plurality, $(2, 1, 0)$ for Borda with three candidates — and the winner is whoever has the most. Fix the other four voters and their contribution is a list of scores, one per candidate. The manipulating voter adds a permutation of the point list to it, and the choice of permutation is the choice of ballot.

Now impose the condition the figures impose: every one of the submissions must produce a single winner, because a tie would need a tie-break and a tie-break is a rule the picture does not show. Two candidates tie under some submission exactly when the gap between their other-voters’ scores equals a difference the point list can supply. For Borda over three candidates the available differences are $1$ and $2$, so a tie-free electorate must have every pair of scores either identical or at least three apart. For plurality the available differences are $0$ and $1$ — a ballot that passes over both candidates gives each of them nothing — so every pair must differ by at least two.

That condition has one consequence and it is fatal to the search. The candidates fall into blocks of equal score, the blocks are further apart than any ballot can bridge, so the winner always comes from the top block — and within the top block the winner is whichever candidate the submitted ballot ranks highest. The honest ballot ranks the voter’s genuine favourite of that block highest. Every other ballot ranks somebody the voter likes no better.

So under any scoring rule, on any electorate this family will draw, no misreport can ever pay. Borda’s 0 of 6 was not evidence about Borda. It was a theorem about what survives the refusal to break ties, and the same theorem is why plurality could not be drawn at all.

A tie-break is a rule the picture does not show #

That is where the teeth of the theorem actually are, and it is worth saying plainly because the figures cannot say it.

Gibbard–Satterthwaite is a statement about a resolute rule: one that is defined on every profile and returns exactly one name. The rules in these pictures are not resolute. They are undefined wherever a count comes out level, because the alternative is to invent a tie-break — alphabetical order, a fixed voter’s ballot, a coin — and an unstated extra rule doing work inside a drawing is precisely what this whole site is against.

A partial rule slips the theorem on a technicality, and the argument above says the technicality is not a small one for scoring rules: all of Borda’s manipulability lives on the profiles that get refused. Put back any tie-break at all and Borda becomes manipulable, because a voter who can turn a tie into a win by reordering the candidates below their favourite has found a lie that pays.

There is a surprising cousin to this, in a field of this collection that has nothing to do with ballots. Dropping the excluded middle makes several classical theorems unprovable, not by contradicting them but by declining to decide the cases they leaned on. A logic that refuses to settle every proposition and a voting rule that refuses to settle every profile escape their respective impossibility results by the same manoeuvre: the theorem quantifies over total, decisive objects, and a partial object is simply not what is being quantified over. The escape is real, and in both cases it costs the thing the object was for.

The zeroes were about the electorate, not the rule #

Coombs returned 0 of 6 above. It would be a mistake to read that as a property of Coombs, and the cheapest way to see the mistake is to run the same search somewhere else.

Same rule, same true ranking, six other voters instead of four, and the count comes back 2 of 6. Coombs is manipulable; the earlier zero said something about that electorate and nothing about the rule.

This is the standing hazard of an exhaustive search over a small space, and it is the reason a caption on this site names what was exhausted rather than what was found. A sweep that comes back empty has ruled out one profile. It has not ruled out anything else, and treating it as though it had is the error four circles are a monument to — where the thing that fails at four succeeds at three, and the count is what tells them apart.

Four candidates, and how much of the space pays #

Three candidates is the smallest arena in which any of this can happen. It is not the arena in which it happens most.

Twenty-four submissions, eight of which pay — a third of the space. The pattern in the table is worth a look: every ballot that puts B first pays, and one that puts B second does too, while the ones that lead with C or D are all worthless. The lie that works is a single, coherent manoeuvre, not a scattering of accidents.

Nothing here concerns how much work the sweep is, or how the work grows with the number of candidates. That is a question about cost, another site in this fleet owns cost, and it belongs there.

The theorem, and the one on the rung below #

The general statement is Gibbard’s, from 1973, and Satterthwaite’s, from 1975, arrived at independently:

Every resolute voting rule with at least three possible winners is either a dictatorship or manipulable. There is some profile and some voter for whom a misreport elects somebody that voter strictly prefers.

Read next to the four conditions of the rung below, the kinship is close enough to be a family resemblance rather than an analogy. Arrow says a rule cannot be non-dictatorial, unanimous and independent of irrelevant alternatives at once. Gibbard–Satterthwaite says a rule cannot be non-dictatorial and strategy-proof at once. The two are convertible: a strategy-proof rule can be shown to satisfy an independence condition of exactly Arrow’s kind, and Arrow’s theorem then finishes the job.

That figure is the bridge. The independence violation is what a strategy-proof rule would have to avoid, and every rule on this ladder has one — found, not quoted, by walking the profile space and counting the pairs that flip. Borda’s sweep is a control in its own right: three voters cannot flip it, four can, and the difference between those two runs is the finding.

The dictatorship clause is not an escape hatch. A dictatorship is trivially strategy-proof, since the dictator gets their favourite by telling the truth and nobody else’s ballot matters, and that is the entire content of the exemption.

What the sweep cannot reach #

The figures settle one kind of question completely and another kind not at all, and the line between them is sharp.

What is settled. For each drawn setting the sweep is exhaustive over one voter’s options: all six rankings, or all twenty-four, with the rest of the electorate held fixed and every outcome computed rather than sampled. When it marks two ballots as profitable, instant runoff on that profile is manipulable, full stop — a single found counterexample settles a universal claim’s negation, and no further search is needed.

What is not. Gibbard–Satterthwaite quantifies over rules, and there are infinitely many. Every picture here fixes one rule, one profile and one voter, and no finite sweep over profiles can reach a quantifier that runs over rules. What the drawings establish is that four named rules fail; what the theorem establishes is that every rule fails, and that gap is not narrowed by making the searches bigger. The same asymmetry runs through Arrow on the rung below and through the exhaustion of all 256 two-input truth functions, where the space happens to be finite and the exhaustion therefore does prove the theorem. Here it does not.

What is not even asked. A voter could only use any of this by knowing the other ballots in advance, and nothing in these pictures says how that knowledge would be come by, or what happens when several voters try at once. Both are outside the field’s line. The result is the existence of a profitable misreport as a fact about a function, not a claim about anybody’s situation.

And the zeroes need the caveat they were given above: 0 of 6 for Borda is a theorem about the tie-free condition, 0 of 6 for Coombs was a fact about one electorate, and neither is evidence of strategy-proofness. This is the reverse of the usual asymmetry — a search that finds something proves more than a search that does not, and the pigeonhole is one of the rare places where an empty search proves anything at all.

Where this anchor ends #

Four rungs have taken the same object apart. A pairwise majority need not be transitive, so a condorcet cycle is possible and 12 of the 216 three-voter profiles have one. Reasonable rules disagree on the same profile. No rule has all four of Arrow’s conditions. And now: no rule is safe from a lie.

The shape of the last two results — a condition that looks modest, a search that finds it broken, and a theorem saying the breakage is universal — is not confined to ballots. The same result in stable matching is next: no rule that always returns a stable matching can be safe from a misreported preference list, found the same way, by searching an instance small enough to search completely. The subject changes entirely and the argument does not, which is the best available evidence that the argument was never about voting.