The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections
원문 초록
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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
SocialDial: A Benchmark for Socially-Aware Dialogue Systems
Synthpop++: A Hybrid Framework for Generating A Country-scale Synthetic Population
SikuGPT: A Generative Pre-trained Model for Intelligent Information Processing of Ancient Texts from the Perspective of Digital Humanities
Cultural-aware Machine Learning based Analysis of COVID-19 Vaccine Hesitancy
Modeling Cell Size Distribution with Heterogeneous Flux Balance Analysis
Vax-Culture: A Dataset for Studying Vaccine Discourse on Twitter
토론
이 논문과 연결된 포럼 글이 아직 없습니다.