Cloning in Elections: Finding the Possible Winners

This paper has a credible continuous mirror. My lead is a high-multiplicity version of its Borda cloning problem, anchored in Theorem 5.5. A second, independent mirror comes from Theorem 5.7 for \(k\)-Approval. In both cases, I expect the continuous problem to be Class B: the population becomes divisible, but the hard combinatorics remain on the candidate side.

The common mirror is as follows. Fix a finite candidate set \(A\), a preferred candidate \(c\), and let \(T_A\) be the set of complete rankings of \(A\). A society is a rational distribution \(\mu\) over \(T_A\), where \(\mu_R\) is the mass of agents with ranking \(R\). The intended regime is a large party, brand, or software-agent election: millions of agents, but only a moderate number of preference segments, with \(N\gg |\operatorname{supp}(\mu)|\). Agents in one type have the same ranking, and the same relevant costs and responses. This is exactly the paper’s party-nomination or multi-agent-planning motivation, with voter multiplicity made explicit.

The candidates themselves remain discrete. A cloning action chooses an integer \(k_a\ge 1\) for every \(a\in A\), replacing \(a\) by \(k_a\) clones. For each original type \(R\), let \(\lambda_{R,R'}\) be the mass assigned to a permissible post-cloning ranking \(R'\): every clone block must remain contiguous, and the blocks must occur in the order specified by \(R\). Thus \(\sum_{R'}\lambda_{R,R'}=\mu_R\). The decision variable is the integer clone vector together with this mass assignment. For \(0^+\)-success, we ask whether there exists such an assignment making a clone of \(c\) a winner. This is the population version of the paper’s explicit observation that \(0^+\)-success is equivalent to being able to dictate the clone order.

The high-multiplicity dictionary is exact for rational instances. If \(\mu_R=n_R/N\), one obtains a finite election by taking \(n_R\) voters of type \(R\); conversely, every finite profile normalizes to such a distribution. Scores and pairwise comparisons are merely divided by \(N\). The mirror therefore does not make outcomes continuous, and it does not make clone numbers fractional. It continuizes the population only.

My lead anchor is Theorem 5.5, proved in this paper rather than cited. It states that for Borda, \(q\)-Cloning in the general cost model is NP-hard for every rational \(q\in(0,1]\) and also for \(q=0^+\), even when every cloning cost belongs to \(\{0,1,\infty\}\). The reduction is from Exact Cover by 3-Sets. Given \(G\) with \(|G|=3K\) and sets \(S_1,\ldots,S_M\), the election has candidates \(G\cup T\cup\{c,u,w\}\), where \(T=\{t_1,\ldots,t_M\}\). Only candidates \(t_i\) may be cloned: creating the first additional clone of \(t_i\) costs \(1\), later clones cost \(0\), and cloning every other candidate costs \(\infty\). The budget is \(K\). If the X3C instance has an exact cover, cloning the corresponding \(t_i\)’s sufficiently many times makes \(c\) a Borda winner with probability \(1\), hence also with every \(q>0\) and under \(0^+\)-success. If there is no exact cover, every choice of at most \(K\) cloneable candidates leaves some element \(g\in G\) uncovered, and that candidate retains a strictly higher Borda score than \(c\). Thus no \(0^+\)-successful manipulation exists.

The corresponding continuous problem is:

“Continuous Borda \(0^+\)-Cloning with type-level costs.” An instance consists of \(A\), a rational distribution \(\mu\) over complete rankings of \(A\), a preferred candidate \(c\), a cloning-cost table \(p(a,j)\), and a budget \(B\). Choose integer clone multiplicities \(k_a\) and a rational mass assignment \(\lambda\) over permissible post-cloning rankings. The cost \(\sum_a p(a,k_a)\) must be at most \(B\), \(c\) must not initially be a Borda winner, and at least one clone of \(c\) must maximize the aggregate Borda score after cloning. The optimization version minimizes this cost.

This is recognizably the paper’s problem. A campaign manager still chooses which similar candidates to multiply, the clones remain contiguous in every ranking, and the manager still benefits if any clone of \(c\) wins. The only replacement is that a repeated constituency is represented by its mass rather than by individually named voters.

I expect hardness to transfer, not dissolve. The reduction’s relevant score comparisons are linear in voter multiplicities, so normalization preserves them exactly. More importantly, the reduction excludes fractional escape directly. If an element \(g\) is not covered by the selected \(t_i\)’s, cloning those \(t_i\)’s does not change the Borda-score difference between \(g\) and \(c\), regardless of how the mass of any type is split among clone orders. Conversely, an exact cover gives a manipulation that succeeds for every ordering of the clones, so it remains valid in the continuous model. The hard object is the selected family of candidate clones, not the number of voters. This is a genuine Class B mirror, not merely an appeal to finite-voter hardness.

The theorem also generates useful follow-up questions. Does the continuous problem remain hard under unit cloning cost rather than the paper’s \(\{0,1,\infty\}\) costs? Does allowing only a bounded number of ranking types yield an algorithm? For a fixed clone vector, the mass-allocation part is a linear feasibility problem, so the real difficulty lies in the integer candidate-side search and in the exponentially many possible clone-order configurations.

The second anchor is Theorem 5.7, also proved in the paper. It states that, for every fixed \(k\ge 2\), deciding whether an election is \(0^+\)-manipulable by cloning under \(k\)-Approval is NP-hard. The reduction is from Dominating Set. The constructed election contains a candidate \(v_i\) for every graph vertex, a preferred candidate \(c\), a candidate \(w\), and dummy candidates. Candidate \(c\) is never ranked first. After the auxiliary voters are added, \(c\) has score \(4t^2-s\), \(w\) has score \(4t^2-2s\), and every \(v_i\) has score \(4t^2\). If the graph has a dominating set \(W\) of size at most \(s\), the candidates in \(W\) can be cloned and their clone blocks placed so that \(c\) and every resulting clone have score at most \(4t^2-2s\). Conversely, any successful manipulation cannot clone \(w\); it can clone at most \(s\) candidates from \(V\), because each such clone lowers \(c\)’s score. Every \(v_i\) must then either itself be cloned or have a neighbor that is cloned. Hence the cloned vertices form a dominating set.

The continuous mirror is:

“Continuous \(k\)-Approval \(0^+\)-Cloning.” An instance consists of a finite candidate set \(A\), a rational society distribution \(\mu\) over rankings of \(A\), and a preferred candidate \(c\). Choose a finite integer clone vector and a permissible post-cloning mass assignment \(\lambda\). The question is whether \(c\), through one of its clones, can become a \(k\)-Approval winner, while \(c\) is not initially a winner. Equivalently, one may minimize the total number of added clones and ask whether the optimum is finite.

Here too, I expect Class B hardness. The continuous \(k\)-Approval scores are simply aggregate masses in the top \(k\) positions. The reduction can normalize every finite voter block to rational mass. Fractionally splitting a ranking type does not help when a vertex has neither itself nor a neighbor among the cloned candidates: no clone block can then displace that vertex from the relevant approval positions. The fixed score of \(w\) still bounds the number of selected vertices by \(s\), and the domination condition remains necessary. The combinatorics live in the graph encoded by candidate interactions, not in voter individuation.

This second mirror is valuable because it removes the possible objection that Theorem 5.5’s hardness is being smuggled in through an unusual cost table. The \(k\)-Approval result is already hard in the zero-cost, unlimited-budget setting. It also shows that the continuous mirror is not restricted to Borda’s particular score geometry.

My weakest point is the probabilistic part of the paper. A continuum of independently randomizing voters does not behave exactly like finitely many independently randomizing voters: aggregate mass may become deterministic by a law-of-large-numbers effect. For that reason I deliberately anchor the mirror at \(0^+\), which the paper itself identifies with controllable clone order, rather than pretending that its \(q\)-success probabilities transfer automatically. A separate stochastic continuum model would need to specify whether randomness acts on individual agents, on mass blocks, or on the aggregate post-cloning distribution.

A secondary soft spot is that \(\lambda\) allows one original type’s mass to split among several clone orders. That is a genuine relaxation of a small finite electorate. But it is exactly what high multiplicity means: a rational fraction of a large homogeneous constituency can respond one way and the rest another way. Every rational \(\lambda\) can be realized by sufficiently replicating the relevant type. The paper’s authors should therefore recognize these as continuous high-multiplicity versions of their cloning problems, not as unrelated fractional voting models.