A PHASE TRANSITION IN ARROW'S THEOREM WITH THREE ALTERNATIVES

• 成果类型: Article
• 署名作者: Koehler, Frederic; Mossel, Elchanan
• 署名单位: University of Chicago; University of Chicago; Massachusetts Institute of Technology (MIT)
• 刊物名称: ANNALS OF APPLIED PROBABILITY
• ISSN/ISSBN: 1050-5164
• DOI: 10.1214/24-AAP2049
• 发表日期: 2024
• 页码: 3735-3780
• 关键词: condorcet paradox; Mean-field; manipulation; MODEL; probability; statistics; rankings

摘要

Arrow's theorem concerns a fundamental problem in social choice theory: given the individual preferences of members of a group, how can they be aggregated to form rational group preferences? Arrow showed that in an election between three or more candidates, there are situations where any voting rule satisfying a small list of natural fairness axioms must produce an apparently irrational intransitive outcome. Furthermore, quantitative versions of Arrow's theorem in the literature show that when voters choose rankings in an i.i.d. fashion, the outcome is intransitive with nonnegligible probability. It is natural to ask if such a quantitative version of Arrow's theorem holds for non-i.i.d. models. To answer this question, we study Arrow's theorem under a natural non-i.i.d. model of voters inspired by canonical models in statistical physics; indeed, a version of this model was previously introduced by Raffaelli and Marsili in the physics literature. This model has a parameter, temperature, that prescribes the correlation between different voters. We show that the behavior of Arrow's theorem in this model of an election with three alternatives undergoes a striking phase transition: in the entire high temperature regime of the model, a quantitative Arrow's theorem holds showing that the probability of paradox for any voting rule satisfying the axioms is nonnegligible; this is tight because the probability of paradox under pairwise majority goes to zero when approaching the critical temperature, and becomes exponentially small in the number of voters beyond it. We prove this occurs in another natural model of correlated voters and conjecture this phenomena is quite general.