Summary
This paper looks at how to fairly represent voters when decisions happen one by one over time and voters can rank their preferences differently each time. The authors find that ensuring fair representation is more complicated when voters rank rather than approve candidates, especially if the criteria for which candidates count as approved changes from round to round or voter to voter. Some fairness guarantees require knowing future voter preferences in advance, while others can be met with limited or no future knowledge depending on the situation. They also show that checking whether these fairness conditions are met can be computationally hard.
What this means in practice
- •For online platform designers: Implement fair sequential voting methods that account for changing user rankings while guaranteeing proportional representation under certain rules.
- •For committee organizers: Design multi-round selection processes to ensure fair representation among voters when preferences evolve over time.
A theory result. No direct application yet.
Abstract
We study proportional representation in temporal voting, where one candidate is selected in each round. While prior work has focused on approval ballots, we consider ranked preferences, which may change over time. A natural approach treats each voter's top candidates as approved, but the right cutoff may differ across voters and rounds. We therefore require proportionality to hold for every admissible choice of cutoffs, whether fixed and common, common but varying across rounds, or set individually for each voter in each round. Combining these interpretations with temporal versions of justified representation (JR), proportional JR (PJR), extended JR (EJR), and proportionality for solid coalitions (PSC) gives us a hierarchy of axioms. We ask which of these axioms can be guaranteed, and with how much knowledge of the future. Unlike with approval ballots, no version of EJR can be guaranteed, and for the other axioms, flexibility in the cutoffs comes at a price. With a fixed common cutoff, JR, PJR, and PSC can be guaranteed, but only by rules that see all preferences in advance. Once the cutoff may vary across rounds, even such rules cannot guarantee JR or PSC for groups that agree in only some rounds. For groups that agree in every round, however, knowing only the number of rounds suffices for PJR in polynomial time, and PSC needs no knowledge of the future at all. Under individual cutoffs, no version of JR or PJR can be guaranteed, yet a rule as simple as serial dictatorship achieves PJR up to an additive loss that no rule can improve on, however much it knows. Natural preference restrictions restore exact guarantees. Finally, we show that checking our axioms is often coNP-complete; but perhaps surprisingly, a stronger axiom can be easier to check.