Weighted Electoral Control

Piotr Faliszewski, Edith Hemaspaandra, Lane A. Hemaspaandra

Introduction

In the field of Computational Social Choice, the integrity of elections is often analyzed through the lens of "attacks." While significant research has focused on voter manipulation (strategic lying) or bribery, electoral control represents a distinct threat. In this scenario, an external authority—the "chair"—attempts to alter the election outcome by strategically adding or deleting voters.

This paper provides the first comprehensive analysis of weighted electoral control. Unlike standard "one person, one vote" systems, many real-world decision-making bodies utilize weighted voting. Examples include corporate stockholders with varying shares, the US Electoral College, or parliamentary coalitions voting as blocks. The authors investigate whether these weights serve as a barrier to interference or if they create new vulnerabilities that can be exploited via clever algorithms.

Methodology and Theoretical Framework

The authors employ the tools of theoretical computer science to classify the computational complexity of control across various voting rules. Their analysis primarily targets scoring rules (such as Plurality, Borda count, and $t$-approval) and Condorcet-consistent rules, which prioritize candidates who can defeat all others in pairwise matchups.

The research utilizes four primary methodological pillars:

  1. Complexity Reductions: To prove that certain control scenarios are NP-complete, the authors map them to classic mathematical puzzles like the "Partition Problem" or "Exact Cover by 3-Sets" (X3C).
  2. Polynomial-Time Algorithms: For scenarios that are not computationally "hard," the authors develop efficient algorithms (in P) that allow a chair to find an optimal strategy quickly.
  3. Approximation Theory: Recognizing that NP-hardness does not necessarily prevent practical attacks, the authors map voting problems to the Weighted Multicover problem. This allows the application of approximation algorithms that find near-optimal solutions within a logarithmic factor.
  4. Greedy Heuristics: The authors introduce the "Greedy by Weight" (GBW) algorithm to test the effectiveness of simple, intuitive strategies, such as prioritizing the addition or removal of the "heaviest" influential voters.

Key Insights: The Complexity of Control

A central finding of the paper is the divergence between control and manipulation. In certain systems, such as 3-candidate Llull voting, weighted control is NP-hard even when weighted manipulation is computationally easy. This suggests that the "chair" often faces a more daunting mathematical challenge than individual voters attempting to game the system.

The paper also provides a definitive characterization for $t$-approval systems (where voters select their top $t$ candidates):

  • Fixed Candidate Count: If the number of candidates is small and fixed, control is generally easy (in P).
  • Unbounded Candidates: If the number of candidates can grow, the problem becomes NP-complete for nearly all variations of adding or deleting voters.
  • Weight Sensitivity: Interestingly, the "complexity barrier" is low; having as few as two distinct weights (e.g., 1 and 2) is often sufficient to make the control problem NP-complete.

Results and Approximation Ratios

The authors' classification efforts are summarized through several key results:

  • Scoring Rules: For any scoring rule with at least three distinct point values (e.g., Borda count), constructive control is NP-complete, even with a limited number of candidates.
  • $t$-Approval and Veto: The paper resolves several long-standing open problems. For instance, it proves that adding voters in 2-approval (WCCAV) is in P, while deleting voters (WCCDV) is NP-complete.
  • Approximation Bounds: The study establishes that $t$-approval control can be approximated within $O(\log m)$, where $m$ is the number of candidates. For $t$-veto, the approximation ratio is $O(\log t)$. The GBW algorithm specifically provides a $t$-approximation for $t$-approval, offering a practical tool for finding near-optimal interventions.

Limitations and Future Directions

While this work significantly advances the understanding of weighted elections, several avenues for future research remain:

  • Winner Models: The study primarily utilizes the "nonunique-winner" model. The authors note that the "unique-winner" model, which requires a candidate to be the sole victor, introduces additional tie-breaking complexities.
  • Candidate Control: The focus remains on voter-based control. Future work could further explore candidate-based control (adding/deleting candidates) in weighted contexts.
  • Empirical Validation: As a theoretical study, these results represent "worst-case" scenarios. Experimental studies are needed to determine if these NP-hardness results truly deter attackers in practice or if heuristics perform better than theoretical bounds suggest.
  • Complex Rules: Extending approximation results to more intricate rules like the Borda count remains an open challenge for the community.

Summary updated

Abstract

Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.
BibTeX
@article{faliszewski2015weighted,
  author = {Piotr Faliszewski and Edith Hemaspaandra and Lane A. Hemaspaandra},
  title = {{Weighted Electoral Control}},
  journal = {J. Artif. Intell. Res.},
  year = {2015},
  doi = {10.1613/jair.4621},
}
Figure