Answer: \(\mathrm{P}\) for all six rule–cost combinations, with running time \(\bigl((m+\tau)L\bigr)^{O(1)}\) bit operations.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate-Bribery is NP-complete (and also W[2]- complete with parameter being the budget) for V ∈ {SP, SA, SB} and C ∈{Cequal, Cdo}.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(q\) binary issues, a supported type set \(T\subseteq\{0,1\}^q\) with binary-rational masses \(\mu_t\), a target bundle \(A\in\{0,1\}^q\), a rule \(V\in\{\mathrm{SP},\mathrm{SA},\mathrm{SB}\}\), a cost scheme \(C\in\{C_{\mathrm{equal}},C_{\mathrm{do}}\}\), and budget \(\beta\), is there a choice of converted masses \(b_t\in[0,\mu_t]\) for \(t\ne A\) that makes \(A\) win at cost at most \(\beta\)? Each type \(t\) has independent unary preferences with value \(1\) for \(t_i\) and \(0\) for the other value on issue \(i\); converting mass changes those preferences to favor \(A\). The cost is \(\kappa_C\sum_{t\ne A}b_t\), where \(\kappa_{C_{\mathrm{equal}}}=1\) and \(\kappa_{C_{\mathrm{do}}}=2\). For each issue \(i\), require the target value’s resulting mass to be at least one half when the fixed tie-break favors it, and strictly greater than one half otherwise.
A society is given by its support: a list \(T\subseteq\{0,1\}^{q}\) of \(\tau=|T|\) types with positive binary-rational masses \(\mu_t\), normalized by \(\sum_{t\in T}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. There are \(m=q\geq1\) binary issues; let \(L\) be the total input bit length.
The input also specifies a target bundle \(A\in\{0,1\}^{q}\), a nonnegative binary-rational budget \(\beta\), a rule \(V\in\{\mathrm{SP},\mathrm{SA},\mathrm{SB}\}\), a cost scheme \(C\in\{C_{\mathrm{equal}},C_{\mathrm{do}}\}\), and a fixed lexicographic order on each issue's domain for breaking electoral ties.
Type \(t\) has independent unary preferences assigning value \(1\) to \(t_i\) and \(0\) to the other value on issue \(i\). Issues are processed in index order. Sequential Plurality \(\mathrm{SP}\) counts mass voting for its best value; Sequential Approval \(\mathrm{SA}\) counts mass approving every best value; Sequential Borda \(\mathrm{SB}\) sums mass-weighted preference values. Thus all three select the issue's majority value on this domain.
A permitted conversion chooses real masses \(b_t\in[0,\mu_t]\) for \(t\in T\setminus\{A\}\), replacing that mass's entire unary preference vector by \(A\)'s. Its cost is \(\kappa_C\sum_{t\in T\setminus\{A\}}b_t\), where \(\kappa_{C_{\mathrm{equal}}}=1\) and \(\kappa_{C_{\mathrm{do}}}=2\).
Write \(s_i=\sum_{t\in T:t_i=A_i}\mu_t+\sum_{t\in T:t_i\ne A_i}b_t\). A conversion makes \(A\) win precisely when every issue satisfies \(s_i\geq\tfrac12\) if its tie-break selects \(A_i\), and \(s_i>\tfrac12\) otherwise.
Is deciding whether a permitted conversion makes \(A\) win at cost at most \(\beta\) in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m=q\), \(\tau\), and \(L\).
The discrete version with indivisible voters is \(\mathrm{NP}\)-complete for all six rule–cost combinations, already with independent binary issues ([Pini, Rossi, and Venable](https://www.dei.unipd.it/~pini/Conference/bsoft-cr.pdf)).
Polynomial-time results are known for continuous bribery under scoring protocols with ordinary candidate rankings ([Koutecký et al.](https://arxiv.org/html/2608.25444v1)); these concern a different ballot domain. No result explicitly treating the conversion problem above was located.
The decision problem is in \(\mathrm{P}\) for all six rule–cost combinations. It can be decided by one rational linear program with at most \(\tau+1\) variables and \(m+2\tau+3\) inequalities, in
\[ \bigl((m+\tau)L\bigr)^{O(1)} \]
bit operations, hence in \(L^{O(1)}\) time. The formulation uses only the explicitly listed support types.
Let \(R=T\setminus\{A\}\), let \(r=|R|\leq\tau\), and set \(B=\beta/\kappa_C\). Thus the budget constraint is \(\sum_{t\in R}b_t\leq B\).
For every issue \(i\in\{1,\ldots,m\}\), define
\(p_i=\sum_{t\in T:t_i=A_i}\mu_t,\qquad h_i=\tfrac12-p_i,\qquad a_{it}=\begin{cases}1,&t_i\neq A_i,\\0,&t_i=A_i.\end{cases}\)
Let \(J\) be the set of issues whose tie-break selects the value different from \(A_i\).
A converted unit of mass from type \(t\) increases support for \(A_i\) by exactly \(a_{it}\): if \(t_i=A_i\), that mass already supported \(A_i\); otherwise its support changes to \(A_i\). Consequently,
\(s_i=p_i+\sum_{t\in R}a_{it}b_t.\)
Under independent unary preferences, processing earlier issues does not change later preferences. Moreover, under each of \(\mathrm{SP}\), \(\mathrm{SA}\), and \(\mathrm{SB}\), a unit of mass contributes one unit to its preferred binary value and zero to the other. Hence the stated winning conditions are exactly
\(\sum_{t\in R}a_{it}b_t\geq h_i\quad(i\notin J),\)
\(\sum_{t\in R}a_{it}b_t>h_i\quad(i\in J).\)
These conditions must hold together with the mass bounds and budget constraint.
Introduce a shared margin variable \(\varepsilon\). Consider the following ordinary, non-strict linear program:
Maximize \(\varepsilon\), subject to
Claim. A permitted winning conversion within budget exists if and only if this LP is feasible and its optimum is strictly positive.
Proof. Suppose \(b\) is a winning conversion within budget. For each \(i\in J\), its excess support over the required threshold is
\(\delta_i=\sum_{t\in R}a_{it}b_t-h_i>0.\)
There are finitely many issues, so
\(\varepsilon=\min\bigl(\{1\}\cup\{\delta_i:i\in J\}\bigr)>0.\)
The pair \((b,\varepsilon)\) satisfies every LP constraint. This definition also handles \(J=\varnothing\), when it gives \(\varepsilon=1\). Therefore the LP optimum is positive.
Conversely, suppose the LP has a feasible solution with \(\varepsilon>0\). For each \(i\in J\),
\(\sum_{t\in R}a_{it}b_t\geq h_i+\varepsilon>h_i.\)
The remaining issue constraints, mass bounds, and budget constraint are already imposed by the LP. Thus \(b\) is a permitted winning conversion within budget. This proves the claim.
The feasible region is closed and bounded: every \(b_t\) lies in \([0,\mu_t]\), and \(\varepsilon\) lies in \([0,1]\). Therefore, whenever feasible, the LP attains its maximum. The decision procedure returns no on infeasibility or optimum zero, and yes on a positive optimum.
We use the standard rational linear-programming theorem: an LP with explicitly encoded rational coefficients can be tested for feasibility and, when feasible with bounded objective, optimized exactly in time polynomial in its binary encoding length. See the [MIT notes on linear programming](https://ocw.mit.edu/courses/6-854j-advanced-algorithms-fall-2008/908fe54d659623efadda2d033b895caf_notes_lp.pdf).
Its hypotheses hold here. There are \(n=r+1\leq\tau+1\) variables and exactly \(m+2r+3\) inequalities, all with rational data. All coefficients on the left-hand sides belong to \(\{-1,0,1\}\).
For completeness, a determinant bound also gives an explicit separation between a positive optimum and zero. Choose a positive integer \(D\) that is a common denominator of all \(\mu_t\), \(B\), and \(\tfrac12\). Such a \(D\) has \(O(L)\) bits: for example, if the input denominators are \(d_t\) and \(d_\beta\), use
\(D=2\kappa_Cd_\beta\prod_{t\in T}d_t.\)
Every LP right-hand side then belongs to \(D^{-1}\mathbb Z\).
If the optimum is positive, choose an optimal vertex \(x=(b,\varepsilon)\), which exists because the feasible polytope is nonempty and bounded. At a vertex, the active constraint normals span all \(n\) dimensions; otherwise a sufficiently small perturbation in both directions orthogonal to those normals would contradict extremality. Select \(n\) independent active constraints, giving
\(Hx=c,\)
where \(H\) is a nonsingular integer matrix with entries in \(\{-1,0,1\}\), and \(Dc\) is integral. Cramer’s rule gives
\(\varepsilon=\dfrac{k}{D\det H}\quad\text{for some }k\in\mathbb Z.\)
The determinant expansion has \(n!\) terms, each of absolute value at most one, so \(|\det H|\leq n!\). Therefore
\(\varepsilon>0\ \Longrightarrow\ \varepsilon\geq\dfrac{1}{Dn!}.\)
This bound has \(O(L+\tau\log(\tau+1))\) bits. Thus strict feasibility never requires distinguishing zero from an arbitrarily small positive quantity without a polynomial-size rational bound. The same argument applies to every coordinate of the optimal vertex, so every yes-instance has a rational winning conversion of polynomial encoding length.
To construct the LP, one scans the support and computes the \(p_i\) and \(a_{it}\) using \(O(m\tau)\) arithmetic operations. With common denominator \(D\), these operations use integers of \(O(L)\) bits. Even a dense encoding of the LP has length
\(S=O\bigl((m+\tau)(\tau+L)\bigr)=O\bigl((m+\tau)L\bigr),\)
because the explicit input has \(L\geq\tau\). Applying rational LP optimization therefore gives the claimed running time \(\bigl((m+\tau)L\bigr)^{O(1)}\). Since also \(m,\tau\leq L\), this is polynomial in total input length.
The discrete hardness result restricts the admissible conversions to indivisible voters; its independent binary construction appears in Theorem 5 of [Pini, Rossi, and Venable](https://www.dei.unipd.it/~pini/Conference/bsoft-cr.pdf). Here each variable can take any real value in its interval, so the constraints above form an ordinary LP.
Strict ties still matter. For example, take \(m=1\), \(T=\{0\}\), \(\mu_0=1\), \(A=1\), and a tie-break favoring \(0\). Winning requires \(b_0>\tfrac12\). A budget \(B=\tfrac12\) therefore fails, although replacing the strict inequality by a weak one would incorrectly accept it. The shared-margin LP correctly has optimum zero in this case.
Thus the support representation, fractional conversions, and exact treatment of strict ties together establish polynomial-time solvability for the specified problem.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and resolves the assigned continuous problem for all six rule–cost combinations. No major or minor mathematical issues were found.
\(s_i=p_i+\sum_{t\in R}a_{it}b_t\)
is correct. Independent unary preferences justify treating issues separately, and all three specified rules use the same majority conditions.
\(\varepsilon>0\Rightarrow\varepsilon\ge1/(Dn!)\).
The claimed bit bound follows. The polynomial-size rational witness claim is also valid: all mass coordinates and the margin are bounded, so their numerators as well as denominators have polynomial bit length.
\(S=O((m+\tau)(\tau+L))=O((m+\tau)L)\)
is valid. Explicit support and target encodings ensure \(m,\tau\le L\), giving the stated polynomial bit-operation bound.
No additional clarification or repair is needed.
⟨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.