A quantitative Arrow theorem

Elchanan MosselProbability 2011 · DOI

Introduction

Kenneth Arrow’s Impossibility Theorem is a cornerstone of social choice theory, proving that no voting system with three or more alternatives can simultaneously satisfy "Independence of Irrelevant Alternatives" (IIA), "Unanimity," and "Non-dictatorship" without risking non-transitive outcomes. While this qualitative result established the inherent flaws in democratic voting systems, it left a critical question unanswered: how often do these paradoxes actually occur in practice?

In "A Quantitative Arrow Theorem," Elchanan Mossel provides a robust mathematical answer. He demonstrates that if a voting system is sufficiently "fair" (far from a dictatorship), the probability of a non-transitive outcome—the Condorcet paradox—is significant and unavoidable, regardless of the number of voters.

The Problem: From Qualitative to Quantitative

The original theorem states that a paradox must exist. However, if the probability of such a paradox were to vanish as the population grows (e.g., $O(6^{-n})$), the theorem would be a mathematical curiosity rather than a practical concern for large-scale democracies. Mossel addresses this by investigating whether being "far" from a dictatorship guarantees a high probability of a paradox.

Methodology: High-Dimensional Analysis

The paper bridges social choice theory with theoretical computer science and high-dimensional analysis. The author treats voting rules as functions on a Boolean cube and employs several sophisticated tools:

  • Fourier Analysis of Boolean Functions: By decomposing voting functions into Fourier components, the author measures the "influence" of individual voters.
  • Inverse-Hypercontractivity: This represents the paper's most significant technical contribution. It is used to prove that if different voters are pivotal for different pairs of alternatives, their influences will eventually conflict, leading to a non-transitive outcome with non-negligible probability.
  • Non-linear Invariance Principles: These allow for the comparison of discrete voting systems to Gaussian distributions, showing that "low-influence" functions (like Majority rule) are particularly susceptible to paradoxes.

Key Insights and Results

The central finding of the paper is the Dictator-or-Paradox Tradeoff. Mossel establishes that for any number of alternatives $k \geq 3$, if a voting rule satisfies IIA and is $\epsilon$-far from being a dictatorship, the probability of a paradox is at least some constant $\delta$. Crucially, $\delta$ depends on $\epsilon$ but is independent of the number of voters $n$.

Theorem 1.3: The Main Result

The paper proves that if the probability of a paradox is very small ($\delta$), the rule must be very close to a dictatorship. Mossel provides an explicit bound for this probability: $\delta = \exp(-C/\epsilon^{21})$. While later research has improved this to a polynomial bound, Mossel’s work was the first to prove that the probability remains bounded away from zero for all $n$.

Characterization of Transitive Rules

Beyond the quantitative bound, the paper provides a structural description of perfectly transitive rules that satisfy IIA. Such rules must essentially be hierarchies of dictators or constant "top-tier" choices.

Limitations and Future Directions

While groundbreaking, the paper acknowledges certain limitations. The provided bound ($\epsilon^{21}$ in the exponent) is not optimal. Furthermore, the proof relies on voters choosing from a symmetric distribution of preferences. Extending these results to non-symmetric or biased distributions remains a challenge due to the complexities of inverse-hypercontractivity in those contexts.

Finally, the author suggests that this quantitative framework could be extended to the Gibbard-Satterthwaite Theorem, potentially quantifying how easily voting systems can be manipulated by tactical voters.

Summary updated

BibTeX
@inproceedings{mossel2011quantitative,
  author = {Elchanan Mossel},
  title = {{A quantitative Arrow theorem}},
  booktitle = {Probability},
  year = {2011},
  doi = {10.1007/s00440-011-0362-7},
}
Figure