Answer: Exactly solvable deterministically in \(\operatorname{poly}(m,\tau,L)\) time; the requested additive guarantee holds with failure probability zero.
Theorem 22 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn SR-Weighted-$Bribery under constant or non-concentrated Rα, let ΨOPT be the minimum cost of bribery in order to make p win. Then there exists a polynomial- time randomized algorithm spending a cost of at most ΨOPT + eO q ψmax(ΨOPT + ψmax)¯rmaxrmax , with an exponentially-small failure probability.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a scoring vector \(\alpha\) in Theorem 22’s constant or non-concentrated classes, a preferred candidate \(p\), and rational-mass types \(t=(r_t,w_t,\psi_t)\) with \(\sum_t\mu_t=1\), choose transfers \(x_{t,\pi}\ge 0\) to destination rankings \(\pi\ne r_t\), with \(\sum_{\pi\ne r_t}x_{t,\pi}\le\mu_t\). Each transferred unit keeps its source type’s weight \(w_t\) and price \(\psi_t\). Minimize \(\sum_t\psi_t\sum_{\pi\ne r_t}x_{t,\pi}\) subject to \(p\)’s final weighted score being at least every competitor’s, where \(S(c)=\sum_t w_t[(\mu_t-\sum_{\pi\ne r_t}x_{t,\pi})\alpha_{\operatorname{pos}_{r_t}(c)}+\sum_{\pi\ne r_t}x_{t,\pi}\alpha_{\operatorname{pos}_{\pi}(c)}]\).
Let \(C\) contain \(m\ge2\) candidates and let \(p\in C\). The input scoring vector \(\alpha=(\alpha_0,\ldots,\alpha_{m-1})\) has binary rational entries with \(\alpha_0\ge\cdots\ge\alpha_{m-1}\ge0\). It is either constant (integer entries bounded by a fixed constant) or non-concentrated: \(\frac1{m-1}\sum_{j=1}^{m-1}\alpha_j\le(1-\epsilon)\alpha_0\) for a fixed \(\epsilon\in(0,1)\).
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types. Each type \(t=(r_t,w_t,\psi_t)\) has a strict ranking \(r_t\), positive integer weight \(w_t\), and positive integer price \(\psi_t\); \(\sum_t\mu_t=1\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
For every destination ranking \(\pi\ne r_t\), choose divisible transfers \(x_{t,\pi}\ge0\) with \(y_t:=\sum_{\pi\ne r_t}x_{t,\pi}\le\mu_t\). Transferred mass retains its source weight and pays its source price per unit, independently of its destination.
With positions indexed from \(0\), define \(S(c)=\sum_t w_t[(\mu_t-y_t)\alpha_{\operatorname{pos}_{r_t}(c)}+\sum_{\pi\ne r_t}x_{t,\pi}\alpha_{\operatorname{pos}_{\pi}(c)}]\). A transfer is successful when \(S(p)\ge S(c)\) for every \(c\ne p\); ties count as wins.
Let \(\Psi_{\mathrm{OPT}}\) be the minimum successful cost \(\sum_t\psi_t y_t\), and define \(\psi_{\max}=\max_t\psi_t\), \(r_{\max}=\max_t\psi_t/w_t\), and \(\bar r_{\max}=\max_t w_t/\psi_t\). Here \(\widetilde O\) suppresses factors polynomial in \(\log(m\tau+2)\).
Can a polynomial-time randomized algorithm find successful transfers costing at most \(\Psi_{\mathrm{OPT}}+\widetilde O(\sqrt{\psi_{\max}(\Psi_{\mathrm{OPT}}+\psi_{\max})}\,\bar r_{\max}r_{\max})\), with exponentially small failure probability in \(L\), or is attaining this guarantee NP-hard?
Discrete weighted priced bribery admits this additive guarantee in randomized polynomial time, with exponentially small failure probability. [Keller–Hassidim–Hazon](https://www.jair.org/index.php/jair/article/view/11538).
Unweighted continuous priced bribery is exactly solvable in \(\operatorname{poly}(m,\tau,L)\) time for every scoring protocol; that stated result does not include source weights. [Koutecký–Melissinos–Vu–Sabater](https://arxiv.org/html/2608.25444v1#S3).
The problem is exactly solvable by a deterministic algorithm in \(\operatorname{poly}(m,\tau,L)\) time. Thus the requested additive guarantee holds with failure probability zero. The algorithm works for every nonincreasing rational scoring vector; the non-concentration assumption is unnecessary.
The cited [continuous-bribery theorem](https://arxiv.org/html/2608.25444v1#S3) establishes polynomial-time solvability in the unweighted setting. Below is a direct proof incorporating source weights and explicitly recovering legal transfers.
For each supported source type \(t\), introduce a variable \(y_t\) and variables \(z_{t,c,j}\), where \(c\in C\) and \(j\in\{0,\ldots,m-1\}\).
The intended meaning of \(z_{t,c,j}\) is the transferred mass from source \(t\) whose destination places candidate \(c\) in position \(j\). Impose
\(\displaystyle 0\le y_t\le\mu_t,\qquad z_{t,c,j}\ge0,\)
\(\displaystyle \sum_{j=0}^{m-1}z_{t,c,j}=y_t\quad\text{for every }t,c,\)
and
\(\displaystyle \sum_{c\in C}z_{t,c,j}=y_t\quad\text{for every }t,j.\)
Define the linear score expression
\(\displaystyle \widehat S(c)=\sum_t w_t\left[(\mu_t-y_t)\alpha_{\operatorname{pos}_{r_t}(c)}+\sum_{j=0}^{m-1}\alpha_jz_{t,c,j}\right].\)
The winning constraints are
\(\displaystyle \widehat S(p)\ge\widehat S(c)\quad\text{for every }c\ne p.\)
Minimize
\(\displaystyle \sum_t\psi_ty_t.\)
Call the optimum of this LP \(V\). Each source retains its own matrix and its own weight and price.
The LP temporarily permits transferred mass to be assigned its source ranking. Section 3 removes such assignments without changing any score.
Given legal transfers \(x_{t,\pi}\), set
\(\displaystyle y_t=\sum_{\pi\ne r_t}x_{t,\pi},\qquad z_{t,c,j}=\sum_{\substack{\pi\ne r_t\\ \operatorname{pos}_\pi(c)=j}}x_{t,\pi}.\)
Each ranking places every candidate in exactly one position and assigns exactly one candidate to every position. Consequently, all row and column sums of the matrix \(Z_t=(z_{t,c,j})\) equal \(y_t\).
Moreover,
\(\displaystyle \sum_j\alpha_jz_{t,c,j} =\sum_{\pi\ne r_t}x_{t,\pi}\alpha_{\operatorname{pos}_\pi(c)}. \)
Thus \(\widehat S(c)=S(c)\) for every candidate, and the LP objective equals the transfer cost. In particular,
\(\displaystyle V\le\Psi_{\mathrm{OPT}}.\)
Successful transfers always exist: fix a ranking \(\rho\) placing \(p\) first, and transfer all mass of every type with \(r_t\ne\rho\) to \(\rho\). Leave the other types unchanged. Every resulting ranking is \(\rho\), so nonincreasing scores and positive weights imply \(S(p)\ge S(c)\) for every \(c\).
The LP is therefore feasible. Its feasible region is closed and bounded: \(0\le y_t\le\mu_t\) and \(0\le z_{t,c,j}\le y_t\). Hence its minimum is attained.
We first give a constructive decomposition for each source matrix.
Decomposition lemma. If an \(m\)-by-\(m\) nonnegative rational matrix \(Z\) has every row and column sum equal to \(y\), then
\(\displaystyle Z=\sum_{k=1}^{K}\lambda_kP_{\pi_k},\qquad \lambda_k>0,\qquad \sum_{k=1}^{K}\lambda_k=y,\qquad K\le m^2,\)
where \(P_{\pi_k}\) is the permutation matrix of a ranking \(\pi_k\). For \(y=0\), the decomposition is empty.
Proof. Maintain a residual matrix \(A\) whose row and column sums all equal \(q\), initially \(A=Z\) and \(q=y\). If \(q=0\), nonnegativity implies \(A=0\).
For \(q>0\), form a bipartite graph with candidates on one side and positions on the other, using an edge precisely when \(A_{c,j}>0\). For any set \(U\) of candidates, let \(N(U)\) be its neighboring positions. Then
\(\displaystyle |U|q =\sum_{c\in U}\sum_{j\in N(U)}A_{c,j} \le\sum_{c\in C}\sum_{j\in N(U)}A_{c,j} =|N(U)|q. \)
Dividing by \(q>0\) verifies Hall’s condition. Therefore the graph has a perfect matching, defining a ranking \(\pi\).
Set
\(\displaystyle \lambda=\min_c A_{c,\operatorname{pos}_\pi(c)}>0.\)
Subtract \(\lambda P_\pi\). The residual stays nonnegative, and every row and column sum becomes \(q-\lambda\). At least one positive entry becomes zero, and no zero entry becomes positive. Thus there are at most \(m^2\) iterations.
At termination the residual is zero. Summing the subtracted matrices gives the claimed decomposition, and summing their row sums gives \(\sum_k\lambda_k=y\). \(\square\)
Apply this lemma to each \(Z_t\), obtaining coefficients \(\lambda_{t,k}\) and rankings \(\pi_{t,k}\). Define
\(\displaystyle q_t=\sum_{k:\,\pi_{t,k}=r_t}\lambda_{t,k}.\)
For each permitted destination \(\pi\ne r_t\), output
\(\displaystyle x_{t,\pi}=\sum_{k:\,\pi_{t,k}=\pi}\lambda_{t,k}.\)
The actual transferred mass is
\(\displaystyle y'_t=\sum_{\pi\ne r_t}x_{t,\pi}=y_t-q_t,\)
so \(0\le y'_t\le\mu_t\).
To check score preservation, fix a candidate \(c\). Its contribution from source \(t\), before multiplying by \(w_t\), becomes
\(\displaystyle (\mu_t-y'_t)\alpha_{\operatorname{pos}_{r_t}(c)} +\sum_{\pi\ne r_t}x_{t,\pi}\alpha_{\operatorname{pos}_\pi(c)} \)
\(\displaystyle =(\mu_t-y_t+q_t)\alpha_{\operatorname{pos}_{r_t}(c)} +\sum_{k:\,\pi_{t,k}\ne r_t}\lambda_{t,k} \alpha_{\operatorname{pos}_{\pi_{t,k}}(c)} \)
\(\displaystyle =(\mu_t-y_t)\alpha_{\operatorname{pos}_{r_t}(c)} +\sum_k\lambda_{t,k}\alpha_{\operatorname{pos}_{\pi_{t,k}}(c)} \)
\(\displaystyle =(\mu_t-y_t)\alpha_{\operatorname{pos}_{r_t}(c)} +\sum_j\alpha_jz_{t,c,j}. \)
Thus every score is exactly \(\widehat S(c)\), and the recovered transfers are successful. Their cost satisfies
\(\displaystyle \sum_t\psi_ty'_t =\sum_t\psi_ty_t-\sum_t\psi_tq_t \le\sum_t\psi_ty_t. \)
Applying this construction to an optimal LP solution yields legal transfers of cost at most \(V\). Consequently,
\(\displaystyle \Psi_{\mathrm{OPT}}\le V\le\Psi_{\mathrm{OPT}}, \)
which proves exact optimality.
The LP has \(\tau(m^2+1)\) variables and \(\mathcal O(\tau m+m)\) constraints apart from nonnegativity. Its coefficients are formed by rational arithmetic on input entries, so its total encoding length is \(\operatorname{poly}(m,\tau,L)\).
The standard exact rational linear programming theorem therefore computes an optimal rational solution in \(\operatorname{poly}(m,\tau,L)\) bit operations. Its applicability follows from the explicit polynomial-size rational formulation and the feasibility, boundedness, and attainment established above.
For reconstruction, each source requires at most \(m^2\) perfect matchings. Using an \(\mathcal O(m^3)\) matching algorithm gives \(\mathcal O(\tau m^5)\) arithmetic operations. These operations retain polynomial bit length: all residual entries are differences of the original rational entries, whose denominators admit a common multiple of polynomial bit length. Hence reconstruction also takes \(\operatorname{poly}(m,\tau,L)\) bit operations.
The output lists at most \(\tau m^2\) nonzero source–destination transfers; all omitted transfers are zero. This bound depends on the supplied support size \(\tau\), without enumerating possible types or all rankings.
The returned cost is exactly \(\Psi_{\mathrm{OPT}}\), so it satisfies the requested bound
\(\displaystyle \Psi_{\mathrm{OPT}} +\widetilde{\mathcal O}\!\left( \sqrt{\psi_{\max}(\Psi_{\mathrm{OPT}}+\psi_{\max})}\, \bar r_{\max}r_{\max} \right). \)
The algorithm is deterministic, so its failure probability is zero, which is stronger than exponentially small failure probability in \(L\). For a constant scoring vector, every candidate already ties and the optimum is zero; the same algorithm also handles all nonconstant cases.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The LP and reconstruction establish exact deterministic polynomial-time solvability for the stated source-weighted model. I found no major or minor issues requiring repair.
The formulation keeps a separate matrix for each supported source type. Both \(w_t\) and \(\psi_t\) remain attached to that source throughout. It therefore respects the task’s requirements that transferred mass retains its source weight and pays its source price independently of its destination.
No step relies on treating \(\tau\) as the number of possible types. The non-concentration assumption is unused, consistently with the claimed stronger result.
For each source, every candidate’s row sum and every position’s column sum equal \(y_t\). These are necessary constraints for destination rankings, and the decomposition proved in Section 3 establishes their sufficiency.
The score expression uses the unchanged mass \(\mu_t-y_t\), the destination marginals, and the source weight exactly as specified in the task. The objective likewise uses the source price.
Temporarily allowing the original ranking is a relaxation whose removal is justified later; it is not an unaddressed modeling discrepancy.
The definitions of \(y_t\) and \(z_{t,c,j}\) give the claimed row and column sums because every strict ranking assigns each candidate exactly one position and each position exactly one candidate.
The displayed score identity follows by regrouping the finite sums. Consequently, successful legal transfers satisfy every winning constraint and have the same objective value. The inequality \(V\le\Psi_{\mathrm{OPT}}\) is justified.
Sending every source whose ranking differs from \(\rho\) to a ranking \(\rho\) with \(p\) first is legal. Sources already ranked as \(\rho\) need no transfer. Nonincreasing scores imply that each source contributes at least as much to \(p\) as to any opponent, and positive weights preserve that inequality.
Nonnegativity and the row sums imply \(z_{t,c,j}\le y_t\le\mu_t\). Thus the LP feasible region is closed and bounded. Its continuous linear objective attains a finite minimum.
When \(q>0\), the displayed calculation proves Hall’s condition for every candidate subset. The graph has equally many candidates and positions, so Hall’s theorem applies and supplies a perfect matching.
Every matched entry is positive, making \(\lambda>0\). Subtraction preserves nonnegativity and reduces every row and column sum by the same amount. At least one positive entry disappears, and no zero entry becomes positive. Hence there are at most \(m^2\) iterations.
A nonzero residual would have positive common row sum and permit another iteration. Therefore termination leaves the zero matrix. The matrix identity and coefficient-sum identity follow from the recorded subtractions. The case \(y=0\) is explicitly covered.
The coefficients counted in \(q_t\) are returned to unchanged mass. The remaining destination coefficients are nonnegative and sum to \(y'_t=y_t-q_t\), with \(0\le y'_t\le\mu_t\).
Each line of the score-preservation calculation is valid: the removed destination contribution at \(r_t\) exactly equals the contribution restored to unchanged mass. Multiplication by the same source weight preserves the equality.
Since \(\psi_t>0\), removing those assignments cannot increase cost. Applying reconstruction to an optimal LP solution therefore establishes \(\Psi_{\mathrm{OPT}}\le V\). Together with the earlier inequality, this proves exact optimality.
The variable and constraint counts are correct. Products and sums of the binary rational input coefficients have polynomial encoding length.
The invoked exact rational LP theorem applies to the explicit rational, feasible, bounded LP and yields an optimal rational solution of polynomial bit length in polynomial time.
Reconstruction performs at most \(m^2\) matchings per source. The stated bound of \(\mathcal O(\tau m^5)\) arithmetic operations is valid. Its common-denominator argument also controls bit complexity: subtraction preserves a common denominator, while residual entries and extracted coefficients remain bounded by the original source mass.
The output contains at most \(\tau m^2\) nonzero transfers and therefore does not require enumerating all rankings.
Exact optimality implies the requested additive upper bound. Determinism gives failure probability zero. Constant scoring vectors, including the all-zero vector, give ties without transfers and optimum zero. The reconstruction also handles sources with \(y_t=0\).
The contextual citation accurately identifies polynomial-time continuous priced bribery for scoring protocols in the [cited paper](https://arxiv.org/html/2608.25444v1#S3). The weighted conclusion is established by the supplied argument independently of that citation.
No additional clarification is needed to make the argument verifiable.
⟨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.