2 Arrow’s Impossibility Theorem
2.1 Overview
This chapter proves Arrow’s Impossibility Theorem via Kalai’s Fourier-analytic approach. For 3 alternatives \(\{ a,b,c\} \) and \(n\) voters, a social welfare function is modelled by an odd Boolean function \(f:\{ 0,1\} ^n\to \mathbb {R}\) applied to each pairwise comparison. The main result is:
Any odd, \(\pm 1\)-valued, unanimous, acyclic social welfare function must be a dictator.
The proof proceeds in three steps:
Acyclicity forces the Fourier correlation function \(\mathrm{corr}(f) = -1/3\).
Since \(\mathrm{corr}(f)\ge -1/3\) always holds (with equality iff all Fourier weight is on level 1), this forces \(W_1[f] = 1\).
A \(\pm 1\)-valued degree-1 unanimous function must be a dictator.
References:
Gil Kalai, A Fourier-Theoretic Perspective on the Condorcet Paradox and Arrow’s Theorem, Advances in Applied Mathematics, 2002.
Ryan O’Donnell, Analysis of Boolean Functions, Chapter 2.
2.2 Social choice definitions
A social welfare function \(f:\{ 0,1\} ^n\to \mathbb {R}\) is unanimous if \(f(\texttt{false},\dots ,\texttt{false}) = 1\): when all voters prefer alternative \(a\) over \(b\), so does society.
\(f\) is a dictatorship if there exists a voter \(i\) such that \(f = \mathrm{dict}_i\), i.e. society’s preference always equals voter \(i\)’s.
2.3 Voter ordering model
Each voter holds one of the 6 strict transitive orderings of \(\{ a,b,c\} \). For each ordering we record three pairwise preferences using the sign convention \(\sigma (\texttt{false}) = 1\) (“pro first alternative”) and \(\sigma (\texttt{true}) = -1\) (“pro second”).
The six orderings and their signs \((s_{ab}, s_{bc}, s_{ca})\) are:
|
Index |
Ordering |
\(s_{ab}\) |
\(s_{bc}\) |
\(s_{ca}\) |
|
0 |
\(a\gt b\gt c\) |
\(1\) |
\(1\) |
\(-1\) |
|
1 |
\(a\gt c\gt b\) |
\(1\) |
\(-1\) |
\(-1\) |
|
2 |
\(b\gt a\gt c\) |
\(-1\) |
\(1\) |
\(-1\) |
|
3 |
\(b\gt c\gt a\) |
\(-1\) |
\(1\) |
\(1\) |
|
4 |
\(c\gt a\gt b\) |
\(1\) |
\(-1\) |
\(1\) |
|
5 |
\(c\gt b\gt a\) |
\(-1\) |
\(-1\) |
\(1\) |
\(\mathrm{abPref}(k)\), \(\mathrm{bcPref}(k)\), \(\mathrm{caPref}(k)\) give the Boolean preference of ordering \(k\in \{ 0,\dots ,5\} \) in the \(a\)-vs-\(b\), \(b\)-vs-\(c\), and \(c\)-vs-\(a\) comparisons, respectively.
A profile assigns each of the \(n\) voters one of the 6 orderings: \(p : \mathrm{Fin}\, n \to \mathrm{Fin}\, 6\).
Given a profile \(p\), the vote vectors \(\mathrm{abVotes}(p)\), \(\mathrm{bcVotes}(p)\), \(\mathrm{caVotes}(p) \in \{ 0,1\} ^n\) record each voter’s pairwise preference.
A social welfare function \(f\) is acyclic if no profile of transitive voter orderings produces a Condorcet cycle in society’s preferences. A cycle occurs when \(f(\mathrm{abVotes}(p)) = f(\mathrm{bcVotes}(p)) = f(\mathrm{caVotes}(p)) = 1\) (the cycle \(a\gt b\gt c\gt a\)) or all equal \(-1\) (the reverse cycle).
2.4 Key correlation lemmas
The following lemma encodes the core computation: for a single voter drawn uniformly from the 6 orderings, the expected product of any two distinct pairwise preference signs is \(-1/3\).
Summing pairwise sign products over all 6 orderings:
Hence \(\mathbb {E}[s_{ab}\cdot s_{bc}] = -2/6 = -1/3\).
2.5 Fourier formula for the cycle correlation
The Fourier correlation function of \(f\) is
For odd \(f\), only odd-level terms contribute.
For voters with i.i.d. uniform orderings,
The same identity holds for the \(bc\)–\(ca\) and \(ab\)–\(ca\) pairs.
For any odd \(\pm 1\)-valued function,
Proof sketch: For odd \(|S|\ge 1\) we have \((-1/3)^{|S|}\ge -1/3\). Even-level coefficients vanish by oddness. Hence \(\mathrm{corr}(f) \ge (-1/3)\sum _S \hat f(S)^2 = -1/3\).
If \(\mathrm{corr}(f) = -1/3\), then \(\hat f(S) = 0\) for all \(S\) with \(|S| \ne 1\). Combined with oddness (\(\hat f(\varnothing ) = 0\)), all Fourier weight lies on level 1: \(W_1[f] = 1\).
2.6 Acyclicity implies degree-1 structure
If \(f\) is \(\pm 1\)-valued and acyclic, then \(\mathrm{corr}(f) = -1/3\).
Proof sketch:
For any \(\pm 1\) triple \((a,b,c)\) avoiding the two all-equal cycles, \(ab + bc + ac = -1\).
Summing over all \(6^n\) profiles: \(\sum _p (f_{\! ab}\cdot f_{\! bc} + f_{\! bc}\cdot f_{\! ca} + f_{\! ab}\cdot f_{\! ca}) = -6^n\).
Each pairwise expected product equals \(\mathrm{corr}(f)\), so \(3\cdot \mathrm{corr}(f) = -1\), giving \(\mathrm{corr}(f) = -1/3\).
2.7 Degree-1 implies dictatorship
Suppose \(f\) is \(\pm 1\)-valued, unanimous, and \(\hat f(S) = 0\) for all \(|S|\ne 1\). Then \(f\) is a dictator.
Proof sketch: Write \(f = \sum _i a_i\chi _{\{ i\} }\) where \(a_i = \hat f(\{ i\} )\).
Parseval: \(\sum _i a_i^2 = 1\).
Unanimity: \(f(\mathbf{0}) = \sum _i a_i = 1\).
For each \(j\), the value \(f(e_j) = 1 - 2a_j \in \{ -1,1\} \) forces \(a_j\in \{ 0,1\} \).
From \(a_j\in \{ 0,1\} \) and \(\sum a_j^2 = \sum a_j = 1\): exactly one \(a_{j_0} = 1\) and the rest are \(0\).
Hence \(f = \chi _{\{ j_0\} } = \mathrm{dict}_{j_0}\).
2.8 Arrow’s Impossibility Theorem
Let \(f:\{ 0,1\} ^n\to \mathbb {R}\) be a social welfare function that is odd (antisymmetric), \(\pm 1\)-valued, unanimous, and acyclic. Then \(f\) is a dictatorship: there exists a voter \(i_0\) such that \(f = \mathrm{dict}_{i_0}\).
Proof:
Acyclicity \(\Rightarrow \) \(\mathrm{corr}(f) = -1/3\) (Lemma ).
\(\mathrm{corr}(f) = -1/3\) \(\Rightarrow \) \(\hat f(S) = 0\) for \(|S|\ne 1\) (Lemma ).
Degree-1 + unanimous + \(\pm 1\)-valued \(\Rightarrow \) dictator (Lemma ).