Answer: \(\mathrm{NP}\)-complete, even when every mass is a dyadic rational.
Lemma 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCopeland is resistant to constructive control via adding a bounded number of can- didates.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given disjoint candidate sets \(C,D\), a target \(p\in C\), a bound \(k\), and a rational distribution \(\mu\) with finite support over strict rankings of \(C\cup D\), is there an \(E\subseteq D\) with \(|E|\le k\) such that \(p\) is a Copeland winner among \(C\cup E\)? For each pair, a candidate receives a Copeland point only when it is preferred by mass strictly greater than \(1/2\); rankings are restricted to the participating candidates.
Given finite disjoint candidate sets \(C,D\), a designated candidate \(p\in C\), and a binary-encoded nonnegative integer \(k\), let \(m=|C\cup D|\).
A society is given by its support: a list of \(\tau\) distinct strict rankings of \(C\cup D\), each with a positive binary-rational mass, with masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length. State running times in \(m,\tau,L,k\).
For any participating set \(A=C\cup E\), restrict each ranking to \(A\). Under \(\mathrm{Copeland}^{0}\), a candidate receives one point against another candidate exactly when the mass preferring it exceeds \(1/2\); losses and pairwise ties receive zero points. Every candidate with maximum total score is a winner, with no further tie-breaking.
The decision problem asks whether some \(E\subseteq D\) with \(|E|\le k\) makes \(p\) a winner.
Is this decision problem solvable in polynomial time in the encoded input size, or is it \(\mathrm{NP}\)-hard?
For explicitly listed discrete voters with strict rankings, constructive control by adding at most \(k\) candidates under \(\mathrm{Copeland}^{0}\) is \(\mathrm{NP}\)-complete, allowing co-winners; the result also holds when a unique winner is required. [Source](https://arxiv.org/pdf/0809.4484).
No result explicitly addressing this normalized binary-rational mass formulation was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete. This holds even when every mass is a dyadic rational, meaning a rational whose denominator is a power of two. Consequently, a polynomial-time algorithm in the encoded input size exists if and only if \(\mathrm{P}=\mathrm{NP}\).
Write the support as \((R_i,w_i)_{i=1}^{\tau}\), where \(R_i\) is a strict ranking and \(w_i=a_i/b_i>0\), with numerator and denominator encoded in binary.
For distinct candidates \(x,y\), define
\(M(x,y)=\sum_{i:\,x\text{ precedes }y\text{ in }R_i}w_i\).
Let \(W(x,y)=1\) when \(M(x,y)>1/2\), and \(W(x,y)=0\) otherwise.
Restricting a ranking to a participating set preserves the relative order of every surviving pair. Therefore, for any participating set \(A\) and any \(x\in A\), its score is exactly
\(s_A(x)=\sum_{y\in A\setminus\{x\}}W(x,y)\).
These quantities can be computed with polynomially bounded exact arithmetic. Set
\(Q=\prod_{i=1}^{\tau}b_i\) and \(u_i=a_i(Q/b_i)\).
The bit length of \(Q\) is at most \(L+1\). Moreover, normalization gives \(\sum_i u_i=Q\), so every partial sum of the positive integers \(u_i\) is at most \(Q\). Thus
\(W(x,y)=1\) exactly when \(2\sum_{i:\,x\text{ precedes }y\text{ in }R_i}u_i>Q\).
Equality is detected exactly and awards zero points.
Using schoolbook integer arithmetic, computing the \(u_i\), inverse rankings, and all pairwise outcomes takes
\(O(\tau L^2+\tau m^2L)\)
bit operations.
A certificate is a bit vector specifying \(E\subseteq D\). Verify that \(|E|\le k\), then compute the scores on \(A=C\cup E\) and check
\(s_A(p)\ge s_A(x)\) for every \(x\in A\).
After pairwise preprocessing, this takes
\(O(m^2\log(m+1)+L)\)
bit operations. The certificate and verification time are polynomial in the encoded input size, proving membership in \(\mathrm{NP}\).
We use the supplied discrete-voter hardness result. Specifically, Theorem 4.9 of Faliszewski, Hemaspaandra, Hemaspaandra, and Rothe proves hardness for adding a bounded number of candidates, including \(\mathrm{Copeland}^{0}\), strict rankings, and the nonunique-winner model. These are precisely the voting rule, preference restriction, and success condition needed here. [Source, Theorem 4.9](https://arxiv.org/pdf/0809.4484).
Take such an instance with \(n>0\) explicitly listed voters. Keep \(C,D,p,k\) unchanged. We construct a normalized society preserving every pairwise outcome.
Choose the least power of two \(T\) satisfying \(T\ge 2n\). Then \(2n\le T<4n\). Form a voter multiset as follows:
The multiplicity in the third step is a nonnegative integer because both \(T\) and \(2n\) are even. The resulting multiset has exactly \(T\) voters.
Now group identical rankings. For every ranking \(S\) with positive multiplicity \(c_S\), output \(S\) once with mass \(c_S/T\). These masses are positive dyadic rationals and sum to one. The output rankings are distinct, as required.
For distinct candidates \(x,y\), let \(v(x,y)\) count original voters preferring \(x\) to \(y\), and define the original margin
\(\Delta(x,y)=v(x,y)-v(y,x)\).
Doubling the original voters changes this margin to \(2\Delta(x,y)\). Each added pair consisting of \(R\) and \(R^{\mathrm{rev}}\) contributes zero: exactly one ranking prefers \(x\) to \(y\).
Consequently, the normalized society satisfies
\(2M(x,y)-1=2\Delta(x,y)/T\).
Since \(T>0\), this identity preserves the sign of every margin. In particular:
Restriction to any \(C\cup E\) preserves these pairwise comparisons. Hence every participating candidate has exactly the same \(\mathrm{Copeland}^{0}\) score before and after the transformation. For every \(E\subseteq D\),
\(p\) is an original winner on \(C\cup E\) if and only if \(p\) is a normalized-society winner on \(C\cup E\).
Because the budget is unchanged, the reduction preserves the answer to the control problem.
There are at most \(n+2\) distinct output rankings. Each multiplicity and \(T\) require \(O(\log(n+1))\) bits. After relabeling candidates by integers, the output bit length is bounded by
\(O((n+2)(m\log(m+1)+\log(n+1))+\log(k+2))\).
The source explicitly lists its voters, so this size is polynomial in its input length. Grouping rankings and computing their masses also take polynomial time; no enumeration of all possible rankings is used.
If zero-voter source instances are permitted, they always have a yes answer in the co-winner model, since all scores are zero. They can be mapped to the fixed yes instance with \(C=\{p\}\), \(D=\varnothing\), \(k=0\), and one ranking of mass one. Thus the reduction covers that case as well.
This proves \(\mathrm{NP}\)-hardness and, together with membership, \(\mathrm{NP}\)-completeness.
Let \(d=|D|\), \(k'=\min\{k,d\}\), and
\(B(d,k')=\sum_{j=0}^{k'}\binom{d}{j}\).
Precompute the pairwise outcomes, then enumerate all eligible subsets and verify their scores. The resulting exact algorithm runs in
\(O(\tau L^2+\tau m^2L+B(d,k')m^2\log(m+1))\)
bit operations.
Thus the problem is polynomial-time solvable for every fixed budget \(k\), while the general problem with binary-encoded, variable \(k\) is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The output resolves the assigned problem correctly. The reduction preserves all pairwise victories, losses, and ties, including after any eligible candidate addition. The membership argument uses exact arithmetic with polynomial bit complexity. No major or minor mathematical issues were found.
The definitions of \(M(x,y)\) and \(W(x,y)\) match the task: a strict majority awards one point, while a loss or exact tie awards zero.
Restricting a strict ranking preserves the relative order of every surviving pair. Consequently, the formula
\[
s_A(x)=\sum_{y\in A\setminus\{x\}}W(x,y)
\]
is correct for every participating set \(A=C\cup E\). It also covers singleton participating sets, where the sum is empty and the score is zero.
Each denominator \(b_i\) is a positive integer, so \(Q/b_i\) and \(u_i=a_i(Q/b_i)\) are integers. The product \(Q\) has bit length bounded by the sum of the denominator encoding lengths, up to an additive constant, so the stated \(L+1\) bound is valid.
Normalization gives \(\sum_i u_i=Q\). Positivity therefore bounds every partial sum by \(Q\), justifying polynomial bit lengths throughout the majority computations. The comparison
\[
2\sum_{i:\,x\text{ precedes }y}u_i>Q
\]
correctly distinguishes strict majorities from equality.
The preprocessing bound \(O(\tau L^2+\tau m^2L)\) is a valid schoolbook-arithmetic upper bound. Scores are integers between zero and \(m-1\), so the stated subsequent verification bound is also valid. The certificate has \(|D|\) bits, and comparison with binary-encoded \(k\) does not require time proportional to its numerical value. Membership in \(\mathrm{NP}\) follows.
The cited theorem is accurately identified. Theorem 4.9 covers constructive control by adding a bounded number of candidates for every rational \(\alpha\in[0,1]\), in both winner models and with strict, transitive rankings. Thus its \(\alpha=0\), nonunique-winner case supplies the required source problem. The paper distinguishes this bounded version from unlimited candidate addition. [Source, Theorem 4.9 and the control definitions](https://arxiv.org/pdf/0809.4484)
All relevant hypotheses match: explicitly represented discrete voters, strict rankings, a designated candidate, a candidate-addition budget, and acceptance of co-winners.
For \(n>0\), the least power of two satisfying \(T\ge 2n\) obeys \(2n\le T<4n\). Both \(T\) and \(2n\) are even, making the padding multiplicity a nonnegative integer.
The total voter count is exactly
\[
2n+2\frac{T-2n}{2}=T.
\]
Grouping identical rankings produces distinct support entries, positive masses, and total mass one. Each mass \(c_S/T\) is dyadic, including after reduction to lowest terms. Coincidences between the padding rankings and original rankings cause no problem because multiplicities are grouped.
Doubling the original electorate multiplies each pairwise margin by two. A ranking and its reverse contribute opposite preferences on every distinct pair, so each padding pair contributes zero margin.
The resulting normalized margin is therefore exactly
\[
2M(x,y)-1=\frac{2\Delta(x,y)}{T}.
\]
The factor is positive, preserving the sign and zero value of every margin. This verifies preservation of strict victories, strict losses, and exact ties.
The argument applies simultaneously to every pair and hence to every \(E\subseteq D\). All participating scores and winner sets are preserved. Since the budget is unchanged, both directions of the decision equivalence follow.
At most \(n+2\) rankings occur. Multiplicities and \(T\) have \(O(\log(n+1))\) bits, and the stated output-size bound is polynomial in the explicitly listed source input. Grouping and constructing the masses require polynomial time.
The optional zero-voter case is handled correctly for the co-winner source problem: all candidates score zero, so choosing no additional candidates succeeds. The proposed fixed target instance is valid and has answer yes.
Capping the budget at \(d=|D|\) is correct. The quantity \(B(d,k')\) counts exactly the eligible subsets, including the empty subset. Combining preprocessing with score checks yields the stated running-time bound. For each fixed \(k\), this is polynomial; the statement does not assert polynomial time for variable \(k\).
The polynomial reduction establishes hardness even for dyadic masses. Together with membership, it establishes \(\mathrm{NP}\)-completeness and the claimed equivalence with \(\mathrm{P}=\mathrm{NP}\).
No additional 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.