Answer: \(\mathrm{NP}\text{-complete}\)
Proposition 4.8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateControl by Adding/Removing Can- didates in Bloc voting is NP-complete, even in single-winner elections.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given registered candidates \(C\), addable candidates \(C'\), a target \(d\in C\), an addition limit \(r\), and a distribution \(\mu\) over complete rankings of \(C\cup C'\), does some \(A\subseteq C'\) with \(|A|\le r\) make \(d\) the unique highest-scoring candidate on the slate \(C\cup A\), where each type votes for its highest-ranked candidate on that slate?
Let \(C\) and \(C'\) be disjoint finite sets of registered and addable candidates, with \(d\in C\), \(m=|C\cup C'|\), and an integer addition limit \(0\le r\le |C'|\).
A society is given by its support: a list of \(\tau\) distinct strict complete rankings of \(C\cup C'\), each with positive binary-rational mass \(\mu_i\), where \(\sum_{i=1}^{\tau}\mu_i=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length; state running times in \(m,\tau,L,r\).
For a slate \(S\), each type assigns its entire mass to its highest-ranked candidate in \(S\). Write \(s_S(c)\) for the total mass assigned to \(c\). There is one seat, and a tie involving \(d\) counts as failure.
Is deciding whether there exists \(A\subseteq C'\) with \(|A|\le r\) such that \(s_{C\cup A}(d)>s_{C\cup A}(c)\) for every \(c\in(C\cup A)\setminus\{d\}\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For discrete voters, constructive control by adding candidates under Bloc is \(\mathrm{NP}\)-complete even with one seat, when Bloc coincides with plurality ([Meir, Procaccia, and Rosenschein](https://ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0008.pdf)).
No result explicitly treating this support-encoded, normalized rational-mass formulation was verified.
The problem is \(\mathrm{NP}\)-complete, and hence \(\mathrm{NP}\)-hard. This holds even when every mass is dyadic: its denominator is a power of two.
The cited paper establishes the discrete result in Proposition 4.8 and specifies adversarial tie-breaking in Remark 3.3. [Meir, Procaccia, and Rosenschein](https://ifaamas.org/Proceedings/aamas08/proceedings/pdf/paper/AAMAS08_0008.pdf). Below is a direct reduction that explicitly satisfies the support and normalization requirements.
A certificate is a subset \(A\subseteq C'\) with \(|A|\le r\).
Write each input mass as \(\mu_i=a_i/b_i\), where \(a_i,b_i\) are positive integers encoded in binary. Set
\(D=\prod_{i=1}^{\tau}b_i\), and \(w_i=a_i(D/b_i)\).
The bit length of \(D\) is \(O(L)\), because the sum of the denominator bit lengths is at most \(L\). Each \(w_i\) also has \(O(L)\) bits. These integers can be computed in \(O(\tau L^2)\) bit operations using ordinary integer multiplication and division.
For each ranking, scan until encountering a candidate in \(C\cup A\), and add \(w_i\) to that candidate’s integer score. These scores equal \(D s_{C\cup A}(c)\), so integer comparison checks the required strict inequalities exactly.
With indexed candidate identifiers, a conservative bound for certificate verification, including arithmetic preprocessing, is
\(O\!\left(\tau L^2+(\tau m+m)L\right)\)
bit operations. Checking \(|A|\le r\) fits within this bound. Thus the problem belongs to \(\mathrm{NP}\).
For completeness, exhaustive enumeration gives a deterministic algorithm taking
\(O\!\left(\tau L^2+\left(\sum_{j=0}^{r}\binom{|C'|}{j}\right)(\tau m+m)L\right)\).
In particular, for each fixed \(r\), this is polynomial time. The hardness result concerns unrestricted input \(r\).
Use the standard \(\mathrm{NP}\)-complete problem Exact Cover by 3-Sets. Its input consists of a universe \(U\), with \(|U|=n=3q\), and a family \(\mathcal F=\{F_1,\ldots,F_t\}\) of three-element subsets of \(U\). The question is whether some \(q\) members partition \(U\).
We may restrict to \(q\ge1\), since the empty-universe case is trivial. If \(t<q\), the instance is necessarily negative; map it to the fixed negative election having \(C=\{d,x\}\), \(C'=\varnothing\), \(r=0\), and the single ranking \(x\succ d\) of mass \(1\). Hence assume \(t\ge q\).
Create a registered candidate \(x_u\) for each \(u\in U\), and an addable candidate \(a_j\) for each \(F_j\). Set the addition limit to \(r=q\).
Initially construct rankings with positive integer weights:
Use any fixed order within unspecified portions, so every ranking is strict and complete.
The total weight is \(T=4+4n\). Let \(B\) be the smallest power of two satisfying \(B\ge T\), and put \(h=B-T\).
Add registered candidates \(z_1,\ldots,z_h\). For each \(z_\ell\), add one ranking of weight \(1\) with \(z_\ell\) first. Place these new candidates at the bottom of every previously constructed ranking. Complete each new ranking arbitrarily.
Thus
\(C=\{d\}\cup\{x_u:u\in U\}\cup\{z_1,\ldots,z_h\}\), and \(C'=\{a_1,\ldots,a_t\}\).
The total integer weight is now \(B\). Divide every weight by \(B\). All masses are positive dyadic rationals and sum to \(1\).
Finally, merge any identical complete rankings by adding their masses. This produces a list of distinct rankings. Merging preserves every slate’s scores because identical rankings choose the same highest available candidate.
Fix any \(A\subseteq C'\). Write \(s_A(c)=s_{C\cup A}(c)\).
The ranking with \(d\) first always supports \(d\). Every other ranking has an available registered candidate above \(d\). Consequently,
\(B s_A(d)=4\).
For an element \(u\), the weight-\(3\) ranking always supports \(x_u\). Its weight-\(1\) ranking supports an added candidate precisely when some selected set contains \(u\). No other ranking can support \(x_u\). Therefore,
\(B s_A(x_u)=3+\mathbf 1\{u\notin\bigcup_{a_j\in A}F_j\}\).
A selected candidate \(a_j\) can receive weight only from the weight-\(1\) element rankings for elements of \(F_j\). Since \(|F_j|=3\),
\(B s_A(a_j)\le3\).
Finally, each padding candidate receives exactly its own weight-\(1\) ranking:
\(B s_A(z_\ell)=1\).
These identities prove the exact equivalence
\(d\text{ is the strict winner on }C\cup A\quad\Longleftrightarrow\quad\bigcup_{a_j\in A}F_j=U\).
Indeed, an uncovered element gives a rival \(x_u\) tying \(d\) at score \(4/B\), which is failure. If every element is covered, every rival has score at most \(3/B\), strictly below \(d\).
If the exact-cover instance is positive, add the \(q\) candidates corresponding to its exact cover. Every element is covered, so \(d\) wins strictly.
Conversely, suppose some \(A\) with \(|A|\le q\) makes \(d\) win strictly. The score calculation proves that its corresponding sets cover \(U\). Hence
\(3q=|U|=\left|\bigcup_{a_j\in A}F_j\right|\le\sum_{a_j\in A}|F_j|=3|A|\le3q\).
All inequalities are equalities. Thus \(|A|=q\), and the selected sets are pairwise disjoint: otherwise their union would have cardinality strictly smaller than the sum of their cardinalities. They therefore form an exact cover.
Because \(T\le B<2T\), we have \(h<T=4n+4\). Consequently, the constructed instance satisfies
\(m=1+n+t+h=O(n+t)\), \(\tau\le1+2n+h=O(n)\), and \(r=q=n/3\).
Each mass requires \(O(\log(n+1))\) bits. Writing all complete rankings and merging duplicates takes polynomial time; for example, a straightforward implementation takes \(O((n+t)^3\log(n+t+1))\) bit operations.
With indexed candidate names, the output length satisfies
\(L=O\!\left(n(n+t)\log(n+t+1)\right)\).
Thus this is a polynomial-time many-one reduction to exactly the required support-encoded, normalized formulation.
The reduction proves \(\mathrm{NP}\)-hardness even for dyadic masses, and exact polynomial-time certificate verification proves membership in \(\mathrm{NP}\). Therefore the problem is \(\mathrm{NP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The direct reduction establishes \(\mathrm{NP}\)-hardness for the specified support encoding, even with dyadic masses, and the certificate verification establishes membership in \(\mathrm{NP}\). I found no major or minor mathematical issues.
Scanning each complete ranking until its first available candidate correctly implements the voting rule. Because the masses are normalized, every accumulated integer score is at most \(D\), so score arithmetic also uses \(O(L)\)-bit integers. The stated verification bound
\[
O\!\left(\tau L^2+(\tau m+m)L\right)
\]
is a valid conservative bound under the stated indexed-candidate convention.
\[
O\!\left(\tau L^2+
\left(\sum_{j=0}^{r}\binom{|C'|}{j}\right)(\tau m+m)L\right)
\]
is consistent with the verification procedure. The fixed-\(r\) polynomial-time claim is correct and does not conflict with hardness when \(r\) is unrestricted.
In particular, the element ranking puts exactly the addable candidates associated with sets containing that element above its registered candidate. Every other candidate lies below that registered candidate. This condition is sufficient for all subsequent score claims; no special choice of the unspecified ordering is needed.
Division by \(B\) produces positive dyadic masses summing to one. Padding candidates appear below the originally decisive candidates in all old rankings, while each new ranking has its own registered padding candidate first. Thus padding does not change the original score behavior.
Merging identical rankings preserves every slate’s scores and ensures that the final support consists of distinct rankings. The merged masses remain positive and dyadic. These statements also cover an element belonging to no listed set, whose element ranking can coincide with its baseline ranking.
Consequently, an uncovered element creates a tie at \(4/B\), while complete coverage leaves every rival strictly below \(4/B\). The asserted winner–coverage equivalence is correct, including the required strict tie convention.
Required feedback: None. No missing lemma, unsupported critical inference, or failing edge case prevents verification.
⟨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.