The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections
The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections
复制标题
联盟的影响：评估选民在大型选举中影响的可能性
DOI：
10.1145/3580507.3597731
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Xia, Lirong
中科院分区：
文献类型：
--
作者：
Xia, Lirong
几个世纪以来，人们普遍认为，在一场大型选举中，一个小的选民联盟的影响可以忽略不计。因此，有大量的文献描述了当选票遵循某些分布时选举受到影响的可能性，特别是在被称为公正文化（IC）的i.i.d均匀分布下被单个选民操纵的可能性。在本文中，我们从三个方面扩展了以前的研究：(1)我们提出了一个更一般的半随机模型，其中分布对手选择最坏情况分布，然后污染对手修改数据的部分；(2)我们考虑了许多联盟影响问题，包括联盟操纵，胜利幅度，各种投票控制和贿赂；(3)我们考虑了任意和可变的联盟规模。我们的主要定理提供了可以在广泛的投票规则下成功影响选举的规模联盟存在的半随机可能性的渐近紧界。主定理及其证明技术的应用解决了长期存在的关于IC下联盟可操控性可能性的开放性问题，表明了许多普遍研究的投票规则的可能性。主要的技术贡献是描述了泊松多项变量（PMV）不稳定的半随机似然，我们认为这是一种具有独立兴趣的通用和有用的技术。
For centuries, it has been widely believed that the influence of a small coalition of voters is negligible in a large election. Consequently, there is a large body of literature on characterizing the likelihood for an election to be influenced when the votes follow certain distributions, especially the likelihood of being manipulable by a single voter under the i.i.d. uniform distribution, known as the Impartial Culture (IC). In this paper, we extend previous studies in three aspects: (1) we propose a more general semi-random model, where a distribution adversary chooses a worst-case distribution and then a contamination adversary modifies up toportion of the data, (2) we consider many coalitional influence problems, including coalitional manipulation, margin of victory, and various vote controls and bribery, and (3) we consider arbitrary and variable coalition size. Our main theorem provides asymptotically tight bounds on the semi-random likelihood of the existence of a size-coalition that can successfully influence the election under a wide range of voting rules. Applications of the main theorem and its proof techniques resolve long-standing open questions about the likelihood of coalitional manipulability under IC, by showing that the likelihood isfor many commonly-studied voting rules. The main technical contribution is a characterization of the semi-random likelihood for a Poisson multinomial variable (PMV) to be unstable, which we believe to be a general and useful technique with independent interest.