# Optimal bounds for dissatisfaction in perpetual voting

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 8 references that are in the map.
- First posted on arXiv 20 Dec 2024.

## Builds on (most cited first, 1 of 1)

- [Temporal Elections: Welfare, Strategyproofness, and Proportionality](https://mlsanity.com/paper/2408.13637/) (2024)

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

- [Not in My Backyard! Temporal Voting Over Public Chores](https://mlsanity.com/paper/2508.08810/) (2025)
- [The End Justifies the Mean: A Linear Ranking Rule for Proportional Sequential Decisions](https://mlsanity.com/paper/2605.12717/) (2026)

## Abstract (arXiv)

In perpetual voting, multiple decisions are made at different moments in time. Taking the history of previous decisions into account allows us to satisfy properties such as proportionality over periods of time. In this paper, we consider the following question: is there a perpetual approval voting method that guarantees that no voter is dissatisfied too many times? We identify a sufficient condition on voter behavior -- which we call 'bounded conflicts' condition -- under which a sublinear growth of dissatisfaction is possible. We provide a tight upper bound on the growth of dissatisfaction under bounded conflicts, using techniques from Kolmogorov complexity. We also observe that the approval voting with binary choices mimics the machine learning setting of prediction with expert advice. This allows us to present a voting method with sublinear guarantees on dissatisfaction under bounded conflicts, based on the standard techniques from prediction with expert advice.