Answer: Borda is \(\mathrm{NP}\)-hard. For every fixed \(k\geq2\), \(k\)-Approval is \(\mathrm{NP}\)-complete under the stated general costs.
Theorem 5.5 — class: hardness
Given a finite candidate set \(A\), preferred candidate \(c\), rational society distribution \(\mu\) over complete rankings of \(A\), candidate cloning costs \(p(a,j)\), and budget \(B\), can one choose integer clone multiplicities \(k_a\) and a rational mass assignment \(\lambda\) over permissible post-cloning rankings, with total cost at most \(B\), so that a clone of \(c\) is a Borda or \(k\)-Approval winner?
Let \(A\) contain \(m\geq2\) candidates, with preferred candidate \(c\in A\). Fix the rule to be Borda or, separately, \(k\)-Approval for a fixed integer \(k\geq2\). Rankings are strict and complete; scores are weighted by mass, and all candidates attaining the maximum score are winners. Require that \(c\) is not initially a winner.
A society is given by its support: the list of the \(\tau\) ranking types with positive mass, each mass a binary rational, with \(\sum_R\mu(R)=1\). Here \(\tau\) is the support size, not the number of possible rankings.
Costs are supplied as an explicit table \(p:A\times\{1,\ldots,t\}\to\mathbb Z_{\geq0}\cup\{+\infty\}\), with \(t\geq2\), \(p(a,1)=0\), and \(p(a,j)=p(a,t)\) for \(j>t\). The budget \(B\in\mathbb Z_{\geq0}\) is finite; finite costs and the budget are binary encoded.
Choose finite integers \(k_a\geq1\), replacing each \(a\) by labeled clones \(a^{(1)},\ldots,a^{(k_a)}\), at total cost \(\sum_{a\in A}\sum_{j=2}^{k_a}p(a,j)\). Thus \(k_a=1\) makes no additional copy, and deletion is forbidden.
For each original ranking \(R\), let \(\mathcal P_R\) consist of rankings obtained by replacing each candidate by a contiguous clone block, retaining the original order of blocks and permitting every internal ordering. Choose rational masses \(\lambda_{R,\rho}\geq0\) satisfying \(\sum_{\rho\in\mathcal P_R}\lambda_{R,\rho}=\mu(R)\); each type's mass may be split arbitrarily among these rankings.
The decision problem asks whether such multiplicities and masses exist with cost at most \(B\) and some clone of \(c\) a winner. Let \(L\) be the total input bit length; state running times in \(m,\tau,t,L\), and \(k\) where applicable.
For Borda and, separately, each fixed \(k\geq2\), is this continuous cloning decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
Discrete existential cloning under Borda is NP-hard with general costs, even when marginal costs belong to \(\{0,1,+\infty\}\); under each fixed \(k\)-Approval with \(k\geq2\), it is NP-hard even with zero costs ([Elkind–Faliszewski–Slinko](https://arxiv.org/pdf/1401.4602)).
No result settling exactly the mass-splitting problem defined above was located in the literature search.
Borda is \(\mathrm{NP}\)-hard, and for every fixed \(k\geq2\), \(k\)-Approval is \(\mathrm{NP}\)-complete. These statements concern the general cost model in the question. Both hardness reductions use \(t=3\) and marginal costs in \(\{0,1,+\infty\}\).
The reductions below explicitly account for mass splitting. Their decisive comparisons involve candidates that cannot be cloned, whose scores are independent of internal clone order.
We reduce from Exact Cover by 3-Sets. Its input consists of a universe \(G\) of size \(N=3K\) and sets \(S_1,\ldots,S_M\subseteq G\), each of size three. The question is whether \(K\) of these sets partition \(G\).
A subfamily of at most \(K\) sets covers \(G\) if and only if it is an exact cover: covering \(3K\) elements requires at least \(K\) three-element sets, and equality leaves no room for overlaps.
For convenience, the constructions first specify positive integer ranking weights. Dividing every weight by their sum produces the required rational masses summing to one. This common scaling preserves all score comparisons. Duplicate rankings, if any, are combined.
The construction is a simplified covering gadget motivated by [Elkind–Faliszewski–Slinko, Theorem 5.5](https://arxiv.org/pdf/1401.4602). We give its score calculation directly for the present model.
Let \(T=\{s_1,\ldots,s_M\}\), with \(s_i\) representing \(S_i\). The candidates are \(G\cup T\cup\{c\}\).
For each \(i\), choose orders on \(G\setminus S_i\) and \(S_i\). Introduce two rankings, each of weight one:
\(R_i:\quad G\setminus S_i\succ c\succ s_i\succ S_i\succ T\setminus\{s_i\}\),
\(R_i':\quad \operatorname{rev}(S_i)\succ c\succ\operatorname{rev}(G\setminus S_i)\succ T\).
Here each occurrence of a set denotes its chosen internal order, and \(\operatorname{rev}\) reverses that order. Fix arbitrary orders wherever none is specified.
Also introduce
\(R_0:\quad G\succ c\succ T\),
with weight \(Q=M+1\). The total weight is \(2M+Q=3M+1\).
Only candidates in \(T\) may be cloned. Set
\(p(s_i,2)=1,\qquad p(s_i,3)=0\),
and \(p(a,2)=p(a,3)=+\infty\) for \(a\in G\cup\{c\}\). Set \(B=K\). Thus selecting a set costs one, after which arbitrarily many additional copies are free.
For \(e\in G\), define \(d_e=|\{i:e\in S_i\}|\). Let \(\delta_e\) be the distance between \(e\) and \(c\) in \(R_0\), so \(1\leq\delta_e\leq N\).
Borda score differences equal reversed position differences. In \(R_i\), \(c\) occupies position \(N-2\); in \(R_i'\), it occupies position \(4\). Its position sum is therefore \(N+2\).
If \(e\notin S_i\), its reversed positions in the two outsider blocks also sum to \(N+2\), so its combined score equals that of \(c\).
If \(e\in S_i\) is the \(h\)-th member in \(R_i\), its positions are \(N-1+h\) and \(4-h\), whose sum is \(N+3\). Its combined score is consequently one below that of \(c\).
Using unnormalized weighted scores, the initial difference is therefore
\(D_e:=\operatorname{score}(e)-\operatorname{score}(c)=Q\delta_e-d_e\).
Since \(d_e\leq M\),
\(1\leq D_e\leq QN\).
In particular, \(c\) is not initially a winner.
Write \(x_i=k_{s_i}-1\) for the number of additional copies of \(s_i\).
In \(R_i\), inserting these copies increases \(c\)'s Borda score by \(x_i\). It increases the score of an outsider \(e\notin S_i\) by the same amount, but does not increase the score of a member \(e\in S_i\).
In every other ranking, both \(c\) and every element of \(G\) precede \(s_i\), so both gain \(x_i\). Hence, after all cloning,
\(\operatorname{score}(e)-\operatorname{score}(c) =D_e-\sum_{i:e\in S_i}x_i.\)
This identity holds under every permitted mass splitting: \(e\) and \(c\) are singleton blocks, and their positions depend only on block sizes.
Moreover, \(c\) precedes every candidate in \(T\) in every original ranking. It therefore precedes every selectable clone in every expanded ranking. Under Borda, \(c\)'s score is strictly greater than each such clone's score, including after mass splitting.
Suppose an exact cover exists. For each selected set choose \(x_i=QN\), and otherwise choose \(x_i=0\). The cost is \(K\). Every element belongs to a selected set, so its final score difference from \(c\) is at most \(D_e-QN\leq0\). All selectable clones score strictly below \(c\). Thus \(c\) wins.
Conversely, suppose a feasible cloning makes \(c\) win. Its cost equals the number of indices with \(x_i>0\), so at most \(K\) sets are selected. If some element \(e\) is uncovered, its score difference remains \(D_e>0\), regardless of mass splitting. This contradicts \(c\)'s victory. The selected sets therefore cover \(G\), and hence form an exact cover.
This proves Borda hardness.
The constructed instance has \(m=N+M+1\), \(\tau\leq2M+1\), and \(t=3\). Its masses have denominators \(3M+1\), and the construction has polynomial bit length.
Again use element candidates \(G\), selectable candidates \(T=\{s_1,\ldots,s_M\}\), and \(c\). Additional padding candidates are introduced below.
Put \(C=M+3\) and \(d_e=|\{i:e\in S_i\}|\). All rankings have weight one.
\(s_i\succ\underbrace{\text{fresh padding candidates}}_{k-2}\succ e.\)
Each padding candidate occurs in the specified prefix of exactly one ranking. Complete every ranking by listing all remaining candidates in any fixed order.
These counts are nonnegative because \(d_e\leq M<C+1\). The number of rankings is
\(V=3M+\sum_{e\in G}(C+1-d_e)+C=N(C+1)+C.\)
Normalize their weights to \(1/V\).
Allow exactly one additional copy of each selectable candidate:
\(p(s_i,2)=1,\qquad p(s_i,3)=+\infty.\)
For every other candidate, set both entries to \(+\infty\). Set \(B=K\).
Initially, the unnormalized scores are:
Thus \(c\) is not initially a winner.
Let \(I\) be the indices of candidates that are doubled.
In an incidence ranking for \(e\in S_i\), doubling \(s_i\) places its two clones in positions one and two. The \(k-2\) padding candidates then occupy positions three through \(k\), and \(e\) moves to position \(k+1\). Consequently,
\(\operatorname{score}(e)=C+1-|\{i\in I:e\in S_i\}|.\)
The score of \(c\) remains \(C\): its first-place approvals persist, and cloning cannot move it into the approved prefix of another ranking.
Each selectable clone scores exactly \(3\), since both copies are approved in its three incidence rankings and nowhere else. Every padding candidate scores at most \(1\), since cloning only moves it downward.
All these statements hold independently of internal clone order and mass splitting.
The cost is \(|I|\). Since \(3<C\), all selectable clones and padding candidates score below \(c\). Therefore \(c\) wins exactly when every element loses at least one approval, equivalently when the selected sets cover \(G\).
A successful cloning of cost at most \(K\) thus exists exactly when the X3C instance has an exact cover.
This proves hardness for each fixed \(k\geq2\).
Here \(\tau=V=O(NM+N+M)\), there are at most \((k-1)V\) padding candidates, and \(m=O(kV+N+M)\). Again \(t=3\), and the construction has polynomial bit length for fixed \(k\).
The exponentially many internal rankings need not be enumerated to test a fixed multiplicity vector.
Let \(n_a\geq1\) denote the specified multiplicities, and let
\(s=\sum_{a\in A}\lceil\log_2(n_a+1)\rceil.\)
Define \(W(a,b)=\sum_{R:a\succ_R b}\mu(R)\). The maximum possible score of a designated clone of \(c\) is
\(H=n_c-1+\sum_{b\neq c}n_bW(c,b).\)
For \(a\neq c\), the average score of its clones is
\(F_a=\frac{n_a-1}{2}+\sum_{b\neq a}n_bW(a,b).\)
The multiplicities succeed exactly when \(F_a\leq H\) for every \(a\neq c\).
Necessity follows because some clone of \(a\) scores at least its average, while no clone of \(c\) can exceed \(H\). For sufficiency, always place the designated \(c\)-clone first in its block, and distribute each other block uniformly over its internal permutations. Every clone of \(a\neq c\) then scores \(F_a\); the remaining \(c\)-clones score below the designated one. These distributions use rational masses.
Computing this criterion and the cost requires \(O(\tau m^2+mt)\) rational arithmetic operations, with operand lengths polynomial in \(L+s\).
For each ranking \(R\), define
\(q_{R,a}=\min\!\left(n_a,\max\!\left(0,k-\sum_{b\succ_R a}n_b\right)\right).\)
This is the number of approved positions occupied by block \(a\). Put
\(Q_a=\sum_R\mu(R)q_{R,a},\qquad H=\sum_{R:q_{R,c}>0}\mu(R).\)
The multiplicities succeed exactly when \(Q_a/n_a\leq H\) for every \(a\neq c\).
Indeed, \(Q_a/n_a\) is the average clone score, and \(H\) is the maximum score of a designated \(c\)-clone. Both bounds are attained simultaneously by putting that clone first and uniformly distributing the internal orders of other blocks. The other \(c\)-clones cannot score above the designated clone.
The criterion and cost can be computed using \(O(\tau m+mt)\) rational arithmetic operations, with bit lengths polynomial in \(L+s+\log k\).
Let \(\mu_{\min}=\min_R\mu(R)>0\), and put \(U=\lceil k/\mu_{\min}\rceil\).
Any successful multiplicity vector can be replaced by one with every \(n_a\leq U\). To prove this, cap all multiplicities at \(U\).
Because \(U\geq k\), this preserves every \(q_{R,a}\), and therefore every \(Q_a\) and \(H\). A successful designated clone has positive score, so \(H\geq\mu_{\min}\). For any capped rival,
\(Q_a/U\leq k/U\leq\mu_{\min}\leq H.\)
Uncapped rivals retain their inequalities. Nonnegative marginal costs ensure that capping cannot increase cost.
Since \(\log U=O(L+\log k)\), successful multiplicities have polynomial encoding length. The exact criterion verifies them in polynomial time, proving membership in \(\mathrm{NP}\).
Thus \(k\)-Approval is \(\mathrm{NP}\)-complete for every fixed \(k\geq2\). Both decision problems lack an algorithm polynomial in \(m,\tau,t,L\), unless \(\mathrm P=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The argument establishes Borda NP-hardness and NP-completeness for every fixed \(k\geq2\) under \(k\)-Approval, subject to one minor clarification about the source instances. I found no substantive error in either reduction or in the membership argument.
The stated covering equivalence is correct: at most \(K\) sets of size three can cover \(3K\) elements only if exactly \(K\) are used and they are pairwise disjoint.
Normalizing positive integer weights by their total preserves every score comparison. Combining duplicate rankings also preserves the election and produces the required support representation.
Minor issue: the source instances should explicitly have a nonempty universe. If \(K=0\), the Borda construction has no element candidate witnessing that \(c\) initially loses; indeed, \(c\) initially wins. This violates the target’s promise. The empty instance can also produce fewer than two Borda candidates.
Minimum clarification: explicitly invoke NP-completeness of X3C restricted to nonempty universes and conduct both reductions on that restriction.
Ranking positions. The displayed rankings are strict and complete. The position computations check out:
Consequently, the paired rankings contribute zero to the score difference for outsiders and minus one for members.
Initial differences. The additional ranking contributes \(Q\delta_e\), so
\[
D_e=Q\delta_e-d_e
\]
is correct. Since \(Q=M+1\), \(1\leq\delta_e\leq N\), and \(0\leq d_e\leq M\), the bounds
\[
1\leq D_e\leq QN
\]
are valid. On nonempty source instances, they establish that \(c\) is initially not a winner.
Cloning effects. Additional copies of \(s_i\) change the difference between \(e\) and \(c\) only in \(R_i\), and only when \(e\in S_i\). The resulting identity
\[
\operatorname{score}(e)-\operatorname{score}(c)
=D_e-\sum_{i:e\in S_i}x_i
\]
is correct. Because \(e\) and \(c\) cannot be cloned, their positions depend only on block sizes. Splitting mass among internal orders therefore cannot change this identity.
Every selectable clone follows \(c\) in every expanded ranking. Its Borda score is consequently strictly below that of \(c\), including under arbitrary mass splitting.
Costs and equivalence. With \(t=3\), the zero tail permits any finite positive \(x_i\) at total cost one. The forward construction uses finite integers \(x_i=QN\), costs exactly \(K\), and makes all element differences nonpositive. Conversely, a successful solution selects at most \(K\) sets, and any uncovered element retains a strictly positive difference. Both directions are valid.
Encoding. The candidate count, support bound, normalization denominator, and cost table all have polynomial size. The reduction does not require enumerating internal clone orders.
The cited [Theorem 5.5](https://arxiv.org/pdf/1401.4602) concerns the discrete cloning model. Here it supplies motivation only: the output independently verifies the comparisons needed for continuous mass splitting.
Construction and counts. Each prefix has exactly \(k\) candidates, including when \(k=2\), where incidence prefixes contain no padding. All completion candidates begin outside the approved prefix.
The baseline count \(C+1-d_e\) is positive. Since the total number of incidences is \(3M\), the calculation
\[
V=N(C+1)+C
\]
is correct.
The initial scores are exactly those stated: \(C\) for \(c\), \(C+1\) for each element, three for each selectable candidate, and one for each padding candidate. A nonempty universe therefore supplies an initial winner above \(c\).
Cloning effects. The cost table permits only multiplicities one and two for selectable candidates and forbids cloning all others. Doubling the first block in an incidence ranking places both clones within the approved prefix and moves its element to position \(k+1\). Hence
\[
\operatorname{score}(e)
=C+1-|\{i\in I:e\in S_i\}|
\]
is correct.
Cloning cannot promote a candidate from the completion into an approved prefix. Thus \(c\)'s score remains \(C\), every selectable clone scores three, and padding candidates score at most one. These statements are independent of internal ordering and mass splitting.
Equivalence and size. Accordingly, \(c\) wins exactly when the selected sets cover every element. The budget imposes at most \(K\) selections, giving the required equivalence with exact cover.
The stated bounds on rankings, padding candidates, and candidates establish polynomial construction size for each fixed \(k\).
Borda. The formulas for \(H\) and \(F_a\) correctly separate contributions from lower blocks and from internal block positions. Necessity follows from the maximum attainable preferred-clone score and each rival block’s average score.
For sufficiency, placing the designated preferred clone first and distributing other blocks uniformly attains all stated bounds simultaneously. The distributions have rational masses. Other preferred clones score below the designated clone. Thus the criterion is exact.
\(k\)-Approval. The formula for \(q_{R,a}\) correctly counts approved positions in each block. Therefore \(Q_a/n_a\) is the rival block’s average score, while \(H\) is the designated preferred clone’s maximum score.
The stated uniform distributions attain the rival averages simultaneously with that maximum. Other preferred clones cannot outscore the designated clone. This criterion is also exact.
The arithmetic-operation bounds are consistent with computing the displayed quantities and evaluating the explicit cost table and its constant tail. Their polynomial operand-length bounds establish polynomial verification time for polynomial-length multiplicity vectors.
The capping argument is valid:
\[ Q_a/U\leq k/U\leq\mu_{\min}\leq H. \]
The bound on \(\log U\) gives polynomial-length certificates. Explicit mass allocations are unnecessary because the exact criterion already establishes their existence. The NP-membership conclusion follows.
Both complexity conclusions survive the audit. The only requested repair is to state the nonempty X3C source restriction explicitly; no replacement argument or additional substantive lemma 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.