Approximation Algorithms for Campaign Management
arXiv:1004.0334
Abstract
We study electoral campaign management scenarios in which an external party can buy votes, i.e., pay the voters to promote its preferred candidate in their preference rankings. The external party's goal is to make its preferred candidate a winner while paying as little as possible. We describe a 2-approximation algorithm for this problem for a large class of electoral systems known as scoring rules. Our result holds even for weighted voters, and has applications for campaign management in commercial settings. We also give approximation algorithms for our problem for two Condorcet-consistent rules, namely, the Copeland rule and maximin.
19 pages
References in corpus (1)
Cited by in corpus (4)
- Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules
- On the Robustness of Winners: Counting Briberies in Elections
- Parameterized Algorithmics for Computational Social Choice: Nine Research Challenges
- Manipulation Can Be Hard in Tractable Voting Systems Even for Constant-Sized Coalitions