A quantitative Arrow theorem
By Elchanan Mossel. 2009
55 citations recorded by the source corpus.
AbstractArrow’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 six rankings of three 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 $${\epsilon > 0}$$ , there exists a $${\delta = \delta(\epsilon) > 0}$$ , which depends on $${\epsilon}$$ only, such that for all n, and all constitutions on three 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 $${\epsilon}$$.For every voter i, the probability that the social choice function agrees with a dictatorship on i at most $${1-\epsilon}$$. Then the probability of a non-transitive outcome is at least δ. Our results generalize to any number k ≥ 3 of alternatives and to other distributions over the alternatives. We further derive a quantitative characterization of all social choice functions satisfying the IIA condition whose outcome is transitive with probability at least 1 − δ. Our results provide a quantitative statement of Arrow theorem and its generalizations and strengthen results of Kalai and Keller who proved quantitative Arrow theorems for k = 3 and for balanced constitutions only, i.e., for constitutions which satisfy for every pair of alternatives a, b, that the probability that the constitution ranks a above b is exactly 1/2. The main novel technical ingredient of our proof is the use of inverse-hypercontractivity to show that if the outcome is transitive with high probability then there are no two different voters who are pivotal with for two different pairwise preferences with non-negligible probability. Another important ingredient of the proof is the application of non-linear invariance to lower bound the probability of a paradox for constitutions where all voters have small probability for being pivotal.
Subfields: Computational Theory and Mathematics, Economics and Econometrics, Management Science and Operations Research
View Paper: https://www.semanticscholar.org/paper/0db98f2554503c45bfd2a8e23f513861ef1d714f
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computational Theory and Mathematics
In Economics and Econometrics
In Management Science and Operations Research
Citations in the corpus
- On Reverse Hypercontractivity (2011, background): “≥ 1−δ, • Fairness: for every pair of alternatives aand b, P{Franks aabove b} = 1/2, • IIA, then there exists a dictator function Gsuch that P{F(σ) 6= G(σ)} ≤ ǫ. Following a challenge by Kalai, Mossel [Mos12] proved a stronger result for any number of alternatives and without the assumption that F is”
- Robust dimension free isoperimetry in Gaussian space (2012, background): “al version of surface area called Gaussian noise sensitivity. This fact has recently found applications in areas such as quantitative social choice and theoretical computer science; see, for example, [14, 22, 24, 25]. A second direction of extension is characterizing the case of equality or almost e”