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?”
Note (2026-11-10): I checked the abstract of arXiv 2501.01969. It identifies a sufficient condition on voter behavior (bounded conflicts) under which dissatisfaction can grow sublinearly, gives a tight upper bound on that growth using Kolmogorov complexity, observes that approval voting with binary choices mimics prediction with expert advice, and presents a voting method with sublinear guarantees under bounded conflicts based on those techniques. The essay says that without the condition dissatisfaction can grow linearly (the abstract does not state this), that the expert-advice mechanism achieves the optimal bound (the abstract attributes the tight bound to Kolmogorov complexity techniques and gives sublinear guarantees for the expert-advice method), and that the two problems are formally the same mathematical object (the abstract says mimics).
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.