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 to $\psi$ portion 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 $B$. Our main theorem provides asymptotically tight bounds on the semi-random likelihood of the existence of a size-$B$ 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 is $\Theta\left(\min\left\{\frac{B}{\sqrt n}, 1\right\}\right)$ for 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.
翻译:几个世纪以来,人们广泛认为小型选民联盟的影响在大规模选举中是微不足道的。因此,有大量文献记载了在投票按照某些分配办法进行时,选举可能受到影响的可能性,特别是统一分配(称为“公正文化 ” ) 下单一选民可以操纵的可能性。 在本文中,我们从三个方面扩展了先前的研究:(1) 我们提议了一个更普遍的半随机模式,即分配对手选择了最坏情况的半随机模式,然后污染对手将数据的一部分修改为1美元;(2) 我们认为许多联合影响问题,包括联合操纵、胜利的幅度以及各种投票控制和贿赂;(3) 我们考虑任意和变异的联盟规模(称为“公正文化 ” )。 我们的主要理论提供了对规模- 美元 有用性联盟存在半随机性的界限,根据广泛的投票规则,可以成功影响选举。 主理论的应用及其证据技术可以解决长期操纵、 胜利的幅度规则是常态 。