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 的联合体的半随机的可能性。技术上的贡献是对于泊松多项式变量的性质进行了进一步的表征。

选民联盟对大选结果的影响可能性有多大？

How Likely A Coalition of Voters Can Influence A Large Election?

Distributionally robust stochastic optimization (DRSO) is an approach to
optimization under uncertainty in which, instead of assuming that there is a
known true underlying probability distribution, one hedges against a chosen set
of distributions. In this paper we first point out that the set of
distributions should be chosen to be appropriate for the application at hand,
and that some of the choices that have been popular until recently are, for
many applications, not good choices. We next consider sets of distributions
that are within a chosen Wasserstein distance from a nominal distribution. Such
a choice of sets has two advantages: (1) The resulting distributions hedged
against are more reasonable than those resulting from other popular choices of
sets. (2) The problem of determining the worst-case expectation over the
resulting set of distributions has desirable tractability properties. We derive
a strong duality reformulation of the corresponding DRSO problem and construct
approximate worst-case distributions explicitly via the first-order optimality
conditions of the dual problem.
Our contributions are four-fold. (i) We identify necessary and sufficient
conditions for the existence of a worst-case distribution, which are naturally
related to the growth rate of the objective function. (ii) We show that the
worst-case distributions resulting from an appropriate Wasserstein distance
have a concise structure and a clear interpretation. (iii) Using this
structure, we show that data-driven DRSO problems can be approximated to any
accuracy by robust optimization problems, and thereby many DRSO problems become
tractable by using tools from robust optimization. (iv) Our strong duality
result holds in a very general setting. As examples, we show that it can be
applied to infinite-dimensional process control and intensity estimation for
point processes.

本文对于分布鲁棒随机优化问题提出了一种新方法：使用 Wasserstein 距离来确定最坏情况下的期望，并通过拟合最优对偶解得到最坏分布，这一方法可以用于控制和估计点过程的强对偶结果。