| paper | On the Convergence of Iterative Voting: How Restrictive Should Restricted Dynamics Be? |
| authors | S. Obraztsova, E. Markakis, M. Polukarov, Zinovi Rabinovich, N. Jennings |
| venue | AAAI 2015 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | no |
Theorems 6 and 7 have genuine computational character under a broad reading of computational dynamics. However, the proposed state \(\rho\)\) replaces one-voter unilateral moves by positive-mass transfers: an atomless individual is non-pivotal, whereas a positive-mass transfer requires new coalition or flow semantics. The resulting limit changes the strategic question, so neither anchor supplies an acceptable continuous-population mirror.
fails bit b-changes — the continuum limit changes the question
In the proposed \(\rho\)-model, a zero-mass individual cannot change the winner, while a positive-mass transfer is a coordinated bloc move with no canonical event granularity; the finite named-voter convergence argument therefore does not survive.
fatal: True
The proposed mirrors target Theorems 6 and 7 only; they leave Theorems 1–5, Theorem 4's maximality claims, and the remaining convergence and open-maximality questions untouched.
The strongest honest case is qualified but real. Strictly speaking, this paper has no named theorem proving membership in \(P\), NP-hardness, FPT, or a related complexity classification. Its named results concern termination of iterative voting processes. If the anchor rule requires a conventional complexity theorem literally, this paper has no qualifying anchor. If convergence is admitted as a computational-dynamics result, however, it supports a substantive continuous mirror.
My lead anchor is Theorem 6, proved in this paper. It says: if \(F\) is an integer positional scoring rule whose consecutive score gaps satisfy \(s_j-s_{j+1}\le 1\), then the Unit Upgrade procedure \((F,\mathrm{UU})\) is both function-monotone and set-monotone, specifically satisfying SM(b). Unit Upgrade lets a voter move their favourite potential winner exactly one position upward, preserving the relative order of all other candidates, and requires that candidate to become the new winner. The theorem covers Plurality, Veto, \(k\)-approval, and Borda.
The natural regime is a large consultation or polling population with a small candidate set and many repeated preference types. A type is a complete true ranking \(\theta\in T\subseteq L(C)\); \(\mu_\theta\) is its population fraction. Millions of respondents may therefore be represented by perhaps dozens or hundreds of ranking types. Reports remain strategic actions, so a state records \(\rho_{\theta,b}\), the mass of true type \(\theta\) currently reporting ballot \(b\). Initially, \(\rho_{\theta,\theta}=\mu_\theta\).
I would call the mirror Continuous Unit-Upgrade Path Length. Given \(C\), a unit-gap scoring rule \(F\), rational masses \(\mu\), and the truthful initial state \(\rho^0\), an update chooses a positive rational mass \(\delta\) of some state \((\theta,b)\), moves the designated favourite potential winner one position upward to \(b'\), and transfers that mass:
\[ \rho'_{\theta,b}=\rho_{\theta,b}-\delta,\qquad \rho'_{\theta,b'}=\rho_{\theta,b'}+\delta. \]
The move is legal only if the new winner is strictly preferred by \(\theta\) and is the winner after the transfer. The problem is to compute
\[ \Lambda_F^{\mathrm{UU}}(\rho^0) = \sup\{\text{length of a legal positive-mass update path from }\rho^0\}, \]
returning either a finite worst-case length and a terminal state, or \(\infty\) together with a nonterminating path certificate. This is the continuous version of the paper’s question: does every allowed improvement path converge?
This is a genuine population continuization. A rational mass vector \(\mu\) with denominator \(N\) expands to \(N\) cloned voters, and a transfer of mass \(1/N\) is exactly one individual deviation. Conversely, the continuous model permits fractional cohort transfers that have no finite-voter counterpart. The original voting rule, tie-breaking, truthful initialization, potential-winner notion, and Unit Upgrade restriction are preserved; only the individual update is replaced by the positive-mass update forced by atomlessness.
I would expect the unrestricted version to be continuum-specifically difficult, rather than to inherit discrete hardness. The finite proof relies on integer scores and a finite profile space. In the mirror, scores change by arbitrary rational amounts, so the monotone potential can increase through infinitely many smaller increments, including possible Zeno behaviour. A restricted whole-cohort or minimum-chunk variant may become tractable through the paper’s monotonicity certificates, but the unrestricted fractional version is a meaningful new boundary problem.
A second, worthwhile anchor is Theorem 7, also proved here. It says that \((\mathrm{Bucklin},\mathrm{UU})\) is set-monotone, specifically satisfying SM(b), and therefore converges by the paper’s general convergence theorem. The corresponding Continuous Bucklin Unit-Upgrade Termination problem has exactly the same instance and mass-transfer definition, but the winner is determined by normalized Bucklin scores and majority thresholds. Its expected classification is again continuum-specific: fractional transfers can move the population arbitrarily close to, or across, Bucklin’s majority boundaries, so the finite set-monotonicity argument may require genuinely new analysis.
These mirrors cover Theorems 6 and 7, not the whole paper. They are plausible because they preserve the paper’s actual object—restricted myopic voting dynamics—rather than merely replacing voter counts by normalized scores. The weakest point is decisive: the paper proves convergence for finite profiles, but does not prove a complexity theorem, and its integer-step arguments do not automatically survive fractional mass transfers. Thus this is a strong substantive mirror of the paper’s computational dynamics, but only a conditional ChoCo anchor under a strict complexity-theorem requirement.
The proponent’s concession is already damaging under the programme’s strict gate: the paper contains no named theorem about polynomial-time solvability, hardness, approximation, parameterized complexity, or an algorithm over a population distribution. Theorems 6 and 7 are finite-state convergence results. They may be computational-dynamics results in a broad sense, but they do not expose the kind of continuous optimization or complexity problem the programme is designed to chart.
More fundamentally, the proposed mirror changes the unit of action. In the paper, one named voter changes one ballot. In a nonatomic society, one individual has measure zero and cannot change the winner. Thus infinitesimal unilateral moves produce no dynamics at all: generically, every voter is non-pivotal and the process stops immediately. A positive-mass transfer fixes that degeneracy only by making a bloc move simultaneously. But that is not an individual improvement move; it is a new coalition or coordination model. Atomlessness does not force positive-mass coalitions. It forces one to choose between a vacuous unilateral dynamics and an additional collective-action assumption.
This defeats Theorem 6. The finite proof relies on unit ballot changes, integer score changes, and a bound on how many times a particular voter can upgrade a particular candidate. In the proposed state \(\rho_{\theta,b}\), there is no counterpart of “the” deviating voter. A type-mass can be split into arbitrarily many submasses, each making its own update, and the paper’s finite bound on consecutive moves by an individual no longer applies. The proposed quantity \(\Lambda_F^{\mathrm{UU}}\) therefore counts arbitrary batch boundaries rather than an invariant feature of the population trajectory. One collective transfer can be represented as one event, or as a sequence of smaller bloc transfers, depending on the added update convention.
The high-multiplicity bridge does not repair this. If transfers are restricted to multiples of \(1/N\), the model is simply the original finite election with \(N\) cloned voters. If arbitrary rational \(\delta\) is allowed, the transitions are no longer paths in any finite-\(N\) election. Taking \(N\) to infinity requires choosing a scaling for path length, a scheduling rule, and possibly update rates. Those choices define a new fluid or coalition dynamics; they are not supplied by Theorem 6.
Theorem 7 has the same defect, with an additional threshold problem. Normalized Bucklin scores and the majority threshold \(1/2\) are perfectly legitimate continuous quantities, so the objection is not that Bucklin cannot be rewritten over masses. The issue is that the proof’s set-monotonicity condition is indexed by named voters and uses a finite bound on consecutive moves by voter \(i\) in favour of candidate \(c\). That combinatorial object disappears in \(\rho\). Replacing it by type-level or bloc-level moves is a new restriction, and replacing it by a measurable flow requires specifying a behavioural law and rates. The resulting question would concern threshold-crossing flows, not the convergence theorem proved in the paper.
The strongest possible repair is therefore a model in which homogeneous voter types act as coordinated blocs, perhaps with fractional bloc sizes and a specified flow rule. That could be interesting in its own right. But it changes the strategic agents, the move semantics, and the convergence object. It is not a continuous-population mirror of the paper’s iterative voting process; it is a new mean-field voting-dynamics model. The alternative repair—retain individual moves—makes the continuum inert.
So both anchors fail for the same structural reason. The paper’s mathematical content is precisely about discrete, identity-indexed unilateral updates. Continuizing the population removes unilateral pivotality; restoring nontriviality requires adding coalition coordination or fluid dynamics not present in the paper. I would therefore reject these as ChoCo anchors, while acknowledging that the universal negative is not logically airtight: a carefully designed bloc-flow model might be worthwhile. Its interest, however, would come from the new aggregate dynamics, not from continuizing Theorems 6 or 7.
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.