ML Anthology

Verifying Proportionality in Temporal Voting

Edith Elkind, Svetlana Obraztsova, Jannik Peters, Nicholas Teh
AAAI 2025 pp. 13805-13813
doi:10.1609/AAAI.V39I13.33509 /aaai/2025/elkind2025aaai-verifying/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Elkind et al. "Verifying Proportionality in Temporal Voting." AAAI Conference on Artificial Intelligence, 2025. doi:10.1609/AAAI.V39I13.33509

Markdown

[Elkind et al. "Verifying Proportionality in Temporal Voting." AAAI Conference on Artificial Intelligence, 2025.](https://mlanthology.org/aaai/2025/elkind2025aaai-verifying/) doi:10.1609/AAAI.V39I13.33509

BibTeX

@inproceedings{elkind2025aaai-verifying,
  title     = {{Verifying Proportionality in Temporal Voting}},
  author    = {Elkind, Edith and Obraztsova, Svetlana and Peters, Jannik and Teh, Nicholas},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2025},
  pages     = {13805-13813},
  doi       = {10.1609/AAAI.V39I13.33509},
  url       = {https://mlanthology.org/aaai/2025/elkind2025aaai-verifying/}
}