Answer: \(\mathrm{NP}\)-complete
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe non-deterministic manipulation problem for Borda when tie-breaking with a random vote is NP- complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a rational background distribution \(b\) over rankings, strategic mass \(\delta>0\) with \(\sum_\rho b_\rho+\delta=1\), preferred candidate \(p\), and threshold \(q\), choose one common report \(\sigma\in\mathcal R(C)\) for the strategic mass. Is \(\max_{\sigma\in\mathcal R(C)}\Pr_{\nu^\sigma}[p\text{ wins under RV-Borda}]\ge q\), where \(\nu^\sigma_\rho=b_\rho+\delta\mathbf 1[\rho=\sigma]\) and a voter is sampled by mass before selecting their highest-ranked Borda co-winner?
Let \(C\) be a nonempty set of \(m\) candidates, \(p\in C\), and \(\mathcal R(C)\) the strict total orders on \(C\).
A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible rankings.
The input gives background masses \(b_\rho\ge0\) by this convention, a binary rational strategic mass \(0<\delta\le1\), and a binary rational threshold \(q\in[0,1]\), with \(\sum_\rho b_\rho+\delta=1\); unlisted background masses are zero.
The strategic mass chooses one common report \(\sigma\in\mathcal R(C)\), yielding \(\nu^\sigma_\rho=b_\rho+\delta\mathbf1[\rho=\sigma]\).
Apply Borda with scores weighted by mass, and let \(W(\nu^\sigma)\) be its full set of co-winners. RV tie-breaking samples a ranking according to \(\nu^\sigma\), including the strategic mass, and elects its highest-ranked member of \(W(\nu^\sigma)\).
Write \(P_p(\sigma)\) for the resulting probability that \(p\) wins, and \(L\) for the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether \(\max_{\sigma\in\mathcal R(C)}P_p(\sigma)\ge q\) in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite unweighted societies with one strategic voter, this threshold problem is \(\mathrm{NP}\)-complete ([Aziz et al., 2013](https://www.cse.unsw.edu.au/~sergeg/papers/AzizGMNW13aaai.pdf)).
No result for exactly the rational-mass, common-report problem above was located in the literature search.
The problem is \(\mathrm{NP}\)-complete. The finite unweighted problem embeds exactly into the stated rational-mass model by normalizing voter multiplicities. This preserves both Borda co-winners and RV winning probabilities, including the contribution of the strategic report.
Here “binary rational” means a rational whose numerator and denominator are encoded in binary.
We use the known result stated in the question: given an explicitly listed profile of nonstrategic voters, one strategic voter, a preferred candidate, and a rational threshold, deciding whether a strategic vote achieves that threshold under Borda with RV tie-breaking is \(\mathrm{NP}\)-complete. The paper defines RV by sampling from the submitted votes, so the strategic vote participates in tie-breaking. See its formal background and Theorem 9 in [Aziz et al. (2013)](https://www.cse.unsw.edu.au/~sergeg/papers/AzizGMNW13aaai.pdf).
Consider such an instance with candidate set \(C\), preferred candidate \(p\), nonstrategic rankings \(\rho_1,\ldots,\rho_{N-1}\), and threshold \(t\). Thus there are \(N\) voters after the strategic voter submits a report.
For each ranking \(\rho\), let \(k_\rho\) be its multiplicity among the nonstrategic votes. Construct the target instance by setting
\(b_\rho=k_\rho/N,\qquad \delta=1/N,\qquad q=t.\)
List only rankings with \(k_\rho>0\). These masses satisfy all required hypotheses:
\(b_\rho\ge 0,\qquad 0<\delta\le 1,\qquad \sum_\rho b_\rho+\delta=((N-1)+1)/N=1.\)
The support size is \(\tau\le N-1\). Each mass has an encoding of length \(O(\log(N+1))\). Grouping identical explicitly listed rankings and computing their multiplicities takes polynomial time in the source input length. The constructed input length is
\(O\bigl(\tau m\log(m+1)+(\tau+1)\log(N+1)+\operatorname{bits}(t)\bigr).\)
For a ranking \(\rho\), define \(\operatorname{pos}_\rho(c)\) as the position of candidate \(c\), starting at one, and define its Borda score by
\(s_\rho(c)=m-\operatorname{pos}_\rho(c).\)
Fix any strategic report \(\sigma\). In the unweighted election, candidate \(c\) has total score
\(S^\sigma(c)=\sum_\rho k_\rho s_\rho(c)+s_\sigma(c).\)
In the constructed rational-mass election, its score is
\(B^\sigma(c)=\sum_\rho b_\rho s_\rho(c)+\delta s_\sigma(c)=S^\sigma(c)/N.\)
Every candidate’s score is multiplied by the same positive factor. Consequently, the two elections have exactly the same full co-winner set for every report \(\sigma\).
Denote this common co-winner set by \(W^\sigma\). Define \(I_\rho(W)\) to equal one when \(p\in W\) and \(\rho\) ranks \(p\) above every member of \(W\setminus\{p\}\), and zero otherwise.
In the unweighted election, exactly
\(\sum_\rho k_\rho I_\rho(W^\sigma)+I_\sigma(W^\sigma)\)
of the \(N\) submitted votes elect \(p\) when sampled for RV tie-breaking. Therefore its winning probability is
\(\bigl(\sum_\rho k_\rho I_\rho(W^\sigma)+I_\sigma(W^\sigma)\bigr)/N.\)
In the rational-mass election, that probability is
\(P_p(\sigma)=\sum_\rho b_\rho I_\rho(W^\sigma)+\delta I_\sigma(W^\sigma),\)
which is the same quantity. This calculation also covers the case where \(\sigma\) coincides with a listed background ranking: their masses simply add.
Thus every report has exactly the same winning probability in both instances. In particular,
\(\max_\sigma P_p(\sigma)\ge q\)
holds precisely when the source instance is a yes-instance. This proves \(\mathrm{NP}\)-hardness.
A certificate is one ranking \(\sigma\), requiring \(O(m\log(m+1))\) bits.
Verification computes every candidate’s weighted Borda score, determines the full co-winner set, and evaluates
\(P_p(\sigma)=\sum_{\rho\text{ listed}}b_\rho I_\rho(W^\sigma)+\delta I_\sigma(W^\sigma).\)
All comparisons can be performed exactly. To see the bit complexity, let \(D\) be the product of the denominators of all listed masses, \(\delta\), and \(q\). Since these denominators are part of the input, \(D\) has \(O(L)\) bits. Multiplication by \(D\) makes every mass and the threshold integral. Scaled Borda scores have \(O(L+\log(m+1))\) bits because each is at most \(D(m-1)\).
Using schoolbook integer arithmetic, a conservative verification bound is
\(O\bigl((\tau+1)m(L+\log(m+1))^2\bigr)\)
bit operations. This includes constructing the common denominator, computing scores, scanning the listed rankings and the certificate, and comparing the probability with \(q\). Hence the problem belongs to \(\mathrm{NP}\).
Enumerating all reports gives a deterministic exact algorithm with running time
\(O\bigl(m!(\tau+1)m(L+\log(m+1))^2\bigr).\)
Neither verification nor enumeration expands rational masses into individual voters.
The reduction and verification establish \(\mathrm{NP}\)-completeness for exactly the stated support-encoded, rational-mass, common-report problem. A polynomial-time algorithm for all such inputs would therefore imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes \(\mathrm{NP}\)-completeness for the problem in USER_TASK. The reduction preserves the outcome for every strategic report, and the verification algorithm has polynomial bit complexity. No major or minor mathematical issues were found.
The prover states the source problem precisely: an explicitly listed unweighted background profile, one remaining strategic voter, a preferred candidate, and a probability threshold under Borda with RV tie-breaking.
The citation matches this statement. The paper’s formal background defines manipulation using one remaining vote and a probability threshold; its RV rule samples from submitted votes, so the strategic report participates. Theorem 9 states the required Borda hardness result. Thus the source theorem’s hypotheses match the reduction. [Aziz et al. (2013), formal background and Theorem 9](https://www.cse.unsw.edu.au/~sergeg/papers/AzizGMNW13aaai.pdf).
The source result is also expressly supplied by USER_TASK. The prover need not reproduce its hardness proof.
The construction
\[
b_\rho=\frac{k_\rho}{N},\qquad \delta=\frac1N,\qquad q=t
\]
is valid under the stated interpretation of binary rational encoding.
Each listed background mass is positive because only rankings with \(k_\rho>0\) are listed. Unlisted masses are zero. Since the source has one strategic voter, \(N\ge1\), and therefore
\[
0<\delta\le1,\qquad
\sum_\rho b_\rho+\delta=1.
\]
The threshold is inherited from the source probability threshold and lies in the required interval.
The encoding claims are correct:
Compression into support types causes no reduction-size problem: the source voters are explicitly listed, and the construction never enumerates all possible rankings.
Issues: none.
For every candidate \(c\) and every strategic report \(\sigma\), the prover correctly computes
\[
B^\sigma(c)=\frac{S^\sigma(c)}N.
\]
Because \(N>0\), this scaling preserves every score comparison, including equality. Consequently, the full co-winner sets coincide.
The argument quantifies over every report and imposes no additional condition on its placement of \(p\). It therefore preserves precisely the strategic choices permitted by USER_TASK.
Issues: none.
The indicator \(I_\rho(W)\) correctly describes when sampling ranking \(\rho\) elects \(p\): \(p\) must belong to \(W\) and appear above every other member of \(W\).
Since the elections have the same co-winner set, the unweighted probability is correctly expressed as
\[
\frac{\sum_\rho k_\rho I_\rho(W^\sigma)+I_\sigma(W^\sigma)}N.
\]
Substituting the constructed masses gives exactly the rational-mass probability written by the prover.
The strategic contribution is included once. If its report coincides with a background type, the two contributions correctly combine into that type’s total mass. There is no double-counting error.
Equality holds for every report, so the maxima and threshold decisions coincide in both directions. This establishes a polynomial many-one reduction and hence \(\mathrm{NP}\)-hardness.
Issues: none.
A ranking is a polynomial-size certificate. Its validity as a permutation can be checked within the stated verification bound.
The described verifier correctly:
The denominator argument is valid. The product \(D\) has \(O(L)\) bits because the sum of the input denominator lengths is bounded by \(L\). Each denominator divides \(D\), so scaling produces integer masses and an integer threshold.
The score bound
\[
0\le D B^\sigma(c)\le D(m-1)
\]
follows from nonnegative masses totaling one and Borda scores bounded by \(m-1\). Hence the asserted integer bit-length bound is correct.
Using schoolbook arithmetic, the conservative bound
\[
O\bigl((\tau+1)m(L+\log(m+1))^2\bigr)
\]
covers denominator construction, scaling, score computation, ranking scans, and exact comparisons. Thus membership in \(\mathrm{NP}\) is established.
Issues: none.
Enumerating the \(m!\) possible reports and applying the verifier gives the stated deterministic running time.
The formulas also cover the relevant boundary cases:
No expansion of rational masses into individual voters is required.
The claimed conclusion follows from the verified reduction and membership argument. The statement that a polynomial-time algorithm would imply \(\mathrm P=\mathrm{NP}\) is also correct.
Required clarification or repair: none.
⟨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.