Multiwinner Temporal Voting with Aversion to Change
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910571235901440 |
|---|---|
| author | Zech, Valentin Boehmer, Niclas Elkind, Edith Teh, Nicholas |
| author_facet | Zech, Valentin Boehmer, Niclas Elkind, Edith Teh, Nicholas |
| contents | We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters' preferences and the role of ties. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_11017 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Multiwinner Temporal Voting with Aversion to Change Zech, Valentin Boehmer, Niclas Elkind, Edith Teh, Nicholas Computer Science and Game Theory Artificial Intelligence Computational Complexity We study two-stage committee elections where voters have dynamic preferences over candidates; at each stage, a committee is chosen under a given voting rule. We are interested in identifying a winning committee for the second stage that overlaps as much as possible with the first-stage committee. We show a full complexity dichotomy for the class of Thiele rules: this problem is tractable for Approval Voting (AV) and hard for all other Thiele rules (including, in particular, Proportional Approval Voting and the Chamberlin-Courant rule). We extend this dichotomy to the greedy variants of Thiele rules. We also explore this problem from a parameterized complexity perspective for several natural parameters. We complement the theory with experimental analysis: e.g., we investigate the average number of changes in the committee as a function of changes in voters' preferences and the role of ties. |
| title | Multiwinner Temporal Voting with Aversion to Change |
| topic | Computer Science and Game Theory Artificial Intelligence Computational Complexity |
| url | https://arxiv.org/abs/2408.11017 |