Four conditions, and no rule that has all of them

Five rules on one profile return five different winners. That is a picture of disagreement, and disagreement invites the obvious next question: which of the five is right?

The answer is that the question has no answer, and the shape of that answer is worth stating before any of it is argued. It is not that the five rules on offer are all defective and that a sixth, more carefully designed, would settle the matter. It is that the conditions anybody would write down when asked what a rule ought to do are jointly unsatisfiable, so the sixth rule fails one of them too, and so does the ten-thousandth.

The four conditions #

A voting rule, for the whole of this essay, takes a preference profile — one complete transitive ranking of the candidates from each of finitely many voters — and returns a single ranking of the candidates that is itself complete and transitive. That the output is a ranking rather than a winner is not a detail; it is a load-bearing part of everything below, and the section on scope returns to it.

Four conditions are then asked of such a rule.

1. Unrestricted domain. The rule accepts every profile. No arrangement of ballots is declared malformed and handed back.
2. Unanimity. If every voter ranks A above B, the rule’s output ranks A above B. This is the weakest possible respect for the ballots and no proposed rule has ever failed it.
3. Independence of irrelevant alternatives. Where the output places A relative to B depends only on where each voter places A relative to B. Moving some third candidate C about, without any voter changing their mind about A against B, cannot change the verdict on A against B.
4. Non-dictatorship. There is no single voter whose own ranking is always the output, whatever the others submit.

Each reads as a minimum rather than an aspiration. The first says the rule is a rule. The second says it is not perverse. The fourth says it counts more than one ballot. The third is the only one with any content at all, and it is the one every rule on this page breaks.

What a broken independence looks like #

A violation of independence of irrelevant alternatives is not a single bad profile. Nothing can be read off one table of ballots, because the condition compares two situations.

The object needed is a pair of profiles with three properties. Every voter ranks A against B the same way in both. At least one voter has moved some other candidate. And the rule’s verdict between A and B is reversed from the first to the second. Exhibit such a pair and the rule is convicted; the condition says the verdict may not move, and here it moved.

The figure above is exactly that object for Borda’s rule. Both tables agree, voter by voter, on A against B. In the first, A has six points to B’s five. In the second, C has been shifted down one ballot and up another, and now B has six to A’s five. Nobody changed their mind about A and B. The verdict changed anyway.

Borda’s rule is the one that reads a whole ballot and awards points by position, which makes the failure easy to see once it is drawn: a point total is a sum over all positions, and where C sits changes what those positions are.

Finding the pair rather than quoting it #

Every textbook has a pair like that one, typed in by hand. The house rule here is that an impossibility is drawn as the search that produced it, so the pair is not typed in — it is found, and the finding is a count.

The search is cheap because the space factors. Fix, for each voter, whether that voter ranks A above B or below it. Every profile falls into exactly one such class, and with three candidates each voter has $3! = 6$ possible ballots, three of which put A above B. So over $v$ voters there are $2^v$ classes and each holds $3^v$ profiles.

A violating pair is any ordered pair inside a single class whose verdicts differ, so the number of them is the sum over classes of (profiles where A wins) times (profiles where B wins), and no pair has to be visited. The total number of ordered pairs available inside classes is $2^v$ times $3^v$ squared: at three voters, $8 \times 729 = 5832$ of them, out of the $6^3 = 216$ profiles arranged into $2^3 = 8$ classes of twenty-seven.

Plurality reads only the top of each ballot, so a candidate moving into first place on somebody’s ballot removes a first place from whoever was there. The picture is a demotion of A from two first places to none, achieved without any voter altering their opinion of A against B.

Four rules, four thresholds #

The search sweeps the electorate upward from three voters and stops at the first size where the count is not zero. That threshold turns out to differ between rules, which was not something this essay expected to report.

Plurality and Coombs both break at three voters, and by the same count: 192 of the 5,832 ordered pairs. Borda cannot be broken by three voters at all — the count there is zero, over every one of the 5,832 pairs — and breaks at four, where 3,456 of the 104,976 pairs reverse it. Instant runoff survives three and four voters and first breaks at five.

Those four thresholds are a real finding and they are worth reading carefully, because the reading that suggests itself is wrong. A rule that needs five voters to break is not more independent than one that breaks at three; it fails the condition exactly as completely, since the condition is a universal statement and one counterexample settles it. What the thresholds measure is how much room a violation needs — how many ballots must be arranged before the rule’s own arithmetic can be turned against itself. Instant runoff needs the most because its verdict comes from an elimination order, and an elimination order is insensitive to small rearrangements in a way a point total is not.

The zeroes are the part that makes the counts trustworthy. A search that finds something everywhere it looks has not been tested, and the same machinery that reports 3,456 pairs for Borda at four voters reports none at three. That contrast is the only reason the positive counts are evidence of anything, and it is the same discipline the search for a polynomial satisfied by π runs on itself with two controls.

More candidates, and no more reach #

Widening the board changes the numbers and nothing else.

With four candidates each voter has $4! = 24$ ballots, twelve of them putting A above B, so three voters give $8 \times 1728^2 = 23887872$ ordered pairs inside classes and Borda breaks at three rather than four. The figures are unanimous and each one is a report about one rule over one finite space.

None of that is progress towards the theorem. Every count above is a fact about the search that produced it, and every one of them convicts a named rule. The condition Arrow’s theorem states is quantified over rules, not over profiles, and adding candidates walks in the wrong direction.

The rule that answers by refusing #

There is a second way for a rule to fail, and it belongs here because the rule that fails that way is the one usually offered as the escape.

A Condorcet rule ranks A above B whenever a majority of voters do, and its verdict on a pair depends on nothing else whatever. It satisfies independence of irrelevant alternatives outright and it satisfies unanimity, and no voter dictates anything. What it fails is the requirement that its output be a ranking, because pairwise majority preference need not be transitive.

On a profile with a Condorcet cycle the rule returns a relation that is not a ranking at all: A over B, B over C, C over A. It has not chosen badly. It has produced something the definition of a voting rule forbids, and repairing that by breaking the cycle somewhere is precisely where independence is lost again, because which link to break can only be decided by looking at something outside the pair.

The two grids together make a point the first alone would overstate. At three voters the 12 filled cells are all true three-way cycles, checked twice over by an independent count of the cyclic margins. At four voters most of the 720 are ties. The failure of completeness and the failure of transitivity are different faults with the same symptom, and a picture that reports one number for both has to say so.

What these searches cannot settle #

Here is the honest position, and it belongs in the middle of the essay rather than at the end of it.

Every figure above settles one thing: a named rule fails a named condition, established by exhibiting a pair of profiles that the condition forbids and the rule produces. That is a complete argument and a reader can check it in the tables. Four rules have been convicted this way, each by its own search over a stated space.

Arrow’s theorem says something else entirely:

For every rule satisfying unrestricted domain, unanimity and independence of irrelevant alternatives, with at least three candidates and finitely many voters, some single voter is a dictator.

The quantifier there runs over rules. A rule is a function from profiles to rankings, and there is no finite list of them to walk — the number of candidates is unbounded, the number of voters is unbounded, and even at three candidates and three voters the functions from the 216 profiles to the thirteen possible complete relations number more than any search will enumerate. A hundred rules failing is not a proof that all of them do, and no amount of searching over profiles will ever become one, because the searching is happening inside a single rule at a time.

That is the same gap, in a different subject, that a finite search for a polynomial satisfied by π has to admit. It is also what makes the sixteen two-valued connectives and the 256 syllogistic forms so unusual: in both of those the space of rules is itself finite, so the impossibility can be settled by walking it, and the figure really is the proof. Here the space of rules is not finite and the figures are reports.

One further scruple. Two of the four rules searched above — instant runoff and Coombs — return a winner rather than a ranking, and the drawing reads their ranking of a pair off the elimination order, whichever of the two survived longer. That is a defensible reading and it is a reading, made by the generator rather than by the rules themselves. For rules that genuinely return only a winner the corresponding impossibility is a different theorem with a different proof, and it is the subject of the rung above.

What the proof does instead #

The actual argument never mentions a named rule, and its manoeuvre is worth having, because it explains why no example was ever going to be enough.

Call a set of voters decisive for the pair (A, B) if, whenever every member of that set ranks A above B, the rule’s output does too, no matter what anybody outside the set submits. Unanimity says the set of all voters is decisive for every pair, so at least one decisive set exists.

Two steps then do everything.

Field expansion. A set decisive for one pair is decisive for every pair. The argument constructs a profile in which the members of the set rank A above C above B while everybody else ranks C anywhere at all, uses decisiveness on (A, B), uses unanimity on the pair the outsiders agree about, and closes the gap with transitivity of the output. Independence is what lets the conclusion be carried back to any profile with the same pairwise pattern.

Group contraction. A decisive set with more than one member has a proper subset that is decisive. Split it in two, build a profile on which the two halves disagree about a third candidate, and transitivity of the output forces one half or the other to have got its way.

Contract repeatedly. The electorate is finite, so the shrinking stops, and it can only stop at a set of one — a single voter decisive for every pair, which is a dictator. Written as a proof by contradiction it is the same argument with the last line inverted: assume non-dictatorship as well and the contraction cannot terminate, which it must.

Three things are visible in that sketch that no figure on this page shows. Transitivity of the output is used in both steps and is doing the real work. At least three candidates are needed, since both constructions require a third to move. And finiteness is used exactly once, at the end — with infinitely many voters the shrinking never terminates, the decisive sets form an ultrafilter, and rules satisfying all four conditions genuinely exist.

Which condition to give up #

Because the four are jointly unsatisfiable, every rule ever proposed is a choice of which one to abandon, and the theorem is best read as a map of the available concessions.

Give up independence and Borda’s rule is available, along with every other scoring rule. This is the usual concession, and the price is exactly what the first figures draw: the verdict between two candidates depends on candidates who are not either of them.

Give up unrestricted domain and the rule may refuse some profiles. If voters’ rankings are all consistent with a single left-to-right ordering of the candidates, majority preference is transitive and the median voter’s favourite is a Condorcet winner. That is a genuine escape and it works by narrowing the question rather than answering it.

Give up transitivity of the output and pairwise majority itself is available, returning a relation with cycles in it. The count is not small: 12 of 216 at three voters, and rising.

Give up non-dictatorship and the problem is trivial. That the trivial rule is the only one is the content of the theorem, and the reason the other three concessions are the whole of the subject.

A theorem shaped like a logician’s #

Kenneth Arrow proved this in his 1951 doctoral thesis, and it was cited in the economics prize awarded to him in 1972. What is striking is the form, which belongs to logic rather than to counting.

Four conditions are stated. They have no model. That is a stronger and stranger situation than the one where a statement is independent of a list of axioms, which needs two structures — one where the statement holds, one where it fails. Here there is no structure at all, and the four conditions are less a set of axioms than a set of four axioms one of which must be false.

The nearest relative in this collection is the sentence that says it has no proof, and the resemblance is in what the result forbids rather than in its machinery. Both say that a system meeting a short list of reasonable-sounding requirements cannot exist, and both are usually first met as a slogan that overstates them. Neither is a discovery that something is broken. Both are the discovery that the requirements were, in combination, describing nothing.

The comparison also marks the difference. The thirty-six officers do not exist, and that was settled by a search over a finite space that a reader can in principle redo; four circles cannot cut the plane into sixteen regions, and that is settled by a count. Arrow’s conditions have no model, and no search will show it, because what has to be searched is not a space of arrangements but a space of functions.

Where the ladder goes next #

Three rungs have now established that pairwise majority can cycle, that reasonable rules disagree, and that the disagreement is not a defect to be engineered away.

One condition has been left alone throughout, and it is the one a voter is most likely to notice. Every profile above was treated as the honest opinions of the voters. The next rung asks what happens when a voter submits a ranking that is not their own, searches every ballot one voter could submit, and counts the ones that pay.