Complexity of Shift Bribery in Committee Elections
Authors: Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Nimrod Talmon
AAAI 2016 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the (parameterized) complexity of SHIFT BRIBERY for multiwinner voting rules. We focus on the 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 significantly 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. 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. |
| Researcher Affiliation | Academia | 1Institut f ur Softwaretechnik und Theoretische Informatik, TU Berlin, Berlin, Germany {robert.bredereck, rolf.niedermeier}@tu-berlin.de, nimrodtalmon77@gmail.com 2AGH University of Science and Technology, Krakow, Poland faliszew@agh.edu.pl |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information for open-source code related to the described methodology. |
| Open Datasets | No | The paper is theoretical and does not involve empirical studies with datasets, therefore no training dataset information is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical studies or dataset splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any hardware used for experiments. |
| Software Dependencies | No | The paper is theoretical and does not list any specific software dependencies with version numbers for experimental reproducibility. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with hyperparameters or training configurations. |