A quantitative Arrow theorem

DOI10.1007/S00440-011-0362-7MaRDI QIDQ1930856zbMATH OpenOpenAlexFDO

Authors Elchanan Mossel

Publication date 14 January 2013

Published in Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.2574

zbMATH Keywords

influence functionvoting theoryArrow theorem

Mathematics Subject Classification ID

Group preferences (91B10) Social choice (91B14) Combinatorial probability (60C05) Voting theory (91B12)

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 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 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 $eps>0$, there exists a $delta=delta(eps)>0$, which depends on $eps$ only, such that for all $n$, and all constitutions on 3 alternatives, if the constitution satisfies: The IIA condition. For every pair of alternatives $a,b$, the probability that the constitution ranks $a$ above $b$ is at least $eps$. For every voter $i$, the probability that the social choice function agrees with a dictatorship on $i$ at most $1-eps$. Then the probability of a non-transitive outcome is at least $delta$.

Recommendations

• A tight quantitative version of Arrow's impossibility theorem
• Super Arrovian Domains with Strict Preferences
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• A quantitative gibbard-satterthwaite theorem without neutrality
• Three brief proofs of Arrow's impossibility theorem

Cites work

• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
• A tight quantitative version of Arrow's impossibility theorem
• Conditional hardness for approximate coloring
• Gaussian bounds for noise correlation of functions
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• Limit theorems for polylinear forms
• Manipulation of Voting Schemes: A General Result
• Noise stability of functions with low influences: invariance and optimality
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• On the probability of a rational outcome for generalized social welfare functions on three alternatives
• Positivity improving operators and hypercontractivity
• Property testing and its connection to learning and approximation
• Robust Characterizations of Polynomials with Applications to Program Testing
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• The geometry of manipulation -- a quantitative proof of the Gibbard-Satterthwaite theorem

Cited in

(20)

• The universal exponentiable arrow
• Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
• Between Arrow and Gibbard-Satterthwaite. A representation theoretic approach
• Quantitative relation between noise sensitivity and influences
• Quantum reverse hypercontractivity
• A quantitative Gobbard-Satterthwaite theorem without neutrality
• Robust dimension free isoperimetry in Gaussian space
• Probabilistic view of voting, paradoxes, and manipulation
• The probability of intransitivity in dice and close elections
• scientific article; zbMATH DE number 7450028 (Why is no real title available?)
• A phase transition in Arrow's theorem with three alternatives
• Computational application of the mathematical theory of democracy to Arrow's impossibility theorem (how dictatorial are Arrow's dictators?)
• On reverse hypercontractivity
• On the probability of a rational outcome for generalized social welfare functions on three alternatives
• A tight quantitative version of Arrow's impossibility theorem
• Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions
• Approximately classic judgement aggregation
• Gaussian bounds for noise correlation of resilient functions
• The number of times an anonymous rule violates independence in the \(3 \times 3\) case
• A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.

This page was built for publication: A quantitative Arrow theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1930856)