Arrow’s Impossibility Theorem
by Willie Wong
Partially prompted by Terry’s buzz, I decided to take a look at Arrow’s Impossibility Theorem. The name I have heard before, since I participated in CollegeBowl as an undergraduate, and questions about Arrow’s theorem are perennial favourites. The theorem’s most famous interpretation is in voting theory:
- Given a set of electors and a finite set of candidates , a preference assigns to each elector an ordering of the set . In particular, we can write for the statement “the elector prefers candidate to candidate “. The set of all possible preferences is denoted .
- A voting system assigns to each preference an ordering of the set .
- Given a preference and two candidates , a bloc biased toward is defined as the subset
- The voting system is said to be
- unanimous if, whenever all electors prefer candidate to , the voting system will return as such. In other words, ““.
- independent if the voting results comparing candidates and only depend on the individual preferences between them. In particular, whether only depends on . An independent system is said to be monotonic if, in addition, a strictly larger biased bloc will give the same voting result: if and , then necessarily.
- dictator-free if there isn’t one elector whose vote always coincides with the end-result. In other words, we define a dictator to be an elector such that for any .
- A voting system is said to be fair if it is unanimous, independent and monotonic, and has no dictators.
And the theorem states
Arrow’s Impossibility Theorem
In an election consisting of a finite set of electors with at least three candidates , there can be no fair voting system.
As we shall see, finiteness of the set of electors and the lower-bound on the number of candidates are crucial. In the case where there are only two candidates, the simple-majority test is a fair voting system. (Finiteness is more subtle.) It is also easy to see that if we allow dictators, i.e. force the voting results to align with the preference of a particular predetermined individual, then unanimity, independence, and monotonicity are all trivially satisfied.
What’s wrong with the simple majority test in more than three candidates? The problem is that it is not, by definition, a proper voting system: it can create loops! Imagine we have three electors and three candidates . The simple majority test says that if and only if two or more of the electors prefer to . But this causes a problem in the following scenario:
then the voting result will have , , and , a circular situation which implies that the “result” is not an ordering of the candidates! (An ordering of the set requires the comparisons to be transitive.) So the simple-majority test is, in fact, not a valid voting system.
From this first example, we see already that, in the situation of more than 2 candidates, designing a voting system is a non-trivial problem. Making them fair, as we shall see, will be impossible.
(So why am I writing this proof down? Mostly for my own benefit. I took a quick search on the internet, and most of the proofs I found are either obscured by the language, or redundant in the mathematics. And some are just simply wrong. Here I hope to give a self-contained proof that is driven by some ideas used in non-standard analysis.)
Proof of Arrow’s Theorem
We need a bit more definitions.
Given an independent voting system , a forcing coalition for candidate over is a subset of electors such that, whenever the bloc contains the coalition as a subset, the vote is in favour of : . We write for the collection of all forcing coalitions preferring to , and we write for the collection of all dominant coalitions, coalitions that can influence the election anyway they wish.
We notice first that if the singleton set is a dominant coalition by itself, then is, by definition, a dictator. We have the following properties of the collection of dominant coalitions
- If the voting system is unanimous, then the entire population is a dominant coalition.
- Any superset of a dominant coalition is another dominant coalition. In other words, if is in , and , then .
- If there are at least three candidates, any intersection between two dominant coalitions is another dominant coalition. In other words, implies .
- Two disjoint subsets , cannot both be dominant.
- If the voting system is monotonic, then for any such that , the bloc is a forcing coalition for over .
Proof. (1) is obvious by the definition of a unanimous voting system. (2) follows from the definition: if , it must also contain since . Since is dominant, must be now forcing for over . Since this holds for any , is dominant. (4) follows from the following observation: let be a preference such that and . If both are forcing, then we have a contradiction. (5) follows from a simple application of the monotonicity property. It remains to show claim (3).
To do (3), fix to be dominant coalitions. Let denote their intersection. Fix arbitrary candidates. Let be a preference such that . Now we construct a preference from as follows: since we have at least three candidates, fix an arbitrary third candidate . For an elector , we choose some ordering of such that . This can be obtained, for example, by shifting down the chain of relations if , or up the chain if . For an elector , we shift the position of to the bottom: so anything else is preferable to , while keeping the order of the remaining candidates the same. For an elector in , we shift the position of all the way to the top: so it is preferred to anything else, while keeping the order of the remaining candidates the same. For all other electors we do not change the preference. Since the construction only involve finitely-many pairwise swaps in the ordering, is still a preference. It has the following properties
, , and
Since are dominant, this implies that . Since the voting system is independent, we must also have . Therefore is forcing for over . Since the choice of candidates was arbitrary, this implies that is dominant. Q.E.D.
The properties given by points 1,2, and 3 of the proposition implies that the collection of dominant coalitions form what is known as a filter in mathematical analysis.
The following lemma is what drives the final step of the proof:
In a unanimous, independent, and monotonic voting system with at least three candidates, the collection has the dichotomy property: given an arbitrary subset , then either or . As a consequence, when the number of electors is finite, there must be a dictator.
Proof. For any fixed , we can choose such that . So by the law of excluded middle, . Therefore by property (5) of the previous proposition, either or . Without loss of generality, we assume that . Next we show that for , . If , the result follows trivially. So we assume that there are at least three candidates and . Fix some preference such that . Define by modifying the following way: outside of , shift to the bottom of the preference. In , shift so that . Then , so since is forcing, we have . By unanimity, we also have that , so . Since , by independence we have that . Symmetrising the argument (n.b. in showing that for , we didn’t need that there are three or more candidates; it is in the symmetrisation here that we strictly require three candidates) we conclude that if , then for any we must have , hence . And the first statement follows.
The statement about dictatorship follows by applying the pigeonhole principle. Pick some elector . If some other elector is a dictator, then we are done. So we can assume that all other electors are not dictators, and hence for any . By the first half of our lemma, are all in for any . Taking the finite intersection of all those sets we have that . And hence is a dictator. Q.E.D.
From the lemma and the proposition, Arrow’s theorem follows.
The dichotomy property is one of several equivalent ways one can use to characterize what is known as a ultrafilter.
It is perhaps important to note where each condition in the statement of the theorem is used. A quick run-down maybe the following:
- Unanimity + independence + more than three electors: the collection of dominant coalitions becomes a filter.
- Unanimity + independence + more than three electors + monotonicity: is an untrafilter.
- is a filter on a finite set : is a principal filter, and contains a smallest element.
A principal ultrafilter on is generated by a single element, and so there exists a dictator.