### Arrow’s Impossibility Theorem

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.