Kalai’s proof of Arrow’s theorem - Analysis of Boolean Functions

3 Kalai’s proof of Arrow’s theorem

Definition 3.1 (Ranking, vote, voting rule, restriction). Let $A = {A_{1}, \dots, A_{k}}$ be a set of candidates. A ranking of $A$ is a total order on $A$ .

Let $R_{A}$ be the set of all rankings of $A$ . A vote with $n$ voters and candidate set $A$ is an element of $R_{A}^{n}$ .

A voting rule is a function $f : R_{A}^{n} \to R_{A}$ .

If $B \subset A$ , then the restriction of a vote on $A$ to $B$ is the element $v$ of $R_{B}^{n}$ where each $v_{i}$ is the restriction of the $i$ -th voter’s ranking of $A$ .

Theorem 3.2 (Arrow’s Theorem). If $| A | \geq 3$ , then there is no voting rule with the following three properties:

(1) Weak monotonicity: If every voter prefers $A_{i}$ to $A_{j}$ , then $A_{i}$ beats $A_{j}$ .
(2) No dictators: There is no $i$ such that the outcome is determined by the $i$ -th vote.
(3) Irrelevant alternatives have no effect: The restriction of the result to a subset $B$ only on the restriction of the vote to $B$ .

Note that in particular, property (3) implies that for any two candidates $A_{i}, A_{j}$ , their eventual relative ranking depends only on their relative rankings by each voter. So if we encode the relative rankings by $x \in {- 1, 1}^{n}$ where

x_{r} = {\begin{matrix} 1 & r prefers A_{i} to A_{j} \\ 0 & r prefers A_{j} to A_{i} \end{matrix}

Then the relative ranking in the outcome is given by a Boolean function $u_{i j} : {- 1, 1}^{n} \to {- 1, 1}$ .

If we calculate all these pairwise rankings, then they must lead to a total order (defining $A_{i} > A_{j}$ if $A_{i}$ is ranked above $A_{j}$ ), i.e. we don’t have a Condorcet paradox, where voters prefer $A_{i}$ to $A_{j}$ , $A_{j}$ to $A_{k}$ and $A_{k}$ to $A_{i}$ . So to prove Arrow’s Theorem, it will be enough to show that such an incompatibility must happen.

Lemma 3.3. Let $f : {- 1, 1}^{n} \to {- 1, 1}$ be a linear function (i.e. of degree $1$ ), with $\hat{f} (\emptyset) = 0$ . Then there exists $i$ such that $\forall x, f (x) = x$ or $\forall x, f (x) = - x$ .

Proof. If $f$ takes values in ${- 1, 1}$ , then changing $x_{i}$ changes $f$ by $- 2$ , $0$ or $2$ . Since $f$ is linear, it has a formula of the form $f (x) = \sum_{i} a_{i} x_{i}$ . Therefore, each $a_{i}$ belongs to ${- 1, 0, 1}$ . At least one $a_{i}$ is non-zero. If $a_{i}$ and $a_{j}$ are non-zero, $i \neq j$ , then $a_{i} x_{i} + a_{j} x_{j}$ takes at least three distinct values, contradiction. □

Example. This is an example to show that the “Irrelevant alternatives have no effect” property is hard to satisfy.

With three voters, a natural way to set up the voting system is to say that candidates award 2 points to their favourite, 1 point to their second favourite, and no points to the least favourite. Suppose that $33$ people vote $A > B > C$ , $33$ vote $C > A > B$ and $34$ vote $B > C > A$ . Then one can check that $B$ ends up higher than $A$ if we run the voting system described above. But if we change the $C > A > B$ voters to $A > C > B$ , then we would get that $A$ scores higher than $B$ , which shows that this voting system does not have the “Irrelevant alternatives have no effect” property.

Given some pairwise rankings, we say that there is a Condorcet winner if they form a transitive relation (i.e., they induce a total ordering).

Remark. If there is always a Condorcet winner, then necessarily $u = v = w$ . To see this, let $x \in {- 1, 1}^{n}$ be arbitrary, let $y = - x$ , and let $z = (u (x), u (x), \dots, u (x))$ . Since $y = - x$ , this is a valid vote (i.e. $(x, y, z) \in X$ ). The outcome is $(u (x), v (- x), u (x))$ (where $w (z) = u (x)$ by weak monotonicity). For this to be a valid ranking, we must have $v (- x) = - u (x)$ . That is true for all $x$ . By symmetry, we also have $v (- x) = - w (x)$ for all $x$ , so $u (x) = w (x)$ , so by symmetry $u = v = w$ .

Proof of Arrow’s Theorem. Suppose we have three candidates $A$ , $B$ , $C$ and $n$ voters. Encode a vote as a sequence $(x, y, z) \in {- 1, 1}^{3 n}$ where for each $i$ , $x_{i} = 1$ if and only if voter $i$ prefers $A$ to $B$ , $y_{i} = 1$ if and only if voter $i$ prefers $B$ to $C$ , and $z_{i} = 1$ if and only if voter $i$ prefers $C$ to $A$ .

For this to be a vote, $(x_{i}, y_{i}, z_{i}) \in {- 1, 1}^{3} ∖ {(1, 1, 1), (- 1, - 1, - 1)}$ . Let $X$ be the set of all such $(x, y, z)$ . A voting rule is then a function $f : X \to {- 1, 1}^{n} ∖ {(1, 1, 1), (- 1, - 1, - 1)}$ . If axiom 3 holds (“Irrelevant alternatives have no effect”), then we can write $f (x, y, z) = (u (x), v (y), w (z))$ for three Boolean functions $u, v, w : {- 1, 1}^{n} \to {- 1, 1}$ .

Let us assume that $u = v = w$ , as shown in the above Remark. Then we have a Condorcet winner if and only if for every $(x, y, z)$ , it is not the case that $u (x) = u (y) = u (z)$ . But $u (x) = u (y) = u (z)$ is false if and only if $u (x) u (y) + u (y) u (z) + u (z) u (x) = - 1$ . So if there is always a Condorcet winner, then

𝔼_{(x, y, z) \in X} (u (x) u (y) + u (y) u (z) + u (z) u (x)) = - 1,

so $𝔼_{(x, y, z) \in X} u (x) u (y) = - \frac{1}{3}$ .

If we choose $(x, y, z)$ uniformly from $X$ , then $x$ is uniform in ${- 1, 1}^{n}$ . Having picked $x$ , the possibilities for $(y_{i}, z_{i})$ are $(- x_{i}, x_{i})$ , $(x_{i}, - x_{i})$ and $(- x_{i}, - x_{i})$ with all three equally likely. So $y_{i} = x_{i}$ with probability $\frac{1}{3} = \frac{1 + (- \frac{1}{3})}{2}$ . Therefore,

𝔼_{(x, y, z) \in X} u (x) u (y) = {Stab}_{- \frac{1}{3}} u .

We can conclude that ${Stab}_{- \frac{1}{3}} u = - \frac{1}{3}$ . By the Fourier formula for $Stab$ , it follows that

\sum_{A} {(- \frac{1}{3})}^{| A |} \hat{u} {(A)}^{2} = - \frac{1}{3} .

By Parseval, $\sum_{A} \hat{u} {(A)}^{2} = 1$ . It follows that $\hat{u} {(A)}^{2} = 0$ when $| A | \neq 1$ , or in other words that $u$ is linear (with zero constant term). By Lemma 3.3, $u$ is a dictator, violating axiom 2. □

We will show that if we relax the above theorem to consider voting rules where with probability $𝜀$ we fail to give a Condorcet winner, then there is an “almost dictator” (someone who determines the vote most of the time).

Note that if $p = ℙ (Condorcet winner)$ , then

𝔼_{(x, y, z) \in X} (u (x) u (y) + u (y) u (z) + u (z) u (x)) = - p + 3 (1 - p) = 3 - 4 p .

So $3 {Stab}_{- \frac{1}{3}} u = 3 - 4 p$ , so $p = \frac{3}{4} (1 - {Stab}_{- \frac{1}{3}} u)$ . Therefore, if $p \geq 1 - 𝜀$ , then $1 - 𝜀 \leq \frac{3}{4} (1 - {Stab}_{- \frac{1}{3}} u)$ so ${Stab}_{- \frac{1}{3}} u \leq - \frac{1}{3} + \frac{4}{3} 𝜀$ . But writing $W_{1} (f)$ for $\sum_{| A | = 1} \hat{f} {(A)}^{2}$ ,

{Stab}_{- \frac{1}{3}} u \geq - \frac{1}{3} W_{1} (u) - \frac{1}{27} (1 - W_{1} (u)),

- \frac{1}{3} W_{1} (u) - \frac{1}{27} (1 - W_{1} (u)) \leq - \frac{1}{3} + \frac{4}{3} 𝜀 .

If $W_{1} (u) = 1 - δ$ then

- \frac{1}{3} + \frac{δ}{3} - \frac{δ}{27} \leq - \frac{1}{3} + \frac{4}{3} 𝜀,

$δ \leq \frac{9}{2} 𝜀$ , i.e. $W_{1} (u) \geq 1 - \frac{9}{2} 𝜀$ .

To show that there is an almost dictator we will need to introduce a lot more theory.