Verifying Proportionality in Temporal Voting

Edith Elkind; Svetlana Obraztsova; Jannik Peters; Nicholas Teh

doi:10.1609/aaai.v39i13.33509

Verifying Proportionality in Temporal Voting

Edith Elkind, Svetlana Obraztsova, Jannik Peters, Nicholas Teh

Computer Science

Research output: Contribution to journal › Conference article › peer-review

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.

Original language	English (US)
Pages (from-to)	13805-13813
Number of pages	9
Journal	Proceedings of the AAAI Conference on Artificial Intelligence
Volume	39
Issue number	13
DOIs	https://doi.org/10.1609/aaai.v39i13.33509
State	Published - Apr 11 2025
Event	39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025 - Philadelphia, United States Duration: Feb 25 2025 → Mar 4 2025

Funding

Edith Elkind was supported by the AI Programme of The Alan Turing Institute and an EPSRC Grant EP/X038548/1. Jannik Peters was supported by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001.

ASJC Scopus subject areas

Artificial Intelligence

Access to Document

10.1609/aaai.v39i13.33509

Cite this

@article{b306f91952f542e28885d4b28ede4741,

title = "Verifying Proportionality in Temporal Voting",

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.",

author = "Edith Elkind and Svetlana Obraztsova and Jannik Peters and Nicholas Teh",

note = "Publisher Copyright: Copyright {\textcopyright} 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025 ; Conference date: 25-02-2025 Through 04-03-2025",

year = "2025",

month = apr,

day = "11",

doi = "10.1609/aaai.v39i13.33509",

language = "English (US)",

volume = "39",

pages = "13805--13813",

journal = "Proceedings of the AAAI Conference on Artificial Intelligence",

issn = "2159-5399",

publisher = "Association for the Advancement of Artificial Intelligence",

number = "13",

}

TY - JOUR

T1 - Verifying Proportionality in Temporal Voting

AU - Elkind, Edith

AU - Obraztsova, Svetlana

AU - Peters, Jannik

AU - Teh, Nicholas

PY - 2025/4/11

Y1 - 2025/4/11

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=105003903801&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=105003903801&partnerID=8YFLogxK

U2 - 10.1609/aaai.v39i13.33509

DO - 10.1609/aaai.v39i13.33509

M3 - Conference article

AN - SCOPUS:105003903801

SN - 2159-5399

VL - 39

SP - 13805

EP - 13813

JO - Proceedings of the AAAI Conference on Artificial Intelligence

JF - Proceedings of the AAAI Conference on Artificial Intelligence

IS - 13

T2 - 39th Annual AAAI Conference on Artificial Intelligence, AAAI 2025

Y2 - 25 February 2025 through 4 March 2025

ER -

Verifying Proportionality in Temporal Voting

Abstract

Funding

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this