Approximating Weighted and Priced Bribery in Scoring Rules

Orgad Keller, Avinatan Hassidim, Noam HazonJAIR 2019 · OpenReview

Abstract

The classic Bribery problem is to find a minimal subset of voters who need to change their vote to make some preferred candidate win. Its important generalizations consider voters who are weighted and also have different prices. We provide an approximate solution for these problems for a broad family of scoring rules (which includes Borda, t-approval, and Dowdall). Our algorithm is based on a randomized reduction from these Bribery generalizations to weighted coalitional manipulation (WCM). To solve this WCM instance, we apply the Birkhoff-von Neumann (BvN) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding a solution in the truncated search space yields a new algorithm for WCM, which is of independent interest.

Introduction

In the field of computational social choice, the Bribery problem serves as a critical lens for evaluating the integrity and robustness of voting systems. The problem asks a fundamental question: what is the minimum cost required to persuade a subset of voters to alter their ballots such that a specific, preferred candidate emerges as the winner? While the term "bribery" often implies illicit activity, in research it serves as a standard model for understanding how susceptible elections are to external influence and for optimizing resource allocation in legitimate political campaigning.

The complexity of this problem increases significantly when we introduce weights (where some voters, like large shareholders, have more influence than others) and prices (where different voters require different incentives to change their votes). For most common voting systems—specifically positional scoring rules like Borda count or $t$-approval—finding an optimal bribery strategy is NP-hard, especially when the number of candidates is large and arbitrary.

The Algorithmic Framework

This research introduces a novel algorithmic framework that provides near-optimal solutions for weighted and priced bribery across a broad class of scoring rules. The approach rests on three primary pillars: Linear Programming, randomized reduction, and the Birkhoff-von Neumann decomposition.

1. Linear Programming Relaxation

The authors first represent the bribery problem as an Integer Program. Since solving such programs is generally intractable, they "relax" the constraints to create a Linear Program (LP). The solution to this LP provides a "fractional" strategy. In this theoretical space, a voter might be asked to cast a ballot that is a mixture of different rankings (e.g., 40% for one ranking and 60% for another). While not physically possible in a real election, this fractional solution provides a mathematical lower bound for the minimum cost.

2. Reduction to Weighted Coalitional Manipulation (WCM)

A key insight of the paper is a formal randomized reduction from the Bribery problem to Weighted Coalitional Manipulation (WCM). WCM involves a group of "new" voters (the manipulators) attempting to swing an election outcome by coordinating their votes. By showing that bribery can be treated as a form of manipulation, the authors allow techniques developed for WCM to be applied to the more complex bribery scenario.

3. Birkhoff-von Neumann (BvN) Decomposition

The most significant technical contribution is the use of the Birkhoff-von Neumann (BvN) theorem to bridge the gap between fractional strategies and real ballots. In an election with $m$ candidates, there are $m!$ (factorial) possible ways to rank them—an astronomical number that makes exhaustive search impossible. However, the BvN theorem proves that any doubly stochastic matrix (representing the fractional strategy) can be decomposed into a weighted combination of at most $m^2$ permutation matrices (representing actual ballots).

By applying this decomposition, the authors reduce the search space from exponential to polynomial. This allows the algorithm to efficiently select a small set of valid ballots that, when chosen randomly according to the LP's weights, closely approximate the optimal fractional scores.

Key Results and Approximation Guarantees

The framework yields impressive approximation guarantees. For elections with constant weights and prices, the algorithm finds a bribery strategy with a cost of at most $\Psi + \tilde{O}(\sqrt{\Psi})$, where $\Psi$ is the optimal cost.

In the context of approximation algorithms, an additive error of this nature is often superior to a multiplicative error. While a multiplicative error might double the cost, this additive error becomes relatively smaller as the total cost of bribery increases. Furthermore, the authors prove that the probability of the randomized algorithm failing to find a valid winning strategy is exponentially small, ensuring high reliability.

Conclusion and Future Directions

This work provides a "universal" approach to bribery, as the algorithms take the scoring rule itself as an input rather than being hard-coded for a single system like Borda. This makes the framework applicable to a wide variety of voting rules used in AI and social choice.

However, some limitations remain. The current framework is designed specifically for positional scoring rules and does not yet extend to Condorcet-consistent rules (like Copeland), where winners are determined by pairwise matchups. Additionally, certain "concentrated" scoring rules fall outside the current approximation bounds. Future research may focus on tightening these bounds or extending the BvN decomposition approach to more complex, non-linear voting systems.

Summary updated

Abstract

The classic Bribery problem is to find a minimal subset of voters who need to change their vote to make some preferred candidate win. Its important generalizations consider voters who are weighted and also have different prices. We provide an approximate solution for these problems for a broad family of scoring rules (which includes Borda, t-approval, and Dowdall).Our algorithm is based on a randomized reduction from these Bribery generalizations to weighted coalitional manipulation (WCM). To solve this WCM instance, we apply the Birkhoff-von Neumann (BvN) decomposition to a fractional manipulation matrix. This allows us to limit the size of the possible ballot search space reducing it from exponential to polynomial, while still obtaining good approximation guarantees. Finding a solution in the truncated search space yields a new algorithm for WCM, which is of independent interest.
BibTeX
@article{keller2019approximating,
  author = {Orgad Keller and Avinatan Hassidim and Noam Hazon},
  title = {{Approximating Weighted and Priced Bribery in Scoring Rules}},
  journal = {J. Artif. Intell. Res.},
  year = {2019},
  url = {https://openreview.net/forum?id=Z5upuchzLGo},
}
Figure