When Votes Change and Committees Should (Not)
Authors: Robert Bredereck, Till Fluschnik, Andrzej Kaczmarczyk
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be easier than being conservative. Our Contributions. We present the first work in the multistage model that studies a problem from computational social choice and that compares the two cases that we call conservative and revolutionary. We prove MSNTV and RMSNTV to be NP-complete, even for two agents. We present a full parameterized complexity analysis of the two problems (see Figure 1 for an overview of our results; refer to a full version [Bredereck et al., 2020a] for a more detailed overview). |
| Researcher Affiliation | Academia | Robert Bredereck 1,2 , Till Fluschnik3 and Andrzej Kaczmarczyk3,4 1 Institut für Informatik, TU Clausthal, Germany 2 Humboldt-Universität zu Berlin, Berlin, Germany 3 Technische Universität Berlin, Faculty IV, Algorithmics and Computational Complexity, Germany 4 AGH University, Kraków, Poland |
| Pseudocode | No | The paper discusses algorithmic running times and complexity classes, but it does not include pseudocode blocks or explicitly labeled algorithm sections. |
| Open Source Code | No | The paper does not provide any explicit statements about making the source code for their methodology publicly available, nor does it include links to a code repository. |
| Open Datasets | No | This is a theoretical paper focused on computational complexity; it does not involve empirical experiments with datasets, and therefore no training data or information about its public availability is mentioned. |
| Dataset Splits | No | This is a theoretical paper focused on computational complexity; it does not involve empirical experiments with datasets, and therefore no validation data or information about its public availability is mentioned. |
| Hardware Specification | No | As a theoretical paper, it does not describe experimental setups or require specific hardware for implementation, thus no hardware specifications are provided. |
| Software Dependencies | No | This paper is theoretical and focuses on computational complexity; it does not describe software implementations or dependencies with version numbers. |
| Experiment Setup | No | As a theoretical paper, no experimental setup details, hyperparameters, or training configurations are described. |