§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
$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

Leave a Reply




You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>