| paper | d4-conf-aaai-2010-0374 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\)-complete · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 12
statement extracted from the paper’s text layer
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.
A society is a distribution \(\mu\) over the supported original rankings. The decision variables are integral clone counts \(k_i\) within the unit-cost budget and mass allocations \(y_{t,\rho}\) from each ranking type to valid clone refinements. The question is whether a clone of the target reaches maximum Copeland score under majority comparisons weighted by mass.
The selected question covers the \(q=0\) UC case of Theorem 12. The separate Theorem 9 anchor also survives; the question does not address the paper’s other cloning characterizations, clone detection results, or adding-candidates control.
The strongest mirror I see keeps candidates and clones discrete while replacing the electorate by a distribution over rankings. That is the programme’s population continuization: the object of mass is voters, not candidates or outcomes.
Take a large ranked preference contest—say, consumers comparing product families—with many people but relatively few distinct rankings over the original options. A type is one such complete ranking, and \(\mu_t\) is the fraction of the population with ranking \(t\), given as a binary rational. It is plausible to have \(N\) very large and support size \(\tau\) small. The decision remains the one in the paper: how many copies of each candidate to create. For the paper’s 0-success model, the manipulator succeeds if some favorable ordering of the clones within each ballot’s blocks makes a clone of the target win. The continuous analogue allows a type’s mass to split among those valid refinements.
More precisely, for a clone-count vector \(\mathbf{k}\), let \(\mathcal R_{\mathbf{k}}(t)\) be the rankings formed by replacing each candidate in \(t\) with its block of clones, keeping each block consecutive and preserving the order of blocks. A refinement allocation is a set of masses \(y_{t,\rho}\ge 0\) with \(\sum_{\rho\in\mathcal R_{\mathbf{k}}(t)}y_{t,\rho}=\mu_t\). These masses define the resulting society on the expanded candidate set. The target must not win in the original society, and the question is whether some clone vector within budget and some valid refinement allocation make a target clone a winner. Each person still has a strict ranking and casts a whole vote; fractions describe cohort shares. Clone counts remain integral.
My lead anchor is Theorem 12, proved in this paper (the proof is among those omitted for space). It says that for Copeland, UC \(q\)-CLONING is NP-hard for every \(q\in[0,1]\). In particular, the result covers \(q=0\): with each additional clone costing one, it is NP-hard to decide whether a cloning manipulation within the given budget can succeed for some ordering of the clones.
The continuous problem I would hand to a prover is Continuous UC Copeland 0-Cloning. Given \(m\) original candidates, a support of \(\tau\) rankings with rational masses summing to one, a target \(c\), and a budget \(B\), decide whether there are integer clone counts \(k_i\ge1\), with \(\sum_i(k_i-1)\le B\), and a valid refinement allocation \(y\) such that some clone of \(c\) is a Copeland winner. Pairwise comparisons use mass: \(x\) beats \(z\) when more than half the resulting society ranks \(x\) above \(z\); the Copeland score is its number of pairwise wins minus losses, with ties contributing zero. A solution is the clone-count vector and the mass allocation. I would first expect hardness to transfer (Class B): Copeland cloning’s combinatorics appear to lie in the candidate agenda and the induced majority tournament, which remain in the model. That is a hypothesis to test against the proof, not a consequence of Theorem 12.
A second, independently useful anchor is Theorem 9, also proved here, with its proof omitted for space. For Borda, \(q\)-CLONING in the general cost model is NP-hard for every \(q\in[0,1]\), even when the per-copy prices belong to \(\{0,1,+\infty\}\). This anchors costly cloning under a scoring rule, rather than only the Copeland case.
Its mirror is Continuous General-Cost Borda 0-Cloning. Use the same distribution over original rankings and the same mass-allocation definition. The input additionally gives a price \(p(i,j)\in\{0,1,+\infty\}\) for each additional copy \(j\) of candidate \(i\), and a budget \(B\). Ask whether a clone-count vector and a valid refinement allocation exist whose total price is at most \(B\) and for which a target clone has maximum Borda score. The expected direction is again Class B, because the clone and price choices remain discrete and range over candidates. This case is less certain: Borda’s linear scores make it a natural place to look for an LP or pricing algorithm, so the continuous question could expose a tractability gain.
Both anchors are results about the cloning problem itself; neither makes outcomes continuous. I am not claiming a continuous version of every result in the paper: these mirrors cover the two named hardness results, not clone detection, adding-candidates control, or the paper’s tractable characterizations.
The main weakness is that fractional mass splitting can change feasibility. A discrete electorate assigns each voter one refinement; the continuous model can divide a ranking type across refinements. Thus the finite NP-hardness results do not, by themselves, prove hardness of either mirror: a discrete no-instance might become a continuous yes-instance. Whether the omitted reductions survive this relaxation is the key question for the Class B prediction. The 0-success semantics are also optimistic: they require only that a favorable refinement exists. If the intended application needs success under random clone orderings or under every ordering, it needs a separate continuous formulation of that success criterion.
I cannot make a convincing case against both anchors. The proposed mirrors continueize the population while keeping the candidate agenda and clone counts discrete, which is exactly the relevant axis here.
For Theorem 12, a large electorate can plausibly contain many voters with the same ranking. In the \(0\)-success model, each such voter’s ordering of clones is available to the manipulator. Splitting a ranking type’s mass among its valid refinements is therefore a natural high-multiplicity version of that choice. Copeland’s majority comparisons and winner condition remain meaningful on the resulting distribution. Clone counts and the unit-cost budget can stay integral. It is unknown from the supplied text whether the omitted hardness reduction survives fractional mass splitting, but that is a question for the prover; a possible tractability gain would make the mirror more valuable, not less.
Theorem 9 has the same basic defense. A continuous Borda mirror can preserve the paper’s per-copy price schedule and budget, while evaluating scores over rational masses of rankings and their refinements. Arbitrary costs may make that mirror harder to solve, but they are already part of the paper’s problem and do not make population mass an incoherent quantity. The mirror would test whether fractional electorate mass changes the complexity of the costly-cloning problem.
The strongest objection I can find concerns semantics: clone ordering is not fixed by an original ranking, and allowing a type’s mass to split across refinements adds fractional choices that an individual finite electorate lacks. But the paper explicitly makes those orderings central to \(0\)-success, and the fractional choices have a straightforward large-cohort interpretation. The objection does not defeat either anchor. Random-order \(q\)-success may need more care in a continuum because probabilities can concentrate, but the \(q=0\) anchors do not depend on that interpretation.
So the negative case is weak. The results’ combinatorics may remain hard because clone choices are discrete, yet that is not a reason to reject the questions. Both mirrors look worth asking; claiming that no scenario can make either worthwhile would go beyond what this paper supports.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.