Answer: \(\mathrm{NP}\text{-complete}\), even with dyadic masses; also \(\mathrm{W}[2]\)-hard parameterized by \(B\).
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePlurality-CSB and Borda-CSB are both NP-hard and W[2]-hard for the parameter B, even for two candidates and even if each shift action has effects of either +1 or 0 on each voter.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given two candidates \(p,d\), a budget \(B\), and \(\tau\) types with positive rational masses \(\mu_t\) summing to \(1\), each type has a ranking and a response \(a_{jt}\in\{0,1\}\) to each of \(\zeta\) campaigns. Is there a set \(S\) of at most \(B\) campaigns such that, after their effects add and \(p\)'s position is capped at the top, at least half the society ranks \(p\) first? Equivalently, does \(\sum_{t:\,p\text{ initially ranks first or }\sum_{j\in S}a_{jt}\ge1}\mu_t\ge\frac12\) hold for some such \(S\)?
The candidate set is \(\{p,d\}\), so \(m=2\). A society is given by its support: a list of \(\tau\) distinct types with positive binary-rational masses \(\mu_t\) satisfying \(\sum_t\mu_t=1\). Each type consists of a strict ranking and its responses to all campaigns; \(\tau\) is the support size, not the number of possible types.
There are \(\zeta\) explicitly listed campaigns, each costing one and usable once, with responses \(a_{jt}\in\{0,1\}\), and a binary-encoded budget \(B\in\mathbb Z_{\ge0}\). Selecting \(S\subseteq\{1,\ldots,\zeta\}\) shifts \(p\) upward by \(\sum_{j\in S}a_{jt}\) positions throughout type \(t\), capped at first place. Campaigns act on the entire mass of each type.
Success means that \(p\) is a Plurality winner, with ties accepted: \(\sum_{t:\,p\text{ initially first}\;\lor\;\sum_{j\in S}a_{jt}\ge1}\mu_t\ge\tfrac12\). Let \(L\) be the total input bit length; state running times in \(m,\tau,\zeta,B,L\).
Is deciding whether a successful campaign set \(S\) with \(|S|\le B\) exists solvable in polynomial time, or is it NP-hard?
For finite unweighted electorates, this campaign problem is NP-hard and \(\mathrm{W}[2]\)-hard parameterized by \(B\), even with two candidates and only nonnegative unit effects; the result holds for both Plurality and Borda. [Discrete result](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p67.pdf)
No result settling the exact rational-mass formulation above was located in the literature search.
The problem is \(\mathrm{NP}\)-complete, even when all masses are dyadic rationals with a common denominator. It is also \(\mathrm{W}[2]\)-hard parameterized by \(B\).
Here \(\tau\) is the number of explicitly listed, distinct support types. The reduction below respects that requirement.
Let \(T_0\) be the types initially ranking \(p\) first, and let \(T_1\) be the remaining types. Define
\(\alpha=\sum_{t\in T_0}\mu_t,\qquad A_j=\{t\in T_1:a_{jt}=1\}.\)
Because \(m=2\), one positive response moves \(p\) to first place. Further positive responses have no additional effect. Thus the final Plurality score of \(p\), measured as mass, is exactly
\(w_p(S)=\alpha+\sum_{t\in\bigcup_{j\in S}A_j}\mu_t.\)
Consequently, the decision problem asks whether at most \(B\) of the explicitly listed sets \(A_j\) cover mass at least \(\tfrac12-\alpha\).
If \(\alpha\ge\tfrac12\), the empty campaign set succeeds. The hardness proof concerns instances with \(\alpha<\tfrac12\).
A certificate is a bit vector specifying \(S\subseteq\{1,\ldots,\zeta\}\). Its length is \(\zeta\), regardless of the binary encoding of \(B\). Count its selected campaigns, check \(|S|\le B\), and determine the covered types.
The mass comparison can be performed exactly. Write each input mass as \(\mu_t=u_t/v_t\), with positive binary-encoded integers \(u_t,v_t\), and set
\(D=\prod_{t=1}^{\tau}v_t.\)
The bit length of \(D\) is at most the sum of the denominator bit lengths, hence is \(O(L)\). Each integer \(u_t(D/v_t)=D\mu_t\) also has \(O(L)\) bits, since \(\mu_t\le1\). The numerator \(N=Dw_p(S)\) is obtained by summing these integers over the types finally ranking \(p\) first. Success is exactly the integer comparison \(2N\ge D\).
Using schoolbook integer arithmetic, a conservative verification bound is
\(O\!\left(L+m\tau+\zeta\tau+\tau L^2\right),\qquad m=2.\)
Therefore the problem belongs to \(\mathrm{NP}\).
Use the standard \(\mathrm{NP}\)-complete Set Cover problem: given an explicitly listed universe \(U\), subsets \(F_1,\ldots,F_s\subseteq U\), and a nonnegative integer \(k\), decide whether at most \(k\) of those sets cover \(U\).
If \(U\) is empty, output a constant-size yes-instance of the campaign problem. If some element belongs to no listed set, output a constant-size no-instance. Such instances can have one type of mass \(1\), one ineffective campaign, and budget \(0\), with the type ranking \(p\) first or \(d\) first, respectively.
For the remaining construction, therefore, assume
\(n=|U|\ge1,\qquad \bigcup_{j=1}^{s}F_j=U.\)
For each \(x\in U\), define its incidence vector
\(v(x)=\left(\mathbf{1}_{x\in F_1},\ldots,\mathbf{1}_{x\in F_s}\right).\)
Partition \(U\) into equivalence classes \(\mathcal C\) under equality of these vectors. Every vector is nonzero, because the listed sets cover \(U\). Different classes have different vectors.
Let \(q\) be the smallest power of two strictly greater than \(n\). Then
\(n<q\le2n.\)
Construct the following support types:
| Type | Initial ranking | Campaign responses | Mass |
|---|---|---|---|
| Initial-support type \(t_p\) | \(p\succ d\) | All zero | \((q-n)/(2q)\) |
| Permanent-rival type \(t_d\) | \(d\succ p\) | All zero | \(1/2\) |
| Element type \(t_C\), for each \(C\in\mathcal C\) | \(d\succ p\) | \(a_{j,t_C}=\mathbf{1}_{x\in F_j}\), for any \(x\in C\) | \(|C|/(2q)\) |
The responses for \(t_C\) are well-defined because every element of \(C\) has the same incidence vector.
Create one campaign for each \(F_j\), with unit cost and usable once. Set
\(m=2,\qquad \zeta=s,\qquad B=k.\)
Every mass is positive: \(q-n>0\), and every equivalence class is nonempty. Their sum is
\(\frac{q-n}{2q}+\frac12+\sum_{C\in\mathcal C}\frac{|C|}{2q} =\frac{q-n+q+n}{2q}=1.\)
All masses are dyadic, since \(2q\) is a power of two.
All support types are distinct:
Thus
\(\tau=|\mathcal C|+2\le n+2.\)
Since \(q\le2n\), every mass requires \(O(\log(n+1))\) bits. The output bit length satisfies
\(L_{\mathrm{out}}=O\!\left((n+2)(s+\log(n+1))+\log(k+2)\right).\)
Incidence vectors and their equivalence classes can be constructed in polynomial time, so this is a polynomial-time reduction.
For a selected campaign set \(S\subseteq\{1,\ldots,s\}\), write
\(c(S)=\left|\bigcup_{j\in S}F_j\right|.\)
Every equivalence class is either entirely covered or entirely uncovered. Its mass moves to \(p\) exactly when it is covered. The permanent-rival type never moves. Therefore
\(w_p(S)=\frac{q-n}{2q}+\frac{c(S)}{2q} =\frac{q-n+c(S)}{2q}.\)
It follows that
\(w_p(S)\ge\frac12 \quad\Longleftrightarrow\quad q-n+c(S)\ge q \quad\Longleftrightarrow\quad c(S)\ge n.\)
Because \(c(S)\le n\), success holds exactly when the selected sets cover all of \(U\). A complete cover gives \(w_p(S)=\tfrac12\), which succeeds under the stipulated acceptance of ties.
Finally, \(|S|\le B\) is exactly \(|S|\le k\). Hence the Set Cover instance is a yes-instance if and only if the constructed campaign instance is a yes-instance.
This proves \(\mathrm{NP}\)-hardness. Together with Section 2, it proves \(\mathrm{NP}\)-completeness.
The same reduction proves \(\mathrm{W}[2]\)-hardness parameterized by \(B\), using the standard \(\mathrm{W}[2]\)-completeness of Set Cover parameterized by \(k\): the construction has \(B=k\), and the trivial branches have \(B=0\).
The hardness result fixes \(m=2\); it allows \(\tau\) and \(\zeta\) to grow. It does not imply hardness for fixed \(\tau\).
Put \(b=\min\{B,\zeta\}\). Enumerating all campaign subsets of size at most \(b\), and applying the verifier above, gives the deterministic bound
\(O\!\left( \left[\sum_{i=0}^{b}\binom{\zeta}{i}\right] \left[L+m\tau+\zeta\tau+\tau L^2\right] \right),\qquad m=2.\)
This is polynomial for every fixed \(B\). If \(B\ge\zeta\), checking all campaigns together suffices, because coverage is monotone, giving polynomial time directly.
There is also an algorithm with running time exponential only in the actual support size. Let \(r=|T_1|\le\tau\). For every subset \(M\subseteq T_1\), maintain the minimum number of processed campaigns whose union of affected types is exactly \(M\).
Initially, only \(M=\varnothing\) has finite value, namely \(0\). When processing campaign \(j\), each previous state \(M\) produces two possibilities:
Take the minimum cost for each resulting state. This recurrence is correct by induction: every subset of the first \(j\) campaigns either contains campaign \(j\) or omits it. Separate layers ensure that each campaign is used at most once.
After all campaigns, accept exactly when some state has cost at most \(b\) and satisfies
\(\alpha+\sum_{t\in M}\mu_t\ge\tfrac12.\)
There are \(2^r\) states per layer. A conservative bit-operation bound, including exact mass arithmetic, is
\(O\!\left( L+m\tau+\tau L^2+ (\zeta+1)2^\tau(\tau+1)L^2 \right),\qquad m=2.\)
Thus the problem is fixed-parameter tractable in \(\tau\), while remaining \(\mathrm{NP}\)-complete for unrestricted support size.
The finite-electorate hardness stated in the question appears as Theorem 4 of [Bredereck et al., *Large-Scale Election Campaigns: Combinatorial Shift Bribery*](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p67.pdf). The reduction above directly establishes the exact rational-mass formulation, including distinct support types and dyadic masses.
⟨structured verdict parsed — rendered above⟩
The prover resolves the task correctly. The reduction proves \(\mathrm{NP}\)-hardness for the exact rational-mass formulation, including the requirement that support types be distinct. Membership in \(\mathrm{NP}\), the additional parameterized hardness claim, and the stated algorithms are also justified. I found no major or minor issues requiring repair.
The formula
\[
w_p(S)=\alpha+\sum_{t\in\bigcup_{j\in S}A_j}\mu_t
\]
is exact under the task’s assumptions.
With \(m=2\), a type initially ranking \(d\) first switches to ranking \(p\) first precisely when at least one selected campaign has response \(1\). Capping shifts at first place makes further positive responses irrelevant. Types initially ranking \(p\) first remain there because responses are nonnegative.
The union counts each affected type’s mass once, including when several selected campaigns affect it. Thus the coverage threshold \(\tfrac12-\alpha\) is correct. The empty-set conclusion when \(\alpha\ge\tfrac12\) correctly includes equality.
The certificate has length \(\zeta\), independently of the numerical value of the binary-encoded budget. Checking the selected count against \(B\) and determining coverage are polynomial-time operations.
The exact-arithmetic argument is valid:
Consequently, the critical integers have \(O(L)\) bits, and success is exactly \(2N\ge D\). No numerical approximation is involved.
The stated schoolbook-arithmetic bound
\[
O\!\left(L+m\tau+\zeta\tau+\tau L^2\right)
\]
is a valid conservative bound for \(m=2\). It accommodates denominator multiplication, exact division, scaling, addition, and comparison.
The source problem is stated precisely: explicitly represented Set Cover with a cardinality bound \(k\). Its standard \(\mathrm{NP}\)-completeness applies to this formulation.
Both preliminary branches preserve the answer:
The proposed constant-size campaign instances are valid. A single type of mass \(1\), one ineffective campaign, and budget \(0\) gives the required yes- or no-instance according to its ranking. Distinctness is automatic with one support type.
After these branches, \(n\ge1\) and every incidence vector is nonzero. These hypotheses are used correctly later.
Partitioning elements by their complete incidence vectors is appropriate. Elements in one class are affected by exactly the same campaigns, so the response definition for \(t_C\) is independent of the chosen representative.
For the smallest power of two strictly exceeding \(n\), the bound \(n<q\le2n\) is correct, including when \(n\) itself is a power of two.
All constructed masses are positive. Their normalization checks exactly:
\[
\frac{q-n}{2q}+\frac12+\frac{n}{2q}=1.
\]
The common denominator \(2q\) is a power of two, so all masses are dyadic.
The distinctness argument checks all possible collisions:
Thus \(\tau=|\mathcal C|+2\le n+2\) counts actual distinct support types, as required by the task.
The mass numerators and denominator have \(O(\log(n+1))\) bits. The stated output-size bound correctly accounts for the response vectors, masses, and binary budget. Explicit incidence-vector construction and grouping require polynomial time in the explicitly represented source input.
The score calculation is correct:
\[
w_p(S)=\frac{q-n+c(S)}{2q}.
\]
Every equivalence class is covered entirely or not at all, so \(c(S)/(2q)\) is exactly the mass transferred from element types. The permanent-rival type never transfers.
The central equivalence checks:
\[
w_p(S)\ge\frac12
\quad\Longleftrightarrow\quad
c(S)\ge n.
\]
Since \(c(S)\le n\), this requires complete coverage. Complete coverage produces equality with the winning threshold, which succeeds because ties are accepted.
The correspondence between campaigns and listed sets preserves cardinality, and \(B=k\). Both directions of the reduction therefore hold, including for \(k=0\) and for budgets exceeding the number of listed sets.
Together with membership in \(\mathrm{NP}\), this establishes the claimed \(\mathrm{NP}\)-completeness.
The invoked theorem concerns Set Cover parameterized by the number of selected sets, matching the source parameter \(k\). The cited paper’s parameterized-complexity preliminaries use this same Set Cover formulation and parameter. [Bredereck et al., preliminaries](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p67.pdf)
The reduction runs in polynomial time and produces \(B=k\) in its main branch and \(B=0\) in its exceptional branches. Thus the output parameter is bounded by a function of \(k\), as required for a parameterized reduction. The \(\mathrm{W}[2]\)-hardness claim follows.
The enumeration algorithm examines exactly the campaign subsets of size at most \(b=\min\{B,\zeta\}\). Multiplying their count by the verification bound gives the stated running time. For each fixed \(B\), the subset count is polynomial in \(\zeta\).
When \(B\ge\zeta\), selecting every campaign maximizes coverage because every response is nonnegative. The claimed polynomial-time shortcut is valid.
The support-subset dynamic program also checks correctly. Its invariant records the minimum number of processed campaigns realizing each exact affected-type union. The omit/select transitions exhaust the possibilities, and separate layers enforce single use of each campaign. Retaining only the minimum cost for a union is valid because subsequent transitions depend solely on that union.
The acceptance condition checks both budget and exact winning mass. The bound
\[
O\!\left(
L+m\tau+\tau L^2+
(\zeta+1)2^\tau(\tau+1)L^2
\right)
\]
is conservative and sufficient. It establishes fixed-parameter tractability in \(\tau\). The initialization and acceptance rule also handle no campaigns, no initially opposing types, and budget zero.
Theorem 4 of the linked paper states the claimed finite-electorate hardness for Plurality and Borda with two candidates and effects restricted to zero or positive one. The attribution is accurate. [Bredereck et al., Theorem 4](https://www.ifaamas.org/Proceedings/aamas2015/aamas/p67.pdf)
The rational-mass conclusion follows from the prover’s explicit reduction, independently of that contextual citation.
No additional clarification, missing lemma, or repair is needed. The complexity classification is hardness for unrestricted support size; the tractable restrictions do not create a representation-dependent split.
⟨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.