# Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules

arXiv: https://arxiv.org/abs/2104.09130 · HTML: https://mlsanity.com/paper/2104.09130/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 35 references that are in the map.
- First posted on arXiv 19 Apr 2021.

## Builds on (most cited first, 8 of 8)

- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Properties of Multiwinner Voting Rules](https://mlsanity.com/paper/1506.02891/) (2015)
- [On the Computation of Fully Proportional Representation](https://mlsanity.com/paper/1402.0580/) (2014)
- [Finding a Collective Set of Items: From Proportional Multirepresentation to Group Recommendation](https://mlsanity.com/paper/1402.3044/) (2014)
- [Computational Aspects of Multi-Winner Approval Voting](https://mlsanity.com/paper/1407.3247/) (2014)
- [Elections with Few Voters: Candidate Control Can Be Easy](https://mlsanity.com/paper/1411.7812/) (2014)
- [Prices Matter for the Parameterized Complexity of Shift Bribery](https://mlsanity.com/paper/1502.01253/) (2015)
- [Complexity of Shift Bribery in Committee Elections](https://mlsanity.com/paper/1601.01492/) (2016)

## Built on by (most cited first, 1 of 1)

- [How Hard is it to Rig a Benchmark? A Social Choice Analysis of Leaderboard Robustness](https://mlsanity.com/paper/2605.23628/) (2026)

## Abstract (arXiv)

We study the problem of bribery in multiwinner elections, for the case where the voters cast approval ballots (i.e., sets of candidates they approve) and the bribery actions are limited to: adding an approval to a vote, deleting an approval from a vote, or moving an approval within a vote from one candidate to the other. We consider a number of approval-based multiwinner rules (AV, SAV, GAV, RAV, approval-based Chamberlin--Courant, and PAV). We find the landscape of complexity results quite rich, going from polynomial-time algorithms through NP-hardness with constant-factor approximations, to outright inapproximability. Moreover, in general, our problems tend to be easier when we limit out bribery actions on increasing the number of approvals of the candidate that we want to be in a winning committee (i.e., adding approvals only for this preferred candidate, or moving approvals only to him or her). We also study parameterized complexity of our problems, with a focus on parameterizations by the numbers of voters or candidates.