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.

研究扩展了先前的研究，提出一种更一般的半随机模型来考虑多数决原则下的联合影响问题。主要结论确定了在各种投票规则下，存在可以成功影响选举的大小为 B 的联合体的半随机的可能性。技术上的贡献是对于泊松多项式变量的性质进行了进一步的表征。