Generalized Distance Bribery

Dorothea Baumeister, Tobias Hogrebe, Lisa ReyAAAI 2019 · DOI

Abstract

This paper introduces Generalized Distance Bribery, a framework for analyzing how an external agent can manipulate election outcomes by changing votes within a fixed "distance" budget. By exploring various metrics like swap and footrule distances, the authors map out which voting rules are robust against such interference and which are computationally vulnerable, providing a near-complete landscape of complexity results for common scoring rules.

Introduction: The Problem of Election Manipulation

In Computational Social Choice (COMSOC), "bribery" serves as a formal model for external influences that alter votes to change an election's winner. Traditional models often focus on the cost per voter or per individual candidate swap. However, these models frequently fail to capture the "stealth" or "effort" required for a campaign.

This paper addresses this gap by introducing a global distance bound. Under this framework, a manipulator must change the outcome while ensuring the total "distance" between the original and modified votes remains under a threshold $K$. This reflects real-world constraints where an agent might seek to avoid detection through minor adjustments or operate within limited resources to shift public opinion.

Formal definition of the (D, E)-DISTANCE BRIBERY problem.

Methodology

The authors utilize computational complexity analysis to determine if finding a successful bribery strategy is "easy" (solvable in polynomial time, P) or "hard" (NP-complete). The study focuses on two primary distance metrics:

  1. Swap Distance: Measures the number of adjacent candidate pairs whose relative order is flipped.
  2. Footrule Distance: Measures the total displacement of candidates from their original positions in a preference list.

These metrics are further refined into unweighted, element-weighted (where moving specific candidates is more costly), and fully weighted (where specific swaps have distinct costs) variants. The analysis covers both constructive bribery (forcing a preferred candidate to win) and destructive bribery (preventing a rival from winning) across pure scoring rules such as Plurality, Borda, and $k$-approval.

Key Insights and Ideas

  • Destructive vs. Constructive: In most scenarios, preventing a candidate from winning is computationally easier than forcing a specific candidate to win.
  • Weights as Complexity Triggers: Transitioning from unweighted to element-weighted or fully weighted distances often shifts a problem from P to NP-complete.
  • The (2, 1, ..., 1, 0) Rule Anomaly: The authors identified a specific scoring rule where swap and footrule distances yield different complexities—a rare occurrence in COMSOC research.
  • Single-Voter Hardness: For complex rules like Borda, the problem can be NP-hard even when influencing only a single voter, suggesting that optimal manipulation is inherently difficult for certain systems.

Key Results

The paper provides a comprehensive "Complexity Map," summarizing the tractability of various voting rules under different distance measures.

Complexity results for various voting rules and distance metrics.

Highlights include:

  • Plurality and Veto: These rules remain largely tractable (P) across most distance measures, making them easier to manipulate but also easier for agents to calculate optimal moves.
  • Borda Count: This rule proves highly resistant to manipulation, with almost all weighted distance variants being NP-complete.
  • Dichotomy Result: The authors achieved a complete dichotomy for pure scoring rules under element-weighted distances, categorizing every such rule as either P or NP-complete.

Limitations and Future Work

As a theoretical study, this work focuses on worst-case analysis. While NP-completeness suggests general hardness, it does not preclude efficient heuristics for "average" or real-world data. Future research directions include:

  1. Parameterized Complexity: Determining if problems become tractable when parameters like the number of candidates or the budget are small.
  2. Approximation Algorithms: Developing methods to find "good enough" solutions quickly when optimal solutions are computationally out of reach.

Summary updated

BibTeX
@inproceedings{baumeister2019generalized,
  author = {Dorothea Baumeister and Tobias Hogrebe and Lisa Rey},
  title = {{Generalized Distance Bribery}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33011764},
}
Figure