Abstract
Arrow's Impossibility Theorem states that any constitution which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a Dictator has to be non-transitive. In this paper, we study quantitative versions of Arrow's theorem. Consider $n$ voters who vote independently at random, each following the uniform distribution over the 6 rankings of 3 alternatives. Arrow's theorem implies that any constitution which satisfies IIA and Unanimity and is not a dictator has a probability of at least $6^{-n}$ for a non-transitive outcome. When $n$ is large, $6^{-n}$ is a very small probability, and the question arises if for a large number of voters it is possible to avoid paradoxes with probability close to 1. Here we give a negative answer to this question by proving that for every $\epsilon > 0$, there exists a $\delta = \delta(\epsilon) > 0$, which depends on $\epsilon$ only, such that for all $n$, and all constitutions on 3 alternatives, if the constitution satisfies IIA, is $\epsilon$-far from a dictatorship, and $\epsilon$-far from being biased toward any alternative, the probability of a non-transitive outcome is at least $\delta$.
Introduction: The Limits of Social Choice
In social choice theory, Arrow’s Impossibility Theorem is a foundational result. It proves that any voting system (constitution) with three or more candidates that satisfies certain "fairness" criteria—specifically Independence of Irrelevant Alternatives (IIA) and Unanimity—must be a dictatorship to guarantee a transitive (rational) outcome. A transitive outcome is one where if the group prefers candidate A to B and B to C, it must also prefer A to C.
However, the original theorem is qualitative. It establishes that a paradox must exist under certain conditions, but it does not quantify how often such a paradox occurs. For a population of $n$ voters, the probability of a non-transitive outcome could theoretically be as small as $6^{-n}$. In a large-scale election with millions of voters, $6^{-1,000,000}$ is effectively zero, suggesting that perhaps "almost fair" and "almost rational" systems could exist in practice. This paper provides a definitive negative answer to that possibility, establishing a robust quantitative version of Arrow's theorem.
The Problem of Scale
The central question addressed is: Can we design a voting system for large populations that is almost always rational and almost fair? If the probability of a paradox vanished as the number of voters increased, Arrow's theorem would be a mathematical curiosity rather than a practical constraint.
Elchanan Mossel demonstrates that the paradox is inescapable. He proves that if a system is "far" from being a dictatorship, the chance of a nonsensical result (e.g., a Condorcet cycle where A > B > C > A) remains bounded away from zero, regardless of whether there are ten voters or ten billion.
Methodological Framework
The proof relies on sophisticated tools from theoretical computer science and probability, moving the problem from social choice theory into the realm of harmonic analysis:
- Fourier Analysis on the Boolean Hypercube: The author treats voting functions as mathematical objects on a high-dimensional space. By decomposing these functions, the research can measure the "influence" of individual voters on the final outcome.
- Inverse-Hypercontractivity: This is the critical technical innovation of the paper. It allows the author to show that if multiple voters are "pivotal" for different pairwise preferences (e.g., one voter swings the A vs. B result and another swings B vs. C), there is a statistically significant probability that their combined influence creates a non-transitive loop.
- Non-linear Invariance Principles: These principles are used to relate discrete voting patterns to Gaussian (normal) distributions. This allows for the analysis of "low-influence" functions—like Majority rule—by studying their continuous counterparts, where the geometry of the paradox becomes more apparent.
Key Insights and Results
1. The Paradox is Robust
The probability of a paradox depends on the "distance" to the nearest dictatorship ($\epsilon$), not on the number of voters ($n$). This means social choice paradoxes are a fundamental mathematical tax on non-dictatorial systems. If you want a system to be $\epsilon$-far from a dictatorship, you must accept a $\delta$-probability of irrationality.
2. Theorem 1.3: The Quantitative Bound
The paper establishes that for any voting system satisfying IIA, if the probability of a paradox is less than some $\delta$, then the system must be very close (in statistical distance) to a specific class of "generalized dictatorships." The established bound is $\delta = \exp(-C/\epsilon^{21})$ for some constant $C$. While this bound is likely loose, it provides the first rigorous proof that $\delta$ is independent of $n$.
3. Transitivity is "Testable"
From a computational perspective, the paper implies that transitivity is a testable property. One can determine if a voting rule is close to a dictatorship simply by sampling a few random voting profiles and checking for the presence of non-transitive outcomes.
Conclusion and Future Directions
While this work settles the question of whether large populations can avoid Arrow's paradox, several open questions remain. The author notes that the $\epsilon^{21}$ dependency is likely not optimal; it is conjectured that the true relationship between the distance to a dictatorship and the paradox probability is polynomial (e.g., $\delta \approx \epsilon^k$).
Furthermore, the current proof assumes a symmetric distribution of voter preferences (where ranking A > B is as likely as B > A). Extending these quantitative results to biased distributions or applying these techniques to derive a quantitative version of the Gibbard-Satterthwaite theorem—which concerns the strategic manipulability of voting systems—represents the next frontier in this line of research.
Summary updated