Answer: \(\mathrm{NP}\)-complete under the standard input-budget constraint \(|S|\leq k\), even with \(|T|=1\) and \(\mu_t=1\).
Theorem 5.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateBorda-CCDC is $\np$-hard, even for elections with only ten voters.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), complete ranking types \(T\) with rational masses \(\mu_t\ge 0\) satisfying \(\sum_t\mu_t=1\), a preferred candidate \(p\), an integer budget \(k\), and a bundle map \(\beta:C\to 2^C\) with \(c\in\beta(c)\), does there exist \(S\subseteq C\) with \(|S|\le k\) and \(p\notin\beta(S)\) such that \(p\) is a Borda co-winner after deleting \(\beta(S)=\bigcup_{s\in S}\beta(s)\)?
A type \(t\in T\) is a strict total order of \(C\), with binary-encoded rational mass \(\mu_t\geq 0\) and \(\sum_{t\in T}\mu_t=1\). A bundle map satisfies \(c\in\beta(c)\) for every \(c\in C\), and \(\beta(S)=\bigcup_{s\in S}\beta(s)\).
For a chosen \(S\subseteq C\), let \(D=\beta(S)\). Rankings are restricted to \(C\setminus D\), and each survivor \(c\) has Borda score \(\sum_{t\in T}\mu_t\,|\{d\in C\setminus D:t\text{ ranks }c\text{ above }d\}|\). Candidate \(p\) is a co-winner if its score is maximal.
Is the weighted-type Borda-Comb-CCDC problem defined above NP-hard, or solvable in polynomial time?
For finite voter lists, Borda-CCDC is NP-hard even with ten voters.
For finite voter lists with bundles, Borda-Comb-CCDC is NP-hard even with one voter, since Borda satisfies unanimity.
Weighted-type Borda-Comb-CCDC is \(\mathrm{NP}\)-complete, even with one type of mass \(1\), under the standard budgeted definition.
Your definitions omit the budget. I use the standard convention: the input includes a nonnegative integer \(k\), and the question is whether there exists \(S\subseteq C\) with \(|S|\leq k\), \(p\notin\beta(S)\), and \(p\) a co-winner after deleting \(\beta(S)\). The budget counts selected candidates, rather than all candidates in their bundles.
Use the stated known result: finite-list Borda-Comb-CCDC is \(\mathrm{NP}\)-hard even with one voter. This also follows from Theorem 6 of [*Elections with Few Voters: Candidate Control Can Be Easy*](https://elektronaj.github.io/newzutot/papers/fewvotersaaai.pdf), which applies to voting rules satisfying unanimity. Borda satisfies that hypothesis: a unanimously first-ranked candidate scores strictly more than every other candidate in each vote, and hence in their sum.
Take any instance of that one-voter problem. Write \(t\) for its voter's strict ranking. Construct a weighted-type instance by retaining \(C\), \(p\), \(\beta\), and \(k\), and setting \(T=\{t\}\) and \(\mu_t=1\).
This is a polynomial-time construction. The mass is a binary-encoded rational of constant encoding length, is nonnegative, and satisfies the required normalization.
To verify correctness, fix any \(S\subseteq C\) with \(|S|\leq k\), and put \(D=\beta(S)\). Both instances delete exactly \(D\). If \(p\in D\), the action is unsuccessful in both instances. Otherwise, for every survivor \(c\in C\setminus D\), its weighted score is
\(\operatorname{score}_{\mathrm{weighted}}(c)=1\cdot|\{d\in C\setminus D:t\text{ ranks }c\text{ above }d\}|=\operatorname{score}_{\mathrm{one\ voter}}(c).\)
Thus all surviving candidates have identical scores in the two instances. In particular, \(p\) is a co-winner in one if and only if it is a co-winner in the other.
The construction therefore preserves yes-instances and no-instances, proving \(\mathrm{NP}\)-hardness. Neither rational weights nor normalization weaken this conclusion: the hard instances already use the single mass \(1\).
A certificate is the selected set \(S\), represented by at most \(|C|\) candidate identifiers. A verifier checks \(|S|\leq k\), computes \(D=\beta(S)\), and rejects if \(p\in D\).
It remains to verify that score comparisons take polynomial time despite rational masses. Write each input mass as \(\mu_t=a_t/b_t\), with integers \(a_t\geq0\) and \(b_t\geq1\), and define \(Q=\prod_{t\in T}b_t\).
The binary length of \(Q\) is at most the sum of the binary lengths of the denominators, up to a constant. It is therefore polynomial in the input length.
For each survivor \(c\), compute the integer
\(N_c=\sum_{t\in T}a_t(Q/b_t)\,|\{d\in C\setminus D:t\text{ ranks }c\text{ above }d\}|.\)
Every count is computable from the explicitly supplied ranking and lies between \(0\) and \(|C|-1\). All intermediate integers have polynomial binary length, so these computations take polynomial time. Since \(Q>0\) and \(N_c=Q\operatorname{score}(c)\), the verifier accepts precisely when \(N_p\geq N_c\) for every survivor \(c\).
Consequently, the budgeted problem belongs to \(\mathrm{NP}\) and is \(\mathrm{NP}\)-complete. If no budget was intended, that is a different decision problem; the hardness reduction above specifically preserves the standard budget constraint.
⟨structured verdict parsed — rendered above⟩
The proof correctly establishes \(\mathrm{NP}\)-completeness for the explicitly stated budgeted problem. However, USER_TASK does not specify a budget or a bound on the selected set. Under a strict reading of the supplied definitions, the output therefore establishes a conditional result rather than fully settling the target.
There is no identified mathematical error in the reduction or the verification algorithm.
The prover adds an input integer \(k\) and requires \(|S|\leq k\). This is explicitly disclosed and matches the standard budgeted interpretation of candidate control, but it is absent from USER_TASK.
This distinction affects the quantified set of admissible actions. A reduction preserving budgeted feasibility does not automatically preserve feasibility when arbitrary selections are allowed. The final caveat correctly acknowledges this limitation; nevertheless, the accompanying "resolved" claim leaves this dependency unresolved.
Minimum clarification: Confirm that USER_TASK includes a budget \(k\) counting selected candidates. If it does, this scope issue disappears without any change to the mathematical argument. If it does not, the supplied proof does not classify that target.
The cited Theorem 6 states that, for every voting rule satisfying unanimity, combinatorial constructive control by deleting candidates is \(\mathrm{NP}\)-hard even with one voter. Here unanimity requires a unanimously first-ranked candidate to be the unique winner. The source uses the non-unique-winner model and explicitly represented bundles containing their selecting candidates. These conventions match the prover’s budgeted formulation. [Cited paper, preliminaries and Theorem 6](https://elektronaj.github.io/newzutot/papers/fewvotersaaai.pdf)
The stated check for Borda is sufficient: a unanimously first-ranked candidate receives strictly more points than each competitor in every vote. With one voter, there is no issue concerning an empty electorate. No additional hardness construction is needed because the applicable source result is also supplied in USER_TASK.
Retaining the candidates, distinguished candidate, bundles, and budget, while replacing the sole voter by a type of mass \(1\), preserves all relevant structural restrictions.
The ranking remains a strict total order. The mass is nonnegative, normalized, and has constant encoding length. Copying the remaining explicit input takes polynomial time.
The proof considers every eligible selected set \(S\), not merely an optimal or specially structured selection. Both instances delete the same union of bundles.
When the distinguished candidate is deleted, both actions fail. Otherwise, every survivor has exactly the same score in both instances, because the only type has mass \(1\). Consequently, all score comparisons and the co-winner condition agree.
Because the budget is also retained, the same selected sets are admissible in both instances. This establishes both directions of the reduction.
A set of candidate identifiers has polynomial encoding length, even if the binary-encoded budget exceeds the number of candidates. Checking its cardinality, computing the bundle union, and checking survival of the distinguished candidate take polynomial time under the explicit representation used here.
The product \(Q\) is positive because every denominator is positive. Its binary length is bounded by the sum of the denominator lengths, so forming it does not require exponentially many bits.
Each division \(Q/b_t\) is exact. The ranking counts lie in the stated range, and multiplying by the encoded numerator and summing over the explicitly listed types preserves polynomial bit length. Thus the integer score comparisons are polynomial-time computations.
The identity \(N_c=Q\operatorname{score}(c)\) justifies the comparisons because \(Q>0\). Zero masses cause no problem.
The verifier handles an empty selection and a zero budget. Rejecting deletion of the distinguished candidate ensures that every evaluated successful action leaves a nonempty survivor set. If that candidate is the sole survivor, its score is zero and the acceptance condition correctly holds.
Accordingly, the budgeted \(\mathrm{NP}\)-completeness claim is rigorous. The only blocking issue is whether that budgeted problem is the intended USER_TASK. This is a specification dependency, not a refutation of the conditional theorem.
⟨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.