2009/03/14 by Mossel, Elchanan · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.0903.2574
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 δ= δ(\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 δ.