Answer: Both the unrestricted and restricted variants are \(\mathrm{NP}\)-complete.
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe unrestricted manipulation problem is NP-complete. Sketch of proof. Membership to NP is straightforward: given com- municated scores, we can efficiently derive the possible unique devi- ation of each voter and compute the winner in the deviating profile.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(M\), supported ranking types \(T\) with rational masses \(\mu_t\), a tie-breaking order, and target \(x^\star\), does there exist a rational report \(y\in\mathbb{Q}_{\ge0}^{M}\) with \(\sum_c y_c=1\) whose induced type responses make \(x^\star\) the plurality winner? For the restricted variant, also require \(\frac12\sum_c|y_c-q_c|\le\alpha\), where \(q_c\) is the truthful plurality share.
Let \(M\) contain \(m\ge3\) candidates, with a fixed strict tie-breaking order and target \(x^\star\in M\). Write \(W(v)\) for the plurality winner of score vector \(v\) under this order.
A society is given by its support: a list \(T\) of \(\tau\) distinct strict ranking types, each with positive binary rational mass \(\mu_t\), where \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
Let \(a_t\) be type \(t\)'s top candidate and \(q_c=\sum_{t:a_t=c}\mu_t\) its truthful plurality share.
An admissible report is \(y\in\mathbb Q_{\ge0}^{M}\) with \(\sum_{c\in M}y_c=1\). Use the infinitesimal-voter response convention: the potential winners are \(P(y)=\operatorname*{arg\,max}_{c\in M}y_c\), including every tied maximizer, and the announced winner is \(w=W(y)\).
Let \(p_t(y)\) be type \(t\)'s favorite candidate in \(P(y)\). Its final ballot is \(b_t(y)=p_t(y)\) if \(p_t(y)\ne w\), and \(b_t(y)=a_t\) otherwise. All of its mass responds once, simultaneously, giving final scores \(f_c(y)=\sum_{t:b_t(y)=c}\mu_t\).
The unrestricted decision problem asks whether an admissible rational report satisfies \(W(f(y))=x^\star\). The restricted variant additionally takes binary rational \(\alpha\in[0,1]\) and requires \(\frac12\sum_{c\in M}|y_c-q_c|\le\alpha\).
For each variant, is this decision problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it NP-hard?
Finite unit-voter unrestricted poll manipulation with integer reports and the corresponding one-vote pivotal response rule is NP-complete. [Source](https://journals.sagepub.com/doi/pdf/10.3233/FAIA240908)
No verified complexity classification was located for the continuous problems defined above.
Both variants are \(\mathrm{NP}\)-complete, and hence NP-hard. The restricted variant is NP-hard already when \(\alpha=1\).
The proof below uses the continuous response convention directly.
For every nonempty \(P\subseteq M\), let \(w(P)\) be its highest-priority candidate under the fixed tie-breaking order. The response to a report depends only on \(P=P(y)\): each type chooses its favorite member of \(P\), then either votes for that candidate or retains its truthful ballot according to whether that favorite is \(w(P)\).
Every nonempty \(P\) is realizable by the rational report
\[ y_c= \begin{cases} 1/|P|,&c\in P,\\ 0,&c\notin P. \end{cases} \]
Thus unrestricted manipulation is exactly the problem of choosing a nonempty maximizer set whose induced response elects the target. In particular, it belongs to \(\mathrm{NP}\): a certificate is \(P\), and its induced scores can be calculated using exact rational arithmetic in time polynomial in \(m,\tau,L\).
We reduce from the standard NP-complete Exact Cover by 3-Sets problem, whose formulation is recalled in [Felsner’s dissertation, Section 2.6](https://page.math.tu-berlin.de/~felsner/Paper/diss.pdf).
An instance consists of a universe \(U=\{u_1,\ldots,u_{3k}\}\), with \(k\ge1\), and a family \(S_1,\ldots,S_n\) of three-element subsets of \(U\). The question is whether some \(k\) of these sets cover every element exactly once.
Define positive integer weights
\[ C=k+1,\qquad B=n+3C+1,\qquad H=B+k. \]
We first describe unnormalized weights. Dividing every weight by their total produces the required society.
Create candidates
\[ M=\{h,x,d,r\}\cup\{e_i:1\le i\le3k\}\cup\{s_j:1\le j\le n\}, \]
with target \(x^\star=x\). Under tie-breaking, \(h\) comes first, \(x\) second, and all remaining candidates follow in any fixed order. This can be implemented simply by assigning candidate names to positions in a predetermined tie-breaking order.
For each element, write \(V_i=\{s_j:u_i\in S_j\}\). Whenever \(V_i\) appears in a ranking, list its members in increasing index order.
The society has the following ranking groups. Every displayed prefix is completed by appending all omitted candidates in a fixed order.
| Group | Unnormalized weight | Ranking prefix |
|---|---:|---|
| Base donor | \(H-n\) | \(d\succ x\succ h\) |
| Selection donor, for each \(j\) | \(1\) | \(d\succ s_j\succ x\succ h\) |
| Guard | \(B\) | \(r\succ h\) |
| Fixed element group, for each \(i\) | \(B\) | \(e_i\succ h\) |
| Cover element group, for each \(i\) | \(C\) | \(e_i\succ V_i\succ h\) |
Here \(H-n=4k+4>0\). In every guard or element ranking, \(x\) lies below \(h\).
The total weight is
\[ D=H+(3k+1)B+3kC. \]
Normalize by \(D\). If two completed rankings coincide, merge them by adding their weights; this gives distinct ranking types without changing any response.
There are \(m=n+3k+4\) candidates and at most \(\tau=n+6k+2\) types. All weights and \(D\) are polynomially bounded in \(n+k\), so constructing the explicit rankings and binary rational masses takes polynomial time.
No ranking has \(x\) first. Consequently, \(q_x=0\).
Suppose \(J\subseteq\{1,\ldots,n\}\) indexes an exact cover. Then \(|J|=k\).
Choose the maximizer set
\[ P=\{h,x\}\cup\{s_j:j\in J\}. \]
The uniform report on \(P\) realizes this set, and its announced winner is \(h\).
Calculate final scores in unnormalized units:
Every candidate other than \(x\) therefore has score at most \(B\). Candidate \(x\) precedes all of them in tie-breaking except \(h\), whose score is zero. Hence \(x\) wins.
Let an arbitrary report elect \(x\), and write \(P=P(y)\) and \(w=W(y)\). Continue to use unnormalized scores.
Because \(q_x=0\), if \(x\notin P\), no type can cast a final ballot for \(x\). Similarly, if \(w=x\), no type switches to \(x\), and no truthful ballot supports it.
A candidate with score zero cannot win when the total score is positive. Thus success requires \(x\in P\) and \(w\ne x\). Since the only candidate preceding \(x\) in tie-breaking is \(h\), necessarily \(h\in P\) and \(w=h\).
With \(h\in P\), every guard or element type ranks \(h\) above \(x\), so none of these types votes for \(x\). Only donor groups can support it; their total weight is \(H\). Hence \(x\)’s final score is at most \(H\).
If \(d\in P\), every donor group chooses its top candidate \(d\), giving \(x\) score zero. Therefore \(d\notin P\).
If \(e_i\in P\), both corresponding element groups choose their top candidate \(e_i\). Its score is consequently at least
\[ B+C=B+k+1=H+1, \]
which exceeds \(x\)’s maximum possible score. Therefore every \(e_i\) is absent from \(P\).
Define \(J=\{j:s_j\in P\}\).
Since \(d\notin P\) while \(x,h\in P\), the base donor chooses \(x\). Selection donor \(j\) chooses \(s_j\) precisely when \(j\in J\), and chooses \(x\) otherwise. Thus
\[ \text{score}(x)=H-|J|. \]
The guard always votes for \(r\): if \(r\in P\), it chooses \(r\); otherwise it chooses \(h\) and retains its truthful ballot for \(r\). Candidate \(r\) therefore has score at least \(B\).
For \(x\) to win, it must have score at least \(B\). Consequently,
\[ H-|J|\ge B,\qquad\text{so}\qquad |J|\le k. \]
Suppose some \(u_i\) belongs to none of the selected sets. Candidate \(e_i\) and every member of \(V_i\) are then absent from \(P\).
Both element groups associated with \(u_i\) choose \(h\) as their favorite member of \(P\), and therefore retain their truthful ballots for \(e_i\). Candidate \(e_i\) receives at least \(B+C=H+1\), again defeating \(x\).
Thus the sets indexed by \(J\) cover all \(3k\) elements. Since each set has cardinality three,
\[ 3k=\left|\bigcup_{j\in J}S_j\right|\le3|J|\le3k. \]
Equality holds throughout. Hence \(|J|=k\), and their \(3k\) element occurrences represent \(3k\) distinct elements. Each element occurs exactly once: \(J\) is an exact cover.
This proves both directions of the polynomial reduction, establishing unrestricted NP-hardness.
For any two probability vectors \(y,q\),
\[ \frac12\sum_c|y_c-q_c| \le\frac12\sum_c(y_c+q_c)=1. \]
Therefore setting \(\alpha=1\) makes the distance restriction vacuous. The same reduction establishes restricted NP-hardness.
For the restricted problem, we must also justify that a successful rational report has a certificate of polynomial bit length.
Fix a nonempty proposed maximizer set \(P\). Introduce real variables \(y_c,z_c,h,\delta\), subject to:
Maximize \(\delta\).
This system has a feasible point with \(\delta>0\) exactly when there is a report within the distance bound whose maximizer set is exactly \(P\). Indeed, positive \(\delta\) makes every outside candidate’s score strictly smaller. Conversely, an exact maximizer set has a positive minimum outside gap whenever its complement is nonempty. If \(P=M\), there are no outside constraints and one may set \(\delta=1\).
The feasible polytope is bounded: the \(y_c,h,\delta\) variables lie in \([0,1]\), and \(0\le z_c\le2\alpha\le2\). Its coefficients are rational with polynomial encoding length, because the truthful shares \(q_c\) can be calculated with polynomial bit length.
If a positive feasible \(\delta\) exists, the maximum is positive and attained at a vertex. There are \(2m+2\) variables. A vertex is determined by that many linearly independent active constraints. After clearing denominators, their integer coefficients have polynomial bit length. Cramer’s rule and the determinant bound \(|\det A|\le (2m+2)!\,K^{2m+2}\), where \(K\) bounds coefficient magnitudes, give polynomial bit length for every vertex coordinate.
Thus every feasible maximizer set has a realizing rational report of polynomial bit length. Its response is unchanged because the maximizer set is unchanged. A verifier can check the report, its distance, and its final winner using exact rational arithmetic in polynomial time. The restricted problem belongs to \(\mathrm{NP}\).
The reduction above uses rational masses encoded by binary numerators and denominators. It also works if “binary rational” is intended to require dyadic masses.
To see this, before normalization choose the smallest power of two \(D'\ge D\). Distribute the additional integer weight \(D'-D\) among fresh auxiliary candidates in positive chunks of size at most \(B\). Each chunk has a ranking beginning with its auxiliary candidate followed by \(h\). Place all auxiliary candidates after \(x\) in tie-breaking, and append them below \(h\) in every original ranking.
Whenever \(h\in P\), each auxiliary group always votes for its own candidate, whose score is at most \(B\). The original groups’ relevant choices are unchanged, so both directions of the reduction remain valid. Since \(D'-D<D\), only polynomially many auxiliary groups are needed. Normalizing by \(D'\) yields dyadic masses.
Both decision problems are therefore \(\mathrm{NP}\)-complete, with respect to the explicitly represented support. Neither admits a running time polynomial in \(m,\tau,L\) unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves both variants correctly. The reduction uses the stated continuous response rule, and the restricted problem’s certificate argument handles strict inequalities and rational encoding. I found no mathematical gaps requiring repair.
The response depends only on the nonempty set \(P(y)\). Its highest-priority member determines the announced winner, and each ranking determines a unique favorite within that set. The numerical report values have no further effect.
The uniform report on any nonempty \(P\) has maximizer set exactly \(P\), including when \(P=M\). It is admissible and rational.
Consequently, the unrestricted certificate consisting of \(P\) is sufficient. Computing favorites, final rational scores, and the tie-broken winner takes polynomial time in the explicit input size. Exact summation of binary rational masses has polynomial bit complexity.
Assessment: Correct.
The cited source states the same Exact Cover by 3-Sets problem: a universe of size \(3k\), for a positive integer \(k\), and a family of three-element subsets, with the question whether there are \(k\) pairwise disjoint sets covering the universe. It identifies this problem as NP-complete. The source therefore supports the hardness premise used here. [Felsner’s dissertation, Section 2.6](https://page.math.tu-berlin.de/~felsner/Paper/diss.pdf)
The constants satisfy
\[
C=k+1,\qquad B=n+3k+4,\qquad H=n+4k+4.
\]
Thus the claimed base-donor weight is correct:
\[
H-n=4k+4>0.
\]
All other group weights are positive. The total donor weight is \(H\), the guard and fixed element groups contribute \((3k+1)B\), and the cover element groups contribute \(3kC\). Hence the stated total
\[
D=H+(3k+1)B+3kC
\]
is correct.
The displayed ranking prefixes contain no repeated candidates. Completing them gives strict rankings. An empty \(V_i\) causes no problem: the corresponding cover prefix becomes \(e_i\succ h\). Merging coincident rankings preserves all response behavior and gives distinct support types.
The candidate and support bounds are correct:
\[
m=n+3k+4,\qquad \tau\le n+6k+2.
\]
The weights, denominator, and explicit ranking lists have polynomial encoding size. Normalization preserves score comparisons and ties.
Assigning \(h\) and \(x\) to the first two positions respects a predetermined tie-breaking order; the construction does not require changing that order.
No ranking has \(x\) first, so \(q_x=0\).
Assessment: The construction is valid and polynomial.
For an exact cover \(J\), the proposed maximizer set contains \(h,x\), and the selected set candidates. Its announced winner is \(h\).
Each asserted response follows from the displayed prefixes:
Thus every competitor has score at most \(B\). The only candidate preceding \(x\), namely \(h\), has score zero. The tie-breaking conclusion is correct.
Assessment: An exact cover yields a successful admissible rational report.
Every exclusion and bound used in this direction is justified.
Forcing the announced winner. If \(x\notin P\), no favorite can be \(x\), and there are no truthful ballots for \(x\). If the announced winner is \(x\), types whose favorite is \(x\) retain their truthful ballots, again giving \(x\) zero. Since total final mass is positive, neither situation permits \(x\) to win.
Success therefore requires \(x\in P\) and an announced winner preceding \(x\). Only \(h\) precedes \(x\), so \(h\in P\) and the announced winner is \(h\).
Bounding target support. With \(h\in P\), every guard or element type has an available candidate preferred to \(x\), and none has truthful top \(x\). Only donors can support \(x\), giving the valid upper bound \(H\).
Excluding \(d\). If \(d\in P\), all donors choose \(d\). Since the announced winner is \(h\), they vote for \(d\), leaving \(x\) with zero. Hence \(d\notin P\).
Excluding element candidates. If \(e_i\in P\), both associated groups choose and vote for their truthful top \(e_i\). Its score is at least
\[
B+C=B+k+1=H+1,
\]
strictly exceeding the target’s upper bound. Thus all element candidates are absent from \(P\).
Bounding selected sets. Under these exclusions, the donor prefixes give exactly
\[
\operatorname{score}(x)=H-|J|.
\]
The guard votes for \(r\) whether or not \(r\in P\): it either chooses \(r\), or chooses \(h\) and retains \(r\). Therefore \(r\) has score at least \(B\), and success requires \(|J|\le k\).
Forcing coverage. If an element is uncovered, its own candidate and all incident set candidates are absent from \(P\). Both associated groups then choose \(h\) and retain their truthful element ballots. Their combined score is \(H+1\), which defeats \(x\). Thus every element is covered.
Finally,
\[
3k=\left|\bigcup_{j\in J}S_j\right|\le3|J|\le3k
\]
forces equality throughout. There are exactly \(k\) selected sets, and their \(3k\) element occurrences are distinct. This is an exact cover.
Assessment: The reverse implication covers arbitrary reports, including maximizer sets containing \(r\). The unrestricted NP-hardness proof stands.
The total variation bound between probability vectors is correctly calculated:
\[
\frac12\sum_c|y_c-q_c|\le1.
\]
Thus \(\alpha=1\) makes the restriction vacuous. The unrestricted reduction directly establishes restricted NP-hardness.
Assessment: Correct.
The proposed linear system correctly encodes the distance constraint: the inequalities force \(z_c\ge|y_c-q_c|\), and choosing equality gives the converse.
For \(P\ne M\), positive \(\delta\) is equivalent to a strict positive gap between every outside candidate and the common score on \(P\). Any report with exact maximizer set \(P\) has such a gap because its complement is finite.
The case \(P=M\) is explicitly handled: outside constraints disappear, and \(\delta=1\) is allowed.
The feasible region is a closed bounded polytope. The bounds on \(y_c,h,\delta\) hold as stated, and nonnegativity together with the sum constraint bounds every \(z_c\) by \(2\).
The vertex argument applies whenever a positive feasible \(\delta\) exists: a linear objective on a nonempty bounded polytope attains its maximum at a vertex. This remains valid for lower-dimensional polytopes. At a vertex, sufficiently many independent active constraints determine the coordinates.
There are \(2m+2\) variables. Clearing denominators gives integer constraint data of polynomial bit length. The stated determinant bound and Cramer’s rule therefore give polynomial-size rational coordinates.
The resulting report preserves \(P\), hence preserves the response and final winner. Its admissibility, distance, and winner can all be checked in polynomial time.
Assessment: The certificate-size argument is sufficient; strict maximizer inequalities do not create a gap.
The optional dyadic construction is also valid.
The added weights total \(D'-D\), and each fresh auxiliary candidate receives a positive chunk of at most \(B\). The number of chunks is polynomial because \(D\) is polynomially bounded.
Auxiliary groups have no truthful support for \(x\). Thus the initial argument forcing \(h\in P\) remains valid. Once \(h\in P\), each auxiliary group either chooses its own candidate or chooses \(h\) and retains its truthful ballot. Its final ballot always supports its own candidate.
Original rankings place auxiliary candidates below \(h\), so their relevant choices remain unchanged. Each auxiliary score is at most \(B\), and every auxiliary candidate follows \(x\) in tie-breaking. Both directions of the reduction therefore survive. Normalization by the power of two \(D'\) gives dyadic masses.
Assessment: Correct under either interpretation of binary rational masses.
Both variants are proved NP-complete for explicitly represented support. The conclusion excluding polynomial-time algorithms unless \(\mathrm P=\mathrm{NP}\) follows.
No additional mathematical clarification or repair is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.