Manipulating Elections by Selecting Issues

Jasper Lu, David Kai Zhang, Zinovi Rabinovich, Svetlana Obraztsova, Yevgeniy Vorobeychik

Abstract

This paper investigates the strategic selection of political issues as a mechanism for election manipulation. Unlike traditional methods that focus on altering voter preferences or the candidate pool, "issue selection" leverages the concept of salience—the relative importance assigned to different topics. We formalize this as a computational problem within the spatial theory of elections and demonstrate that while optimal agenda-setting is generally NP-hard, greedy heuristics provide robust approximations in practice.

Introduction

In political science, the "salience" of an issue determines its weight in a voter's decision-making process. A candidate who is unpopular on a broad range of topics might still secure a victory if the public discourse is narrowed to a single issue where they hold a competitive advantage. This paper explores constructive election control via issue selection, where an external agent seeks to maximize a target candidate's support by strategically choosing which dimensions of the political space are highlighted during a campaign.

Problem Formulation

We model elections using the spatial theory of elections. Voters and candidates are represented as points in a multi-dimensional issue space $\mathbb{R}^d$. A voter's preference is determined by their proximity to a candidate, typically measured using $L_p$ norms.

The core challenge, defined as the Max Support problem, is to identify a subset of issues $S \subseteq \{1, \dots, d\}$ that maximizes the number of voters who prefer a target candidate $c$ over all other candidates, given that only the dimensions in $S$ are considered. This framework treats issue selection as a novel variant of the bribery problem: instead of purchasing votes directly, the manipulator invests effort to shift public attention.

Computational Complexity

The authors establish several key hardness results:

  • Real-Valued Issues: Even with a single voter, finding the optimal set of real-valued issues to win their support is NP-complete. Furthermore, for two candidates, the problem is inapproximable within any constant factor unless P=NP.
  • Binary Issues: When issues are restricted to binary values (e.g., support/oppose), the problem becomes more tractable for very small numbers of voters. However, it remains NP-hard for three or more voters under specific tie-breaking conditions.

Algorithmic Approaches

To address these computational barriers, the paper proposes three primary methods:

  1. Integer Linear Programming (ILP): An exact approach used to find optimal solutions for smaller instances.
  2. Greedy Heuristic: An iterative algorithm that adds the issue providing the highest marginal gain in voter support until no further improvement is possible.
  3. Best-Single-Issue: A simplified strategy that selects the single most advantageous issue, which is proven to provide a 1/2-approximation in the binary two-candidate case.

Experimental Evaluation

The algorithms were tested on synthetic datasets representing both continuous and binary issue spaces. Continuous issues were sampled from multivariate normal distributions, while binary issues were generated using a vertex-weighted tree structure to simulate complex inter-issue dependencies.

Performance of Greedy and Best-Single-Issue heuristics across varying numbers of candidates, voters, and issues for both continuous and binary issue spaces.

Key Results

As shown in the experimental data, the Greedy Heuristic consistently outperforms the Best-Single-Issue strategy and maintains high approximation ratios across various parameters:

  • Scalability with Voters: Interestingly, the performance of the greedy algorithm tends to improve as the number of voters increases, particularly in binary issue spaces. This suggests that the heuristic is highly effective for large-scale democratic contests.
  • Candidate Pressure: Heuristic performance generally declines as the number of candidates increases. This effect is more pronounced in binary spaces, where the discrete nature of the preferences creates more local optima that can trap greedy searches.
  • Continuous vs. Binary: In continuous spaces with fewer than five candidates, the greedy heuristic typically achieves over 80% of the optimal support, demonstrating its practical utility for real-world political modeling.

Conclusion and Future Work

This research highlights the power of agenda-setting as a tool for election control. While the underlying optimization problems are theoretically difficult, simple heuristics are remarkably effective at identifying influential issue subsets. Future research could extend this model by incorporating dynamic candidate positioning, non-uniform issue weights among voters, and alternative voting systems such as Borda count or Instant Runoff Voting.

Summary updated

BibTeX
@inproceedings{lu2019manipulating,
  author = {Jasper Lu and David Kai Zhang and Zinovi Rabinovich and Svetlana Obraztsova and Yevgeniy Vorobeychik},
  title = {{Manipulating Elections by Selecting Issues}},
  booktitle = {AAMAS},
  year = {2019},
}
Figure