| paper | Convergence of Iterative Scoring Rules |
| authors | Omer Lev, J. Rosenschein |
| venue | JAIR 2016 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 4 is a structural impossibility theorem about iterative dynamics, not a computational result under the stated ChoCo gate. The proposed continuous mass-cycle problem is coherent, but positive-mass cohort moves replace the paper’s unilateral pivotal deviations and require a newly specified update model. Since no qualifying named computational anchor remains, the paper is red.
fails bit a — no named computational result to mirror
The proposed question covers Theorem 4’s non-convergence constructions for scoring rules other than plurality and veto, while leaving Theorems 1 and 3, their convergence proofs, and the detailed tie-breaking analysis without an eligible computational anchor.
There is a real, but qualified, positive case. The paper’s strongest anchor is Theorem 4, proved in the paper:
Under the iterative procedure, with myopic voters using best-response strategies, no scoring rule apart from plurality and veto converges.
The theorem covers all other scoring rules, including \(k\)-approval, three-valued scoring rules, and strictly monotone scoring rules with more values. The proofs construct best-response cycles, generally from truthful initial states, and establish that the failure is independent of the deterministic tie-breaking rule.
A natural continuous mirror is the following.
Call it \(\textsc{Mass\text{-}Best\text{-}Response\text{-}Cycle}_{\infty}\). An instance contains candidates \(C\), a scoring vector \(\alpha\), a deterministic tie-breaking rule \(t\), a rational distribution \(\rho\) over truthful preference rankings \(a\in\pi(C)\), and an initial report state \(x^0=(x^0_{a,b})\), where \(x^0_{a,b}\) is the mass with truthful ranking \(a\) currently reporting ranking \(b\), and \(\sum_b x^0_{a,b}=\rho_a\).
The score of candidate \(c\) at state \(x\) is \(\mathrm{sc}_x(c)=\sum_{a,b}x_{a,b}\alpha_{\operatorname{rank}_b(c)}\), and \(w(x)\) is the candidate selected by \(t\) among the maximizers. A move transfers some rational mass \(q>0\) from \((a,b)\) to \((a,b')\). It is permitted only if the new winner is strictly preferred by \(a\), and \(b'\) is a best response for that mass transfer: among all alternative reports, it produces an \(a\)-maximal attainable winner. The question is whether a finite best-response cycle reachable from \(x^0\) exists. A solution is the explicit sequence of rational mass states returning to the same state, together with the witnessing transfers.
The regime is plausible: a large election or polling population may contain millions of agents but only a small collection of repeated preference types. Their current declared ballots can change in coordinated cohorts after poll information. Here \(m\) and the relevant type support are fixed or modest, while the population mass is large. Rankings remain integral; only the population is represented by rational masses. This is recognisably the paper’s object: the same scoring rule, truthful preferences, declared votes, deterministic tie-breaking, myopic improvement, and best responses.
The expected direction is transfer, not continuum-specific hardness. Every finite cycle in the paper can be normalized into a rational mass cycle by assigning each voter mass \(1/n\). Thus Theorem 4’s non-convergence survives in the mass model for every scoring rule other than plurality and veto. The interesting follow-up is whether cycle reachability, minimum cycle mass, or cycle length has a nontrivial complexity classification when the number of ranking types is small.
The weakest point is important: a nonatomic individual has zero influence on the winner. Therefore the literal one-voter move from the paper becomes vacuous in the continuum. The proposed model must interpret a move as a positive-mass cohort transfer. That is a genuine extension, although a defensible one given the paper’s poll-based motivation and its discussion of large elections. If the authors insist that only unilateral atomic deviations count, the mirror collapses.
The paper’s Theorem 3 supplies a useful boundary—proved there, it states that iterative veto with linear-order tie-breaking and best responses converges even from non-truthful states—but I would not make it a second anchor. Its finite proof uses bounds proportional to the number \(n\) of voters, and extending it to arbitrary fractional mass transfers requires a new potential or a careful treatment of infinitely many partial moves.
Finally, under the strict ChoCo source gate, this paper has no numbered NP-hardness, polynomial-time, FPT, approximation, or parameterized-complexity theorem. Theorems 1–4 are structural convergence results, with Theorem 1 cited from Meir et al. and Theorems 2–4 proved here. So this is a credible dynamic-population mirror, but not a fully eligible complexity-landscape anchor unless “computational result” is interpreted broadly enough to include convergence classification.
The negative case is unusually strong under ChoCo’s source gate: this paper contains no named computational result to mirror. Theorems 1–4 classify convergence of a finite best-response process. They do not define an input language, a search or decision problem, or a complexity measure. Theorem 4 is therefore not a polynomial-time/NP-hardness/approximation result; it is a structural theorem about a particular dynamic.
The proposed \(\textsc{Mass\text{-}Best\text{-}Response\text{-}Cycle}_{\infty}\) must consequently choose between two bad alternatives. If it preserves Theorem 4’s quantifiers—whether some preferences admit a cycle—it merely reformulates the theorem’s existential convergence classification. If it fixes \(x^0\) and asks whether a cycle is reachable, it introduces a new reachability problem absent from the paper. An explicit rational cycle is a certificate, but without a bounded input encoding or complexity claim it does not supply the computational anchor the programme requires.
There is also a deeper obstruction to the proposed population limit. Repeated preference types are perfectly plausible here; I would not object that voters lack a high-multiplicity interpretation, nor that identity is essential. The problem is the move. In the paper, one voter changes their report, and the move matters because that individual can be pivotal. In a nonatomic society, an individual has mass zero. Changing their report leaves every aggregate score unchanged:
\[ \mathrm{sc}_{\mu'}(c)=\mathrm{sc}_{\mu}(c) \]
for every candidate \(c\). Hence the winner cannot change, and the paper’s valid moves—precisely those that change the winner—disappear. The continuum does not merely require a harmless tie convention; it removes the strategic event on which the dynamics are built.
Duplicating voters does not resolve this cleanly. With \(K\) copies, a unilateral move has mass \(1/K\). The paper’s cycles often exploit exactly such vanishing score perturbations at ties. As \(K\to\infty\), the state records the limiting mass but loses the \(1/K\)-scale information determining which side of a tie the move lands on. The finite dynamics therefore have a singular, non-continuous limit.
The proponent’s best repair is to let a positive mass \(q>0\) move together. That is defensible as a new polling or cohort model, but it is not the paper’s one-voter best-response process. It replaces unilateral deviation with coordinated coalition deviation and introduces new primitives: which cohorts coordinate, what values of \(q\) are allowed, how cohorts are scheduled, and whether partial updates count. The paper itself treats simultaneous updates as a materially different model—indeed, it notes that convergence can fail even for plurality—so this cannot be dismissed as a routine population redefinition.
Taking whole type cohorts as the moving units does not help the mirror case. It produces a finite game among report cohorts with weighted scores; population mass becomes a weight, not a high-multiplicity relaxation of individual strategic behaviour. Allowing arbitrary partial transfers creates a different difficulty: the paper’s finite stabilization notion no longer applies, since one can make arbitrarily small updates and obtain infinite or Zeno-like trajectories. Theorem 3’s bound \(n(m-2)\) is not merely a proof artifact; it counts discrete voters traversing discrete preference levels. There is no corresponding bound when \(q\) has no positive minimum.
Thus Theorem 3 cannot rescue the proposal, and the same objection applies to the cited plurality result, Theorem 1. A continuous convergence theorem might be developed for a carefully chosen cohort or flow dynamic, but its interest would come from inventing that new dynamic, not from continuizing this paper’s computational problem. Theorem 4’s finite cycles can be embedded in such a model only by granting positive mass to coordinated blocks; that demonstrates a possible new model, not a worthwhile continuous mirror of the named result.
The honest weakness in this negative case is that a researcher could reasonably decide that poll-driven cohort dynamics are themselves worth studying. But under the stated ChoCo standard, that is a successor programme in mean-field voting dynamics, with a newly supplied update law and a newly supplied computational problem. This paper provides no eligible computational anchor, and its central unilateral dynamics collapse under the population limit. That is enough for a negative verdict.
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.