Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet Y ∈{FO, RC, RV}. Then, RCAC for µY ◦ϕ where ϕ ∈{Borda, Maximin, Copelandα}, and RCDC for µY ◦ϕ where ϕ ∈{Borda, Copelandα} are NP-hard. Faliszewski, Hemaspaandra and Hemaspaandra [12] proved that both CCDC and DCDC for Maximin are polynomial-time solvable. We extend these results to resolute control problems.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given registered candidates \(R\), addable candidates \(D\), a nonempty set \(J\subseteq R\), a budget \(b\), and a list of \(\tau\) complete rankings \(t\) over \(R\cup D\) with positive rational masses \(\mu_t\) summing to \(1\), is there an \(A\subseteq D\), \(|A|\le b\), such that no candidate in \(J\) is a Maximin winner after restricting every ranking to \(R\cup A\)? Here \(M_\mu(a,c)=\sum_{t:a\succ_t c}\mu_t\), and the score of \(a\) is \(\min_{c\ne a}M_\mu(a,c)\); under random-candidates tie-breaking, the condition is that the resulting winner set is disjoint from \(J\).
Given disjoint finite sets of registered candidates \(R\) and addable candidates \(D\), assume \(|R|\ge 2\), \(D\ne\varnothing\), a nonempty set \(J\subseteq R\), and an integer budget \(1\le b\le |D|\).
A society is given by its support: the list of \(\tau\) distinct strict complete rankings over \(R\cup D\) with positive binary-rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings.
For \(A\subseteq D\), restrict every ranking to \(S=R\cup A\). Define \(M_\mu(a,c)=\sum_{t:a\succ_t c}\mu_t\), the Maximin score \(s_S(a)=\min_{c\in S\setminus\{a\}}M_\mu(a,c)\), and the winner set \(W(S)=\operatorname*{arg\,max}_{a\in S}s_S(a)\).
Random-candidates tie-breaking selects uniformly from \(W(S)\); success means \(W(S)\cap J=\varnothing\). Candidate additions are indivisible, and the society remains fixed.
Let \(m=|R\cup D|\), \(k=|J|\), and \(L\) be the total binary input length; state running times in \(m,\tau,L,b,k\).
Is deciding whether there exists \(A\subseteq D\) with \(|A|\le b\) and \(W(R\cup A)\cap J=\varnothing\) solvable in polynomial time, or is it NP-hard?
For an explicitly listed finite electorate, this candidate-addition problem with random-candidates tie-breaking is NP-hard. Its discrete version also admits an \(O(2^k\operatorname{poly}(m,n))\)-time algorithm, where \(n\) is the number of voters.
The problem is \(\mathrm{NP}\)-complete. Moreover, it admits an algorithm running in \(O(2^k\operatorname{poly}(m,\tau,L))\) time.
The hardness proof uses the finite-electorate hardness stated in the question. The algorithm below works directly with rational masses and does not expand them into voters.
Write each input mass as \(\mu_t=p_t/q_t\), with positive binary-encoded integers \(p_t,q_t\). Let \(Q=\prod_{t=1}^{\tau}q_t\). Its binary length is \(O(L)\). Thus every pairwise support can be represented exactly as
\(M_\mu(a,c)=Q^{-1}\sum_{t:a\succ_t c}p_t(Q/q_t).\)
The numerators also have \(O(L)\) bits, because the masses sum to one.
After computing all pairwise supports, a proposed addition set \(A\) can be verified by computing the scores and winner set on \(R\cup A\). All comparisons are exact integer comparisons with the common denominator \(Q\).
Using elementary integer arithmetic, preprocessing and verification take \(O(L^3+\tau m^2L)\) time. The certificate is simply the list of candidates in \(A\), whose size is polynomial in \(L\). Hence the problem belongs to \(\mathrm{NP}\).
Start with an instance of the explicitly listed finite-electorate problem whose hardness is given in the question. Let its electorate contain \(n\ge 1\) voters, and let \(v(a,c)\) count the voters ranking \(a\) above \(c\).
Grouping identical rankings and assigning each its frequency divided by \(n\) already preserves all winner sets. To cover even the stricter interpretation in which “binary-rational” requires dyadic masses, use the following padding construction.
Duplicate every voter. Choose the smallest power of two \(N\) satisfying \(N\ge 2n\), and put
\(h=(N-2n)/2.\)
Both \(N\) and \(2n\) are even, so \(h\) is a nonnegative integer. Fix any complete ranking \(\rho\), and add \(h\) voters with ranking \(\rho\) and \(h\) with its reverse. Every reverse pair contributes exactly one vote to each ordered pairwise comparison. Consequently, the resulting normalized support is
\(M_\mu(a,c)=(2v(a,c)+h)/N.\)
Aggregate identical rankings and give each distinct ranking its multiplicity divided by \(N\). These masses are positive dyadic rationals summing to one.
For any restricted candidate set \(S\), define the original count-based Maximin score by
\(s^{\mathrm{old}}_S(a)=\min_{c\in S\setminus\{a\}}v(a,c).\)
Since the affine map \(x\mapsto(2x+h)/N\) is strictly increasing,
\(s^\mu_S(a)=(2s^{\mathrm{old}}_S(a)+h)/N.\)
Therefore the two societies have exactly the same winner set for every \(S\). In particular, they have the same answer for every permitted addition set \(A\). The sets \(R,D,J\) and budget \(b\) remain unchanged.
The construction has polynomial size: \(N<4n\), there are at most \(n+2\) distinct rankings, and each mass requires \(O(\log(n+1))\) bits. It is therefore a polynomial-time many-one reduction from the hard problem supplied in the question.
This proves \(\mathrm{NP}\)-hardness, including for dyadic masses. Together with Section 1, it proves \(\mathrm{NP}\)-completeness.
The following characterization also transfers the stated parameterized tractability to the support representation.
Enumerate a candidate \(w\in(R\cup D)\setminus J\) and a threshold
\(q\in\{M_\mu(w,c):c\in(R\cup D)\setminus\{w\}\}.\)
There are at most \(m(m-1)\) such pairs.
Set \(S_0=R\cup\{w\}\), and let \(\varepsilon_w\) equal one if \(w\in D\), and zero otherwise. Discard the pair if \(\varepsilon_w>b\), or if some \(c\in S_0\setminus\{w\}\) satisfies \(M_\mu(w,c)<q\).
For every remaining pair, define the unwanted candidates still requiring a score decrease:
\(T=\{j\in J:s_{S_0}(j)\ge q\}.\)
An additional candidate is admissible precisely when it preserves the required lower bound on \(w\)'s score. Thus define
\(E=\{d\in D\setminus S_0:M_\mu(w,d)\ge q\}.\)
For each \(d\in E\), define its covered subset
\(C_d=\{j\in T:M_\mu(j,d)<q\}.\)
For any \(B\subseteq E\), put \(S=S_0\cup B\). By the admissibility tests, \(s_S(w)\ge q\).
If \(j\in J\setminus T\), then \(s_{S_0}(j)<q\). Adding candidates can only decrease its Maximin score, so \(s_S(j)<q\).
If \(j\in T\), all its comparisons against \(S_0\setminus\{j\}\) have support at least \(q\). Consequently,
\(s_S(j)<q\quad\Longleftrightarrow\quad j\in\bigcup_{d\in B}C_d.\)
It follows that, whenever
\(\bigcup_{d\in B}C_d=T\quad\text{and}\quad |B|\le b-\varepsilon_w,\)
the addition set \((\{w\}\cap D)\cup B\) succeeds: every candidate in \(J\) has score strictly below \(w\), and therefore none can be a winner.
Conversely, suppose \(A\) succeeds. Choose any winner \(w\in W(R\cup A)\). Success implies \(w\notin J\). Take \(q=s_{R\cup A}(w)\). Because the minimum defining this score is attained, this threshold occurs in the enumeration.
Now \(S_0\subseteq R\cup A\). Every comparison of \(w\) against a selected candidate has support at least \(q\), so the pair passes the initial test and \(B=A\setminus\{w\}\) is contained in \(E\).
Every \(j\in J\) has score strictly below \(q\); otherwise it would also be a winner. For \(j\in T\), its comparison witnessing this strict inequality must therefore be against a candidate in \(B\). Hence the sets \(C_d\), for \(d\in B\), cover \(T\), within the remaining budget.
Thus the original instance succeeds if and only if some enumerated pair has a cover within its remaining budget.
For a fixed pair, use dynamic programming over subsets of \(T\). Process the admissible candidates one at a time. A state records the minimum number of processed candidates whose covered union is exactly \(U\subseteq T\).
Initially, only the empty union has finite cost, namely zero. When processing \(d\), each finite state \(U\) gives two transitions:
These transitions exhaust the possibilities for selecting processed candidates, which proves the state invariant by induction. Accept the pair exactly when the final cost for \(T\) is at most \(b-\varepsilon_w\). Costs can be capped at \(b+1\).
There are at most \(2^k\) states, at most \(m\) candidates per pair, and at most \(m^2\) pairs. Accounting for exact rational preprocessing, comparisons, subset operations, and budget counters, a conservative bit-operation bound is
\(O\!\left(L^3+\tau m^2L+m^3(k+1)L+2^k m^3\bigl(k+\log(b+2)\bigr)\right).\)
In particular, the running time is \(O(2^k\operatorname{poly}(m,\tau,L))\). This proves fixed-parameter tractability in \(k\), alongside general \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes \(\mathrm{NP}\)-completeness and gives a valid algorithm with running time \(O(2^k\operatorname{poly}(m,\tau,L))\). No major or minor mathematical issues were found.
The common-denominator construction is valid. Since the denominator encodings contribute to the total input length \(L\), the product \(Q=\prod_t q_t\) has \(O(L)\) bits.
Each scaled weight \(p_t(Q/q_t)\) is an integer. Positivity and \(\sum_t\mu_t=1\) imply that every pairwise numerator lies between zero and \(Q\), so its bit length is also \(O(L)\). Thus pairwise supports, scores, and winner comparisons can all be computed exactly.
The stated preprocessing bound \(O(L^3+\tau m^2L)\) is conservative and sufficient:
A certificate lists at most \(b\le |D|\) candidates. Checking membership in \(D\), distinctness, the budget, and the required winner condition is polynomial. The membership claim is therefore justified.
The proof uses the finite-electorate hardness explicitly supplied by the task. This is an authorized premise, rather than an unsupported external theorem.
The padding calculation is correct. For \(n\ge1\), the smallest power of two \(N\ge2n\) satisfies \(N<4n\). Both \(N\) and \(2n\) are even, so \(h=(N-2n)/2\) is a nonnegative integer.
After duplication, there are \(2n\) original voters. The \(h\) reverse-ranking pairs add \(2h\) voters, giving exactly \(N\) voters. For every distinct candidate pair, each reverse-ranking pair contributes one vote in each direction. Consequently,
\[
M_\mu(a,c)=\frac{2v(a,c)+h}{N}.
\]
Restriction to a candidate subset preserves the relative order of every retained pair. The same formula therefore applies to every permitted restricted election.
Taking minima commutes with this strictly increasing affine transformation:
\[
s^\mu_S(a)=\frac{2s^{\mathrm{old}}_S(a)+h}{N}.
\]
Hence score comparisons, ties, and complete winner sets are preserved. This establishes preservation of the success condition for every addition set, including the empty set.
Aggregation produces at most \(n+2\) distinct rankings, with positive dyadic masses summing to one. The construction and its output size are polynomial in the explicitly listed electorate input. The reduction also preserves \(R,D,J,b\), and thus preserves their stated restrictions.
The hardness conclusion, including the dyadic interpretation of binary-rational masses, follows.
Every successful election has a winner \(w\notin J\). Because \(|R|\ge2\), the minimum defining its score is over a nonempty finite set and is attained. Therefore its score is among the enumerated values \(M_\mu(w,c)\).
The initial feasibility test correctly checks the registered candidates and the mandatory inclusion of \(w\). The set \(E\) contains exactly the remaining additions that preserve the lower bound \(s_S(w)\ge q\).
The definition of \(T\) correctly distinguishes unwanted candidates already strictly below \(q\) from those that still need a comparison below \(q\).
The forward implication is valid. Adding candidates can only decrease an existing candidate’s Maximin score. Thus every \(j\in J\setminus T\) remains below \(q\).
For \(j\in T\), all comparisons in \(S_0\) have support at least \(q\). Its final score is below \(q\) exactly when some selected candidate \(d\in B\) satisfies \(M_\mu(j,d)<q\). This is precisely the covering condition.
If all of \(T\) is covered, every unwanted candidate has score strictly below \(q\), while \(w\) has score at least \(q\). Therefore no unwanted candidate can be a winner. This reasoning does not require \(w\) itself to remain a winner.
The converse is also valid. In a successful election, every unwanted candidate has score strictly below the chosen winner’s score \(q\). For a candidate in \(T\), a comparison witnessing this inequality cannot belong to \(S_0\); it must involve a candidate in \(B\). The resulting sets cover \(T\).
Budget accounting is exact: \(|B|=|A|-\varepsilon_w\). Both registered and addable choices of \(w\) are handled correctly.
The skip/select transitions exhaust the subsets of processed admissible candidates. The minimum-cost invariant follows by induction, and testing the final cost of \(T\) gives exactly the required cover decision.
Capping costs at \(b+1\) preserves the decision because every remaining budget is at most \(b\). The initialization also handles \(T=\varnothing\), allowing a cover with zero additional candidates.
There are at most \(m^2\) candidate-threshold pairs, at most \(m\) admissible candidates per pair, and at most \(2^k\) states. The stated bound
\[
O\!\left(L^3+\tau m^2L+m^3(k+1)L+
2^k m^3\bigl(k+\log(b+2)\bigr)\right)
\]
adequately accounts for preprocessing, threshold comparisons, subset operations, and budget counters.
The algorithm operates directly on the support representation and does not depend on expanding rational masses into voters.
No additional lemma, clarification, or correction is required. Both the complexity classification and the parameterized running-time claim are established.
⟨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.