| paper | Complexity of Manipulation with Partial Information in Voting |
| authors | P. Dey, Neeldhara Misra, Y. Narahari |
| venue | IJCAI 2016 |
| filed under | voting · manipulation |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: The problem is in \(\mathrm{P}\) for every fixed \(k>1\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), fixed \(k>1\), rational masses \(\mu_p\) over partial-vote types \(p\) with at most four undetermined pairs, manipulator mass \(\lambda>0\), and preferred candidate \(c\), decide whether there exist a bloc vote \(v\in L(C)\) and nonnegative masses \(x_{p,\rho}\) satisfying \(\sum_{\rho\succeq p}x_{p,\rho}=\mu_p\) such that \(c\) is the unique \(k\)-approval winner of the completion masses plus mass \(\lambda\) voting \(v\).
A high-multiplicity partial-information \(k\)-approval election: observed types \(p\) carry masses \(\mu_p\), latent complete rankings \(\rho\succeq p\) receive completion masses \(x_{p,\rho}\), and a coordinated bloc of mass \(\lambda\) chooses one vote \(v\). The decision objective is to satisfy strict \(k\)-approval score inequalities for \(c\), equivalently to obtain positive minimum winning margin.
The mirror covers Theorem 1's weak \(k\)-approval NP-completeness and Theorem 7's Borda opportunistic co-NP-hardness, while leaving the other voting rules and remaining results untreated.
The strongest positive case is a high-multiplicity version of manipulation in which the population is continuous, while partial information remains genuine uncertainty rather than being replaced by averaged scores.
Let \(C\) be the candidate set and let \(\mathcal P\) be a finite set of recurring partial-vote types. A society is given by rational masses \(\mu_p\) for \(p\in\mathcal P\), with \(\sum_p\mu_p=1-\lambda\). The remaining mass \(\lambda>0\) is a homogeneous manipulator bloc: its members share the preferred candidate \(c\) and cast one coordinated vote \(v\). For each partial type \(p\), nature may distribute its mass among linear extensions \(\rho\succeq p\). Write \(x_{p,\rho}\ge 0\) for that mass, subject to
\[ \sum_{\rho\succeq p}x_{p,\rho}=\mu_p. \]
For a voting rule \(r\), the resulting score or winner is computed from the completion masses \(x\) together with the manipulator mass \(\lambda\) voting \(v\). Rational completion masses have the usual clone interpretation: clearing denominators gives a large finite electorate in which many voters share each partial type, but different clones of one partial type may have different admissible completions.
This is a plausible regime for a large election in which millions of voters fall into a few hundred or thousand recurring survey or privacy-preserving response patterns. The number of agents is much larger than the number of partial types. The manipulator is not literally one atomless individual; it is a campaign, union, or coordinated bloc of positive population mass. That is a necessary co-modification, since a singleton has zero influence in an atomless election.
My lead anchor is Theorem 1, proved in this paper:
“The WEAK MANIPULATION problem is NP-complete for the \(k\)-approval voting rule even with one manipulator for any constant \(k>1\), even when the number of undetermined pairs in each vote is no more than \(4\).”
The proof reduces from the NP-complete POSSIBLE WINNER problem for \(k\)-approval. Thus the hardness is not merely cited: it is established here, and it applies to fixed \(k>1\), one manipulator, and only four undetermined pairs per partial vote.
The corresponding continuous problem is:
\[ \mathsf{WM}^{\infty}_{k\text{-Approval}} \]
Given \(C\), the partial-type masses \(\mu\), a manipulator mass \(\lambda\), a preferred candidate \(c\), and the promise that every \(p\in\mathcal P\) has at most four undetermined pairs, does there exist a vote \(v\in L(C)\) and a feasible completion-mass assignment \(x\) such that \(c\) is the unique \(k\)-approval winner?
Equivalently, with
\[ S_x(a,v) = \sum_{p\in\mathcal P}\sum_{\rho\succeq p} x_{p,\rho}\mathbf 1[a\text{ is in the top }k\text{ positions of }\rho] + \lambda\mathbf 1[a\text{ is in the top }k\text{ positions of }v], \]
the question is whether
\[ S_x(c,v)>S_x(a,v) \qquad\text{for every }a\ne c. \]
A solution consists of the manipulator’s vote \(v\) and the completion masses \(x\).
I expect this mirror to be Class A. For fixed \(k\), enumerate the manipulator’s top-\(k\) set. Each partial type has only constantly many completions, so the remaining question is a rational linear program in the variables \(x_{p,\rho}\). The objective can be written as maximizing the winning margin
\[ \max_{v,x}\min_{a\ne c}\bigl(S_x(c,v)-S_x(a,v)\bigr). \]
The discrete NP-hardness plausibly disappears because its combinatorial core is the integral choice of one completion for every individual voter. In the continuous high-multiplicity regime, a mass of identical partial types may be split among their admissible completions. That is not an arbitrary fractionalization of a ranking: it is exactly what many indistinguishable clones permit. The resulting question remains weak manipulation under \(k\)-approval with the same partial-information semantics; only the population granularity has changed.
A second worthwhile anchor is Theorem 7, also proved here:
“The OPPORTUNISTIC MANIPULATION problem is co-NP-hard for the Borda rule even when the number of manipulators is one and the number of undetermined pairs in every vote is no more than \(7\).”
The reduction is from X3C. The theorem therefore establishes co-NP-hardness for a single manipulator and extremely limited incompleteness, specifically seven undetermined pairs per vote.
Its continuous mirror is:
\[ \mathsf{OM}^{\infty}_{\mathrm{Borda}}. \]
The input is \(C\), rational masses \(\mu_p\) over partial-vote types with at most seven undetermined pairs, manipulator mass \(\lambda\), and preferred candidate \(c\). A completion assignment \(x\) is called viable if there exists some manipulator vote \(v'\) for which \(c\) is the unique Borda winner. The question is whether there exists one vote \(v\) such that, for every viable completion assignment \(x\), \(c\) is the unique Borda winner when the manipulator bloc votes \(v\).
Formally, define
\[ B_x(a,v) = \sum_{p,\rho}x_{p,\rho}b(\rho,a)+\lambda b(v,a), \]
where \(b\) is the Borda score. We ask whether there exists \(v\in L(C)\) such that
\[ \left[ \exists v'\in L(C): B_x(c,v')>B_x(a,v')\ \forall a\ne c \right] \Longrightarrow \left[ B_x(c,v)>B_x(a,v)\ \forall a\ne c \right] \]
for every feasible \(x\). As in the paper, if no completion is viable, the condition is vacuously satisfied.
I would classify this second problem as a likely Class C boundary case rather than assuming that Theorem 7’s co-NP-hardness transfers. For fixed \(v\) and \(v'\), the conditions on \(x\) are linear programs, but opportunism quantifies over a union of viable polyhedra and asks for one manipulator vote robust against all of them. The fractional completion masses may dissolve the paper’s exact-cover integrality, while the robust viability quantifier may introduce genuinely continuum-specific hardness. The key questions are whether the Borda structure yields a polynomial robust algorithm, or whether the quantified completion polytope itself is hard.
These mirrors cover only Theorems 1 and 7. I would not claim that the paper’s other results automatically continuize. The strongest case is that Theorem 1 gives a clean, author-recognizable Class A transition: an NP-complete weak-manipulation problem becomes a mass-completion LP because its hardness was driven by individual completion choices.
The weakest point is the manipulator. A literal single manipulator has vanishing mass in an atomless society, so preserving influence requires a positive-mass coordinated bloc. That is a real extension, not a disguised direct restatement. It is nevertheless faithful to the paper’s manipulation question: the bloc still chooses one vote, the nonmanipulators still have partial orders, and weak or opportunistic success is defined by exactly the same winner predicates and quantifiers. A referee should therefore recognize these as legitimate continuous-population versions, while expecting the paper’s one-person hardness statements to be re-proved rather than assumed to survive.
I cannot honestly sustain the universal negative. Theorem 1 defeats it.
The proposed \(k\)-approval mirror is a legitimate high-multiplicity problem. If many voters share the same partial observation \(p\), their actual rankings may differ among the extensions of \(p\); rational masses \(x_{p,\rho}\) are exactly the aggregate form of assigning those clones different completions. With at most four undetermined pairs, each \(p\) has constantly many extensions. For fixed \(k\), enumerating the manipulator’s top-\(k\) set leaves a linear feasibility problem. That is not merely a change in the answer: it is a clean continuous relaxation of the paper’s named NP-complete problem, with an ordinary finite-clone interpretation.
The strongest objection is that \(p\) is an information state rather than a complete type. But it does not survive the natural repair: regard \((p,\rho)\) as the latent complete type and let the unknown society distribution range over all \(\nu\) satisfying \(\sum_{\rho\succeq p}\nu_{p,\rho}=\mu_p\). The resulting question is still a population-continuum problem with genuine partial information, and the same LP applies. A positive-mass coordinated bloc is also a natural continuous analogue of the paper’s coalition model; a singleton would indeed disappear in the atomless limit.
Theorem 7 is a weaker anchor for the proponent. Its X3C reduction relies on choosing whole completions of whole votes. Under mass splitting, “exact cover” becomes a fractional-cover condition, so the discrete reduction does not transfer. The opportunistic quantifier also retains the paper’s vacuous-YES pathology when no completion is viable. Those points undermine any claim that the theorem itself predicts the continuous complexity.
They do not, however, eliminate the mirror. The robust question—whether one bloc vote succeeds for every viable completion distribution—is well-defined and computationally nontrivial. It may be Class A, B, or C, but “the discrete reduction fractionalizes” is precisely the kind of boundary the programme is meant to investigate.
Thus the best negative case can downgrade Theorem 7, but it cannot defeat Theorem 1. A claim that no worthwhile continuous mirror exists in any scenario would be manufactured rather than supported by this paper.
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.