Research map / Learning theory and algorithms / Submodular and game algorithms
Optimal Bounds for Dissatisfaction in Perpetual Voting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies perpetual approval voting and shows that sublinear per-voter dissatisfaction is achievable under a bounded-conflicts condition, with a tight T^{1-1/k} bound via Kolmogorov complexity and an explicit exponential-weights voting rule.
Problem
Designing perpetual approval voting methods so that no voter is dissatisfied too many times across many decisions, given adversarially changing preferences.
Approach
Introduces a 'bounded conflicts' condition (every small group of agents is in conflict only a bounded number of rounds) under which sublinear dissatisfaction is possible; gives a tight non-constructive bound via Kolmogorov complexity and an explicit exponential-weights voting rule that multiplies a voter's weight by (1+eps) on each dissatisfaction.
Key results
- Under C-conflict condition, a strategy guarantees dissatisfaction at most T^{1-1/k} C^{1/k} (ln N ln C)^W, sublinear when C=o(T) and k constant.
- A matching lower bound of T^{1-1/k}/k-type dissatisfaction holds for C=1 with N=kM agents and T=M^k rounds, showing the exponent is tight.
- An explicit exponential-weights rule achieves O(T^{1-1/(k+1)} (C k ln N)^{1/(k+1)}) dissatisfaction; simple majority and compassionate strategies (e.g., Perpetual Equality) suffer dissatisfaction of order T under the 1-conflict condition.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the Kolmogorov-complexity strategy under a C-conflict condition | Perpetual voting with k options, N agents, and T rounds · C-conflict perpetual voting | maximum dissatisfaction: T^{1 - 1/k}·C^{1/k}·(ln N·ln C)^{W} | Helped |
| Use the explicit Exponential Weights Algorithm under a C-conflict condition | Perpetual voting with k options, N agents, and T rounds · C-conflict perpetual voting | maximum dissatisfaction: O(T^{1 - 1/(k+1)} · (C·k·ln N)^{1/(k+1)}) | Helped |
| Use Approval Vote, choosing the most-approved option without considering history | Perpetual voting · 1-conflict perpetual voting, 2 options, N = 2T + 1 agents | maximum dissatisfaction: T | Hurt |
| Use a compassionate strategy, including Perpetual Equality | Perpetual voting · 1-conflict perpetual voting, 2 options, N = T agents | maximum dissatisfaction: ⌊T/2⌋ | Hurt |
| Restrict the adversary to 1-conflict plays with N = k·M and T = M^k | Any decision-maker strategy · 1-conflict perpetual voting, k options | maximum dissatisfaction: M^{k-1}/k = T^{(k - 1)/k}/k | Hurt |
Surprising findings
- Simple majority and Perpetual Equality cannot achieve o(T) dissatisfaction even under the bounded conflicts condition with k=2 and C=1.
Limitations
- The optimal Kolmogorov-based strategy is not computationally efficient and it is unknown whether it is attainable by efficient strategies.
- The explicit exponential-weights rule has a weaker dependence on T (exponent 1-1/(k+1)) than the optimal bound.
- Analysis assumes a constant number of options k.
Experimental setup
Metrics: maximum per-agent dissatisfaction
Baselines: Simple Majority (Approval Vote) Perpetual Equality
Builds on: Exponential Weights Algorithm prediction with expert advice Lackner perpetual voting Romashchenko-Zimand inequality
Closest papers by meaning
- Proportional Decisions in Perpetual Voting (AAAI 2023 · similarity 0.88)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.85)
- Computing Voting Rules with Improvement Feedback (ICML 2025 · similarity 0.84)
- Participation Incentives in Approval-Based Committee Elections (AAAI 2024 · similarity 0.84)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.83)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.