Verifying Proportionality in Temporal Voting

We study a model of multiwinner voting where candidates are selected sequentially in rounds over a time horizon. Prior work has adapted popular notions of justified representation as well as voting rules that provide strong representation guarantees from the standard single-round multiwinner election case to the temporal setting. In our work, we focus on the complexity of verifying whether a given outcome is proportional. We show that the temporal setting is strictly harder than the standard single-round model of multiwinner voting, but identify natural special cases that enable efficient verification.

Authors

• Edith Elkind Northwestern University, USA
• Svetlana Obraztsova Carleton University, Canada
• Nicholas Teh University of Oxford, UK

Keywords

• Temporal Voting
• Proportionality
• Computational Social Choice