| paper | Detecting Possible Manipulators in Elections |
| authors | P. Dey, Neeldhara Misra, Y. Narahari |
| venue | ATAL 2015 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathsf{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4.7
Given \(C\), \(T=\mathcal{L}(C)\), rational \(\mu\in\mathbb{Q}_{\ge0}^{T}\) with \(\sum_t\mu_t=1\), rational \(\rho\le\mu\), and fixed STV tie-breaking, let \(x=\operatorname{STV}(\mu)\). Decide whether there exist \(y\ne x\) and rational \(\eta\ge0\) with \(\sum_t\eta_t=\sum_t\rho_t\), \(\eta_t>0\Rightarrow x\succ_t y\), and \(\operatorname{STV}(\mu-\rho+\eta)=y\).
Weighted high-multiplicity STV possible-manipulator detection: ranking types \(t\in T\) carry reported mass \(\mu_t\), suspected mass \(\rho\) is replaced by truthful mass \(\eta\), and the question is whether some target winner \(y\) results.
The STV proof's \(c=1\) manipulator has normalized mass \(1/N\to0\), while a positive-mass coalition can split across rankings and destroy the reduction's single-set choice; no transfer lemma is supplied.
fatal: False
The mirror covers the STV CPM hardness theorem and motivates the analogous maximin CPMW mirror from Theorem 4.5. It leaves the scoring-rule, Borda, \(k\)-approval, Bucklin, single-voter maximin, and search-result analyses unmirrored.
The strongest positive case is a high-multiplicity version of possible-manipulator detection for weighted STV, with maximin as a second, more exploratory mirror.
The population consists of many voters sharing complete ranking types. Let \(C\) be the candidates and \(T=\mathcal L(C)\) the ranking types. A society is a rational distribution \(\mu\) over \(T\). A suspected coalition is a subdistribution \(\rho\le\mu\), with mass \(\kappa=\sum_t\rho_t\). The reported society has current winner \(x\). A possible truthful coalition is another distribution \(\eta\) of mass \(\kappa\), replacing \(\rho\), subject to
\[ \eta_t>0\implies x\succ_t y. \]
Thus the action is not changing an individual’s identity but reallocating a mass of voters among complete preference types. The decision question is whether some \(\eta\) makes an alternative \(y\ne x\) win. All tie-breaking is inherited from the paper.
This is a credible regime for elections with party-line or ideological voting blocs: millions of voters, relatively few recurring ballots, and an audit asking whether a positive mass of one or more blocs could have truthfully preferred the current winner while strategically reporting votes that produced it. If \(\mu_t=n_t/n\), this is exactly the paper’s election after normalization. The paper itself identifies weighted elections as an immediate direction for future work, so the authors should recognize the population-weighted version as their problem’s natural high-multiplicity extension, not as a different voting model. The continuity is only in the population; rankings and the elimination rule remain discrete. [The paper’s stated results and weighted-election motivation are in the arXiv version.](https://arxiv.org/abs/1404.2367)
My lead anchor is Theorem 4.7, proved in this paper: “The CPM problem for STV rule is in \(\mathsf{NPC}\).” In full, CPM gives an election, its reported votes, and a specified coalition \(M\); it asks whether there exists a truthful preference profile for the members of \(M\), with every member preferring the current winner \(x\) to the resulting actual winner \(y\), such that replacing their reported votes by those preferences makes \(y\) win. The theorem proves NP-completeness already for coalition size \(c=1\), by a many-one reduction from X3C. The construction uses repeated blocks of voters and candidate gadgets encoding the sets in the exact-cover instance; the single suspected voter’s possible truthful ranking determines which \(b_i\) or \(\overline b_i\) is eliminated first. The reduction makes \(y\) win exactly when those choices encode an exact cover.
The corresponding continuous problem is:
\[ \textsf{CCPM}_{\infty}\text{-STV} \]
Given \(C\), rational population mass \(\mu\), rational suspected-coalition mass \(\rho\le\mu\), and fixed STV tie-breaking, let \(x=\operatorname{STV}(\mu)\). Decide whether there exist a candidate \(y\ne x\) and a rational mass distribution \(\eta\) with \(\sum_t\eta_t=\sum_t\rho_t\) such that \(x\succ_t y\) whenever \(\eta_t>0\), and
\[ \operatorname{STV}(\mu-\rho+\eta)=y. \]
A yes-certificate is \((y,\eta)\). I expect this to be Class B, with the X3C hardness transferring: the reduction’s combinatorics live in the candidates and the possible elimination paths, while its voters already occur in large repeated blocks. The technical issue is genuine: arbitrary \(\eta\) can split mass across several rankings, whereas the discrete theorem has one manipulator. A successful transfer therefore needs a rounding or gap lemma showing that a fractional truthful mass can be converted to one of the gadget’s discrete choices, or a scaled version of the construction that makes fractional splitting useless. If that fails, the problem may instead become continuum-specifically hard or even tractable; that uncertainty is a research question, not a defect in the mirror.
A second anchor is Theorem 4.5, also proved here: “The CPMW problem for maximin voting rule is in \(\mathsf{NPC}\), for \(c>1\).” CPMW additionally supplies the actual winner \(y\). The theorem proves NP-completeness by reducing from the restricted unweighted coalitional manipulation problem for maximin, whose hardness is cited from Xia et al. The reduction adds candidates \(w,d_1,d_2,d_3\), engineers pairwise margins using the McGarvey-style lemma, makes \(w\) the current winner, and sets \(z\) as the designated actual winner. The coalition is a possible coalition against \(z\) exactly when its votes can make \(z\) win in the source manipulation instance.
The continuous counterpart is:
\[ \textsf{CCPMW}_{\infty}\text{-Maximin} \]
Given \(C\), rational \(\mu\), suspected mass \(\rho\), and designated \(y\), let
\[ D_\nu(a,b)=\sum_t\nu_t \bigl(\mathbf 1[a\succ_t b]-\mathbf 1[b\succ_t a]\bigr) \]
and let \(M_\nu(a)=\min_{b\ne a}D_\nu(a,b)\). With \(x\) the current maximin winner under \(\mu\), decide whether there is a rational \(\eta\) of mass \(\sum_t\rho_t\), supported only on rankings with \(x\succ_t y\), such that \(y\) is the maximin winner under \(\mu-\rho+\eta\). The solution is the replacement mass distribution \(\eta\).
I would tentatively classify this as Class C, rather than claiming direct hardness transfer. Pairwise margins become linear in \(\eta\), so fractionalization may dissolve the discrete \(c\)-manipulator obstruction. But the winner condition still compares minima of many pairwise margins, and optimizing over complete rankings brings in the linear-ordering-polytope/separation boundary. Thus any remaining hardness would be caused by the structure of maximin and ranking space, not by named voters. With an explicit small type catalogue it may collapse to a finite optimization problem; with all rankings implicit, continuum-specific hardness is plausible.
The weakest point is the fractional coalition. In the paper, a coalition is a set of named voters whose truthful rankings may be chosen individually. In the mirror, \(\eta\) permits the mass to split among arbitrarily many rankings. That is exactly what a population model should permit, but it means neither discrete NP-hardness theorem automatically survives. The positive case therefore rests most securely on the legitimacy of the questions themselves and on STV’s unusually strong high-multiplicity structure; proving the expected complexity classifications is the substantive follow-up.
This scope deliberately covers Theorem 4.7 and Theorem 4.5 only. It does not claim that every P-result for Borda, scoring rules, or Bucklin has been continuized, nor that CPMS and CPMSW automatically inherit the same classification. Further natural questions are minimum suspicious mass, winner robustness under perturbations of \(\mu\), fixed-\(\tau\) algorithms, and the exact boundary between fractional rounding and genuinely continuum-specific hardness.
The strongest negative case is that neither cited theorem gives a clean *continuum limit* of the result it proves.
For the STV anchor, the hardness theorem is already for \(c=1\). In a normalized society of size \(N\), that coalition has mass \(\kappa=1/N\), which vanishes as multiplicity grows. The reduction’s essential choice is the ranking of one named voter: that ranking determines which of \(b_i\) and \(\overline b_i\) is eliminated first, thereby encoding one set in the X3C instance. The repeated voter blocks are scaffolding, not the manipulated population.
There are two ways to repair this, but each changes the object. If \(\kappa\) remains positive, the suspected coalition is now proportional to the electorate, and its truthful mass may split across many rankings. The single-set choice in the reduction becomes a fractional mixture of choices; the theorem supplies no reason that exact-cover behavior survives. If one forbids splitting and requires \(\eta\) to be a point mass, one has reintroduced an indivisible agent and lost the high-multiplicity interpretation. Taking \(\kappa=1/N\) instead merely stores the original discrete election in rational coordinates; it is compression, not a substantive continuum model.
The maximin anchor has the same problem in a less decisive form. Its theorem concerns \(c>1\) named manipulators, while the reduction engineers integer pairwise margins through individual rankings. A positive-mass version permits
\[ D_{\eta}(a,b)=\sum_t \eta_t \bigl(\mathbf 1[a\succ_t b]-\mathbf 1[b\succ_t a]\bigr) \]
to take convex combinations unavailable to a fixed number of indivisible voters. Conversely, keeping \(c\) fixed makes the coalition mass vanish. Thus the cited reduction neither transfers upward nor identifies a canonical nonvanishing limit.
These points do defeat the proponent’s claim that the paper’s NP-completeness results themselves motivate the proposed classifications. They do not, however, defeat the mirror as a research question. Elections plainly admit high-multiplicity regimes: party-line or ideological blocs are exactly recurring ranking types, and the paper’s own proposed extension to weighted elections points in this direction. The CPM and CPMW objectives do not track individual identity; they depend only on reported types, coalition mass, and whether a replacement population can make \(y\) win. That information survives aggregation.
Consequently, I cannot honestly support the universal negative. The best case against is that the proponent has shown a legitimate continuous-population problem, but has not shown that either cited hardness theorem is its correct discrete shadow. That is a substantial warning about the proposed reductions, not a convincing argument that no worthwhile continuous mirror exists.
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.