The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections

• URL: http://arxiv.org/abs/2202.06411v4
• Date: Sat, 10 Jun 2023 00:53:24 GMT
• Title: The Impact of a Coalition: Assessing the Likelihood of Voter Influence in Large Elections
• Authors: Lirong Xia
• Abstract summary: It has been widely believed that the influence of a small coalition of voters is negligible in a large election. We show that the likelihood is $Thetaleft(minleftfracBsqrt n, 1rightright)$ for many commonly-studied voting rules.
• Score: 30.930621357547487
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Representation Bias in Political Sample Simulations with Large Language Models [54.48283690603358]
  This study seeks to identify and quantify biases in simulating political samples with Large Language Models. Using the GPT-3.5-Turbo model, we leverage data from the American National Election Studies, German Longitudinal Election Study, Zuobiao dataset, and China Family Panel Studies.
  arXiv  Detail & Related papers  (2024-07-16T05:52:26Z)
• Information Capacity Regret Bounds for Bandits with Mediator Feedback [55.269551124587224]
  We introduce the policy set capacity as an information-theoretic measure for the complexity of the policy set. Adopting the classical EXP4 algorithm, we provide new regret bounds depending on the policy set capacity. For a selection of policy set families, we prove nearly-matching lower bounds, scaling similarly with the capacity.
  arXiv  Detail & Related papers  (2024-02-15T19:18:47Z)
• Redistricting for Proportionality [0.0]
  American democracy is heavily reliant on plurality in single-member districts, or PSMD, as a system of election. We consider whether it is feasible to bring PSMD into alignment with a proportionality norm by targeting proportional outcomes in the design and selection of districts.
  arXiv  Detail & Related papers  (2023-08-22T15:56:40Z)
• The Distortion of Binomial Voting Defies Expectation [26.481697906062095]
  We study the expected distortion of voting rules with respect to an underlying distribution over voter utilities. Our main contribution is the design and analysis of a novel and intuitive rule, binomial voting.
  arXiv  Detail & Related papers  (2023-06-27T17:50:58Z)
• Fairly Allocating Utility in Constrained Multiwinner Elections [0.0]
  A common denominator to ensure fairness across all such contexts is the use of constraints. Across these contexts, the candidates selected to satisfy the given constraints may systematically lead to unfair outcomes for historically disadvantaged voter populations. We develop a model to select candidates that satisfy the constraints fairly across voter populations.
  arXiv  Detail & Related papers  (2022-11-23T10:04:26Z)
• Obvious Manipulability of Voting Rules [105.35249497503527]
  The Gibbard-Satterthwaite theorem states that no unanimous and non-dictatorial voting rule is strategyproof. We revisit voting rules and consider a weaker notion of strategyproofness called not obvious manipulability.
  arXiv  Detail & Related papers  (2021-11-03T02:41:48Z)
• Assertion-Based Approaches to Auditing Complex Elections, with Application to Party-List Proportional Elections [21.883045335485317]
  We show that assertions with linear dependence on transformations of the votes can easily be transformed to canonical form for SHANGRLA. We illustrate the approach by constructing assertions for party-list elections using the D'Hondt method.
  arXiv  Detail & Related papers  (2021-07-25T22:52:49Z)
• Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules [58.8640284079665]
  We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV) In general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee.
  arXiv  Detail & Related papers  (2021-04-19T08:26:40Z)
• Electoral David vs Goliath: How does the Spatial Concentration of Electors affect District-based Elections? [0.5076419064097732]
  district-based elections where there is a "seat" for each district in the governing body. In each district, the party whose candidate gets the maximum number of votes wins the corresponding seat. locations of the electors and boundaries of the districts may severely affect the election result even if the proportion of popular support of different parties remains unchanged. This has led to significant amount of research on whether the districts may be redrawn or electors may be moved to maximize seats for a particular party.
  arXiv  Detail & Related papers  (2020-06-21T18:17:57Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.