Arrow's theorem, counted by hand: 64 voting rules go in, two dictatorships come out

An election is supposed to answer a question: what does this group want. Most arguments about voting systems assume the question has an answer and that we are arguing about how to find it.

Condorcet noticed in 1785 that it may not. Three voters, three candidates, every individual preference perfectly sensible and consistent, and the group can end up preferring A to B, B to C, and C to A. Not because anyone was confused. Because majority preference does not have to be transitive.

Kenneth Arrow proved in 1951 that this is not a quirk of one counting method. No ranked voting system can satisfy four obviously reasonable conditions at once.

Anyone can recite that. I wanted to count it.

Why it is countable at all

Arrow’s four conditions are: every possible set of individual rankings is allowed, if everyone prefers X to Y then society does, society’s view on X against Y depends only on how people rank X against Y, and no single voter decides everything.

The third one is called independence of irrelevant alternatives, and it is enormously strong. It says that when society decides between X and Y, the only information it may use is how each voter ranks X against Y. Where C sits is not allowed to matter.

Take the smallest interesting case: two voters, three candidates. Each pair of candidates has four possible inputs, since each voter either prefers the first or the second. If everyone agrees, unanimity fixes the answer, which pins two of the four. That leaves two free choices per pair, and three pairs.

So the entire space of rules obeying those conditions is 2 to the 6. Sixty-four.

Not sixty-four families. Sixty-four rules, which I can write down and test.

Running all of them

Each of the 64 rules gets applied to each of the 36 possible pairs of voter rankings. The only extra demand is that the output be an actual ranking rather than a loop.

Two survive. One is “do whatever voter one says.” The other is “do whatever voter two says.”

The right panel is all 64, with the number in each cell counting how many of the 36 electorates that rule answers with a contradiction. The two pale cells are the dictators. Fifty-eight milliseconds of arithmetic, and Arrow’s theorem is not a claim I am relaying, it is something I watched happen.

The narrowest failure is worth seeing, because it shows how little room there is. The best non-dictatorial rule breaks on exactly two of the 36 electorates. Here is one of them. Voter one ranks A over C over B. Voter two ranks B over A over C. The rule says society prefers A to C, and B to A, and C to B. Ask it who won and it points in a circle.

Checking that every condition is load-bearing

A proof you cannot break is a proof you have not understood, so I dropped each condition in turn.

Drop unanimity, and 94 rules survive instead of two. Most of them are rules that ignore the voters entirely and always return the same ranking. Perfectly consistent, perfectly non-dictatorial, and it never listens to anyone.

Drop independence, and the Borda count works. It is unanimous, never produces a loop, and nobody’s dictatorship. My search found its violation and I checked it by hand: in one electorate Borda says B beats A, in another it says A beats B, and both voters rank A against B identically in both. The only thing that moved was where the third candidate sits.

Drop the requirement that every set of rankings be allowed, and something real happens. Line the candidates up left to right and only permit voters whose preferences fall off as you move away from their favourite. Four of the six possible rankings survive that filter.

Of the 216 possible three-voter electorates, 12 produce a majority cycle. Of the 64 that are single-peaked, zero do. Majority rule is perfectly well behaved on every one of them.

That is the escape hatch, and it is the one democracies actually use. Arrange politics on a line and the paradox goes away. The price is refusing to consider some preferences people genuinely hold.

How often there is no answer

Condorcet’s cycle sounds like a curiosity. I computed how often it happens, as exact fractions rather than simulation estimates, because every quantity involved is a whole number.

Three voters and three candidates: 1 in 18. Five voters: 5 in 72. As voters increase it converges to about 8.8 percent, which reproduces the published value.

Then the measurement I had not expected, holding the voters at 1001 and raising the number of candidates. Three candidates, 9 percent. Five candidates, 47 percent. Eight candidates, 92 percent.

At eight candidates, an electorate having a coherent majority preference is the exception rather than the rule. The more choices you put on a ballot, the less likely it is that “what the majority wants” refers to anything.

That number carries its model, because a number without one is a lie. This assumes every ranking is equally likely and voters are independent, which is a known worst case rather than a description of real electorates. Real voters cluster. Which is exactly what the last section measures.

The second wall

The natural reply to Arrow is that a group does not need a ranking, only a winner. Gibbard and Satterthwaite closed that in the 1970s: any deterministic rule that can elect any of three or more candidates, and is not a dictatorship, can be manipulated. Some voter does better by lying.

I had cited that and built nothing for it, in a night whose whole discipline was counting rather than quoting. So it got the same treatment.

There is no 64-rule collapse available here. A rule mapping 36 electorates to three winners has about 1.5 times 10 to the 17 possibilities. But strategy-proofness constrains densely, tying every electorate to the ten reachable by one voter changing their ballot, so a search with backtracking flattens it.

It visited 1,422 nodes. Two survivors. Both dictatorships.

Relax the requirement that all three candidates can win, and 17 rules survive, every one of them degenerate: three constants, twelve that quietly delete a candidate and run a two-way race, and the two dictators. A two-candidate election genuinely is safe from strategy, because there is nothing to lie about. Three is where it breaks, and three is the whole point of holding an election.

Three pathologies, as real ballots

Found by search and verified by re-running the method on both versions. Not claims. Exhibits.

Raising the winner makes them lose. 21 voters, instant runoff elects A. Two voters then change their ballot from B over A over C, to A over B over C. The only change is that the winner moved up one place. Instant runoff now elects C.

The rounds show why. Before, the first count is A 8, B 7, C 6, so C is eliminated and A wins 12 to 9. After, A has 10 and B has 5 and C has 6, so B is eliminated instead, and C wins 11 to 10. Raising A took two first-place votes away from B, which changed who got eliminated, and elimination order is what decides an instant-runoff race.

Three methods, three different winners. 100 voters. Plurality elects C. Instant runoff elects B. And A beats C head-to-head 52 to 48 and beats B 66 to 34. A majority prefers A to each of the other two, and A wins under neither rule.

That is the structure of the 2009 Burlington, Vermont mayoral election. Plurality favoured Wright, instant runoff elected Kiss, and Montroll beat both of them head-to-head by 930 and 590 votes, and lost.

Voting honestly makes it worse. 17 voters, instant runoff elects C. Three voters who sincerely rank B first and A second stay home. Instant runoff now elects A, whom they prefer to C. By turning up and voting honestly for their actual favourite, they got a worse result than by not voting.

A method’s pathology, drawn as a picture

Fix four candidates in a two-dimensional space of opinion. For every possible position of the electorate’s centre, run a complete election with 301 voters clustered there, each ranking candidates by how close they are. Colour that point by who won. That is 44,100 full elections per panel.

The first panel is the reference: whoever is nearest. A method whose map looks like that is doing what a reasonable person would call the right thing.

Then I counted rather than eyeballed. How many disconnected regions does each candidate win? A sane map gives each candidate exactly one, because moving the electorate a little should change the winner only at a boundary.

Plurality gives four. Borda gives four. The head-to-head rule gives four and matches the reference 96.2 percent of the time, the best of any.

Approval gives five. Instant runoff gives six, with two islands sitting right in the middle of the field. An island is a candidate winning territory entirely surrounded by territory they lose, so you can walk the electorate across the map in a straight line and watch the winner flip and flip back.

They are the same elimination-order sensitivity as the monotonicity failure above, showing up as a shape. I did not put them there and I did not expect them.

What actually makes methods disagree, and I had it wrong

I went in assuming crowded candidates are what drives methods apart. That is the vote-splitting story everyone tells, and it is why I placed two of my four candidates close together in the first place.

My own sweep said no. Hold the candidates fixed and vary how spread out the voters are, and disagreement climbs steadily: plurality from 0.6 percent to 8.4. Vary how far apart the candidates sit instead, and almost nothing moves.

So when voters largely agree with each other, every method elects the same person and the rule barely matters. It is disagreement among the voters, not crowding among the candidates, that decides how much the choice of rule decides.

Two more the data handed me against my expectations. Instant runoff tracks the head-to-head winner better than any other non-Condorcet method at every diversity level, 0.2 percent to 4.1. That is the same method whose pathology I exhibited twice. Ugly failure modes and the best average agreement, both true, and I am keeping both.

And approval’s curve spikes where voters agree most, which is not noise. Approval is not a rule, it is a rule plus a strategy, and mine is “approve everyone above your own average.” A different plausible strategy gives a different curve. That is the price of escaping Arrow: the methods that dodge the impossibility do it by importing voter strategy, and Gibbard and Satterthwaite are waiting on the other side.

What I re-ran before writing this

All of it, two months later. 64 rules against 36 electorates, two survivors, both dictators. Each condition dropped in turn, with the Borda violation and the single-peaked escape reproducing exactly. The monotonicity exhibit reproducing ballot for ballot.

Two of the three exhibits did not reproduce. The search that finds them is seeded, so I expected the same ballots, and the Burlington-shaped profile and the no-show paradox both came back as different electorates with different margins than my own notes from that night record. The structure is identical and the profiles are not, which means the committed code no longer produces the exhibits written down beside it, most likely because the search gained a stricter tie-breaking requirement after those two were printed. The ballots above are the ones tonight’s run produced and can be checked against.

One plate had a caption running 178 pixels off the edge of a 730 pixel canvas, which the renderer discarded silently, taking with it the half of the sentence that says what an island does to an election. It is two lines now, and the renderer raises on an overrun rather than quietly cropping.