Szczegóły publikacji
Opis bibliograficzny
When votes change and committees should (not) / Robert Bredereck, Till Fluschnik, Andrzej KACZMARCZYK // W: IJCAI-22 [Dokument elektroniczny] : proceedings of the thirty-first International Joint Conference on Artificial Intelligence : Vienna, Austria, 23-29 July 2022 / ed. Luc De Raedt. — Wersja do Windows. — Dane tekstowe. — [USA] : International Joint Conferences on Artificial Intelligence, cop. 2022. — e-ISBN: 978-1-956792-00-3. — S. 144-150. — Wymagania systemowe: Adobe Reader. — Tryb dostępu: https://www.ijcai.org/proceedings/2022/0021.pdf [2022-10-19]. — Bibliogr. s. 150, Abstr. — A. Kaczmarczyk - dod. afiliacja: Technische Universität Berlin
Autorzy (3)
- Bredereck Robert
- Fluschnik Till
- AGHKaczmarczyk Andrzej
Słowa kluczowe
Dane bibliometryczne
| ID BaDAP | 143152 |
|---|---|
| Data dodania do BaDAP | 2022-10-20 |
| DOI | 10.24963/ijcai.2022/21 |
| Rok publikacji | 2022 |
| Typ publikacji | materiały konferencyjne (aut.) |
| Otwarty dostęp |  |
| Konferencja | International Joint Conference on Artificial Intelligence 2022 |
Abstract
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 two time-dependent multistage models based on simple scoring-based 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.
