| paper | Generalized scoring rules and the frequency of coalitional manipulability |
| authors | Lirong Xia, Vincent Conitzer |
| venue | SIGECOM 2008 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Neither named theorem is a computational result under the supplied gate: both provide asymptotic probability statements rather than an algorithm with a complexity guarantee, a hardness result, or a computational formulation used to solve instances. The proposed \(\mathrm{CM\text{-}Force}_\infty\) is a sensible high-multiplicity extension of the underlying manipulation problem, but that cannot cure the failure of bit (a). The finite-sample fluctuation arguments also do not transfer unchanged to a deterministic continuum.
fails bit a — no named computational result to mirror
The proposed mirror covers the underlying coalitional-manipulation feasibility problem for generalized scoring rules, but not the paper's finite-sample frequency bounds, the \(n^p\) threshold regimes, or the generalized-scoring-rule characterization results.
The strongest positive case is a high-multiplicity version of the paper’s coalitional-manipulation problem. It is a faithful mirror, although not a clean ChoCo anchor under the strictest source gate: the paper contains no named NP-hardness, polynomial-time, FPT, or similar complexity theorem. Its relevant named results are asymptotic probability theorems.
Let \(C\) be the alternatives, \(T=L(C)\) the ranking types, and \(r=GS(f,g)\) a generalized scoring rule. A continuous society is a rational mass vector \(\mu\) over \(T\), with \(\sum_t\mu_t=1-\alpha\), where \(\alpha\) is the mass of a manipulating coalition. The coalition chooses a distribution \(\nu\in\Delta(T)\) of reported rankings. The resulting generalized score vector is
\[ S(\mu,\nu)=\sum_{t\in T}\mu_t f(t)+\alpha\sum_{t\in T}\nu_t f(t). \]
The coalition’s objective is to make a designated alternative \(c^\star\) win under \(g\). A solution is a distribution \(\nu\) satisfying \(g(S(\mu,\nu))=c^\star\); infeasibility means that \(c^\star\) cannot be made to win. Equivalently, define
\[ W_\alpha(\mu)=\{g(S(\mu,\nu)):\nu\in\Delta(T)\}; \]
the continuous instance is open if \(|W_\alpha(\mu)|>1\), and closed otherwise.
This is the natural regime of a very large election or consultation with millions of voters but relatively few distinct rankings: for fixed \(m\), there are \(\tau=m!\) possible types, while each type has high multiplicity. The coalition is a coordinated bloc with positive mass, not an atomless individual. Clearing denominators recovers the finite problem exactly: \(N\mu_t\) gives the nonmanipulator counts and \(N\alpha\nu_t\) gives the coalition’s integral reports. Thus \(\nu\) is an aggregate of many ordinary ballots, not a fractional ballot submitted by one voter.
My lead anchor is Theorem 2, proved in this paper. It states that if \(GS(f,g)\) is compatible with a partition \(\mathcal K\), the random-vote distribution \(\pi_{\mathcal K}\) has equal expected \(f\)-scores within each block of \(\mathcal K\), and \(c\in W_{\mathcal K}(f,g)\), then for fixed \(m\), any \(h>0\), and \(1/2<p<1\), whenever the number of manipulators is at least \(hn^p\) but \(o(n)\), there is a manipulator profile \(P^M\) such that
\[ \Pr\bigl(GS(f,g)(P^{NM}\cup P^M)=c\bigr) > 1-t_m e^{-u_m n^{2p-1}}, \]
for constants \(t_m,u_m>0\) independent of \(n\). Here \(W_{\mathcal K}(f,g)\) consists of outcomes attained by distinctive profiles whose generalized-score components are pairwise unequal within every block of \(\mathcal K\).
The corresponding continuous problem is:
\[ \mathrm{CM\text{-}Force}_\infty: \]
given \((f,g,\mathcal K,\mu,\alpha,c^\star)\), decide whether there exists \(\nu\in\Delta(T)\) such that \(c^\star\in W_\alpha(\mu)\), and return such a \(\nu\) if one exists.
For the balanced population \(\mu=(1-\alpha)\pi_{\mathcal K}\), the theorem’s construction has a direct continuum interpretation. The background population contributes equal expected scores within each block of \(\mathcal K\); a distinctive coalition distribution creates strict within-block score differences, so the coalition’s intended outcome survives in the exact continuum. For the common neutral rules covered later by Proposition 3 and Corollary 2—positional scoring rules, Copeland, STV, maximin, and ranked pairs—this reaches every alternative.
This problem is plausibly Class A when \(T\) is explicit or \(m\) is fixed. For any fixed winning order-region of \(g\), feasibility is a linear program in the variables \(\nu_t\). With rankings represented implicitly, the LP has exponentially many variables and its separation problem is
\[ \max_{t\in L(C)} y\cdot f(t), \]
which is exactly the kind of pricing question that makes the mirror computationally interesting. For standard scoring rules this may be tractable; for general succinct generalized scoring rules it could instead produce a continuum-specific Class C problem.
A second, weaker anchor is Theorem 1, also proved here. Under the paper’s i.i.d. random-vote assumptions, if \(r=GS(f,g)\) has order \(k\), \(p<1/2\), \(h\) is fixed, and \(|M|\le hn^p\), then the probability
\[ T(r,m,n,\pi,|M|) \]
that the random manipulation instance is open satisfies
\[ T(r,m,n,\pi,|M|) \le t_{m,p,h} n^{p-1/2}, \]
for a constant \(t_{m,p,h}\) independent of \(n\).
Its continuous counterpart is:
\[ \mathrm{CM\text{-}Open}_\infty: \]
given \((f,g,\mu,\alpha)\), decide whether there are two coalition distributions \(\nu,\nu'\in\Delta(T)\) with
\[ g(S(\mu,\nu))\ne g(S(\mu,\nu')). \]
This is an exact mass version of the paper’s closed/open definition. It is again an LP or finite union of LPs under explicit type representation. The paper’s probability bound would then become a separate question about the measure of open societies \(\mu\) under a specified distribution over the population simplex.
That last qualification is the main weakness. The \(n^{-1/2}\) phenomenon in Theorem 1 comes from sampling fluctuations of a finite electorate. In an exact continuum, the society is \(\mu\), not a random empirical sample, so those fluctuations disappear. To retain the paper’s frequency statement one must add a law over societies, or study the volume of the boundary tube around winner regions. That is a meaningful extension, but not a theorem already supplied by the paper.
The authors would nevertheless recognize the proposed mirror: it keeps the same generalized scoring rule, the same coalition, the same possible-winner question, and the same aggregate score vector. The paper’s \(\pi\) is a sampling distribution, not itself a continuous society, and its appendix on fractional votes concerns finite voters rather than a population represented by type masses. Thus this is not a novelty collision.
My honest bottom line is therefore: the paper supports a precise and credible high-multiplicity mirror, strongest for \(\mathrm{CM\text{-}Force}_\infty\), probably Class A in explicit form and potentially an interesting pricing problem in implicit ranking form. But because its named results are asymptotic-probability results rather than complexity classifications, it should be recorded as a promising extension—not as a fully qualified ChoCo computational anchor.
The strongest negative case is that both anchors lose the phenomenon they claim to mirror when the population is made continuous.
The paper’s named results are asymptotic probability theorems, not computational results. Theorem 1 and Theorem 2 quantify the effect of finite-sample fluctuations in an \(n\)-voter profile; they do not establish a complexity classification, an algorithm, or even a new computationally hard problem. The proposed \(\mathrm{CM\text{-}Force}_\infty\) silently replaces those theorems with a different deterministic possible-winner problem. That problem may be legitimate, but it is not the continuous form of the paper’s principal result. Under a strict ChoCo source gate, this is already fatal.
For Theorem 1, the coalition mass is
\[ \alpha_n=\frac{|M|}{n}=O(n^{p-1})\longrightarrow 0 \qquad (p<1/2). \]
With fixed \(m\), generalized score vectors are bounded, so such a coalition changes the normalized score vector by only \(O(\alpha_n)\). The rule \(g\) is constant away from finitely many score-order hyperplanes. Hence a generic continuous society has a positive margin from every decision boundary, and an asymptotically vanishing coalition cannot change its winner. Exact openness survives only on the boundary itself, which has measure zero under any ordinary smooth distribution over societies.
The paper’s \(O(n^{p-1/2})\) bound comes from something the continuum has removed: finite-election fluctuations of order \(n^{-1/2}\). One can preserve the result only by placing an \(n\)-dependent random law on \(\mu\), concentrated in an \(n^{-1/2}\)-neighbourhood of the boundary. But that is effectively a stochastic finite-sample or noise model, not a high-multiplicity population limit.
The same issue is sharper for Theorem 2. There,
\[ \alpha_n=\frac{|M|}{n}=\Theta(n^{p-1})\longrightarrow 0 \qquad (1/2<p<1). \]
The theorem works because the coalition’s unnormalised signal \(n^p\) dominates the background’s random fluctuation of order \(\sqrt n\). In an exact continuum with society \(\mu=(1-\alpha)\pi_{\mathcal K}\), there is no fluctuation to dominate: the background scores are exactly balanced, and the coalition’s effect is simply deterministic. For a generic fixed society, however, the score margin is constant while the coalition mass tends to zero, so the coalition cannot force arbitrary alternatives. A fixed positive coalition mass would give a sensible control problem, but it would no longer mirror the theorem’s \(o(n)\) regime.
The proposed LP therefore demonstrates a reasonable adjacent high-multiplicity manipulation problem, not a continuization of the paper’s probability results. Its ranking-type formulation may indeed be computationally interesting, especially with implicit permutations and pricing. That is the point at which the negative case becomes weak: the programme explicitly permits a paper’s mathematical problem to yield a worthwhile high-multiplicity problem even when its particular theorem does not survive unchanged.
So the defensible negative verdict is narrow: the paper supplies no qualified ChoCo computational anchor, and its two main asymptotic anchors degenerate because their content is precisely the interaction between sampling noise and coalition size. A universal claim that no worthwhile continuous mirror exists is not honestly sustainable, because \(\mathrm{CM\text{-}Force}_\infty\) remains a sensible high-multiplicity computational problem if adjacent extensions are admissible.
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.