# §2.5: Highlight: Arrow’s Theorem

When there are just $2$ candidates, the majority function possesses all of the mathematical properties that seem desirable in a voting rule (e.g., May’s Theorem and Theorem 32). Unfortunately, as soon as there are $3$ (or more) candidates the problem of social choice becomes much more difficult. For example, suppose we have candidates $a$, $b$, and $c$, and each of $n$ voters has a ranking of them. How should we aggregate these preferences to produce a winning candidate?

In his 1785 Essay on the Application of Analysis to the Probability of Majority Decisions [dC85], Condorcet suggested using the voters’ preferences to conduct the three possible pairwise elections, $a$ vs. $b$, $b$ vs. $c$, and $c$ vs. $a$. This calls for the use of a $2$-candidate voting rule $f : \{-1,1\}^n \to \{-1,1\}$; Condorcet suggested $f = \mathrm{Maj}_n$ but we might consider any such rule. Thus a “$3$-candidate Condorcet election” using $f$ is conducted as follows:

election \ voter #1 #2 #3 societal
aggregation
$a$ ($+1$) vs. $b$ ($-1$) $+1$ $+1$ $-1$ $= x$ $f(x)$
$b$ ($+1$) vs. $c$ ($-1$) $+1$ $-1$ $+1$ $= y$ $f(y)$
$c$ ($+1$) vs. $a$ ($-1$) $-1$ $-1$ $+1$ $= z$ $f(z)$

In the above example, voter $\#1$ ranked the candidates $a > b > c$, voter $\#2$ ranked them $a > c > b$, voter $\#3$ ranked them $b > c > a$, etc. Note that the $i$th voter has one of $3! = 6$ possible rankings, and these translate into a triple of bits $(x_i, y_i, z_i)$ from the following set: $\Bigl\{(+1, +1, -1), (+1, -1, -1), (-1,+1,-1), (-1,+1,+1), (+1,-1,+1), (-1, -1, +1)\Bigr\}.$ These are precisely the triples satisfying the not-all-equal predicate $\mathrm{NAE}_3$.

In the example above, if $n = 3$ and $f = \mathrm{Maj}_3$ then the societal outcome would be $(+1,+1,-1)$, meaning that society elects $a$ over $b$, $b$ over $c$, and $a$ over $c$. In this case it is only natural to declare $a$ the overall winner.

Definition 54 In an election employing Condorcet’s method with $f : \{-1,1\}^n \to \{-1,1\}$, we say that a candidate is a Condorcet winner if it wins all of the pairwise elections in which it participates.

Unfortunately, as Condorcet himself noted, there may not be a Condorcet winner. In the example above, if voter $1$’s ranking was instead $c > a > b$ (corresponding to $(+1, -1, +1)$), we would obtain the “paradoxical” outcome $(+1, +1, +1)$: society prefers $a$ over $b$, $b$ over $c$, and $c$ over $a$! This lack of a Condorcet winner is termed Condorcet’s paradox; it occurs when the outcome $(f(x), f(y), f(z))$ is one of the two “all-equal” triples $\{(-1, -1, -1), (+1,+1,+1)\}$. One might wonder if the Condorcet paradox can be avoided by using a voting rule $f : \{-1,1\}^n \to \{-1,1\}$ other than majority. However in 1950 Arrow [Arr50] famously showed that the only means of avoidance is an unappealing one:

Arrow’s Theorem Suppose $f : \{-1,1\}^n \to \{-1,1\}$ is a unanimous voting rule used in a $3$-candidate Condorcet election. If there is always a Condorcet winner, then $f$ must be a dictatorship.

(In fact, Arrow’s Theorem is slightly stronger than this, as will be discussed in an exercise.)

To prove Arrow’s Theorem, let’s take our cue from the title of Condorcet’s work and compute the probability of a Condorcet winner. We will do this under the “impartial culture assumption” for $3$-candidate elections: each voter independently chooses one of the $6$ possible rankings uniformly at random.

Theorem 55 Consider a $3$-candidate Condorcet election using $f : \{-1,1\}^n \to \{-1,1\}$. Under the impartial culture assumption, the probability of a Condorcet winner is precisely $\tfrac34 – \tfrac34 \mathbf{Stab}_{-1/3}[f]$.

Proof: Let ${\boldsymbol{x}}, \boldsymbol{y}, \boldsymbol{z} \in \{-1,1\}^n$ be the votes for the elections $a$ vs. $b$, $b$ vs. $c$, and $c$ vs. $a$, respectively. Under impartial culture, the bit triples $({\boldsymbol{x}}_i, \boldsymbol{y}_i, \boldsymbol{z}_i)$ are independent and each is drawn uniformly from the $6$ triples satisfying the not-all-equal predicate $\mathrm{NAE}_3 : \{-1,1\}^3 \to \{0,1\}$. There is a Condorcet winner if and only if $\mathrm{NAE}_3(f({\boldsymbol{x}}),f(\boldsymbol{y}),f(\boldsymbol{z})) = 1$. Hence \begin{equation} \label{eqn:prob-cond} \mathop{\bf Pr}[\exists \text{ Condorcet winner}] = \mathop{\bf E}[\mathrm{NAE}_3(f({\boldsymbol{x}}),f(\boldsymbol{y}),f(\boldsymbol{z}))]. \end{equation} The multilinear (Fourier) expansion of $\mathrm{NAE}_3$ is $\mathrm{NAE}_3(w_1, w_2, w_3) = \tfrac34 - \tfrac14w_1 w_2 -\tfrac14 w_1 w_3 - \tfrac14 w_2w_3;$ thus $\eqref{eqn:prob-cond} = \tfrac34 - \tfrac14\mathop{\bf E}[f({\boldsymbol{x}})f(\boldsymbol{y})] – \tfrac14\mathop{\bf E}[f({\boldsymbol{x}})f(\boldsymbol{z})]- \tfrac14\mathop{\bf E}[f(\boldsymbol{y})f(\boldsymbol{z})].$ In the joint distribution of ${\boldsymbol{x}}, \boldsymbol{y}$ the $n$ bit pairs $({\boldsymbol{x}}_i, \boldsymbol{y}_i)$ are independent. Further, by inspection we see that $\mathop{\bf E}[{\boldsymbol{x}}_i] = \mathop{\bf E}[{\boldsymbol{y}}_i] = 0$ and that $\mathop{\bf E}[{\boldsymbol{x}}_i \boldsymbol{y}_i] = (2/6)(+1) + (4/6)(-1) = -1/3$. Hence $\mathop{\bf E}[f({\boldsymbol{x}})f(\boldsymbol{y})]$ is precisely $\mathbf{Stab}_{-1/3}[f]$. Similarly $\mathop{\bf E}[f({\boldsymbol{x}})f(\boldsymbol{z})] = \mathop{\bf E}[f(\boldsymbol{y})f(\boldsymbol{z})] = \mathbf{Stab}_{-1/3}[f]$ and the proof is complete. $\Box$

Arrow’s Theorem is now an easy corollary:
Proof of Arrow’s Theorem: By assumption, the probability of a Condorcet winner is $1$; hence $1 = \tfrac34 - \tfrac34 \mathbf{Stab}_{-1/3}[f] = \frac34 – \frac34 \sum_{k=0}^n(-1/3)^{k} \mathbf{W}^{k}[f].$ Since $(-1/3)^k \geq -1/3$ for all $k$, the equality above can only occur if all of $f$’s Fourier weight is on degree $1$; i.e., $\mathbf{W}^{1}[f] = 1$. By Exercise 1.19(a) this implies that $f$ is either a dictator or a negated-dictator. Since $f$ is unanimous, it must in fact be a dictator. $\Box$

An advantage of this analytic proof of Arrow’s Theorem is that we can deduce several more interesting results about the probability of a Condorcet winner. For example, combining Theorem 55 with Theorem 44 we get Guilbaud’s formula:

Guilbaud’s Formula In a $3$-candidate Condorcet election using $\mathrm{Maj}_n$, the probability of a Condorcet winner tends to $\tfrac34 - \tfrac{3}{2\pi} \arcsin(-1/3) = \tfrac{3}{\pi}\arccos(1/\sqrt{3}) \approx 91.2\%.$ as $n \to \infty$.

This is already a fairly high probability. Unfortunately, if we want to improve on it while still using a reasonably fair election scheme, we can only set our hopes higher by a sliver:

Theorem 56 In a $3$-candidate Condorcet election using an $f : \{-1,1\}^n \to \{-1,1\}$ with all $\widehat{f}(i)$ equal, the probability of a Condorcet winner is at most $\frac79 + \frac{4}{9\pi} + o_n(1) \approx 91.9\%$.

The condition in Theorem 56 seems like it would be satisfied by most reasonably fair voting rules $f : \{-1,1\}^n \to \{-1,1\}$ (e.g., it is satisfied if $f$ is transitive-symmetric or is monotone with all influences equal). In fact, we will show that Theorem 56‘s hypothesis can be relaxed in Chapter 5; we will further show in Chapter 13 that $\frac79 + \frac{4}{9\pi}$ can be improved to the tight value $\tfrac34 – \tfrac{3}{2\pi} \arcsin(-1/3)$ of majority. To return to Theorem 56, it is an immediate consequence of the following two results, the first being an exercise (based on Theorem 32) and the second being an easy corollary of Theorem 55.

Proposition 57 Suppose $f : \{-1,1\}^n \to \{-1,1\}$ has all $\widehat{f}(i)$ equal. Then $\mathbf{W}^{1}[f] \leq 2/\pi + o_n(1)$.

Corollary 58 In a $3$-candidate Condorcet election using $f : \{-1,1\}^n \to \{-1,1\}$, the probability of a Condorcet winner is at most $\frac79 + \frac29 \mathbf{W}^{1}[f]$.

Proof: From Theorem 55, the probability is \begin{align*} \tfrac34 – \tfrac34 \mathbf{Stab}_{-1/3}[f] &= \tfrac34 – \tfrac34(\mathbf{W}^{0}[f] – \tfrac13 \mathbf{W}^{1}[f] + \tfrac19 \mathbf{W}^{2}[f] – \tfrac{1}{27} \mathbf{W}^{3}[f] + \cdots)\\ &\leq \tfrac34 + \tfrac14 \mathbf{W}^{1}[f] + \tfrac{1}{36} \mathbf{W}^{3}[f] + \tfrac{1}{324} \mathbf{W}^{5}[f] + \cdots\\ &\leq \tfrac34 + \tfrac14 \mathbf{W}^{1}[f] + \tfrac{1}{36} (\mathbf{W}^{3}[f] + \mathbf{W}^{5}[f] + \cdots)\\ &\leq \tfrac34 + \tfrac14 \mathbf{W}^{1}[f] + \tfrac{1}{36} (1 – \mathbf{W}^{1}[f]) \quad=\quad \tfrac79 + \tfrac29\mathbf{W}^{1}[f]. \quad \Box \end{align*}

Finally, using Corollary 58 we can prove a “robust” version of Arrow’s Theorem, showing that a Condorcet election is almost paradox-free only if it is almost a dictatorship.

Corollary 59 Suppose that in a $3$-candidate Condorcet election using $f : \{-1,1\}^n \to \{-1,1\}$, the probability of a Condorcet winner is $1 – \epsilon$. Then $f$ is $O(\epsilon)$-close to $\pm \chi_i$ for some $i \in [n]$.

Proof: From Corollary 58 we obtain that $\mathbf{W}^{1}[f] \geq 1 – \tfrac92 \epsilon$. The conclusion now follows from the FKN Theorem. $\Box$

Friedgut–Kalai–Naor (FKN) Theorem Suppose $f : \{-1,1\}^n \to \{-1,1\}$ has $\mathbf{W}^{1}[f] \geq 1-\delta$. Then $f$ is $O(\delta)$-close to $\pm \chi_i$ for some $i \in [n]$.

We will see the proof of the FKN Theorem in later chapter. We’ll also show in a later chapter that the $O(\delta)$ closeness can be improved to $\delta/4 + O(\delta^2 \log(2/\delta))$.

### 9 comments to §2.5: Highlight: Arrow’s Theorem

• Dave Pritchard

Awesome! Here is a typo I found: “In the joint distribution of x,y the n bits pairs (xi,yi) are independent.”

• Ryan O'Donnell

Thanks!

• Dave Pritchard

I have one other question. Taking elections that respect IIA and then viewing them as boolean functions in this way seems to be a great insight. Are there versions where we quantitatively relax IIA? (A survey-esque post of Nisan in the same vein also seemed to mention only strict IIA.)

• Ryan O'Donnell

Hi David — not that I personally know of, but I wouldn’t doubt it; there’s tons of literature on this with which I’m not so familiar.

• Diodato Ferraioli

just after definition 54 you say “if voter 2’s ranking was instead b>c>a (corresponding to (−1,+1,+1)), we would obtain the “paradoxical” outcome (−1,−1,−1)”. It seems wrong. Would it be right to say “if voter 1’s ranking was instead b>a>c (corresponding to (−1,+1,-1)), we would obtain the “paradoxical” outcome (−1,−1,−1)”?

At the next line there is also a typo: “two “all-equal” triples {(−1,−1,1),(+1,+1,+1)}” instead of “two “all-equal” triples {(−1,−1,-1),(+1,+1,+1)}”

• Ryan O'Donnell

Fixed both, thanks!

• John Engbers

Just after definition 54, you wrote:

we would obtain the “paradoxical” outcome (−1,−1,−1): society prefers a over b, b over c, and c over a

This should be:
…society prefers b over a, c over b, and a over c

• John Engbers

In the first line to the proof of Theorem 2.56, there should be a space between vs. and $c$ in `$b$ vs.$c$’

• Ryan O'Donnell

Thanks! I think I fixed these.