# Complexity of Shift Bribery in Committee Elections

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Jan 2016.

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

- [Bribery as a Measure of Candidate Success: Complexity Results for Approval-Based Multiwinner Rules](https://mlsanity.com/paper/2104.09130/) (2021)
- [Pandering in a Flexible Representative Democracy](https://mlsanity.com/paper/2211.09986/) (2022)

## Abstract (arXiv)

Given an election, a preferred candidate p, and a budget, the SHIFT BRIBERY problem asks whether p can win the election after shifting p higher in some voters' preference orders. Of course, shifting comes at a price (depending on the voter and on the extent of the shift) and one must not exceed the given budget. We study the (parameterized) computational complexity of S HIFT BRIBERY for multiwinner voting rules where winning the election means to be part of some winning committee. We focus on the well-established SNTV, Bloc, k-Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule, since the original rule is NP-hard to compute. We show that SHIFT BRIBERY tends to be harder in the multiwinner setting than in the single-winner one by showing settings where SHIFT BRIBERY is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. Moreover, we show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin-Courant rule sometimes affects the complexity of SHIFT BRIBERY.