Answer: The continuous budget decision problem is in \(\mathrm{P}\) for every fixed \(q\ge 3\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateDetermining whether there exists a solution with at most k demotion operations to t-approval-TNC is NP-hard for every fixed t ≥3. We provide a proof sketch for the case t = 3 (the other cases are similar) and defer the complete proof to the full version of the paper. The idea is to reduce a 3SET COVER instance with a cover size k to a 3-approval-TNC instance with 3k allowed demotion operations as follows. For every S ∈S, we define a voter who ranks the elements of S at the 3 top positions, then two unique dummy candidates, and then p.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), preferred candidate \(p\), fixed \(q\ge3\), and rational masses \(\mu_r\) on a support \(R\) of \(\tau\) rankings, choose \(y_{r,S}\ge0\), the mass of ranking type \(r\) assigned to final top-\(q\) set \(S\in\binom{C}{q}\), to minimize \(\sum_{r\in R,S\in\binom{C}{q}}\kappa_r(S)y_{r,S}\), subject to \(\sum_{S\in\binom{C}{q}}y_{r,S}=\mu_r\) for every \(r\), and \(\sum_{r,S:p\in S}y_{r,S}\ge\sum_{r,S:c\in S}y_{r,S}\) for every \(c\ne p\). Here \(\kappa_r(S)=|\{c\notin S:\operatorname{rank}_r(c)<\max_{s\in S}\operatorname{rank}_r(s)\}|\), the minimum number of demotion operations per unit of mass needed to make \(S\) the approved set. Each unit of mass receives an ordinary integral ranking after its demotions, and \(p\) must be a co-winner.
Fix an integer \(q\ge3\). Let \(C\) contain \(m>q\) candidates, with preferred candidate \(p\in C\), and use \(q\)-approval with the co-winner convention.
A society is given by its support: a list \(R\) of \(\tau\) strict rankings of \(C\), each with positive mass \(\mu_r\) encoded as a binary rational, where \(\sum_{r\in R}\mu_r=1\). Here \(\tau\) is the support size, not the number of possible rankings.
A demotion moves any candidate down a positive integer number of positions in the current ranking, preserving the relative order of the other candidates; operations are sequential and each costs one per unit of affected mass, independently of distance. Mass may be split, but every portion receives an ordinary integral ranking.
For \(S\in\binom{C}{q}\), define \(\kappa_r(S)=|\{c\in C\setminus S:\operatorname{rank}_r(c)<\max_{s\in S}\operatorname{rank}_r(s)\}|\), the minimum operation count needed to make \(S\) the final approved set; ranks start at \(1\).
Choose real masses \(y_{r,S}\ge0\) satisfying \(\sum_{S\in\binom{C}{q}}y_{r,S}=\mu_r\), and define \(s(c)=\sum_{r\in R}\sum_{S\in\binom{C}{q}:c\in S}y_{r,S}\). Require \(s(p)\ge s(c)\) for every \(c\ne p\); the cost is \(\sum_{r\in R}\sum_{S\in\binom{C}{q}}\kappa_r(S)y_{r,S}\).
Given a nonnegative binary-rational budget \(B\), decide whether such an assignment has cost at most \(B\). Let \(L\) be the total input bit length, including rankings, masses, and budget; state running times in \(m,\tau,L\), with \(q\) fixed.
Is this continuous budget decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard, for each fixed \(q\ge3\)?
For a finite list of indivisible voters, the corresponding unit-cost budget problem is NP-hard for every fixed \(q\ge3\). [Zagoury et al., 2021](https://ojs.aaai.org/index.php/AAAI/article/download/16723/16530)
The discrete optimization problem also admits a polynomial-time \(\min(q,m-q)\)-factor approximation; no result settling the exact mass problem above was identified in the literature search. [Zagoury et al., 2026, full text](https://www.researchgate.net/publication/408611892_Efficiently_Negative_Complexity_and_Approximations_of_Targeted_Negative_Campaigning)
For every fixed \(q\ge 3\), the continuous budget decision problem belongs to \(\mathrm{P}\).
The decisive fact is that each support ranking has only \(\binom{m}{q}=O(m^q)\) possible final approved sets. Thus the stated mass formulation is an explicitly constructible rational linear program of polynomial size. Below, we verify both its operational meaning and its bit complexity.
Fix a ranking \(r\) and a set \(S\in\binom{C}{q}\). Let \(s_*\) be the member of \(S\) ranked last in \(r\), and put \(a=\operatorname{rank}_r(s_*)\).
Exactly \(q\) members of \(S\) occur in the first \(a\) positions. Consequently,
\(\kappa_r(S)=a-q.\)
We prove that this is precisely the minimum number of demotions needed to make \(S\) the approved set.
Lower bound. Consider any candidate \(c\notin S\) initially preceding \(s_*\). In the final ranking, every member of \(S\) must precede every candidate outside \(S\), so \(s_*\) must precede \(c\).
A demotion of a third candidate preserves the relative order of \(c\) and \(s_*\). Demoting \(s_*\) cannot change their order from \(c\) preceding \(s_*\) to \(s_*\) preceding \(c\). Therefore \(c\) itself must be demoted at least once. There are \(\kappa_r(S)\) such candidates, and each operation demotes only one candidate. At least \(\kappa_r(S)\) operations are necessary.
Upper bound. Demote each candidate outside \(S\) that initially precedes \(s_*\) to the bottom, once each. Until such a candidate is demoted, it still precedes \(s_*\), because operations on other candidates preserve their relative order. Every prescribed demotion therefore moves its candidate a positive distance.
After these operations, precisely the members of \(S\) precede or equal \(s_*\). All other candidates follow \(s_*\), so the first \(q\) positions contain exactly \(S\). This uses \(\kappa_r(S)\) operations.
Hence the minimum is \(\kappa_r(S)\), and
\(0\le \kappa_r(S)\le m-q.\)
Let \(\mathcal S=\binom{C}{q}\). Introduce one real variable \(y_{r,S}\) for every \(r\in R\) and \(S\in\mathcal S\). Impose the following constraints:
Here \(\mathbf 1_{\{c\in S\}}\) equals \(1\) if \(c\in S\), and \(0\) otherwise. The co-winner inequalities are exactly \(s(c)\le s(p)\).
This system is equivalent to the allowed manipulation problem.
Indeed, any campaign induces \(y_{r,S}\) by aggregating the portions originating from \(r\) whose final approved set is \(S\). Section 1 shows that its actual cost is at least the budget expression above. Thus every successful campaign within budget yields a feasible assignment.
Conversely, given a feasible assignment, split the mass \(\mu_r\) into the finitely many portions \(y_{r,S}\). On each positive portion, perform the demotion sequence from Section 1. Every portion receives an ordinary strict ranking, and its cost is exactly \(\kappa_r(S)y_{r,S}\). The resulting scores satisfy the co-winner inequalities and the total cost is at most \(B\).
No integrality condition on the variables is needed, because mass splitting is explicitly permitted.
Write \(H=\binom{m}{q}\) and \(N=\tau H\). The system has:
Replacing each equality by two inequalities gives \(2\tau+m\) rows, apart from variable nonnegativity.
All matrix coefficients are integers. Conservation and score coefficients belong to \(\{-1,0,1\}\), while budget coefficients lie between \(0\) and \(m-q\). Thus each matrix coefficient requires \(O(\log(m+1))\) bits. The rational right-hand sides are the input masses, the budget, their negatives where needed, and zeros.
A dense encoding therefore has bit length at most
\(K=O\!\left(L+(\tau+m)\tau\binom{m}{q}\log(m+1)\right).\)
It can be constructed in polynomial time: compute inverse ranks for each input ranking, enumerate all \(q\)-element subsets, and use \(\kappa_r(S)=\max_{s\in S}\operatorname{rank}_r(s)-q\).
We apply the standard polynomial-time rational linear feasibility theorem: feasibility over the reals of an explicitly given finite system of non-strict rational linear inequalities can be decided in time polynomial in its binary encoding length. This is the polynomial-time linear programming theorem originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319).
Its hypotheses hold here: the system is finite and explicit, all coefficients and right-hand sides are rational, and every inequality is non-strict. In particular, it decides feasibility exactly, including instances where the minimum cost equals \(B\); numerical approximation is unnecessary.
The resulting bit running time is
\(\left[L+(\tau+m)\tau\binom{m}{q}\log(m+1)\right]^{O(1)},\)
and hence, for fixed \(q\),
\(\left[L+(\tau+m)\tau m^q\log(m+1)\right]^{O(1)}.\)
Because the rankings and support are explicitly listed, \(m\) and \(\tau\) are bounded by the input length. This running time is therefore polynomial in \(L\).
For an indivisible voter, exactly one final approved set must be selected. Encoding that restriction requires discrete choices. In the present problem, a support mass may be divided among multiple final approved sets, and every such division has the exact operational realization proved above.
Thus the continuous formulation itself is a polynomial-size linear program for fixed \(q\). Its polynomial-time solvability does not require an integrality theorem or contradict the stated hardness result for indivisible voters.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: for every fixed \(q\ge 3\), the continuous budget decision problem is in \(\mathrm{P}\). The operational argument, linear programming formulation, and binary encoding bound are sound. No major or minor issues were found.
Fix \(r\) and \(S\), and let \(s_*\) be the last-ranked member of \(S\), at position \(a\).
All \(q\) members of \(S\) lie within the first \(a\) positions, and position \(a\) contains \(s_*\). Hence precisely \(a-q\) candidates outside \(S\) precede \(s_*\). The identity \(\kappa_r(S)=a-q\) is correct.
The lower bound correctly accounts for sequential operations. For each candidate \(c\notin S\) initially preceding \(s_*\), their relative order must eventually reverse. Operations on third candidates preserve that order, and demoting \(s_*\) cannot produce the required reversal. Consequently, \(c\) must itself be demoted at least once. Since each operation demotes only one candidate, at least \(\kappa_r(S)\) operations are necessary.
The upper bound is also valid. Each prescribed candidate still precedes \(s_*\) until its own demotion, because earlier operations affect other candidates. Thus moving it to the bottom is a permitted demotion of positive distance. After all prescribed operations, every outsider follows \(s_*\), while every other member of \(S\) precedes \(s_*\). The approved set is therefore exactly \(S\).
The boundary case \(\kappa_r(S)=0\) is covered: \(S\) already occupies the first \(q\) positions, and the sequence is empty. Since \(q\le a\le m\), the stated bound \(0\le\kappa_r(S)\le m-q\) is correct.
The variables and constraints match the task exactly:
The formulation imposes the co-winner convention, including ties. It introduces no unwanted integrality requirement or restriction on permitted real mass splitting.
Both directions are justified.
A permitted campaign determines masses \(y_{r,S}\) by final approved set. On each portion, its operation count is at least \(\kappa_r(S)\), so aggregation gives the asserted lower bound on campaign cost. Its scores agree with those computed from the aggregated masses.
Conversely, a feasible assignment has only finitely many indexed portions. Each positive portion can receive the explicit sequence from Section 1. Its final ranking is integral and strict, even though its mass is real. Its cost is exactly \(\kappa_r(S)y_{r,S}\). Summing gives the required scores and budget.
Zero portions require no operations. No additional realization lemma is needed.
With \(H=\binom{m}{q}\) and \(N=\tau H\), the variable count is correct. Replacing the \(\tau\) equalities by two inequalities gives \(2\tau+(m-1)+1=2\tau+m\) rows, excluding variable nonnegativity.
The coefficient ranges are correct: conservation and score entries lie in \(\{-1,0,1\}\), and budget entries lie in \(\{0,\ldots,m-q\}\). Thus the stated coefficient bit bound is valid.
The dense encoding estimate
\(K=O\!\left(L+(\tau+m)\tau\binom{m}{q}\log(m+1)\right)\)
is sound. Copying and negating input right-hand sides adds only a constant-factor amount of their encoding length. Nonnegativity can be represented as standard variable bounds and does not invalidate this estimate.
Inverse ranks, subset enumeration, and the formula for \(\kappa_r(S)\) provide a polynomial-time construction for fixed \(q\).
The prover states the applicable theorem precisely: real feasibility of an explicitly encoded finite system of non-strict rational linear inequalities is decidable in polynomial time in binary encoding length. This is the standard rational linear programming feasibility theorem; the linked reference correctly identifies [Khachiyan’s polynomial linear programming result](https://www.mathnet.ru/eng/dan42319).
Every required hypothesis is satisfied. Real variables and rational coefficients are compatible with the theorem. Conservation equalities are correctly converted into non-strict inequalities. Exact feasibility also covers lower-dimensional feasible sets and budget equality, so no strict-slack assumption is hidden in the argument.
The resulting running-time expressions are valid. For fixed \(q\), \(\binom{m}{q}=O(m^q)\); explicit input listings bound both \(m\) and \(\tau\) polynomially in \(L\). The claimed polynomial dependence on \(L\) follows.
The distinction is correct. Indivisible voters require discrete selection of final approved sets, whereas the task explicitly allows fractional allocation of each support mass. The continuous LP therefore does not establish an algorithm for the indivisible problem or conflict with its stated hardness.
None required. The output establishes the claimed classification, with no missing hypothesis, false step, or unresolved edge case.
⟨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.