Answer: \(\mathrm{NP}\)-complete
Theorem 12 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFor Copeland, UC q-CLONING is NP-hard for each q ∈[0, 1]. Detecting Clones So far we have considered the problem of introducing clones so that a given candidate becomes a winner. In this section we focus on the reverse issue: Given an election, we would like to know if it could have been obtained from a smaller one via cloning. This is important from the point of view of a candidate who wants to defend herself from a manipulator performing cloning: Before she can apply any countermea- sures, she has to determine whether clones exist.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) original candidates, a target \(c\), a budget \(B\), and a support of \(\tau\) rankings \(t\) with rational masses \(\mu_t\) summing to \(1\), where \(c\) is not initially a Copeland winner, does there exist an integer clone count \(k_i\ge1\) for each candidate with \(\sum_i(k_i-1)\le B\), and nonnegative rational masses \(y_{t,\rho}\) over valid refinements \(\rho\) of each ranking \(t\), such that \(\sum_{\rho}y_{t,\rho}=\mu_t\) and some clone of \(c\) is a Copeland winner? A valid refinement replaces each candidate with its block of clones, keeps each block consecutive, and preserves the original order of blocks. Pairwise comparisons use the resulting masses: \(x\) beats \(z\) when more than half the mass ranks \(x\) above \(z\); Copeland scores count wins minus losses, with ties contributing zero.
Given a candidate set \(A=\{c_1,\ldots,c_m\}\) with \(m\ge2\), a target \(c\in A\), and a finite nonnegative integer budget \(B\) encoded in binary, consider the following decision problem.
A society is given by its support: a list of \(\tau\) distinct strict rankings \(t\) of \(A\), each with positive binary rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
Pairwise victories require mass strictly greater than \(1/2\); equality gives a tie. Copeland scores are wins minus losses, with pairwise ties contributing zero; every candidate attaining the maximum score is a winner. Assume \(c\) is not initially a winner.
Choose integers \(k_i\ge1\), replacing \(c_i\) by \(k_i\) distinct labeled clones, at unit cost \(k_i-1\), subject to \(\sum_i(k_i-1)\le B\).
For these counts, let \(\mathcal R_t(k)\) contain all strict rankings obtained from \(t\) by replacing each candidate by a consecutive block of its clones, preserving the order of blocks and allowing arbitrary orders within them.
The decision is whether there exist nonnegative rational masses \(y_{t,\rho}\), for \(\rho\in\mathcal R_t(k)\), with \(\sum_{\rho\in\mathcal R_t(k)}y_{t,\rho}=\mu_t\), such that some clone of \(c\) is a Copeland winner under the resulting masses.
Is this continuous unit-cost Copeland cloning problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard? State running times in \(m,\tau,L\) and \(B\).
For finite lists of voters, unit-cost Copeland cloning is NP-hard when clone orders may be chosen to make some target clone a winner; this holds even with an odd number of voters. [Full-version result](https://www.math.auckland.ac.nz/~slinko/Research/main.pdf)
No result settling exactly the divisible-mass problem stated here was located in the literature search.
1. Result. The stated divisible-mass problem is \(\mathrm{NP}\)-complete. Hardness holds even when \(B\le m\), the support has size \(O(m^2)\), and all masses are dyadic rationals with denominators \(O(m^2)\).
The cited [finite-voter result, Theorem 5.12](https://www.math.auckland.ac.nz/~slinko/Research/main.pdf) does not by itself establish hardness under mass splitting. The proof below addresses that freedom explicitly.
2. An exact criterion for fixed clone counts. For distinct candidates \(i,j\), define \(w_{ij}=1\) if \(i\) defeats \(j\), \(w_{ij}=-1\) if \(j\) defeats \(i\), and \(w_{ij}=0\) if they tie. Set \(w_{ii}=0\). Thus \(w_{ij}=-w_{ji}\).
Fix counts \(k_i\ge1\). Every clone of \(i\) has the same score from contests against other blocks:
\[ E_i(k)=\sum_j w_{ij}k_j. \]
Indeed, every permitted refinement preserves the order of distinct blocks, so their pairwise outcomes remain unchanged.
Within any block, the internal scores sum to zero: each decisive contest contributes \(1\) and \(-1\), while a tie contributes zero to both clones. Consequently, every rival block \(i\ne c\) contains a clone with total score at least \(E_i(k)\). A target clone has internal score at most \(k_c-1\). Therefore, feasibility requires
\[ E_i(k)\le E_c(k)+k_c-1\qquad(i\ne c). \]
This condition is also sufficient. In each original ranking \(t\), create two refinements of mass \(\mu_t/2\). Use mutually reversed internal orders in every rival block. In the target block, use the same order in both refinements, with a distinguished target clone first. Then every rival block is internally tied, and the distinguished target clone defeats all its siblings. Its score is \(E_c(k)+k_c-1\), and no other target clone scores higher. Coincident refinements are simply combined.
Thus the displayed inequalities are an exact feasibility criterion, with an explicit rational realization using at most \(2\tau\) positive-mass refinements.
Writing \(x_i=k_i-1\) and \(s_i=\sum_jw_{ij}\), the decision problem is equivalent to the integer system
\[ x_i\in\mathbb Z_{\ge0},\qquad \sum_i x_i\le B, \]
\[ s_i+\sum_jw_{ij}x_j \le s_c+\sum_jw_{cj}x_j+x_c \qquad(i\ne c). \]
3. Membership in \(\mathrm{NP}\). A certificate consists only of the integers \(x_i\), encoded in binary. Each is at most \(B\), so the certificate has \(O(m\log(B+2))\) bits.
The matrix \(w\) can be computed exactly from the input rational masses in polynomial time. The integer inequalities above can then be checked in polynomial time. Their sufficiency supplies the required rational masses, so an exponentially large expanded society need not appear in the certificate. Hence the problem belongs to \(\mathrm{NP}\).
4. Hardness construction. We reduce from Exact Cover by \(3\)-Sets, the standard \(\mathrm{NP}\)-complete problem: given a ground set \(U\) of size \(3K\) and a labeled family \(S_1,\ldots,S_M\) of three-element subsets, decide whether \(K\) sets partition \(U\).
We may assume \(K\ge1\) and \(M\ge2K\). Starting with a nonempty family, duplicate a set until the latter inequality holds. This preserves the answer because an exact cover cannot contain two copies of the same nonempty set.
Create candidates
\[ \{c,z\}\ \cup\ G\ \cup\ F\ \cup\ D, \]
where \(G=\{g_u:u\in U\}\), \(F=\{f_1,\ldots,f_M\}\), and \(D=\{d_1,\ldots,d_{2M}\}\). Set the cloning budget to \(B=K\).
Specify the following strict pairwise victories; every unspecified pair is tied.
These specifications are well-defined: \(M+2K\le2M\), and \(0\le M-K+r_u\le2M\).
Put \(N=2M\) and \(s=N-K\). The initial scores are as follows:
| Candidate | Initial score |
|---|---:|
| \(c\) | \(s\) |
| \(g_u\) | \(s+1\) |
| \(z\) | \(N\) |
| \(f_j\) | \(2-3K\) |
| \(d_\ell\) | at most \(-1\) |
For completeness, the nontrivial calculations are
\[ s_c=M-3K+(M+2K)=2M-K, \]
\[ s_{g_u}=1+(M-r_u)+(M-K+r_u)=2M-K+1. \]
Each \(f_j\) loses to \(c\) and to the \(3K-3\) element candidates outside \(S_j\), giving score \(2-3K\). Every dummy loses to \(z\) and has no victories. The sentinel has exactly \(2M\) victories.
In particular, \(c\) is not initially a winner, as required.
5. Realizing the construction by a polynomial-size society. We give an explicit realization, including the prescribed ties.
For every required victory \(a\) over \(b\), choose an order \(R\) of the remaining candidates and introduce the two strict rankings
\[ a\succ b\succ R, \qquad \operatorname{rev}(R)\succ a\succ b. \]
Together, these rankings give pairwise margin \(2\) to \(a\) over \(b\) and margin zero to every other pair. For a pair involving one remaining candidate and \(a\) or \(b\), the two rankings disagree; pairs entirely within \(R\) are also reversed.
Let \(e\) be the number of prescribed victories. Choose the smallest power of two \(Q\) satisfying \(Q\ge2e\). Add \((Q-2e)/2\) copies of an arbitrary ranking and the same number of its reverse. These additional rankings contribute zero margin everywhere.
Normalize the resulting \(Q\) rankings to mass \(1/Q\), and merge identical rankings. Every prescribed victory has normalized margin \(2/Q>0\), while every prescribed tie has margin zero. Therefore the strict-majority convention is satisfied exactly.
The merged support has \(\tau\le2e+2=O(m^2)\). Its positive masses are dyadic rationals with denominator \(Q=O(m^2)\). Here
\[ m=3K+3M+2, \]
and the resulting input length is \(L=O(m^3\log m)\). The construction and merging take polynomial time.
6. Correctness of the reduction.
*An exact cover gives a successful cloning.*
Suppose \(J\subseteq\{1,\ldots,M\}\) indexes an exact cover, with \(|J|=K\). Introduce one additional clone of each \(f_j\) for \(j\in J\), and no other clones. Make these blocks internally tied using the construction in Section 2.
The target gains \(K\) points, reaching \(s+K=N\). Each \(g_u\) defeats exactly \(K-1\) of the added clones, because exactly one selected set contains \(u\). Its score becomes
\[ s+1+(K-1)=N. \]
The sentinel retains score \(N\). Set-block external scores remain \(2-3K\), because all contests between distinct set blocks are tied. Dummy scores remain at most \(-1\). Thus \(c\) is a winner at cost \(K\).
*A successful cloning gives an exact cover.*
Now suppose a successful cloning has cost at most \(K\). Write \(x_i=k_i-1\), and let \(S\) be the score of a winning target clone. For a candidate subset \(T\), write \(X_T=\sum_{i\in T}x_i\). Let \(H\subseteq D\) be the \(M+2K\) dummies defeated by \(c\).
The target’s score satisfies
\[ S\le s+x_c+X_F+X_H-X_G. \]
Every sentinel clone has external score \(N+X_D\). Since its block’s internal scores sum to zero, some sentinel clone scores at least \(N+X_D\). The winning condition therefore gives
\[ N+X_D\le S. \]
Combining these bounds and using \(N-s=K\) yields
\[ K \le x_c+X_F-X_G-X_{D\setminus H} \le x_c+X_F \le \sum_i x_i \le K. \]
Every inequality is consequently an equality. In particular,
\[ x_c+X_F=K, \qquad X_G=X_D=x_z=0. \]
Thus only \(c\) and set candidates can have been cloned. The target bound now gives \(S\le N\), while the sentinel forces \(S\ge N\), so \(S=N\).
Every element candidate is un-cloned. Its score is exactly
\[ s+1+x_c+\sum_{j:\,u\notin S_j}x_{f_j} = N+1-\sum_{j:\,u\in S_j}x_{f_j}. \]
Since the target is a winner, this score is at most \(N\). Therefore
\[ \sum_{j:\,u\in S_j}x_{f_j}\ge1 \qquad(u\in U). \]
Summing over the \(3K\) elements, and using that every set has size three, gives
\[ 3X_F = \sum_{u\in U}\sum_{j:\,u\in S_j}x_{f_j} \ge3K. \]
Together with \(x_c+X_F=K\), this implies \(X_F=K\) and \(x_c=0\). Equality in the sum forces every element’s coverage sum to equal one. Hence each \(x_{f_j}\) is either zero or one: a value at least two would give coverage at least two to every element of \(S_j\).
The \(K\) sets with \(x_{f_j}=1\) therefore partition \(U\). They form an exact cover.
This proves the reduction in both directions under arbitrary rational mass splitting.
7. Running times and the role of \(B\). Using elementary binary arithmetic, a conservative bound for computing the majority matrix is \(O(\tau m^2L^2)\) bit operations. Once that matrix is available, a count certificate can be verified in
\[ O\!\left(m^2\log(B+m+2)\right) \]
bit operations.
There is also an explicit exhaustive algorithm. Increasing \(x_c\) by one changes the difference between the maximum achievable target score and rival block \(i\)’s external score by \(1-w_{ic}\ge0\). Thus unused budget may always be spent on the target.
Enumerate the nonnegative counts for the other \(m-1\) candidates whose sum is at most \(B\), and assign the remaining budget to \(c\). There are \(\binom{B+m-1}{m-1}\) such vectors. The resulting running time is
\[ O\!\left( \tau m^2L^2+ \binom{B+m-1}{m-1}\, m^2\log(B+m+2) \right). \]
This is polynomial in the numerical value of \(B\) for fixed \(m\). However, a uniform algorithm polynomial in \(m,\tau,L,B\) would imply \(\mathrm{P}=\mathrm{NP}\): the hardness construction already has \(B=K\le m\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct. The fixed-count criterion, rational realization, reduction, and complexity bounds establish that the stated divisible-mass problem is \(\mathrm{NP}\)-complete. No major or minor issues were found.
The external score formula
\[
E_i(k)=\sum_j w_{ij}k_j
\]
is correct. Block preservation ensures that every clone of \(i\) has the original pairwise outcome against every clone of \(j\), including when the original contest is tied.
The necessity argument is valid:
The sufficiency construction also works. Splitting each original mass equally between two refinements with reversed rival-block orders makes every internal rival contest a tie. Keeping the distinguished target clone first makes it defeat every sibling. Its internal score is \(k_c-1\), the maximum possible, so no other target clone exceeds its score.
All resulting masses are rational, each original mass is preserved, and combining coincident refinements preserves every pairwise outcome. The construction also covers singleton blocks.
Substituting \(k_i=1+x_i\) gives exactly the displayed integer system.
The count certificate has the claimed polynomial size because \(0\le x_i\le B\). Exact rational arithmetic determines all strict-majority outcomes and ties.
The criterion established above lets the verifier accept a count certificate without explicitly writing the potentially enormous expanded rankings. This is a valid \(\mathrm{NP}\) certificate argument: sufficiency proves that the required rational refinement exists.
The source problem is precisely specified. Restricting to \(K\ge1\) and a nonempty family excludes only trivial source instances. Duplicating a nonempty set preserves exact-cover feasibility and permits \(M\ge2K\) with polynomial growth.
All dummy indices are valid:
\[
M+2K\le2M,\qquad
0\le M-K+r_u\le2M.
\]
The candidate count \(m=3K+3M+2\) is correct. The initial-score calculations check:
Since \(K\ge1\), the sentinel strictly exceeds the target initially, satisfying the task’s promise.
The two rankings assigned to a prescribed victory contribute margin \(2\) to that pair and zero to every other pair. Cancellation holds both for pairs within the remaining order and for pairs involving one of the two designated candidates.
The padding is valid: \(e>0\), so the chosen power of two \(Q\ge2e\) is even, and \((Q-2e)/2\) is a nonnegative integer. A ranking and its reverse cancel all margins.
After normalization, prescribed victories have positive margin \(2/Q\), and unspecified pairs have exactly zero margin. Thus the construction respects strict majority and ties exactly.
Merging identical rankings yields distinct positive-mass support entries. The bounds \(\tau=O(m^2)\), \(Q=O(m^2)\), and \(L=O(m^3\log m)\) follow from the number of pairs, the ranking lengths, and the rational encoding sizes. The realization is polynomial in size and construction time.
Cloning the \(K\) selected set candidates once costs exactly \(K\).
The target gains \(K\) points. Each element candidate gains \(K-1\), because exactly one selected set contains its element. Both therefore reach score \(N\).
The sentinel remains at \(N\). Set-block external scores remain \(2-3K\), their internal contests can be tied, and dummy scores remain at most \(-1\). Hence the target is a winner.
The target-score bound accounts correctly for every block:
\[
S\le s+x_c+X_F+X_H-X_G.
\]
Some sentinel clone has score at least its external score \(N+X_D\), regardless of its internal ordering. Combining these bounds yields the displayed inequality chain.
Because its endpoints are both \(K\), every inequality is an equality. Equality between \(x_c+X_F\) and total cost forces
\[
X_G=X_D=x_z=0.
\]
Consequently only target and set candidates can have been cloned, and the sentinel and target bounds force \(S=N\).
Every element candidate is then un-cloned. Its displayed score formula is correct, using \(x_c+X_F=K\). The winning condition forces every element’s coverage sum to be at least one.
Summing these inequalities counts each set multiplicity exactly three times. Thus \(X_F\ge K\), which together with \(x_c+X_F=K\) forces \(X_F=K\) and \(x_c=0\). Equality of the total coverage forces every individual coverage sum to equal one.
Since every set contains three elements, any multiplicity at least two would violate those coverage equalities. The selected sets therefore have multiplicities zero or one and form an exact cover.
This direction handles arbitrary permitted rational mass splitting; it does not assume the prover’s sufficient realization was used.
The majority-matrix bound is conservative but valid using elementary exact binary arithmetic. The certificate-verification bound accommodates the bit lengths of counts, sums, and scores.
Increasing \(x_c\) changes the target-versus-rival feasibility difference by \(1-w_{ic}\ge0\), so spending unused budget on the target preserves feasibility.
The number of enumerated rival-count vectors is correctly
\[
\binom{B+m-1}{m-1}.
\]
The stated exhaustive running time follows. It is polynomial in numerical \(B\) for fixed \(m\), while the reduction’s \(B=K\le m\) rules out a uniform polynomial bound in \(m,\tau,L,B\) unless \(\mathrm{P}=\mathrm{NP}\).
The finite-voter theorem is not used to justify the reduction, so its applicability to divisible masses is not an unresolved dependency.
No repair or additional clarification 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.