Answer: Polynomial-time solvable.
Theorem 3.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximate\dbribery{plurality}{weighted} is $\np$-complete, even for just two candidates.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C=\{p,c\}\), a finite type set \(T\), rational masses \(\mu_t\) summing to \(1\), each type's ranking, per-agent voting weight \(w_t\), and per-agent bribe price \(\pi_t\), plus normalized budget \(K\), does there exist mass \(x_t\) for the types with \(c\succ_t p\), with \(0\le x_t\le\mu_t\), such that bribing that mass to report \(p\succ c\) costs \(\sum_t\pi_t x_t\le K\) and makes \(p\) a plurality winner, namely \(S_p+\sum_t w_t x_t\ge S_c-\sum_t w_t x_t\)?
Definition. An instance has \(C=\{p,c\}\), a finite type set \(T\), and nonnegative rational \(\mu_t,w_t,\pi_t,K\) encoded in binary, with \(\sum_{t\in T}\mu_t=1\); each type has a strict ranking of \(p,c\). Let \(S_p=\sum_{t:p\succ_t c}\mu_tw_t\) and \(S_c=\sum_{t:c\succ_t p}\mu_tw_t\).
For each \(t\) with \(c\succ_t p\), one may bribe mass \(x_t\in[0,\mu_t]\) to report \(p\succ c\), at cost \(\sum_t\pi_tx_t\). The bribery succeeds when its cost is at most \(K\) and \(S_p+\sum_t w_tx_t\geq S_c-\sum_t w_tx_t\).
Target. Is this continuous two-candidate weighted, priced plurality-bribery problem solvable in polynomial time, or is it NP-hard?
Known results. For individually listed voters, weighted, priced plurality bribery is NP-complete even with two candidates.
The problem is solvable in polynomial time. The continuous bribable masses make it a fractional optimization problem, for which a greedy algorithm is optimal.
Let \(B=\{t\in T:c\succ_t p\}\). The success inequality is equivalent to \(\sum_{t\in B}w_tx_t\geq D\), where \(D=(S_c-S_p)/2\).
If \(D\leq 0\), choosing every \(x_t=0\) succeeds, since \(K\geq 0\). Hence assume \(D>0\).
Types with \(w_t=0\) or \(\mu_t=0\) may be assigned \(x_t=0\): they contribute no score gain, and their costs are nonnegative. For each remaining type, define its score-gain capacity \(a_t=\mu_tw_t>0\), its cost per unit of score gain \(d_t=\pi_t/w_t\geq 0\), and the variable \(y_t=w_tx_t\). This substitution is a bijection between the intervals \(x_t\in[0,\mu_t]\) and \(y_t\in[0,a_t]\), and \(\pi_tx_t=d_ty_t\).
Thus the instance succeeds exactly when there exist \(y_t\) satisfying \(0\leq y_t\leq a_t\), \(\sum_t y_t\geq D\), and \(\sum_t d_ty_t\leq K\).
If \(\sum_t a_t<D\), success is impossible. Otherwise, the following algorithm computes the minimum cost of attaining the required gain.
Index the remaining types so that \(d_1\leq d_2\leq\cdots\leq d_m\), breaking ties arbitrarily. Let \(A_0=0\) and \(A_i=\sum_{h=1}^{i}a_h\). Since \(D>0\) and \(A_m\geq D\), there is a smallest index \(j\) such that \(A_j\geq D\).
Choose:
By minimality of \(j\), we have \(0< D-A_{j-1}\leq a_j\). Consequently, this choice respects every capacity and has total gain \(\sum_i y_i^*=D\). Its cost is \(H=\sum_{i<j}d_i a_i+d_j(D-A_{j-1})\).
Claim. Every feasible allocation with total gain at least \(D\) has cost at least \(H\).
Proof. Let \(y\) be any such allocation and set \(\lambda=d_j\geq 0\). Since \(\sum_i y_i^*=D\), the difference in costs satisfies
\(\sum_i d_i y_i-H=\sum_i(d_i-\lambda)(y_i-y_i^*)+\lambda(\sum_i y_i-D)\).
Each term on the right is nonnegative:
Therefore \(\sum_i d_i y_i\geq H\), proving the claim. This argument also covers zero prices and equal ratios.
It follows that the answer is yes exactly when \(H\leq K\). In that case, an explicit successful bribery is \(x_i=y_i^*/w_i\), with zero bribery for discarded types.
Let \(L\) be the total binary input length. Scores, capacities, ratios, prefix sums, and \(H\) can all be computed using exact rational arithmetic.
Each initial product or ratio has bit length bounded by a constant multiple of \(L\). A sum of at most \(|T|\) such rationals can be represented over the product of their denominators, whose bit length is at most the sum of the denominator bit lengths. Thus all the quantities used above have bit lengths polynomial in \(L\).
Sorting requires \(O(|T|\log |T|)\) rational comparisons, each performed by integer cross-multiplication with polynomial bit length. The remaining computation uses polynomially many arithmetic operations on integers of polynomial bit length. Hence the algorithm runs in polynomial time in the binary input length.
The known NP-completeness result concerns indivisible voters. Here, the interval constraint \(x_t\in[0,\mu_t]\) permits bribing a fraction of a type. The algorithm crucially uses this permission for the boundary type \(j\), whose selected mass can lie strictly between zero and its full mass. Thus the stated discrete hardness result does not contradict this polynomial-time algorithm.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the continuous version is solvable in polynomial time under the stated binary rational encoding. The proof is rigorous, including the optimality argument and bit complexity analysis. No major or minor issues were found.
Subtracting the initial scores and dividing by two gives precisely
\( \sum_{t\in B} w_t x_t \geq (S_c-S_p)/2 = D \).
The definition of \(B\) correctly restricts bribery to types initially preferring \(c\).
Taking every bribery variable to be zero satisfies the score requirement and has cost zero. The hypothesis \(K\geq 0\) ensures budget feasibility. This correctly includes an initial tie.
If \(w_t=0\), bribery produces no gain, and setting its variable to zero cannot increase cost because \(\pi_t\geq 0\). If \(\mu_t=0\), the interval constraint already forces \(x_t=0\). Discarding these types therefore preserves the existence of a successful bribery.
Every remaining type has \(w_t>0\) and \(\mu_t>0\). Consequently, \(y_t=w_tx_t\) is a bijection between the stated intervals, with inverse \(x_t=y_t/w_t\). The identities \(a_t=\mu_tw_t>0\), \(d_t=\pi_t/w_t\geq 0\), and \(\pi_tx_t=d_ty_t\) are valid. Both score feasibility and cost are preserved exactly.
The inequality \(\sum_t a_t<D\) rules out feasibility because each variable is bounded above by its capacity. Otherwise, \(D>0\) and \(A_m\geq D\) ensure that the smallest index \(j\) exists. Minimality gives \(A_{j-1}<D\leq A_j\), so the proposed boundary allocation satisfies \(0<D-A_{j-1}\leq a_j\). The empty remaining-type case is also handled: with \(D>0\), it fails the capacity check before any boundary index is needed.
Every selected coordinate lies within its allowed interval, and the coordinates sum to exactly \(D\). The displayed expression for \(H\) is precisely its cost. The construction includes the endpoint cases \(j=1\), \(j=m\), and \(D=A_j\).
The identity
\( \sum_i d_i y_i-H=\sum_i(d_i-\lambda)(y_i-y_i^*)+\lambda(\sum_i y_i-D) \)
is correct: it follows by expansion using \(H=\sum_i d_i y_i^*\) and \(\sum_i y_i^*=D\).
All subsequent sign checks are valid. Before \(j\), both factors in each product are nonpositive; at \(j\), the coefficient vanishes; after \(j\), both factors are nonnegative. The final term is nonnegative because \(\lambda=d_j\geq 0\) and the competing allocation has gain at least \(D\).
Thus the argument establishes optimality against every capacity-feasible allocation attaining at least the required gain, including allocations that exceed it. Zero prices and equal ratios cause no exception.
The greedy allocation attains cost \(H\), and every allocation attaining the required gain costs at least \(H\). Therefore success is equivalent to \(H\leq K\). Applying the inverse substitution yields a valid successful bribery whenever this comparison holds. The non-strict comparison correctly permits exact budget equality.
The bit complexity argument is sufficient. Products and ratios of input rationals have polynomial bit length. Sums contain at most \(|T|\) terms, and using products of denominators gives polynomial-length representations. The subsequent expressions for \(D\), the boundary allocation, and \(H\) preserve this polynomial bound.
Rational comparisons by cross-multiplication are exact and involve polynomial-length integers. Sorting and the remaining arithmetic require polynomially many such operations. Hence the proof establishes polynomial running time in binary input length, rather than merely a polynomial count of unit-cost arithmetic operations.
The explanation identifies the relevant difference correctly: the present variables permit partial bribery of a type. The boundary allocation explicitly uses that permission. The stated hardness result for indivisible voters therefore does not contradict the algorithm.
No repair or additional clarification is required. The proof is self-contained and does not rely on an unstated optimization theorem.
⟨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.