Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Complexity of Shift Bribery in Committee Elections
Authors: Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Nimrod Talmon
AAAI 2016 | Venue PDF | 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 EMAIL, EMAIL 2AGH University of Science and Technology, Krakow, Poland EMAIL |
| 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. |