An electorate too large for a dictator

Four conditions, and no rule that has all of them proved Arrow’s theorem. A rule that turns every profile of voters’ rankings into a ranking of the candidates, that respects unanimity, and that decides each pair of candidates from the voters’ opinions on that pair alone, must be a dictatorship once there are three candidates or more. The proof works with decisive sets — sets of voters whose agreement on a pair forces the outcome — and it has two steps. A set decisive for one pair is decisive for all. A decisive set with more than one member has a decisive proper subset. Contract the whole electorate this way and it shrinks to a single voter, who is the dictator.

That essay ended with a remark about the last step. The contraction stops because the electorate is finite; with infinitely many voters it need not stop, the decisive sets form what is called an ultrafilter, and rules satisfying all four conditions genuinely exist. The remark is one sentence, and the sentence hides a strange story. The rules that exist cannot be described. No formula, no algorithm and no definition in the language of set theory produces one, and there are models of mathematics in which they do not exist at all. Arrow’s theorem for an infinite electorate is a statement whose truth depends on the axiom of choice, in the same way that the choice nobody can write down described for bases of the real numbers and well-orderings of the line.

This essay takes the remark apart. First the finite theorem, checked by machine on every rule small enough to check. Then the decisive sets as an algebraic object, and what happens to the contraction when it never ends. Then the rule an ultrafilter defines, and why nobody can hold one in their hands.

Every small rule, tried #

With three candidates there are three pairs — A against B, B against C, C against A — and a rule that respects independence of irrelevant alternatives decides each pair by looking only at who prefers which of that pair. For two voters the opinions on a pair have four patterns, so the rule’s decision on that pair is a truth table of four entries, one of sixteen possibilities, and the whole rule is three such tables: $16^3 = 4{,}096$ rules. Each can be tested against all $6^2 = 36$ profiles of two rankings, asking whether the three pairwise decisions ever form a cycle.

Ninety-four of the 4,096 never produce a cycle. Impose unanimity — on each pair, if both voters agree the rule agrees — and two remain: voter 1 decides everything, or voter 2 does. For three voters each truth table has eight entries and unanimity fixes two of them, leaving $2^6 = 64$ tables a pair and $64^3 = 262{,}144$ rules. Each was tested against all 216 profiles of three rankings. Exactly three survive, and they are the three dictatorships.

This is Arrow’s theorem verified by exhaustion, for electorates small enough to exhaust, and it is worth seeing because the count makes the theorem’s severity visible. A designer choosing among a quarter of a million reasonable-looking rules — each one treating each pair separately, each one respecting the unanimous will — finds that all but three of them produce, on some profile, a society that prefers A to B, B to C and C to A. The survivors are the rules in which the other voters do not matter. The cycle that kills the others is the one the majority that goes in a circle found in majority voting, and the exhaustion shows that no cleverer way of combining three ballots pair by pair escapes it.

Four voters would mean $2^{14}$ tables a pair and more than four million million rules, which is where exhaustion stops being the right tool and the proof takes over. The proof’s contraction step is what the figures that follow are about, because it is the step that changes when the electorate is no longer finite.

Without unanimity, and what the survivors look like #

Drop unanimity and the 94 transitive rules for two voters are more varied, but not by much. Sorting their truth tables by hand finds four kinds and nothing else.

Six are constant: one fixed ranking, whatever anybody submits. Eighty-four fix one candidate at the top or the bottom regardless of the ballots and let the voters decide the order of the other two, by any of the fourteen non-constant truth tables for one pair. Two are dictatorships. And two are dictatorships turned upside down, in which the society’s ranking is one voter’s ranking reversed. No rule among the 94 uses both voters on every pair. Robert Wilson proved the general statement in 1972: a rule that respects independence and lets every pair be decided both ways by some profile is a dictatorship or an inverted dictatorship — or, if the society is allowed to be indifferent, the rule that declares every pair a tie. The constant and the eighty-four partly imposed rules are exactly what Wilson’s condition, every outcome on every pair possible, rules out, and unanimity is what then removes the inverted dictators.

The classification matters for what follows, because it shows the source of the impossibility is not unanimity. The engine is transitivity combined with pair-by-pair independence. Unanimity merely points the engine at a dictator rather than at an anti-dictator or at nobody. And transitivity combined with independence is exactly what forces the decisive sets into a rigid algebraic shape.

The decisive sets have the laws of an ultrafilter #

Take any rule with Arrow’s properties and list its decisive sets — the sets of voters who, by agreeing on a pair, force the outcome on that pair whatever everyone else submits. For three voters and the rule in which voter 2 decides, the decisive sets are the four sets containing voter 2.

Three laws are visible in the figure, and the figure checks each of them on all eight sets. Of every set and its complement, exactly one is decisive. A set containing a decisive set is decisive. The common part of two decisive sets is decisive. And the empty set is not decisive, since unanimity of nobody forces nothing. A collection of subsets with these properties is called an ultrafilter. The sets containing one fixed member always form one, the principal ultrafilter at that member, and on a finite set those are the only ultrafilters there are: intersect all the sets in one and the result, being an intersection of finitely many decisive sets, is decisive and so nonempty, and if it has two members then one of them alone, or its complement, would be decisive.

The laws are not a property of dictatorships alone; they follow from Arrow’s conditions for any electorate. The two steps of the proof establish them. Field expansion says decisiveness does not depend on the pair. Group contraction, examined more carefully, says that if a decisive set is split into two parts, one part is decisive — and running the same construction with a set and its complement shows one of the two must be. Alan Kirman and Dieter Sondermann put it this way in 1972, after Peter Fishburn had given the first infinite example in 1970: the decisive sets of any rule with Arrow’s properties form an ultrafilter on the electorate, and conversely every ultrafilter on the electorate is the family of decisive sets of such a rule. Arrow’s theorem is then a fact about finite sets: every ultrafilter on a finite set is principal, and a principal ultrafilter is a dictator.

The contraction that never ends #

On an infinite electorate — voters numbered 1, 2, 3, and so on for ever — the contraction can be carried on without stopping. Split the voters into odd and even; one of the halves is decisive. Split that half by its remainder mod 4; one quarter is decisive. Keep going.

If the rule is the dictatorship of voter 37, the decisive class at each level is the one containing 37: odd, then $1 \bmod 4$, then $5 \bmod 8$, $5 \bmod 16$, $5 \bmod 32$, $37 \bmod 64$, and from there on the class of 37 at every level. The chain closes down on voter 37. But nothing in Arrow’s conditions forces a chain of that kind. The chain that keeps remainder $2^k - 1$ at every level, which a 2-adic number theorist would write as …111, consists of nested infinite classes whose common part is empty: a whole number $n$ is $2^k - 1 \bmod 2^k$ only while $2^k \le n + 1$, so every voter drops out at some level. Below 4,096 only voter 4,095 survives twelve halvings, and the thirteenth halving removes that voter too.

An ultrafilter containing every set in that chain has no dictator. Each set in the chain is decisive, the sets get thinner without limit, and no voter is in all of them. Nor does an ultrafilter that follows voter 37’s chain need to be principal: the classes of 37 with 37 himself removed are still nested and infinite, and an ultrafilter can contain all of those instead. What fails on an infinite electorate is the step that turned a decisive chain into a decisive voter — the intersection of infinitely many decisive sets need not be decisive, because the third law speaks only of finitely many. Kirman and Sondermann called the result an invisible dictator: a point that every decisive set approaches but which is not a voter, a member of the Stone–Čech compactification of the electorate rather than of the electorate itself.

An ultrafilter containing no finite set is called free, and on an infinite electorate a rule is non-dictatorial exactly when its ultrafilter is free.

A rule built from an ultrafilter #

The converse direction is a construction, and a short one. Fix an ultrafilter $U$ on the voters. Given a profile, declare A above B in the society’s ranking when the set of voters ranking A above B belongs to $U$.

The four properties follow from the four laws. The set preferring A to B and the set preferring B to A are complements, so exactly one is in $U$ and every pair is decided one way. If the sets preferring A to B and B to C are both in $U$, their common part is in $U$, and every voter in it prefers A to C by their own transitivity, so the set preferring A to C contains a member of $U$ and is in $U$: the output is transitive. Unanimity holds because the whole electorate is in $U$. Independence holds because the decision on A and B looks at nothing but who prefers A to B. And if $U$ is free, no single voter’s set $\{i\}$ is in it, so no voter is a dictator.

The two profiles in the figure show what such a rule does. The first is the Condorcet cycle made infinite: the voters fall into three classes by remainder mod 3, ranking A, B, C, then B, C, A, then C, A, B, and each pair is preferred by two classes of three, so a majority count would cycle. The ultrafilter holds exactly one of the three classes — the classes are disjoint and together make up everyone — and every pair is then decided as that class decides it. The rule returns one class’s ranking, and that class, in this profile, plays the dictator. Which class it is depends on $U$ and cannot be read off from anything else. The second profile is the reassuring one: five voters against all the rest, and every free ultrafilter, holding every set that misses only finitely many voters, sides with the rest. The ultrafilter at voter 3 would side with the five.

So the rule respects large majorities of a particular kind — all but finitely many — and is indifferent to every finite group, however large. Between those extremes, on sets that are infinite with infinite complements, it decides, and the decisions it makes on those sets are what nobody can describe. How few voters any majority needs measured how small a winning coalition can be on a finite electorate; here every winning coalition can be made thinner indefinitely, by splitting it and keeping the half the ultrafilter holds.

Nobody can say which half #

Every infinite set carries a free ultrafilter, and the proof is the ultrafilter lemma: start with the sets that miss only finitely many voters, which satisfy the laws except the first, and extend that collection to a maximal one by Zorn’s lemma, exactly as a spanning tree for every graph extended forests to a maximal one. The extension makes, all at once, a decision on every one of the uncountably many sets of voters that are infinite with infinite complements.

For the ultrafilter at voter 37 every entry of the table is computable: 37 is odd, prime and a multiple of 37, so it holds the odd voters, the primes and the multiples of 37. For a free ultrafilter the table can be filled in only on finite and cofinite sets. On the even voters it must say yes or no, and either answer is consistent with everything else that has been decided — any finite list of such decisions can be made one at a time, each choosing a side that meets every earlier choice in an infinite set, just as the guessers in infinitely many guessers, finitely many wrong chose a representative of each class of sequences. What cannot be done by any finite procedure is make all of the decisions at once.

This is not a gap in ingenuity. It is a theorem. Solomon Feferman showed in 1965 that it is consistent with the axioms of set theory without choice that no free ultrafilter on the whole numbers exists. In such a model, Arrow’s theorem holds for the countable electorate as well: every rule with his properties is a dictatorship, because every ultrafilter is principal. In the usual mathematics, with choice, it fails. The theorem is therefore not decided by the axioms of set theory without some choice, and the existence of a non-dictatorial Arrovian rule on a countable electorate turns out to be exactly equivalent to the existence of a free ultrafilter on the whole numbers — a principle strictly weaker than the full axiom, and one of the weak choices of the kind that the choice inside a countable union found holding up the theory of length. The connection with length is direct: Wacław Sierpiński showed in 1938 that a free ultrafilter, read as a set of infinite binary sequences, is a set of reals that has no length at all.

There is a computational echo. Ryo Mihara showed in 1997 that if the rule is required to be computable in a natural sense — a machine that, given enough of a profile, eventually announces the outcome on each pair — then the infinite electorate is no help and the rule must again be dictatorial. The non-dictatorial rules exist only as the kind of object a proof by Zorn’s lemma produces: certified to exist, impossible to evaluate.

What the infinite case says about the finite one #

It would be easy to read the infinite rules as a loophole that rescues democracy from Arrow, and every author who has written about them has warned against that reading. A free-ultrafilter rule is not a fair rule in any sense a voter would recognise. Every finite set of voters, however numerous, is powerless. The decisive coalitions in the cyclic profile are a third of the electorate by any count of the first million voters, and a different third under a different ultrafilter. Like the discontinuous additive functions met earlier, the rules are a demonstration that a theorem’s hypothesis was doing real work, not an alternative to the theorem.

What the infinite case does clarify is the shape of the finite impossibility. On a finite electorate every ultrafilter is principal, and so the four conditions — which together say exactly “the decisive sets form an ultrafilter” — leave room only for a dictator. Arrow’s theorem is the statement that a finite set has no free ultrafilters, a fact so simple it hardly feels like a theorem, dressed in the language of ballots. The exhaustive counts at the start are the same fact seen from below: 262,144 candidate rules, of which the survivors are the three principal ultrafilters on a three-voter electorate.

Read that way, the result also says where to look for escapes on finite electorates. The ones that work give up a condition. Majority voting with a restricted domain gives up the universality of profiles, and a majority wiser than its members showed what it gains when the voters are trying to find a fact rather than express a taste. Scoring rules give up independence, which is the condition that makes the decisive sets meaningful at all; how often the rules find the majority favourite measured what that costs. None of them gives up finiteness, because no actual electorate can.

Still open: how much choice the infinite electorate needs #

The equivalence between non-dictatorial Arrovian rules and free ultrafilters is for a countable electorate and a set of three or more candidates. Other versions of the question are less settled. With uncountably many voters, or with infinitely many candidates, or with rules required only to produce a preorder rather than a strict ranking, the corresponding decisive structures are filters of various kinds, and where the existence of each such rule sits among the weak forms of the axiom of choice is mapped only in part. The principle that every infinite set carries a free ultrafilter is implied by the Boolean prime ideal theorem and is known to be strictly weaker than full choice, but its exact position among the hundreds of principles that Howard and Rubin catalogued, and that of its social-choice versions, has unresolved cells.

A second question is about measurement. Since every free ultrafilter is non-measurable, no probability distribution over the voters can make a free-ultrafilter rule’s coalitions “large” in a way that a sampling procedure could detect. Whether a weakened Arrow theorem holds for rules that are required to be measurable in some sense — rules a statistician could at least approximate — has been answered for particular notions of measurability and not for all, and the boundary between the rules that can be approximated and the rules that can only be proved to exist is still being drawn.