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:

Some definitions

  1. Given a set of electors E and a finite set of candidates C, a preference \pi assigns to each elector e \in E an ordering of the set C. In particular, we can write \pi_e(c_1) > \pi_e(c_2) for the statement “the elector e prefers candidate c_1 to candidate c_2“. The set of all possible preferences is denoted \Pi.
  2. A voting system v assigns to each preference \pi\in\Pi an ordering of the set C.
  3. Given a preference \pi and two candidates c_1,c_2, a bloc biased toward c_1 is defined as the subset b(\pi,c_1,c_2) := \{ e\in E | \pi_e(c_1) > \pi_e(c_2) \}
  4. The voting system is said to be
    1. unanimous if, whenever all electors prefer candidate c_1 to c_2, the voting system will return as such. In other words, “\pi_e(c_1) > \pi_e(c_2) \forall e\in E \implies v(\pi,c_1) > v(\pi,c_2)“.
    2. independent if the voting results comparing candidates c_1 and c_2 only depend on the individual preferences between them. In particular, whether v(\pi,c_1) > v(\pi,c_2) only depends on b(\pi,c_1,c_2). An independent system is said to be monotonic if, in addition, a strictly larger biased bloc will give the same voting result: if v(\pi,c_1) > v(\pi,c_2) and b(\pi,c_1,c_2) \subset b(\pi',c_1,c_2), then v(\pi',c_1) > v(\pi',c_2) necessarily.
    3. dictator-free if there isn’t one elector e_0\in E whose vote always coincides with the end-result. In other words, we define a dictator to be an elector e_0 such that v(\pi,c_1) > v(\pi,c_2) \iff \pi_{e_0}(c_1) > \pi_{e_0}(c_2) for any \pi\in \Pi, c_1,c_2\in C.
  5. 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 E with at least three candidates C, 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 e_1, e_2, e_3 and three candidates c_1,c_2,c_3. The simple majority test says that v(\pi,c_1) > v(\pi,c_2) if and only if two or more of the electors prefer c_1 to c_2. But this causes a problem in the following scenario:

e_1: c_1 > c_2 > c_3
e_2: c_2 > c_3 > c_1
e_3: c_3 > c_1 > c_2

then the voting result will have v(c_1) > v(c_2), v(c_2) > v(c_3), and v(c_3) > v(c_1), 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.

Definition
Given an independent voting system v, a forcing coalition for candidate c_1 over c_2 is a subset X\subset E of electors such that, whenever the bloc b(\pi,c_1,c_2) contains the coalition as a subset, the vote is in favour of c_1: b(\pi,c_1,c_2) \supset X \implies v(\pi,c_1) > v(\pi,c_2). We write F_{c_1,c_2} for the collection of all forcing coalitions preferring c_1 to c_2, and we write F := \cap_{c_1 \neq c_2} F_{c_1,c_2} for the collection of all dominant coalitions, coalitions that can influence the election anyway they wish.

We notice first that if the singleton set \{e_0\} is a dominant coalition by itself, then e_0 is, by definition, a dictator. We have the following properties of the collection of dominant coalitions F

Proposition

  1. If the voting system is unanimous, then the entire population E is a dominant coalition.
  2. Any superset of a dominant coalition is another dominant coalition. In other words, if X\subset E is in F, and Y \supset X, then Y\in F.
  3. If there are at least three candidates, any intersection between two dominant coalitions is another dominant coalition. In other words, X,Y\in F implies X\cap Y \in F.
  4. Two disjoint subsets X,Y\subset E, X\cap Y = \emptyset cannot both be dominant.
  5. If the voting system is monotonic, then for any \pi such that v(\pi,c_1) > v(\pi,c_2), the bloc b(\pi,c_1,c_2) is a forcing coalition for c_1 over c_2.

Proof. (1) is obvious by the definition of a unanimous voting system. (2) follows from the definition: if b(\pi,c_1,c_2) \supset Y, it must also contain X since X\subset Y. Since X is dominant, Y must be now forcing for c_1 over c_2. Since this holds for any c_1,c_2, Y is dominant. (4) follows from the following observation: let \pi\in \Pi be a preference such that X\subset b(\pi,c_1,c_2) and Y\subset b(\pi,c_2,c_1). If both X,Y 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 X,Y to be dominant coalitions. Let Z denote their intersection. Fix c_1,c_2 arbitrary candidates. Let \pi be a preference such that Z\subset b(\pi,c_1,c_2). Now we construct a preference \pi' from \pi as follows: since we have at least three candidates, fix an arbitrary third candidate c_3. For an elector e\in Z, we choose some ordering of C such that \pi'_e(c_1) > \pi'_e(c_3) > \pi'_e(c_2). This can be obtained, for example, by shifting c_3 down the chain of relations if \pi_e(c_3) > \pi_e(c_1), or up the chain if \pi_e(c_2) > \pi_e(c_3). For an elector e \in X\setminus Z, we shift the position of c_3 to the bottom: so anything else is preferable to c_3, while keeping the order of the remaining candidates the same. For an elector in Y\setminus Z, we shift the position of c_3 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, \pi' is still a preference. It has the following properties

X \subset b(\pi',c_1,c_3), Y\subset b(\pi',c_3,c_2), and b(\pi,c_1,c_2) = b(\pi',c_1,c_2)

Since X,Y are dominant, this implies that v(\pi',c_1) > v(\pi',c_3) > v(\pi',c_2). Since the voting system is independent, we must also have v(\pi,c_1) > v(\pi,c_2). Therefore Z is forcing for c_1 over c_2. Since the choice of candidates was arbitrary, this implies that Z is dominant. Q.E.D.

Remark
The properties given by points 1,2, and 3 of the proposition implies that the collection F 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:

Lemma
In a unanimous, independent, and monotonic voting system with at least three candidates, the collection F has the dichotomy property: given an arbitrary subset X\subset E, then either X\in F or E\setminus X\in F. As a consequence, when the number of electors is finite, there must be a dictator.

Proof. For any fixed c_1,c_2, we can choose \pi such that X = b(\pi,c_1,c_2). So by the law of excluded middle, E\setminus X = b(\pi,c_2,c_1). Therefore by property (5) of the previous proposition, either X \in F_{c_1,c_2} or E\setminus X \in F_{c_2,c_1}. Without loss of generality, we assume that X\in F_{c_1,c_2}. Next we show that for c_3\neq c_2, X\in F_{c_3,c_2}. If c_3 = c_1, the result follows trivially. So we assume that there are at least three candidates and c_3 \neq c_1. Fix \tilde{\pi} some preference such that b(\tilde{\pi},c_3,c_2) \supset X. Define \pi' by modifying \tilde{\pi} the following way: outside of X, shift c_1 to the bottom of the preference. In X, shift c_1 so that \pi'_e(c_3) > \pi'_e(c_1) > \pi'_e(c_2). Then b(\pi',c_1,c_2) \supset X, so since X is forcing, we have v(\pi',c_1) > v(\pi',c_2). By unanimity, we also have that v(\pi',c_3) > v(\pi',c_1), so v(\pi',c_3) > v(\pi',c_2). Since b(\tilde{\pi},c_3,c_2) = b(\pi',c_3,c_2), by independence we have that v(\tilde{\pi},c_3) > v(\tilde{\pi},c_2). Symmetrising the argument (n.b. in showing that F_{c_1,c_2} = F_{c_3,c_2} for c_1\neq c_2 \neq c_3, 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 X\in F_{c_1,c_2}, then for any c_3\neq c_4 we must have X\in F_{c_3,c_4}, hence X\in F. And the first statement follows.

The statement about dictatorship follows by applying the pigeonhole principle. Pick some elector e_0. If some other elector e' is a dictator, then we are done. So we can assume that all other electors are not dictators, and hence \{e'\} \not\in F for any e' \neq e_0. By the first half of our lemma, E\setminus \{e'\} are all in F for any e' \neq e_0. Taking the finite intersection of all those sets we have that \{e_0\} = \cap_{e'\neq e_0} E\setminus \{e'\} \in F. And hence e_0 is a dictator. Q.E.D.

From the lemma and the proposition, Arrow’s theorem follows.

Remark
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 F becomes a filter.
  • Unanimity + independence + more than three electors + monotonicity: F is an untrafilter.
  • F is a filter on a finite set E: F is a principal filter, and contains a smallest element.

A principal ultrafilter on E is generated by a single element, and so there exists a dictator.