Answer: Borda and \(\mathrm{Copeland}_{\alpha}\) for every fixed rational \(\alpha\in[0,1]\) are \(\mathrm{NP}\)-complete, even with dyadic rational masses.
Theorem 5.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateT ◦Borda-MANIPULATION is NP-hard. PROOF. Suppose that we are given an instance C of 3-SAT with s variables. Note that this instance can be encoded by a binary vector (σ1, . . . , σℓ), where ℓ= `2s 3 ´ , as described in the construc- tion of T: σi = 1 if and only if C contains the i-th 3-variable clause with respect to the lexicographic order. We will now con- struct an instance of our problem with m = ℓ+ 2s + 4 candidates c1, c2, . . . , cm.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), the paper’s tie-breaker \(T\), a rule \(F\in\{\mathrm{Borda},\mathrm{Copeland}_{\alpha}\}\), a rational-mass society \(\mu\) containing a designated strategic atom \(b\delta_{R^{\star}}\) with \(b>0\), and the bloc’s strict preference order \(\succ\), decide whether some ballot \(L\in\mathcal{L}(C)\) makes \(T(W_F(\mu-b\delta_{R^{\star}}+b\delta_L))\succ T(W_F(\mu))\), where \(W_F\) is the set of maximum-score candidates.
Let \(C=\{c_1,\ldots,c_m\}\), with \(m\geq2\), have this fixed label order, and let \(\mathcal L(C)\) denote its strict linear orders. A society \(\mu\) is given by its support: the list of the \(\tau\) ranking types with positive mass, each mass a binary rational, summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length.
The input designates a binary rational \(b\) with \(0<b\leq\mu(R^{\star})\). The strategic bloc has sincere preference order \(\succ=R^{\star}\) and must replace its entire mass by one ballot \(L'\in\mathcal L(C)\); it cannot split its mass among ballots.
Use Borda with scores weighted by mass, or \(\mathrm{Copeland}_{\alpha}\) with pairwise majorities determined by mass, for a fixed rational \(\alpha\in[0,1]\). Write \(W_F(\nu)\) for the nonempty set of maximum-score candidates under society \(\nu\).
Fix the following deterministic tie-breaker \(T\). For nonempty \(S\subseteq C\), return its least-indexed candidate unless \(m=\binom{2s}{3}+2s+4\) for an integer \(s>0\), \(c_m\in S\), and \(S\) contains exactly one of \(c_{\ell+2i-1},c_{\ell+2i}\) for every \(i\in\{1,\ldots,s\}\), where \(\ell=\binom{2s}{3}\).
When these conditions hold, enumerate all three-element subsets of the literals in the order \(x_1<\neg x_1<\cdots<x_s<\neg x_s\) lexicographically, interpreting each subset as a disjunctive clause \(\phi_j\). Set \(x_i\) true exactly when \(c_{\ell+2i-1}\in S\). Return \(c_m\) if this assignment satisfies \(\bigwedge_{j\leq\ell:\,c_j\in S}\phi_j\), and otherwise return the least-indexed member of \(S\); the empty conjunction is true.
The decision problem asks whether some \(L'\in\mathcal L(C)\) satisfies \(T(W_F(\mu-b\delta_{R^{\star}}+b\delta_{L'}))\succ T(W_F(\mu))\), where \(\delta_R\) is unit mass at ranking \(R\).
For Borda, and separately for \(\mathrm{Copeland}_{\alpha}\) for each fixed rational \(\alpha\in[0,1]\), is this decision problem in \(\mathrm P\) or \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and \(L\).
For finite unweighted societies, beneficial manipulation by one voter under this \(T\) is \(\mathrm{NP}\)-hard for Borda and for every rational \(\alpha\in[0,1]\) under \(\mathrm{Copeland}_{\alpha}\). [Source](https://www.ifaamas.org/Proceedings/aamas2011/papers/BP2_B42.pdf)
No result settling the exact rational-mass formulation above was located in the literature checked.
The problem is \(\mathrm{NP}\)-complete for Borda and for \(\mathrm{Copeland}_{\alpha}\) for every fixed rational \(\alpha\in[0,1]\). Hardness holds even when all masses are dyadic rationals.
The proof uses the unweighted hardness result supplied in the question and an explicit reduction preserving every possible manipulation.
Use the following given result: beneficial manipulation by one designated voter under the specified \(T\) is \(\mathrm{NP}\)-hard for Borda and for each fixed rational \(\alpha\in[0,1]\) under \(\mathrm{Copeland}_{\alpha}\). These are Theorems 5.2 and 5.5 of [Obraztsova, Elkind, and Hazon](https://www.ifaamas.org/Proceedings/aamas2011/papers/BP2_B42.pdf).
Let an instance of that problem consist of an explicitly listed profile \(P=(R_1,\ldots,R_n)\), with designated manipulating voter \(i\). Set \(R^{\star}=R_i\). Preserve the candidate set and its label order.
Let \(N\) be the smallest power of two with \(N\geq n\). Choose any ranking \(A\), and let \(\overline A\) be its reverse. Define
\[ \text{} \]
\(b=\dfrac1N,\qquad \eta=\dfrac{N-n}{2N},\qquad \mu=\dfrac1N\sum_{j=1}^{n}\delta_{R_j}+\eta\delta_A+\eta\delta_{\overline A}.\)
Merge identical ranking types and omit zero-mass entries.
All masses are nonnegative, and their sum is \(n/N+2\eta=1\). Moreover, \(\mu(R^{\star})\geq1/N=b>0\). Thus this is a valid target instance. Its support size satisfies \(\tau\leq n+2\).
All masses have denominator dividing \(2N\), so they are dyadic and have \(O(\log(n+1))\) bits. The output length is
\(O\bigl((n+2)m\log(m+1)+(n+2)\log(n+1)\bigr).\)
Sorting the explicit rankings and merging equal ones takes polynomial time.
For any replacement ballot \(L'\), let \(P^{L'}\) denote the unweighted profile obtained by replacing \(R_i\) with \(L'\). The manipulated rational society is exactly
\(\mu^{L'}=\mu-b\delta_{R^{\star}}+b\delta_{L'} =\dfrac1N\sum_{j=1}^{n}\delta_{P^{L'}_j} +\eta\delta_A+\eta\delta_{\overline A}.\)
Consequently, the strategic mass corresponds to precisely one source voter and submits precisely one replacement ballot.
Write \(s_P(c)\) for the unweighted Borda score of candidate \(c\), using scores \(m-1,\ldots,0\).
If \(c\) occupies position \(r\) in \(A\), it occupies position \(m+1-r\) in \(\overline A\). Its two Borda scores therefore sum to
\((m-r)+(r-1)=m-1.\)
It follows that, for every candidate \(c\),
\(s_{\mu^{L'}}(c)=\dfrac1N s_{P^{L'}}(c)+\eta(m-1).\)
Multiplication by the positive constant \(1/N\) and addition of a candidate-independent constant preserve all score comparisons and equalities. Hence
\(W_{\mathrm{Borda}}(\mu^{L'})=W_{\mathrm{Borda}}(P^{L'}).\)
The same argument applies to the sincere profile, giving \(W_{\mathrm{Borda}}(\mu)=W_{\mathrm{Borda}}(P)\).
For distinct candidates \(a,c\), define the unweighted majority margin
\(d_P(a,c)=|\{j:a\text{ precedes }c\text{ in }R_j\}| -|\{j:c\text{ precedes }a\text{ in }R_j\}|.\)
Define the rational majority margin by replacing voter counts with masses. The rankings \(A\) and \(\overline A\) have opposite orientations on every pair, so their equal masses cancel. Therefore
\(d_{\mu^{L'}}(a,c)=\dfrac1N d_{P^{L'}}(a,c).\)
Every pairwise win, loss, and tie is preserved. Thus each candidate has exactly the same Copeland score in both elections, for every \(\alpha\in[0,1]\). In particular,
\(W_{\mathrm{Copeland}_{\alpha}}(\mu^{L'}) =W_{\mathrm{Copeland}_{\alpha}}(P^{L'}),\)
and the sincere winning sets are also equal.
For either rule, both the sincere and manipulated winning sets are preserved. The candidate labels are unchanged, so applying the fixed \(T\) gives identical outcomes in the source and target instances.
The sincere preference order is also unchanged. Consequently, for every \(L'\),
\(T(W_F(\mu^{L'}))\succ T(W_F(\mu)) \quad\Longleftrightarrow\quad T(W_F(P^{L'}))\succ T(W_F(P)).\)
This proves a polynomial-time many-one reduction and establishes \(\mathrm{NP}\)-hardness for both rules.
A certificate is a permutation \(L'\) of the candidates, of length \(O(m\log(m+1))\).
First, \(T\) is polynomial-time computable. Test the possible integers \(1\leq s\leq m\) for the required candidate-count equation. If its exceptional conditions hold, enumerate the \(\ell=\binom{2s}{3}\leq m\) literal triples in lexicographic order and evaluate the selected clauses under the assignment specified by the winning set. This evaluates a supplied assignment; it requires no satisfiability search.
All election calculations can also be performed exactly in polynomial bit complexity. Let \(D\) be the product of the denominators of the input masses and \(b\). Their total encoding length is at most \(L\), so \(D\) has \(O(L)\) bits. Define the integers
\(q_j=D\mu(R_j),\qquad B=Db.\)
For Borda, the manipulated score multiplied by \(D\) is
\(\sum_{j=1}^{\tau}q_j\bigl(m-\operatorname{rank}_{R_j}(c)\bigr) -B\bigl(m-\operatorname{rank}_{R^{\star}}(c)\bigr) +B\bigl(m-\operatorname{rank}_{L'}(c)\bigr).\)
For Copeland, put \(\sigma_R(a,c)=1\) when \(a\) precedes \(c\), and \(\sigma_R(a,c)=-1\) otherwise. The manipulated majority margin multiplied by \(D\) is
\(\sum_{j=1}^{\tau}q_j\sigma_{R_j}(a,c) -B\sigma_{R^{\star}}(a,c)+B\sigma_{L'}(a,c).\)
Taking its sign determines the pairwise result exactly. Since \(\alpha\) is fixed rational, Copeland scores can subsequently be compared using its fixed denominator.
These integers have \(O(L+\log(m+1))\) bits. Compute both outcomes, apply \(T\), and compare their positions in \(R^{\star}\). This verifies the certificate in polynomial time, proving membership in \(\mathrm{NP}\).
Let \(H=L+\lceil\log_2(m+1)\rceil+1\). Using schoolbook integer arithmetic, the following conservative bit-operation bounds hold.
| Rule | Verification of one certificate | Deterministic decision by enumerating all ballots |
|---|---:|---:|
| Borda | \(O((L+\tau m)H^2)\) | \(O((L+\tau m+m!\,m)H^2)\) |
| \(\mathrm{Copeland}_{\alpha}\) | \(O((L+\tau m^2)H^2)\) | \(O((L+\tau m^2+m!\,m^2)H^2)\) |
For enumeration, compute the original Borda scores or majority margins once, then update them for each ballot. The bounds include exact rational preprocessing and evaluation of \(T\).
Thus both classifications are resolved: both problems are \(\mathrm{NP}\)-complete, and a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument is correct and resolves both requested classifications. No major or minor mathematical issues were found. The reduction preserves every available replacement ballot, and the certificate verification and stated running-time bounds are valid.
The prover explicitly uses the unweighted hardness premise supplied in USER_TASK. The cited paper defines manipulation as replacing one designated voter’s sincere ballot to obtain a strictly preferred outcome. Its Section 5 specifies the same tie-breaker, and Theorems 5.2 and 5.5 state the required hardness results for Borda and \(\mathrm{Copeland}_{\alpha}\), respectively. Thus the citation concerns beneficial manipulation under the specified \(T\), with the relevant hypotheses satisfied. [Source](https://www.ifaamas.org/Proceedings/aamas2011/papers/BP2_B42.pdf)
The prover need not reproduce the underlying unweighted hardness proofs: that result is expressly supplied as a premise of the task.
A designated voter implies \(n\geq1\), so the chosen power of two \(N\) is positive. Since \(N\geq n\), the padding mass \(\eta\) is nonnegative. The normalization calculation
\(n/N+2\eta=1\) is correct.
The designated ranking contributes at least \(1/N\) to \(\mu(R^{\star})\), establishing \(0<b\leq\mu(R^{\star})\). Merging identical rankings and omitting zero masses therefore yields precisely the required positive-mass support representation.
There is no failure when \(A\), \(\overline A\), or another source ballot coincides with \(R^{\star}\). The manipulation subtracts only \(b\), and the displayed identity for the resulting society remains valid after aggregation.
Every mass before merging has denominator dividing \(2N\). Merging preserves this property. Since \(N\) is a power of two, all resulting masses, including \(b\), are dyadic.
The support bound \(\tau\leq n+2\) is correct. The numerator and denominator lengths are \(O(\log(n+1))\), and the displayed output-length bound correctly accounts for the explicit rankings and masses. Sorting and merging explicit ballots takes polynomial time.
When \(n\) is already a power of two, \(\eta=0\); omitting the padding entries handles this case correctly.
The reverse-position calculation is correct: positions \(r\) and \(m+1-r\) receive scores whose sum is \(m-1\).
Consequently, the prover’s identity
\(s_{\mu^{L'}}(c)=N^{-1}s_{P^{L'}}(c)+\eta(m-1)\)
holds for every candidate and every replacement ballot. The positive scaling and common additive term preserve all score inequalities and equalities, including ties.
The same calculation applies to the sincere profile. Both claimed winning-set equalities follow.
A ranking and its reverse give opposite orientations to every pair of distinct candidates. Equal padding masses therefore cancel in every majority margin.
The identity
\(d_{\mu^{L'}}(a,c)=N^{-1}d_{P^{L'}}(a,c)\)
preserves positive, negative, and zero margins. Hence every pairwise win, loss, and tie is unchanged, and the Copeland scores are identical.
This argument includes \(\alpha=0\) and \(\alpha=1\); it uses no strict inequality involving \(\alpha\). The sincere winning-set equality follows as well.
The candidate set, label order, and sincere preference order remain unchanged. Equal winning sets therefore produce equal outcomes under the fixed deterministic \(T\).
The displayed beneficial-manipulation equivalence holds for every \(L'\), rather than merely for selected ballots. Taking existence over the same set \(\mathcal L(C)\) proves the required many-one reduction.
The strategic bloc submits one ballot throughout. Aggregation of identical sincere rankings does not introduce permission to split its mass. Thus the reduction respects the central restriction in USER_TASK.
A permutation certificate has polynomial length, and its validity can be checked routinely.
The proposed evaluation of \(T\) is polynomial. Testing \(1\leq s\leq m\) covers every possible exceptional case. When that case holds, the number of clauses is \(\ell\leq m\), and the assignment is supplied by the winning set. Clause evaluation therefore requires no satisfiability search. The procedure also handles an empty conjunction and the ordinary least-index fallback.
The denominator product \(D\) has \(O(L)\) bits, as claimed. Every input denominator divides \(D\), so the scaled masses and bloc size are integers. Both displayed update formulas correctly subtract the sincere contribution and add the replacement contribution.
The asserted integer-length bound \(O(L+\log(m+1))\) is valid. Exact signs determine Copeland pairwise results, and the fixed denominator of \(\alpha\) permits exact score comparisons. Computing both outcomes and comparing their positions in \(R^{\star}\) verifies precisely the requested strict improvement.
With the stated \(H\), schoolbook exact arithmetic fits within the supplied \(H^2\) allowance per arithmetic operation. Rational preprocessing is covered by \(O(LH^2)\).
Borda requires \(\tau m\) ranking contributions; Copeland requires \(\tau m^2\) pairwise contributions. Winner selection, preference comparison, and evaluation of \(T\) fit within the respective verification bounds.
For exhaustive decision, the sincere scores or margins can be computed once. Each replacement requires \(O(m)\) Borda updates or \(O(m^2)\) Copeland updates, with the arithmetic and tie-breaker costs absorbed by the displayed bounds. Enumerating all \(m!\) ballots therefore gives the stated deterministic decision bounds.
The conclusion of \(\mathrm{NP}\)-completeness, including hardness on dyadic masses, follows. No additional lemma, clarification, or repair is required.
⟨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.