| paper | d4-conf-aaai-2007-0106 |
| 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, even when every mass is a dyadic rational. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Lemma 6
statement extracted from the paper’s text layer
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.
The society is a finite support of ranking types carrying rational masses \(\mu_t\). The decision variable is the discrete set \(E\subseteq D\), with \(|E|\le k\); the question is whether adding \(E\) makes \(p\) a Copeland winner.
The mirror covers Lemma 6's Copeland constructive control by bounded candidate addition. It leaves the paper's other bribery and control results, including the rest of Theorem 4, unaddressed.
My strongest case is the paper’s Copeland candidate-addition result. Lemma 6, proved here, says that constructive control by adding a bounded number of candidates is resistant: deciding whether the chair can make \(p\) a winner by adding at most \(k\) candidates is NP-hard, and the problem is in NP. Its reduction is from Vertex Cover. It builds an election with \(p\), one initial candidate for each graph edge, and one possible added candidate for each graph vertex. Each edge candidate initially defeats \(p\); \(p\) defeats every vertex candidate; and an edge candidate defeats each vertex candidate that is not incident to that edge. The other pairs are tied. Adding a set of vertices makes \(p\) a winner exactly when those vertices cover every edge. The lemma’s claim and reduction are the anchor; the continuous problem below mirrors that same control question.
Call the mirror Continuous-Population Copeland Candidate Addition. An instance has disjoint sets \(C,D\) of candidates, a target \(p\in C\), a bound \(k\), and a distribution \(\mu\) over strict rankings of all candidates in \(C\cup D\). The input lists only the \(\tau\) rankings with positive mass; each mass \(\mu_t\) is a binary rational and the masses sum to \(1\). For candidates \(a,b\), let \(a\) defeat \(b\) when \(\sum_{t:a\succ_t b}\mu_t>1/2\); a tie gives neither candidate a Copeland point. The question is whether there is an \(E\subseteq D\), with \(|E|\le k\), such that \(p\) is a Copeland winner among \(C\cup E\), using each ranking restricted to those candidates. A solution is the set \(E\).
A plausible regime is a large association or online community where many members rank the same slate of potential candidates in the same way, while the chair can add candidates from a reserve list. There might be hundreds of thousands of voters but only hundreds or thousands of distinct rankings, so \(N\gg\tau\). A ranking is a complete type for this problem: voters with that ranking are indistinguishable to the election rule. Candidate addition stays a discrete agenda choice, while voter counts become masses. That is a natural high-multiplicity form of the authors’ own Copeland-CCAC problem, rather than a different question made easy by changing the objective.
I expect Class B: hardness transfers. From any explicit \(n\)-voter instance, form \(\mu_t=n_t/n\), where \(n_t\) is the number of voters with ranking \(t\). Every pairwise result, and thus every winner outcome after every candidate addition, is preserved. This is a polynomial-size map to the continuous input, so Lemma 6’s NP-hardness carries over. The continuous problem is also in NP: a proposed set \(E\) can be checked by summing the listed rational masses and computing the resulting Copeland scores. Thus this mirror is NP-complete. The combinatorics in the anchor are in choosing candidates to cover edges, not in the indivisibility of the voters.
The natural follow-up questions are whether tractability appears when \(\tau\) or the candidate agenda is restricted, and whether useful approximation or parameterized algorithms exist for particular regimes.
The weakest point is that this mirror gives a particularly clean high-multiplicity formulation, but not a new source of hardness: the discrete result embeds directly, and the reduction’s central combinatorics remain in candidate selection. Its strength is that it is a faithful, precise continuous-population version of a named result—not that continuity makes this anchor easier.
The strongest negative case against Lemma 6 is about expected methodological payoff. In the proposed mirror, Copeland uses the distribution \(\mu\) only through pairwise majority margins, while the chair still chooses a discrete set \(E\) of candidates. Once those margins are computed, the ranking support itself is irrelevant to the control decision. This mirror may therefore offer little opportunity to use the continuous optimization tools that motivate ChoCo.
That is a research-priority concern, though, not a reason to reject the mirror. Large associations or online communities with many repeated rankings and a reserve slate of candidates are plausible high-multiplicity settings. The problem still asks the paper’s question—whether adding at most \(k\) candidates can make \(p\) a winner—and it depends on population masses. Voters have no relevant identities; ties and majority thresholds remain meaningful in the continuum. Lemma 6’s discrete instances also embed exactly as rational mass distributions. That makes the mirror a clear Class B case, which the programme explicitly counts as useful.
I can’t honestly defeat this anchor. There is no named-result, multiplicity, identity, degeneracy, or prior-continuous-treatment objection supported by the paper or the brief. The limited use of continuous optimization is the best reason to rank this mirror below others; it does not establish that the question is unworthwhile in every scenario. On the stated criteria, Lemma 6 survives, so the paper should be green on this anchor.
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.