| paper | Optimal Bounds for Dissatisfaction in Perpetual Voting |
| authors | Alexander Kozachinskiy, Alexander Shen, Tomasz Steifer |
| venue | AAAI 2025 |
| filed under | voting · theory |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given \(k,T,C,B\) and rational masses over persistent observable cohorts, with online current approval sets and no future revelation, construct or decide existence of an online rule choosing \(\theta_r \in [k]\) that guarantees \(\max_q \sum_r 1[\theta_r \notin A_q^r] \le B\) whenever every positive-mass \(k\)-tuple has empty approval intersection in at most \(C\) rounds.
A finite high-multiplicity online approval game with mass \(\mu\) over cohorts, one weight \(w_q\) per cohort, mass-weighted dissatisfaction probabilities for choosing each option, and objective minimizing the maximum cohort dissatisfaction under the type-level \(C\)-conflict condition.
For unrestricted adaptive trajectories, complete policy types may be exponentially numerous or require extra cohort-label and state assumptions, so the compression is regime-dependent rather than canonical.
fatal: False
The mirror directly covers Theorem 2, formulates a computational extension around Theorem 1, and preserves Proposition 1 as a cloning check; it leaves Theorem 3 and the Kolmogorov-complexity lemmas without separate mirrors.
There is a credible continuous mirror here, and the strongest anchor is Theorem 2, proved in this paper. It gives an explicit Exponential Weights strategy for perpetual approval voting and guarantees
\[ O\!\left(T^{1-\frac1{k+1}}(Ck\ln N)^{\frac1{k+1}}\right) \]
dissatisfaction per agent under the \(C\)-conflict condition. This is an algorithmic theorem, although the paper does not claim a P/NP classification.
The mirror is a continuous bounded-conflict perpetual approval game. There are \(k\) discrete options and \(T\) rounds. The population is divided into \(\tau\) behavioral types \(q_1,\ldots,q_\tau\), with rational masses \(\mu_q>0\) summing to one. A type is a complete description of an agent’s approval behavior over the horizon: its approval set \(A_q^r\subseteq [k]\) in every round, or, in the adaptive version, its complete nonanticipating approval policy. All agents of the same type are indistinguishable in every respect relevant to the game.
The game remains online. At round \(r\), the decision maker sees the current approval set of each type, but not future approval sets, and chooses one discrete option \(\theta_r\in[k]\). Type \(q\)’s dissatisfaction is
\[ D_q=\sum_{r=1}^T {\bf 1}[\theta_r\notin A_q^r]. \]
The objective is to minimize \(\max_{q:\mu_q>0}D_q\). This deliberately preserves the paper’s worst-agent objective; replacing it by average dissatisfaction would be a different problem.
The continuous conflict condition is the direct type-level analogue of the paper’s condition. For every ordered \(k\)-tuple of positive-mass types,
\[ \left|\left\{r:\bigcap_{j=1}^k A_{q_j}^r=\varnothing\right\}\right|\le C. \]
Repeated types are allowed in the tuple, corresponding to choosing several distinct agents from the same positive-mass class. Subsets of fewer than \(k\) agents are covered by padding the tuple with repetitions.
Call the problem CBPV\(_\infty\)-Guarantee:
Given \(k,T,C\), a finite rational mass vector \(\mu\), and online access to the current approval sets, output an online strategy whose worst-type dissatisfaction is at most \(B\) against every \(C\)-conflict reveal sequence, or report that no such strategy exists.
The continuous version of the paper’s Exponential Weights strategy is immediate and computationally meaningful. Maintain one weight \(w_q\) per type, initially \(1\). At round \(r\), define
\[ \delta_{r,\theta} = \frac{\sum_{q:\theta\notin A_q^r}\mu_q w_q} {\sum_q\mu_q w_q}. \]
Choose an option minimizing \(\delta_{r,\theta}\), then multiply \(w_q\) by \(1+\varepsilon\) precisely for the dissatisfied types. The update costs \(O(k\tau)\) arithmetic operations per round, hence polynomial time in \(k,\tau,T\) and the mass encoding length, independent of the raw number \(N\) of agents.
The same potential argument suggests a genuinely continuous improvement. Let
\[ \Lambda=1+\ln(1/\mu_{\min}), \qquad \mu_{\min}=\min_q\mu_q. \]
Because the total initial weight is normalized to one, the paper’s \(\ln N\) term is replaced by \(\ln(1/\mu_q)\). Thus the same proof yields the bound
\[ O\!\left( T^{1-\frac1{k+1}} (Ck\Lambda)^{\frac1{k+1}} \right), \]
with the trivial bound \(T\) used when \(Ck\Lambda>T\). For balanced types, \(\mu_{\min}=1/\tau\), so the dependence becomes logarithmic in the number of types rather than in the number of agents. This is exactly the high-multiplicity computational gain: a society with millions of cloned agents is processed through \(\tau\) mass coordinates.
The natural regime is a large recurring population—say, residents of a city or campus choosing one public activity or service each week. There may be millions of agents but only a modest number of approval-behavior classes: childcare constraints, accessibility needs, work schedules, health restrictions, and so on. Preferences can change from week to week, as in the paper, while remaining identical within a cohort. If \(\mu_q=a_q/A\), clearing denominators and taking \(H a_q\) agents of each type gives a finite election with \(N=HA\) agents and exactly the same decisions and dissatisfaction values. This is rational-clone fidelity, not an average-welfare reinterpretation.
I would classify the constructive CBPV\(_\infty\) problem as Class A: the mass implementation of Theorem 2 is polynomial in the compressed population description. The exact minimax version—finding the best possible online strategy rather than one with the Theorem 2 guarantee—remains open. The paper’s Theorem 1, also proved here, naturally generates the next question: can its sharper \(T^{1-1/k}C^{1/k}\operatorname{polylog}\) bound be achieved in polynomial time in \(\tau,T\) and the mass encoding? The paper explicitly says its strategy is obtained only through brute-force finite-game analysis, so this would be a real computational extension rather than a restatement.
As a fidelity check, Proposition 1 should survive cloning: replicate every agent in its construction \(H\) times. The number of named agents becomes \(HkM\), but the number of behavioral types remains at most \(kM\), and the same \(M^{k-1}/k\) worst-type lower bound remains. Thus continuization does not erase the paper’s temporal conflict obstruction.
The weakest point is the dynamic notion of type. If agents’ approval histories are genuinely idiosyncratic, then their complete behavioral trajectories become distinct types and \(\tau\) may grow with \(T\), possibly exponentially. Also, the future must remain hidden: giving the decision maker the full trajectory distribution would destroy the paper’s online-information model. The proposed mirror therefore requires a real high-multiplicity regime of recurring behavioral cohorts, not merely a population that happens to be large. That is a limitation of the scenario, but not a defect in the formulation: the option remains discrete, the adversary remains online, conflict remains type-tuple based, and the objective remains worst-agent dissatisfaction.
The strongest case against is that perpetual voting is not naturally a population-of-types problem. In the paper, an agent is not characterized by a ballot or a stable preference. The adversary may change that agent’s approval set every round, and the objective tracks the same agent’s cumulative dissatisfaction. Two agents who have identical approval sets today may have different past dissatisfaction and completely different future behaviour. Grouping them by their current approval set therefore loses exactly the identity information the problem uses.
To repair that, one must make a type the agent’s complete trajectory, or its complete nonanticipating policy. That creates a serious trilemma. If trajectories are explicit, there may be \(2^{\Theta(T)}\) possible types and essentially one type per agent; the purported continuous input contains the original temporal data in full. If trajectories are known to the decision maker, the paper’s online-information model has largely disappeared. If they are hidden, then the mass vector does not tell the decision maker which agents share future behaviour, so the proposed aggregation is unavailable without persistent cohort labels or an additional state-transition model. A compact finite-state version would be a new model of population dynamics, not a direct continuization of the paper’s adversarial game.
This is the best objection to the proposed mirror of Theorem 2. It does not, however, defeat the strongest version of that mirror. One can posit observable recurring cohorts whose members have identical, possibly hidden, approval policies. Then the exponential-weights update really does aggregate exactly:
\[ \sum_q \mu_q w_q \]
replaces the sum over cloned agents, and the worst-type objective remains the worst-agent objective. The \(\ln N\) term can genuinely become \(\ln(1/\mu_{\min})\), and rational cloning gives exact finite-population fidelity. A city or campus with recurring behavioural cohorts is a defensible high-multiplicity regime. Thus Theorem 2 survives the negative case; dismissing it as merely an average-welfare reformulation would be wrong.
Theorem 1 faces the same trajectory problem, but its proposed continuous question is still legitimate under that cohort model: can the sharp nonconstructive bound be attained by an online strategy polynomial in the number of cohorts? The paper explicitly identifies efficient constructivity as unresolved. The fact that arbitrary trajectory types may destroy compression is a limitation on the regime, not a reason the restricted question is ill-posed.
Proposition 1 is weaker as an anchor. It is a lower-bound proposition, not a computational optimization result. Cloning its agents preserves the lower bound, but each exceptional temporal schedule becomes a separate type, so the construction has \(kM\) types and offers no meaningful population compression. That makes it a fidelity check rather than an independent continuous-computational contribution. Still, it does not invalidate a mass version.
So the negative case can credibly say that general perpetual voting has no canonical static continuous society: its essential object is an online population of temporally individuated behaviours. But the requested universal conclusion is not defensible. A recurring-cohort model is both recognizable as high multiplicity and faithful enough for Theorem 2—and probably for the sharper Theorem 1 question. The honest negative verdict is therefore weak: Proposition 1 is not a strong anchor, but the principal Theorem 2 mirror survives.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.