Iterative Calculus of Voting under Plurality

The honest positive case is narrow but real. This paper has no numbered theorem asserting NP-hardness, membership in \( \mathrm{P} \), FPT, or a comparable complexity classification. Thus it is not itself a ChoCo complexity result. Nevertheless, it supplies an unusually natural continuous-population object, and its exact probability calculations make a credible computational mirror possible.

The strongest regime is a large online electorate or multi-agent platform with \(N\) extremely large but only \(\tau\ll N\) recurring utility templates. A type must be a complete cardinal utility vector \(u\in\mathbb Q^m\), not merely an ordinal ranking, because Proposition 1 uses differences \(u_j-u_t\). Type \(r\) has mass \(\mu_r\), with \(\sum_r\mu_r=1\). Agents of that type have identical utilities, abstention convention, and tie-breaking behavior. The analyst knows \(\mu\), but agents still observe only the current vote-share vector, exactly as in the paper.

A finite profile with \(N_r\) agents of type \(r\) embeds as \(\mu_r=N_r/N\), while a rational \(\mu\) can be expanded back into a finite high-multiplicity electorate. The continuous object is therefore the population distribution, not a fractional outcome or a lottery. Vote shares are masses: \(s_j\) is the mass currently voting for candidate \(j\).

My lead anchor is Proposition 9, proved in this paper: “Poisson pivotal probabilities can be jointly calculated and with no explicit calculation of \(f_P\) or \(F_P\).” Proposition 4, also proved here, supplies the exact Poisson formulas. I would mirror them with the following problem.

Poisson-Pivotal ICV\(_\infty\). An instance consists of candidates \(J=\{1,\ldots,m\}\), explicit utility types \(u^1,\ldots,u^\tau\), rational masses \(\mu_1,\ldots,\mu_\tau\), a current rational vote-share vector \(s\), a rational Poisson population parameter \(\lambda>0\), a fixed tie-breaking order, and a precision request \(\varepsilon>0\).

For every \(j\in J\) and nonempty \(T\subseteq J\setminus\{j\}\), let \(K=J\setminus(\{j\}\cup T)\), and define \(\alpha_{j,T}(s,\lambda)\) and \(\beta_{j,T}(s,\lambda)\) exactly as in Proposition 4:

\(\alpha_{j,T}=\sum_{d\ge0} f_P(d,s_j\lambda)\prod_{t\in T}f_P(d+1,s_t\lambda)\prod_{k\in K}F_P(d,s_k\lambda)\),

and

\(\beta_{j,T}=\sum_{d\ge0} f_P(d,s_j\lambda)\prod_{t\in T}f_P(d,s_t\lambda)\prod_{k\in K}F_P(d-1,s_k\lambda)\).

For type \(u^r\), calculate the expected-reward increment

\(\Delta_j(u^r;s,\lambda)=\sum_{\varnothing\ne T\subseteq J\setminus\{j\}}\left(\frac{\alpha_{j,T}}{|T|}+\beta_{j,T}\right)\frac{\sum_{t\in T}(u^r_j-u^r_t)}{|T|+1}\).

The type chooses the candidate maximizing \(\Delta_j\), or abstains if every increment is nonpositive. The next population state is \(s'_j=\sum_{r:a_r=j}\mu_r\). A valid solution returns an \(\varepsilon\)-accurate \(s'\), the induced winner set, and certificates for any type whose best action is separated from its second-best action by more than the numerical error.

This is recognizably the paper’s problem: plurality remains plurality; agents maximize the same pivotal expected reward; making and breaking multiway ties remain present; updates are simultaneous; and agents need not know \(\mu\). Only the representation of the electorate changes from an individual list to a mass vector. The mass vector is precisely what the paper’s vote-share and Poisson formulations already treat as the relevant state.

I expect this problem to be Class A in the fixed-\(m\), explicit-type, approximation setting, probably FPT in \(m\) and polynomial in \(\tau\), input precision, and \(\log(1/\varepsilon)\), subject to a careful Poisson-tail analysis. Proposition 9 gives the key type-independent recurrence, while aggregation over types costs only \(O(\tau m)\) once the pivotal quantities are known. Crucially, the running time need not scale with \(N\). With \(10^9\) agents represented by \(100\) utility types, the computation remains a type-level computation.

That classification is not proved by the paper. The unresolved questions are whether the infinite sums admit a bit-complexity bound polynomial in binary \(\lambda\), whether the \(2^m\) family of tie sets can be avoided when \(m\) is variable, and how exact ties should be represented. Those questions could reveal an \(m\)-parameterized barrier or even continuum-specific hardness. They do not undermine the mirror; they are exactly the computational questions the paper leaves open.

My secondary anchor is Proposition 7, “ICV asymptotic convergence,” proved here, though its proof invokes the cited Condition 1 from Palfrey and Chen–Xia. The proposition states that, as \(N\to\infty\), the probability of reaching an iteration with unchanged vote shares tends to \(1\). Corollary 1, proved as a consequence, gives bounds on the number of iterations, and Corollary 2 says that the limiting equilibrium is strongly Duvergerian with probability tending to \(1\).

The corresponding problem is Asymptotic ICV-Convergence\(_\infty\). Its input is the same finite type distribution, an initial mass state \(s^0\), a precision \(\varepsilon\), and an iteration bound \(D\). Using the update map \(\Phi_{\mu,\lambda}\) defined above, return a terminal mass state \(s^\star\) and a threshold \(\lambda_0\) such that, for every \(\lambda\ge\lambda_0\),

\(\|\Phi_{\mu,\lambda}^{D}(s^0)-s^\star\|_1\le\varepsilon\),

and

\(\|\Phi_{\mu,\lambda}^{D+1}(s^0)-\Phi_{\mu,\lambda}^{D}(s^0)\|_1\le\varepsilon\).

The solution must also report the limiting winner set and whether the terminal state is strongly Duvergerian, meaning \(s^\star_1\ge s^\star_2>0\) and \(s^\star_h=0\) for all \(h\notin\{1,2\}\). Under the paper’s genericity assumptions, the expected bounds are \(D\le m-1\) in the all-tied and one-leader cases, \(D=1\) with two viable leaders, and \(D\le g\) when the initial state has \(g\) viable leaders.

The asymptotic, margin-promised version should also be Class A: once the relevant utility gaps and vote-share ordering are separated from zero, the continuous population can be updated for a bounded number of rounds independent of \(N\). The exact finite-\(\lambda\) version is more interesting. The paper explicitly says cycles cannot be theoretically excluded for small electorates, so deciding convergence, finding the least convergence threshold, and certifying an SDE may become continuum-specific hard. That is a useful boundary problem rather than a defect.

The authors would likely recognise both mirrors. The paper already discusses non-atomic ICV games, treats vote shares as probabilities, introduces \(\lambda\) as an electorate-size parameter, and bases every update on a type’s cardinal utility vector. This is not a tractability-motivated weakening that removes strategic voting; it is the high-multiplicity form of the same simultaneous best-response process.

The weakest point is that the paper itself has already made much of the population “continuous” in the analytic sense. Moreover, exact repeated cardinal utility vectors may be more plausible for templated software agents or platform cohorts than for human voters drawn from the paper’s continuous Beta distributions. Finally, Proposition 9 is an efficient calculation claim, not a formal polynomial-time theorem, and Proposition 7 is a convergence theorem, not a complexity classification. So this paper cannot honestly be presented as already supplying a ChoCo Class A result.

It can, however, supply a strong starting point: a faithful mass-input version of its pivotal update and convergence problems, with a clear high-multiplicity interpretation and an immediate computational agenda concerning precision, parameterized dependence on \(m\), convergence thresholds, finite-population rounding, and the precise point at which small-electorate cycles become hard.