| paper | Iterative voting and acyclic games |
| authors | R. Meir, M. Polukarov, J. Rosenschein, N. Jennings |
| venue | AI 2017 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 7
statement extracted from the paper’s text layer
Given candidates \(C\), a rational ranking-type distribution \(\mu\in\mathbb{Q}^{\pi(C)}\), per-capita fixed scores \(\hat{\rho}\in\mathbb{Q}_{\ge 0}^{C}\), and an initial report state \(x=(x_{t,a})\) with \(x_{t,a}\ge 0\) and \(\sum_{a\in C}x_{t,a}=\mu_t\), decide whether every legal sequence of positive-mass cohort direct replies terminates at a state with no legal move. Moving all mass \(x_{t,a}>0\) from report \(a\) to \(b\) is legal exactly when \(b\) is the post-move lexicographic winner and \(b\succ_t f(x)\); if termination is guaranteed, compute a terminal state and a worst-case move bound.
Types are complete rankings \(t\in\pi(C)\); mass is \(\mu_t\); state variables are report masses \(x_{t,a}\) satisfying \(\sum_a x_{t,a}=\mu_t\); scores are \(S_x(c)=\hat{\rho}(c)+\sum_t x_{t,c}\); and the computational objective is universal termination and terminal-state computation under cohort direct replies.
The unit-score invariants in Theorem 7 do not automatically extend to fractional cohort moves, and Proposition 9 shows that weighted direct-reply dynamics can cycle; the analogue may therefore lack convergence or a polynomial bound.
fatal: False
It covers Theorem 7's unweighted Plurality with lexicographic tie-breaking and direct-reply convergence; it leaves weighted Plurality, randomized tie-breaking, custom game forms, and the other acyclicity results untouched.
The strongest honest case is qualified: this paper has a natural population mirror, but under ChoCo’s strict anchor rule it does not provide a compliant positive case.
The paper contains no named NP-hardness, polynomial-time, parameterized, approximation, or LP/separation result. Its numbered results concern acyclicity and convergence. The strongest usable anchor is therefore Theorem 7, proved in this paper:
For unweighted Plurality with lexicographic tie-breaking, \(f^{PL}_{\hat s}\) has the finite direct-reply property: every path of direct replies converges, from every initial profile, after at most \(m^2n^2\) steps. Hence Plurality is order-free acyclic.
The cited \(O(mn)\) improvement is not proved here and is not my anchor.
A natural mirror would be Continuous Lexicographic-Plurality Direct-Reply Convergence. Let \(C\) be the candidates and \(T=\pi(C)\) the ranking types. The population is a rational distribution \(\mu\in\mathbb Q^{T}\), with \(\sum_t\mu_t=1\). A state is \(x=(x_{t,a})\), where \(x_{t,a}\) is the mass of type \(t\) currently reporting candidate \(a\), satisfying
\[ \sum_{a\in C}x_{t,a}=\mu_t. \]
With a per-capita fixed-score vector \(\hat\rho\), candidate \(c\)'s score is
\[ S_x(c)=\hat\rho(c)+\sum_{t\in T}x_{t,c}, \]
and the winner is the lexicographic maximizer.
A continuous direct reply selects a positive-mass cohort \(x_{t,a}\), moves it to \(b\), and is legal exactly when:
The question is whether every such sequence reaches a mass Nash equilibrium, namely a state with no legal positive-mass direct reply. A computational version asks whether this universal-convergence property holds and, if it does, computes a terminal state and a bound on the number of cohort moves. The expected direction is Class A, if the score-monotonicity invariants behind Theorem 7 extend to mass blocks; otherwise the continuum may produce a genuinely new Class C obstruction.
The regime is plausible: a large election, platform poll, or referendum with many voters but relatively few repeated rankings. The type count is \(\tau=m!\), while the population may be millions; \(\mu_t=n_t/n\) is exactly the high-multiplicity representation of \(n_t\) identical voters. This is not a claim that the paper’s small-agent examples already have a continuum interpretation. It changes the scenario to the one the programme considers natural: many exchangeable voters over a small effective support of ranking types.
The authors would likely recognise the model as their Plurality game with truthful states, direct replies, lexicographic tie-breaking, and fixed scores, with the electorate replaced by a distribution of repeated voter types. It covers only Theorem 7’s unweighted Plurality result, not the weighted examples, custom game forms, or random tie-breaking results.
The weakness is substantial. In an atomless population, a literal unilateral deviation has zero effect on the winner, so almost every non-tied state becomes trivially stable. The positive-mass cohort move is therefore a necessary co-modification, but it turns the paper’s one-voter dynamics into a block or coalition dynamics. Theorem 7 does not establish convergence for that model; it only motivates the question.
Thus the best positive verdict is: natural and author-recognisable high-multiplicity mirror, with a credible tractability conjecture, but no qualifying computational anchor in the paper itself. Under the strict ChoCo rubric, that means the paper should not be presented as a fully compliant positive case.
Theorem 7 is not a qualifying computational anchor. It proves finite convergence in a finite individual game, with a bound \(m^2n^2\); it gives neither a complexity classification nor an algorithmic optimization problem. The terminal state is scheduler-dependent and generally non-unique. Replacing \(n\) explicit voters by a rational distribution \(\mu\) therefore does not automatically produce a ChoCo problem.
The proposed mirror also faces a real modelling dichotomy. If the continuum preserves the paper’s individual better-reply semantics, one agent has mass zero and cannot change any score. Except at exact score ties, unilateral deviations therefore have no effect, so the dynamics and Nash condition become generically trivial. The discrete proof’s crucial unit increment, such as the \(+1\) and \(-1\) score changes behind its invariants, disappears in the limit.
If instead a positive mass \(\delta\) is allowed to move, the move is a coalition or bloc deviation, not an individual iterative-voting step. Allowing arbitrary \(\delta\) creates a continuous transition system in which a type can be split indefinitely, so “number of moves” has no intrinsic meaning. Requiring an entire type-mass to move avoids that problem only by producing a finite weighted Plurality bloc game. That is a different model, and the paper itself shows why the distinction matters: Proposition 9 gives cycles of direct replies for weighted voters with weights \(1,2,3\), even from the truthful state.
Thus duplicating voter types does not repair the anchor. Individual moves vanish in the limit; collective moves turn the problem into weighted or coalition dynamics. A continuous reachability question could certainly be invented, but it would require a new move semantics and a new computational problem absent from the paper. Theorem 7 therefore supplies no worthwhile, author-recognisable continuous-population mirror under the programme’s strict anchor rule.
This is a strong negative case, though not a formal proof that no imaginative reinterpretation could ever be useful.
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.