Verifying Proportionality in Temporal Voting

Abstract

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.