论文标题
联盟的影响：评估选民在大选中影响的可能性
The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections
论文作者
论文摘要
几个世纪以来，人们普遍认为，一小部分选民联盟在大选中可以忽略不计。因此，有大量文献来表征当选票遵循某些分布的可能性，尤其是在I.I.D.下的单个选民可以操纵的可能性时，选举可能会受到影响的可能性。均匀分布，称为公正培养（IC）。 在本文中，我们在三个方面扩展了先前的研究：（1）我们提出了一个更一般的半随机模型，其中分布对手选择最差的分布，然后污染对手可修改多达$ψ$的数据部分，（2）我们考虑许多联盟影响问题，包括电汇和各种胜利，以及各种投票和各种投票范围，以及3个我们的投票范围，以及3个我们的投票范围，（3）我们（3）我们（3）我们（3）我们（3）我们考虑了（3），（3）我们考虑了（3），（3）我们考虑了（3）的（3）我们的竞争范围（3）我们考虑了（3）的范围，（3）我们考虑了（3）的范围，（3）我们考虑了（3）的（3）我们考虑了（3）的（3）我们考虑了（3）。 $ b $。我们的主要定理在半随机的可能性上提供了渐近的界限，该大小 - $ b $联盟的存在，该联盟可以在广泛的投票规则下成功影响选举。 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 $Θ\left(\min\left\{\frac{B}{\sqrt n}, 1\right\}\right)$ for many commonly-studied voting rules. 主要的技术贡献是对泊松多种变量（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 to $ψ$ 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 $Θ\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.
