Arrow's impossibility theorem establishes, all fair voting systems are a dictatorship. My initial investigation led me to believe Arrow's claim was misleading. However, upon attempting to design a colloquially "fair" Arrow dictatorship, I discovered the condition to be much stronger than expected. This essay delves into Arrow's dictatorship condition, and proves all fair dictatorships must arbitrarily chose a dictator. As far as I know (08/07/2023), the proof is original.

Introduction

Impossibility theorems are peculiar. While most of modeling deals with what may happen, they deal with what may not. Incredibly, many impossibility theorems are highly applicable. For example, light moves at the speed limit of the universe, fault-tolerant distributed consensus is impossible, and clocks can sometimes be synchronized.

Arrow's Impossibility Theorem is peculiar among impossibility theorems. In inexact terms: no ranked-choice voting system can be fair, and a non-dictatorship.

My first reaction was one of incredulity. Arrow's Impossibility Theorem is trivially false; ranked-choice voting is used by many non-dictatorships. For example, Portland, OR will be using single-transferable-vote, ranked-choice voting, starting November 2024.

The reason for this confusion is, Arrow does not use the colloquial meaning of dictatorship. By Arrow's construction, an individual is a dictator if all their preferences are satisfied. Thus, vacuously, someone ranking all options equally is a dictator.

Upon discovering this, I felt vindicated, and wrote an essay about it; Titled Always A Happy Voter, with the abstract:

Hubris.

In actuality, Arrow's theorem is quite applicable. This essay delves into why non-dictatorship is a stronger condition than it appeared to me.

What Is A Voting System?

We are presented with a set of voters $v \in V$, and a set of at least three options. During an election, each voter $v$ turns in a ballot $b_v$; which is a relation ordering the options according to their preferences. Let $B$ denote a matrix containing all ballots.

The job of a voting system is to take $B$, and produce a single ordering of options, which reflects the will of voters. Let $\succ$ denote the voting system's ordering. If all voters prefer $x$ to $y$ to $z$, then $\succ$ should satisfy $x \succ y \succ z$. Lets call the requirement, if all voters prefer $x$ to $y$; then $x \succ y$, unanimity.

What other requirements do we have for $\succ$ to be fair? Lets require $\succ$ be non-circular, and adding or removing options not impact the rankings of unrelated ones.

1. Transitivity: If $x \succ y$ and $y \succ z$, then $x \succ z$. Circular orderings where rock beats scissors, beats paper, beats rock, are not allowed.
2. Independence of Irrelevant Alternatives (IIA): For unique candidates $x$, $y$, and $z$; if $z$ is removed from the set of options, $x \succ y$ does not change.

We say a voting system is fair if it satisfies unanimity , transitivity , and IIA. These requirements are relatively sparse, and one may prefer to add more. Though, they are all we need: Arrow's impossibility theorem shows all fair voting systems are dictatorships. For an excellent proof of this, see John Geanakoplos's paper Three Brief Proofs of Arrow's Impossibility Theorem.

The Perfectly Fair Dictatorship

Imagine a voting system which picks a dictator at random and uses their ballot: $\succ = \text{random}(b_v \in B)$.

1. If all voters prefer $x$ to $y$, any random voter prefers $x$ to $y$, thus unanimity is satisfied.
2. No $b_v$ contains a cycle by construction, thus transitivity is satisfied.
3. Removing an option has no impact on which ballot is selected, thus IIA is satisfied.

While fair, this voting system does little to express the collective will of voters. Can we do better than arbitrarily selecting a dictator?

We Can't Do Better

Here's an idea: instead of selecting a dictator at random, select a dictator who's preferences are very close to the popular will. For example, say we used a popular form of ranked-choice voting to determine an ordering, then selected the ballot "closest" to that ordering as dictator. I believe it is impossible for a fair voting system to do this. This section provides an attempt at a proof.

Let $2^B$ denote the set containing all permutations of $B$ with one or more option removed. Let $f: B \mapsto \succ$ denote a voting system which maps $B$ (a matrix of ballots) to an ordering, $\succ$. Let $o: B \mapsto O$ be a function which yields the set of options being considered in a ballot matrix.

I derive a contradiction.

1. To be a dictatorship, $f$ must satisfy $\exists b_v \in B: b_v = f(B)$.

   This follows from the definition of dictatorship, as a voter's ballot must be selected as the social choice function.

2. To satisfy IIA, $\forall (B, B') \in 2^B: \{x, y\} \in o(B) \cap o(B') \implies x f(B) y = x f(B') y$.

   This follows from the definition of IIA, as the ranking of two options must be independent of the other options being considered.

3. $f$ must satisfy $\forall B' \in 2^B: f(B') \subseteq b_v = f(B)$.

   Per (2), options must be ranked the same regardless of the set of options being considered. Thus, per (1) the same dictator's ballot must be selected regardless of what options are considered.

4. $f$ is not a function of the ballots inputted.

   Let $O_1 = o(B)$. Now, let $O_2$ represent a set of options disjoint from $O_1$, and $B'$ a ballot matrix such that $O_1 \cup O_2 = o(B')$ and $B \subseteq 2^{B'}$. Per (3), the same dictator must be selected for all subsets of $2^{B'}$. Let $B_1 \in 2^{B'}$ and $B_2 \in 2^{B'}$ be ballot matrices such that $o(B_1) \subseteq O_1$ and $o(B_2) \subseteq O_2$. Per (3), $f(B_1)$ and $f(B_2)$ must select the same dictator. As $B_1$ and $B_2$ have no overlap, $f$ cannot be a function of the ballot matrix inputted.

Thus, it is impossible to select the dictator as a function of the ballots, and satisfy IIA. Putting this together with Arrow's impossibility theorem: All fair voting systems must select a dictator arbitrarily.