Optimal bounds for dissatisfaction in perpetual voting
This work addresses fairness in sequential decision-making for voting systems, but it is incremental as it builds on existing methods from machine learning.
The paper tackles the problem of minimizing voter dissatisfaction in perpetual approval voting, where decisions are made over time, and shows that under a 'bounded conflicts' condition, a sublinear growth of dissatisfaction is achievable using techniques from prediction with expert advice.
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.