Verifying Proportionality in Temporal Voting
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910820085006336 |
|---|---|
| author | Elkind, Edith Obraztsova, Svetlana Peters, Jannik Teh, Nicholas |
| author_facet | Elkind, Edith Obraztsova, Svetlana Peters, Jannik Teh, Nicholas |
| contents | We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05949 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Verifying Proportionality in Temporal Voting Elkind, Edith Obraztsova, Svetlana Peters, Jannik Teh, Nicholas Computer Science and Game Theory Artificial Intelligence We study a model of temporal voting where there is a fixed time horizon, and at each round the voters report their preferences over the available candidates and a single candidate is selected. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the multiwinner election setting to this model. In our work, we focus on the complexity of verifying whether a given outcome offers proportional representation. We show that in the temporal setting verification is strictly harder than in multiwinner voting, but identify natural special cases that enable efficient algorithms. |
| title | Verifying Proportionality in Temporal Voting |
| topic | Computer Science and Game Theory Artificial Intelligence |
| url | https://arxiv.org/abs/2502.05949 |