Answer: The problem is in \(\mathrm P\) for every fixed \(k\ge3\), and also for input-dependent \(1\le k<m\), in time \((m+\tau+L+\log(k+1))^{O(1)}\) with an exponent independent of \(k\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe FRUGAL-$BRIBERY problem is NP-complete for the k-approval voting rule for any constant k ⩾3, even if the price of every vulnerable vote is either 1 or ∞.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Fix \(k\ge3\). Given candidates \(C\), complete-ranking voter types \(T\) with rational masses \(\mu_t\) summing to \(1\), source prices \(\kappa_t\in\{1,\infty\}\), target \(p\), a fixed tie-breaking order, and a rational per-capita budget \(B\), let \(w\) be the current \(k\)-approval winner and \(V=\{t:p\succ_{\rho_t}w\}\). Decide whether there exist transfers \(x_{t,\rho}\ge0\), for \(t\in V\) and \(\rho\in L(C)\), satisfying \(\sum_{\rho}x_{t,\rho}\le\mu_t\) and \(\sum_{t,\rho}\kappa_t x_{t,\rho}\le B\), such that replacing the transferred mass from ranking \(\rho_t\) by ranking \(\rho\) makes \(p\) win under \(k\)-approval.
Fix an integer \(k\ge3\). Let \(C\) contain \(m>k\) candidates. A society is given by its support: a list \(T\) of \(\tau\) types with positive binary-rational masses \(\mu_t\) summing to \(1\). Each type specifies a strict complete ranking \(\rho_t\) and a source price \(\kappa_t\in\{1,\infty\}\); types may share a ranking but have different prices. Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length.
Use mass-weighted \(k\)-approval with a supplied fixed priority order to select one winner among tied maximum-score candidates. Let \(w\) be the initial winner, and let the target \(p\in C\) satisfy \(p\ne w\). The budget \(B\ge0\) is a finite binary rational.
Define the eligible sources once, from the initial rankings: \(E=\{t\in T:p\succ_{\rho_t}w,\ \kappa_t=1\}\). Infinite-priced and non-vulnerable mass cannot move. Write \(\mathcal L(C)\) for all strict complete rankings of \(C\).
A transfer chooses real masses \(x_{t,\rho}\ge0\) for \(t\in E\) and \(\rho\in\mathcal L(C)\setminus\{\rho_t\}\), with \(\sum_\rho x_{t,\rho}\le\mu_t\) and \(\sum_{t,\rho}x_{t,\rho}\le B\). It replaces each transferred mass from \(\rho_t\) by \(\rho\); all remaining mass retains its initial ranking. A source may split its mass among arbitrary destination rankings.
Is deciding whether such transfers make \(p\) the selected winner in \(\mathrm P\), or is it NP-hard, for each fixed \(k\ge3\)? State running times in \(m,\tau,L\), with dependence on \(k\) explicit.
Discrete frugal priced bribery under \(k\)-approval is NP-complete for every fixed \(k\ge3\), even with vulnerable-voter prices in \(\{1,\infty\}\). [Dey–Misra–Narahari](https://arxiv.org/pdf/1504.08248)
Continuous priced bribery for scoring protocols with finite rational prices and a co-winner goal is polynomial-time solvable; this result does not explicitly treat the vulnerability restriction and supplied winner priority used here. [Koutecký–Melissinos–Vu–Sabater](https://arxiv.org/pdf/2608.25444)
The problem is in \(\mathrm P\) for every fixed \(k\ge3\). In fact, the same algorithm is polynomial-time when \(k\) is part of the input, subject to \(1\le k<m\).
We give an exact linear program with at most \(\tau+m+1\) variables and \(O(\tau+m)\) constraints. It handles the fixed eligibility restriction, infinite prices, forbidden transfers to the source ranking, and the supplied winner priority.
For each type \(t\), let \(A_t\subseteq C\) be its set of top-\(k\) candidates. Define \(a_{t,c}=1\) when \(c\in A_t\), and \(a_{t,c}=0\) otherwise. The initial score of candidate \(c\) is
\(\displaystyle s_c=\sum_{t\in T}\mu_t a_{t,c}.\)
Compute the initial selected winner \(w\), using the supplied priority order, and then compute
\(\displaystyle E=\{t\in T:p\succ_{\rho_t}w,\ \kappa_t=1\}.\)
Throughout the construction, only these original source types may move. In particular, eligibility is never recomputed after transfers.
Let \(H\subseteq C\setminus\{p\}\) consist of the candidates preceding \(p\) in the priority order. For any final score vector \(S\), candidate \(p\) is selected exactly when
\(\displaystyle S_p>S_c\quad(c\in H),\qquad S_p\ge S_c\quad(c\in C\setminus(H\cup\{p\})).\)
Lemma. Let \(M\ge0\). A vector \(z\in\mathbb R^C\) is the aggregate approval vector of mass \(M\) distributed among strict complete rankings if and only if
\(\displaystyle 0\le z_c\le M\quad(c\in C),\qquad \sum_{c\in C}z_c=kM.\)
Proof. Necessity follows because each unit of mass approves exactly \(k\) distinct candidates.
If \(M=0\), the stated inequalities force \(z=0\), which is realizable by zero mass. Suppose \(M>0\), and set \(q=z/M\). Consider the bounded polytope
\(\displaystyle Q=\left\{q\in[0,1]^C:\sum_{c\in C}q_c=k\right\}.\)
Every vertex of \(Q\) is integral. Indeed, a point with a fractional coordinate must have at least two fractional coordinates: exactly one would contradict the integrality of its coordinate sum. If \(q_i,q_j\in(0,1)\), choose
\(\displaystyle 0<\varepsilon<\min\{q_i,1-q_i,q_j,1-q_j\}.\)
Both \(q+\varepsilon(e_i-e_j)\) and \(q-\varepsilon(e_i-e_j)\) belong to \(Q\). They are distinct and have midpoint \(q\), so \(q\) is not a vertex.
By the convex-hull theorem for bounded polytopes, every point of \(Q\) is a convex combination of its vertices. Each vertex is the characteristic vector of a \(k\)-element subset of \(C\). Consequently, there are such subsets \(U_1,\ldots,U_r\) and nonnegative coefficients \(\lambda_1,\ldots,\lambda_r\) satisfying
\(\displaystyle \sum_{j=1}^r\lambda_j=1,\qquad q=\sum_{j=1}^r\lambda_j\mathbf1_{U_j}.\)
Choose a strict complete ranking \(\sigma_j\) whose top-\(k\) set is \(U_j\), and assign it mass \(M\lambda_j\). Its aggregate approval vector is \(z\). This proves sufficiency. \(\square\)
Introduce the following variables:
Use \(M=\sum_{t\in E}y_t\) as an abbreviation, not an additional variable. Impose
\(\displaystyle 0\le y_t\le\mu_t\quad(t\in E),\qquad M\le B,\)
\(\displaystyle 0\le z_c\le M\quad(c\in C),\qquad \sum_{c\in C}z_c=kM,\)
and \(\displaystyle 0\le\delta\le1.\)
Define the following affine expressions for final scores:
\(\displaystyle S_c=s_c-\sum_{t\in E}a_{t,c}y_t+z_c\quad(c\in C).\)
Finally, impose
\(\displaystyle S_p-S_c\ge\delta\quad(c\in H),\)
\(\displaystyle S_p-S_c\ge0\quad(c\in C\setminus(H\cup\{p\})).\)
Maximize \(\delta\). Reject if the program is infeasible; otherwise accept exactly when its optimum \(\delta^\star\) is positive.
This is an ordinary rational linear program after substituting the abbreviations \(M\) and \(S_c\).
Suppose a permitted transfer makes \(p\) the selected winner. Set
\(\displaystyle y_t=\sum_{\rho\ne\rho_t}x_{t,\rho},\)
and
\(\displaystyle z_c=\sum_{t\in E}\sum_{\rho\ne\rho_t}x_{t,\rho}\mathbf1_{\{c\text{ is top-}k\text{ in }\rho\}}.\)
Source capacities and the budget give the constraints on \(y\). The lemma’s necessary conditions give the constraints on \(z\). Removing source approvals and adding destination approvals gives precisely the displayed formula for \(S_c\).
For every \(c\in H\), the margin \(S_p-S_c\) is strictly positive. If \(H\ne\varnothing\), choose
\(\displaystyle \delta=\min\left\{1,\min_{c\in H}(S_p-S_c)\right\}>0.\)
If \(H=\varnothing\), choose \(\delta=1\). All remaining winner constraints hold because \(p\) is selected. Thus \(\delta^\star>0\).
Conversely, suppose the program has a feasible solution with \(\delta>0\).
If \(M=0\), all \(y_t\) and \(z_c\) are zero. The unchanged society then has scores \(S_c=s_c\), and the winner constraints select \(p\). Under the premise \(p\ne w\), this case cannot occur, but it needs no transfers.
Now suppose \(M>0\). By the lemma, choose rankings \(\sigma_j\) and coefficients \(\lambda_j\) such that
\(\displaystyle z_c=M\sum_{j=1}^r\lambda_j\mathbf1_{\{c\text{ is top-}k\text{ in }\sigma_j\}},\qquad \sum_{j=1}^r\lambda_j=1.\)
For every \(t\in E\), provisionally reassign mass \(y_t\lambda_j\) to ranking \(\sigma_j\). The total provisional destination mass at \(\sigma_j\) is
\(\displaystyle \sum_{t\in E}y_t\lambda_j=M\lambda_j,\)
so the resulting scores are exactly \(S_c\).
The only possible violation is a provisional reassignment to the source’s own ranking. Cancel every such reassignment: whenever \(\sigma_j=\rho_t\), leave that mass at its original source instead. Each cancellation leaves the resulting society unchanged, since the mass has the same ranking before and after. It also decreases the charged transfer mass.
After cancellation, every destination differs from its source ranking, each source transfers at most \(y_t\le\mu_t\), and total cost is at most \(M\le B\). All sources belong to \(E\). Hence these are permitted transfers with final scores \(S_c\).
The constraints give strict superiority over every candidate preceding \(p\) in priority and weak superiority over every other candidate. Therefore \(p\) is selected.
This proves the acceptance criterion.
Write \(e=|E|\le\tau\). The program has \(e+m+1\) variables, \(2e+3m+2\) inequality constraints, and one equality constraint. Its matrix coefficients belong to \(\{-1,0,1,-k\}\).
All initial scores have \(O(L)\)-bit rational representations. To see this, write the masses with their encoded denominators and take their product as a common denominator. Its bit length is \(O(L)\); because every initial score lies in \([0,1]\), its numerator has the same bit bound. Score differences likewise have \(O(L)\)-bit representations.
Consequently, a dense encoding of the program has bit length
\(\displaystyle S_{\mathrm{LP}}=O\!\left((m+\tau)^2+(m+\tau)L+\tau\log(k+1)\right).\)
Preprocessing and constructing this encoding take polynomial time in \(m,\tau,L\). Standard exact rational linear programming then solves the program in \(S_{\mathrm{LP}}^{O(1)}\) bit operations, with an absolute exponent independent of \(k\). Overall, the running time is
\(\displaystyle (m+\tau+L+\log(k+1))^{O(1)}.\)
The feasible region, when nonempty, is compact: \(y_t\le\mu_t\) implies \(M\le1\), hence \(z_c\le1\), and \(\delta\in[0,1]\). Thus its optimum is attained. Exact rational optimization permits an exact comparison of \(\delta^\star\) with zero; no predetermined positive tolerance is used.
This agrees with the polynomial-time scoring-protocol result in [Koutecký–Melissinos–Vu–Sabater, Theorem 2](https://arxiv.org/pdf/2608.25444). The direct formulation above establishes the required eligibility and priority variants.
⟨structured verdict parsed — rendered above⟩
The output correctly resolves the task: the decision problem is in \(\mathrm P\) for every fixed \(k\ge3\). Its stronger claim, allowing input-dependent \(k\) with \(1\le k<m\), is also justified. I found no major or minor mathematical issues.
The definition \(s_c=\sum_{t\in T}\mu_t a_{t,c}\) correctly computes mass-weighted \(k\)-approval scores.
The eligible set is computed from the original rankings and the original selected winner. Restricting removal variables to \(t\in E\) correctly freezes eligibility and prevents movement of infinite-priced or non-vulnerable mass. Distinct types sharing a ranking remain separate source types with separate capacities.
The winner conditions are exact. A candidate preceding \(p\) in priority must have strictly smaller score than \(p\); every other opponent may tie \(p\). These conditions are both necessary and sufficient for \(p\) to be the selected winner.
The lemma is correct.
Thus the lemma characterizes all possible aggregate destination approval vectors. It does not require enumerating rankings in the algorithm.
All constraints have the intended meaning:
The common margin variable correctly handles strict inequalities. Since \(H\) is finite, strictly positive margins against every member of \(H\) admit a common positive lower bound. When \(H\) is empty, setting \(\delta=1\) correctly makes acceptance depend only on the weak winner constraints.
The cap \(\delta\le1\) does not exclude any successful transfer, as the forward correspondence explicitly selects a margin satisfying this cap.
The definitions of \(y_t\) and \(z_c\) from a permitted transfer satisfy all capacity, budget, and aggregate-approval constraints.
The score expression exactly matches the resulting society. The chosen \(\delta\) is positive whenever \(p\) is selected, including the separately treated case \(H=\varnothing\).
Consequently, a successful transfer produces a feasible LP point with positive objective value. This direction is complete.
This is the crucial correspondence, and it is valid.
For \(M>0\), the lemma supplies a finite distribution over destination rankings realizing \(z\). Assigning each source the same destination proportions gives aggregate mass \(M\lambda_j\) at each destination and therefore produces exactly the LP scores.
The cancellation argument correctly handles the prohibition on transferring to the source ranking. Leaving such provisional mass at its original source:
The budget is an upper bound, so decreasing the transferred mass is permitted. No constraint requires using exactly the LP value \(M\).
The \(M=0\) case is also handled correctly: it would select \(p\) without changing the society, contradicting the given premise \(p\ne w\).
Thus every feasible positive-margin LP solution yields permitted successful transfers.
The stated counts are correct. With \(e=|E|\), there are \(e+m+1\) variables. The inequality count is
\(2e+1+2m+2+(m-1)=2e+3m+2\),
with one additional equality.
After substitution, the matrix coefficients belong to the stated set \(\{-1,0,1,-k\}\).
The rational bit-length argument is valid. The product of the encoded mass denominators has \(O(L)\) bits. Since scores lie in \([0,1]\), their numerators over that denominator also have \(O(L)\) bits. Score differences retain this bound.
The dense LP encoding bound
\(S_{\mathrm{LP}}=O((m+\tau)^2+(m+\tau)L+\tau\log(k+1))\)
therefore follows. Polynomial-time exact rational LP optimization applies to this explicitly represented rational program. Its exponent does not depend on \(k\), giving the claimed overall polynomial bound.
The feasible region is closed and bounded: \(0\le y_t\le\mu_t\), \(M\le1\), \(0\le z_c\le1\), and \(0\le\delta\le1\). Hence a nonempty feasible region is compact, and the objective attains its optimum.
Exact rational optimization permits comparison of the optimum with zero. The proof therefore correctly distinguishes arbitrarily small positive winning margins from zero margins without relying on a numerical tolerance.
The concluding comparison with [Koutecký–Melissinos–Vu–Sabater, Theorem 2](https://arxiv.org/pdf/2608.25444) is accurate: that theorem establishes polynomial-time continuous priced bribery for scoring protocols with rational populations and prices. The submitted proof independently establishes the eligibility restriction, infinite-price exclusion, and supplied-priority conditions; it does not assume these follow directly from that theorem.
No repair or additional clarification is required. The aggregate-approval lemma, source reconstruction with cancellation, and exact margin optimization together establish the claimed decision algorithm.
⟨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.