Single elections are well-studied: Arrow's theorem, Gibbard-Satterthwaite, the whole apparatus of social choice theory. But many democratic decisions repeat — city councils vote monthly, committees approve weekly, organizations choose regularly. In perpetual voting, the question shifts from “who wins?” to “how dissatisfied can anyone get over time?”
Kozachinskiy, Shen, and Steifer (arXiv:2501.01969) establish tight bounds on cumulative dissatisfaction in perpetual approval voting. The key finding: under a “bounded conflicts” condition — meaning voter preferences don't create too many fundamental disagreements — dissatisfaction grows sublinearly in the number of rounds. Without this condition, it can grow linearly, meaning some voters become arbitrarily unhappy.
The structural surprise is the method: the proof uses Kolmogorov complexity, connecting perpetual voting to algorithmic information theory. And the mechanism that achieves the optimal bound draws from prediction with expert advice — an online learning framework where the voting method treats each voter as an “expert” whose satisfaction it's trying to optimize. The voting system doesn't deliberate; it learns.
The deeper point: the problem of keeping everyone tolerably satisfied over time is formally equivalent to the problem of predicting as well as the best expert in hindsight. Democratic fairness across time and machine learning's regret minimization are the same mathematical object. The techniques developed for one solve the other.
Voting well repeatedly is a learning problem. The dissatisfaction is the regret.