When Votes Change and Committees Should (Not)
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2020
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916098160459776 |
|---|---|
| author | Bredereck, Robert Fluschnik, Till Kaczmarczyk, Andrzej |
| author_facet | Bredereck, Robert Fluschnik, Till Kaczmarczyk, Andrzej |
| contents | Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce and study two time-dependent multistage models based on simple Plurality voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. 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: If the (upper- resp. lower-) bound on the size of symmetric differences is constant, the conservative model remains NP-hard while the revolutionary model becomes polynomial-time solvable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2005_02300 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | When Votes Change and Committees Should (Not) Bredereck, Robert Fluschnik, Till Kaczmarczyk, Andrzej Computational Complexity Data Structures and Algorithms F.2.2; G.2.1 Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce and study two time-dependent multistage models based on simple Plurality voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. 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: If the (upper- resp. lower-) bound on the size of symmetric differences is constant, the conservative model remains NP-hard while the revolutionary model becomes polynomial-time solvable. |
| title | When Votes Change and Committees Should (Not) |
| topic | Computational Complexity Data Structures and Algorithms F.2.2; G.2.1 |
| url | https://arxiv.org/abs/2005.02300 |