A quantitative Arrow theorem

• 成果类型: Article
• 署名作者: Mossel, Elchanan
• 署名单位: University of California System; University of California Berkeley; University of California System; University of California Berkeley; Weizmann Institute of Science
• 刊物名称: PROBABILITY THEORY AND RELATED FIELDS
• ISSN/ISSBN: 0178-8051
• DOI: 10.1007/s00440-011-0362-7
• 发表日期: 2012
• 页码: 49-88
• 关键词: noise stability; Invariance; bounds

摘要

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 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 , there exists a , which depends on 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 . For every voter i, the probability that the social choice function agrees with a dictatorship on i at most .