Prices Matter for the Parameterized Complexity of Shift Bribery
Authors: Robert Bredereck, Jiehua Chen, Piotr Faliszewski, André Nichterlein, Rolf Niedermeier
AAAI 2014 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the parameterized computational complexity of SHIFT BRIBERY with respect to a number of parameters (pertaining to the nature of the solution sought and the size of the election) and several classes of price functions. When we parameterize SHIFT BRIBERY by the number of affected voters, then for each of our voting rules (Borda, Maximin, Copeland) the problem is W[2]-hard. If, instead, we parameterize by the number of positions by which p is shifted in total, then the problem is fixed-parameter tractable for Borda and Maximin, and is W[1]-hard for Copeland. If we parameterize by the budget for the cost of shifting, then the results depend on the price function class. We also show that SHIFT BRIBERY tends to be tractable when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic. |
| Researcher Affiliation | Academia | 1TU Berlin, Berlin, Germany {robert.bredereck, jiehua.chen, andre.nichterlein, rolf.niedermeier}@tu-berlin.de 2AGH University of Science and Technology, Krakow, Poland faliszew@agh.edu.pl |
| Pseudocode | No | The paper describes algorithms conceptually, for example, mentioning "greedy procedure" or the |
| Open Source Code | No | The paper does not mention providing open-source code or links to a code repository for the methodology described. |
| Open Datasets | No | The paper is theoretical and focuses on computational complexity analysis. It does not describe or use any datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with training, validation, or test data splits. |
| Hardware Specification | No | The paper is theoretical and does not describe empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe empirical experiments, therefore no experimental setup details like hyperparameters are provided. |