# When Votes Change and Committees Should (Not)

arXiv: https://arxiv.org/abs/2005.02300 · HTML: https://mlsanity.com/paper/2005.02300/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 May 2020.

## Built on by (most cited first, 7 of 7)

- [Temporal Fairness in Multiwinner Voting](https://mlsanity.com/paper/2312.04417/) (2023)
- [Temporal Elections: Welfare, Strategyproofness, and Proportionality](https://mlsanity.com/paper/2408.13637/) (2024)
- [Multiwinner Temporal Voting with Aversion to Change](https://mlsanity.com/paper/2408.11017/) (2024)
- [Strengthening Proportionality in Temporal Voting](https://mlsanity.com/paper/2505.22513/) (2025)
- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [The Leximin Approach for a Sequence of Collective Decisions](https://mlsanity.com/paper/2305.18024/) (2023)
- [Efficient Algorithms for Electing Successive Committees](https://mlsanity.com/paper/2505.18287/) (2025)

## Abstract (arXiv)

Electing a single committee of a small size is a classical and well-understood voting situation. Being interested in a sequence of committees, we introduce and study two time-dependent multistage models based on simple Plurality voting. Therein, we are given a sequence of voting profiles (stages) over the same set of agents and candidates, and our task is to find a small committee for each stage of high score. In the conservative model we additionally require that any two consecutive committees have a small symmetric difference. Analogously, in the revolutionary model we require large symmetric differences. We prove both models to be NP-hard even for a constant number of agents, and, based on this, initiate a parameterized complexity analysis for the most natural parameters and combinations thereof. Among other results, we prove both models to be in XP yet W[1]-hard regarding the number of stages, and that being revolutionary seems to be "easier" than being conservative: If the (upper- resp. lower-) bound on the size of symmetric differences is constant, the conservative model remains NP-hard while the revolutionary model becomes polynomial-time solvable.