Answer: Polynomial-time solvable exactly: a deterministic algorithm outputs a feasible rational plan of cost \(K\) in \(\operatorname{poly}(m,\tau,L)\) time, with zero failure probability.
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateIn Rα-Bribery under constant or non- concentrated Rα, let k be the minimum number of voters needed to be bribed in order to make p win. Then there ex- ists a polynomial-time randomized algorithm using at most k + O( √ k)-voters, with exponentially-small failure proba- bility.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a qualifying scoring vector \(\alpha\), a target \(p\), and a rational distribution \(\mu\) supported on \(\tau\) rankings, compute a minimum-mass bribery plan \(x_{t,\pi}\ge 0\) that moves mass from each initial ranking \(t\) to a new ranking \(\pi\ne t\). Require \(\sum_{\pi\ne t}x_{t,\pi}\le\mu_t\) for each \(t\), and require \(p\) to be a co-winner under the resulting distribution.
Let \(C=\{p,c_1,\ldots,c_m\}\), with \(m\ge1\), and let rankings be strict total orders. Use positional scoring with a nonnegative integer vector \(\alpha_0\le\cdots\le\alpha_m\), where \(0<\alpha_m\le(m+1)^d\) for a fixed constant \(d\). A qualifying vector satisfies either \(\alpha_m\le A\) or \(\frac{1}{m+1}\sum_{j=0}^m\alpha_j\le(1-\epsilon)\alpha_m\), for fixed constants \(A>0\) and \(0<\epsilon<1\).
A society is given by its support: a list \(T\) of \(\tau\) rankings with positive binary rational masses \(\mu_t\), summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
A bribery plan splits mass arbitrarily: \(x_{t,\pi}\ge0\) for \(t\in T\) and any ranking \(\pi\ne t\), with \(\sum_{\pi\ne t}x_{t,\pi}\le\mu_t\). Unmoved mass retains its ranking; moved mass adopts \(\pi\), at unit cost per unit mass. Plans are represented by their nonzero rational transfers.
Scores are integrated against the resulting distribution, and feasibility requires \(p\) to have score at least that of every other candidate; ties count as wins. Let \(K\) be the minimum feasible cost \(\sum_{t\in T}\sum_{\pi\ne t}x_{t,\pi}\).
Does a randomized algorithm running in \(\operatorname{poly}(m,\tau,L)\) always produce a feasible plan of cost at most \(K+\widetilde O(\sqrt K)\), with failure probability at most \(\exp(-\Omega(L))\), or is achieving this approximation guarantee NP-hard? Here \(\widetilde O\) hides only polylogarithmic factors in \(2+m+\tau+L\), with constants allowed to depend on \(A,\epsilon,d\).
For discrete unit-cost bribery under these scoring conditions, a polynomial-time randomized algorithm uses at most \(k+\widetilde O(\sqrt k)\) voters, where \(k\) is optimal, with exponentially small failure probability. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/11476/11335).
An extension treats discrete weighted and priced voters; the search identified no result establishing or excluding the stated guarantee for this exact divisible-mass problem. [Source](https://www.jair.org/index.php/jair/article/view/11538).
The requested guarantee holds. In fact, a deterministic algorithm computes a feasible rational plan of cost exactly \(K\) in \(\operatorname{poly}(m,\tau,L)\) time. The proof applies to every scoring vector in the question, without requiring either qualifying condition.
The essential point is that replacement mass can realize a fractional assignment of candidates to positions exactly.
Write \(n=m+1\), and index candidates by \(i\in\{0,\ldots,m\}\), with \(c_0=p\). Index positions by \(j\in\{0,\ldots,m\}\), so that position \(j\) awards score \(\alpha_j\).
For a ranking \(t\), let \(s_t(i)\) denote the score it awards candidate \(c_i\). The initial score is
\(S_i=\sum_{t\in T}\mu_t s_t(i).\)
Introduce variables:
Impose the following linear constraints:
\(0\le y_t\le\mu_t\quad(t\in T),\qquad b=\sum_{t\in T}y_t,\qquad B_{i,j}\ge0.\)
\(\sum_{j=0}^{m}B_{i,j}=b\quad(i=0,\ldots,m).\)
\(\sum_{i=0}^{m}B_{i,j}=b\quad(j=0,\ldots,m).\)
Define the proposed final scores by the linear expressions
\(F_i=S_i-\sum_{t\in T}y_t s_t(i)+\sum_{j=0}^{m}\alpha_j B_{i,j}.\)
Require
\(F_0\ge F_i\quad(i=1,\ldots,m),\)
and minimize \(b\). Denote the optimum by \(v\).
This LP is feasible: take \(y_t=\mu_t\), \(b=1\), and let \(B\) be the permutation matrix of any ranking placing \(p\) first. Then \(p\) receives \(\alpha_m\), and every opponent receives at most \(\alpha_m\).
Its feasible region is compact. Indeed, \(0\le b\le1\), and the nonnegative row-sum constraints imply \(0\le B_{i,j}\le1\). Thus the optimum is attained.
Consider any feasible plan \(x\). Set
\(y_t=\sum_{\pi\ne t}x_{t,\pi},\qquad b=\sum_{t\in T}y_t,\)
and
\(B_{i,j}=\sum_{t\in T}\sum_{\pi\ne t}x_{t,\pi}\mathbf{1}\{\pi\text{ places }c_i\text{ in position }j\}.\)
Every ranking places each candidate in exactly one position and assigns exactly one candidate to each position. Consequently, every row and every column of \(B\) sums to \(b\).
The expression \(F_i\) equals candidate \(c_i\)'s actual final score: it subtracts the score contributed by removed mass and adds the score contributed by replacement mass. Thus the winner constraints hold, and the objective \(b\) equals the plan's cost.
Therefore every feasible plan has cost at least \(v\). In particular,
\(v\le K.\)
We next construct a feasible rational plan of cost at most \(v\), proving equality.
Take a rational optimal LP solution \((y,b,B)\).
If \(b=0\), nonnegativity and the row-sum constraints give \(B=0\). The winner constraints then say that \(p\) already wins. The empty plan is optimal.
Suppose \(b>0\). We prove constructively that
\(B=\sum_{\ell=1}^{q}\lambda_\ell P_{\pi_\ell},\qquad \lambda_\ell>0,\qquad \sum_{\ell=1}^{q}\lambda_\ell=b,\qquad q\le n^2,\)
where \(P_{\pi_\ell}\) is the candidate–position permutation matrix of a strict ranking \(\pi_\ell\).
Start with residual matrix \(R=B\). Its rows and columns have a common sum \(\rho=b\). Whenever \(\rho>0\), form the bipartite graph whose vertices are candidates and positions, with edge \((i,j)\) exactly when \(R_{i,j}>0\).
For any candidate subset \(U\), let \(N(U)\) be its neighboring positions. Since entries outside those neighboring columns vanish,
\(\rho|U|=\sum_{i\in U}\sum_{j\in N(U)}R_{i,j}\le\sum_{j\in N(U)}\sum_{i=0}^{m}R_{i,j}=\rho|N(U)|.\)
Dividing by \(\rho>0\) verifies Hall's condition. Hall's marriage theorem therefore gives a perfect matching, corresponding to a ranking \(\pi\).
Set
\(\lambda=\min\{R_{i,j}:(i,j)\text{ belongs to this matching}\}>0,\)
and replace \(R\) by \(R-\lambda P_\pi\). This preserves nonnegativity, reduces every row and column sum to \(\rho-\lambda\), and makes at least one previously positive entry zero. No zero entry becomes positive.
There are initially at most \(n^2\) positive entries, so this process terminates after at most \(n^2\) iterations. At termination the residual is zero. Summing the subtractions gives the claimed decomposition; tracking any row sum gives \(\sum_\ell\lambda_\ell=b\).
All operations preserve rationality.
Merge repeated rankings in the decomposition if necessary. Let \(\lambda_\pi\) be their combined weights, assigning \(\lambda_\pi=0\) to rankings absent from the decomposition. Thus
\(\sum_\pi\lambda_\pi=b,\qquad B=\sum_\pi\lambda_\pi P_\pi.\)
For every source \(t\) and every decomposed ranking \(\pi\ne t\), output the transfer
\(x_{t,\pi}=\dfrac{y_t\lambda_\pi}{b},\)
omitting zero transfers.
These transfers are nonnegative rational numbers. For each source,
\(\sum_{\pi\ne t}x_{t,\pi}=\dfrac{y_t}{b}(b-\lambda_t)\le y_t\le\mu_t.\)
Thus the source-capacity constraints hold, and every output transfer changes the ranking.
To verify the resulting scores, temporarily consider assigning \(y_t\lambda_\pi/b\) from source \(t\) to every decomposed ranking, including \(\pi=t\). The assignment back to \(t\) simply retains that mass, so deleting this self-assignment from the transfer list leaves the resulting distribution unchanged.
Under this bookkeeping, source \(t\) contributes
\((\mu_t-y_t)s_t(i)+\sum_\pi\dfrac{y_t\lambda_\pi}{b}s_\pi(i)\)
to candidate \(c_i\)'s score. Summing over sources and using \(\sum_t y_t=b\) gives
\(S_i-\sum_t y_t s_t(i)+\sum_\pi\lambda_\pi s_\pi(i) =S_i-\sum_t y_t s_t(i)+\sum_j\alpha_j B_{i,j}=F_i.\)
Hence the constructed plan makes \(p\) a co-winner.
Its cost satisfies
\(\operatorname{cost}(x)=\sum_t\sum_{\pi\ne t}x_{t,\pi}\le\sum_t y_t=b=v.\)
Section 2 showed that every feasible plan has cost at least \(v\). Applying that bound to this constructed plan proves
\(\operatorname{cost}(x)=v=K.\)
This also proves that a rational optimum exists for the original problem.
The LP has \(\tau+n^2+1\) variables and \(O(\tau+n^2)\) constraints, including nonnegativity constraints.
Its encoding length is polynomial in \(m,\tau,L\). The scores \(s_t(i)\) have \(O(1+d\log n)\) bits. Each \(S_i\) is a sum of the input rational masses multiplied by these integers, so its exact rational encoding also has polynomial length.
We use the standard polynomial-time theorem for rational linear programming: an explicitly encoded rational LP can be optimized exactly in time polynomial in its dimensions and encoding length, with a rational optimal solution of polynomial encoding length when its optimum is attained. The feasibility, boundedness, and attainment hypotheses were verified above.
The decomposition requires at most \(n^2\) perfect-matchings computations. Using an elementary \(O(n^3)\) bipartite matching algorithm, it takes \(O(n^5)\) combinatorial operations.
Exact arithmetic during decomposition also remains polynomial in bit complexity. To see this, choose a common denominator \(Q\) for the entries of the returned rational matrix \(B\). Its bit length is polynomial because the total encoding length of \(B\) is polynomial. Every residual entry and every extracted weight remains an integer multiple of \(1/Q\), between \(0\) and \(1\). Thus repeated subtraction cannot cause uncontrolled denominator growth.
There are at most
\(\tau q\le\tau(m+1)^2\)
nonzero transfers. Each has polynomial encoding length because it is obtained through the rational operations \(y_t\lambda_\pi/b\). Writing the rankings and checking which transfers are self-assignments takes at most \(O(\tau n^3)\) elementary operations.
Consequently, the complete algorithm, including exact optimization and explicit output, runs in
\(\operatorname{poly}(m,\tau,L).\)
The algorithm is deterministic and always returns cost exactly \(K\). Its additive error and failure probability are both zero, so it satisfies the requested \(K+\widetilde O(\sqrt K)\) guarantee.
The cited discrete algorithm also uses a Birkhoff decomposition, but samples rankings to assign indivisible voters. Here the decomposition weights themselves are implementable as divisible mass, which makes exact realization possible. See [Keller, Hassidim, and Hazon, Theorem 7 and Algorithm 1](https://ojs.aaai.org/index.php/AAAI/article/download/11476/11335).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes exact deterministic polynomial-time solvability of the stated divisible-mass problem. The LP, decomposition, transfer construction, and bit-complexity argument are correct. No major or minor issues were found.
The argument addresses the exact model in USER_TASK: arbitrary splitting of source masses, unrestricted replacement rankings, unit cost per moved mass, and ties counting as wins.
The position convention is consistent: position \(j\) awards \(\alpha_j\), so a ranking placing \(p\) first assigns it \(\alpha_m\). The proof does not require distinct score values.
The claim that the qualifying conditions are unnecessary is justified. The construction uses neither condition; the stated polynomial bound on scoring entries suffices for its encoding analysis.
The variables have the stated meanings:
Every replacement ranking contributes once to each candidate row and each position column, making the common row and column sums \(b\) necessary.
The final-score expression correctly subtracts removed contributions and adds replacement contributions. The inequalities \(F_0\ge F_i\) implement precisely the required co-winner condition.
The proposed feasible point is valid: removing all mass and replacing it with one ranking placing \(p\) first gives \(p\) score \(\alpha_m\), while each opponent receives at most \(\alpha_m\).
The feasible region is closed, since all constraints are non-strict linear constraints. It is bounded: \(0\le y_t\le\mu_t\), \(0\le b\le1\), and \(0\le B_{i,j}\le b\le1\). Thus the compactness and attainment claims hold.
For every legal plan, the definitions of \(y_t\), \(b\), and \(B\) satisfy all LP constraints. The score identity is exact, and the objective equals the actual moved mass.
Consequently, every feasible plan has cost at least \(v\). This implication does not depend on already having established existence of an optimal original plan; the later construction establishes that existence.
No source rankings or destination rankings are omitted from this direction.
The case \(b=0\) is handled correctly: nonnegative entries with zero row sums force \(B=0\), and the winner constraints certify that the empty plan succeeds.
For \(b>0\), the residual matrix maintains nonnegative entries and equal row and column sums \(\rho\). The displayed calculation correctly verifies \(|N(U)|\ge|U|\) for every subset \(U\) of candidate vertices.
Hall’s marriage theorem applies: a finite bipartite graph admits a matching covering its left vertex set if every left subset has at least as many neighbors. Here both vertex sets have size \(n\), so such a matching is perfect.
Subtracting the smallest entry on the matching:
The claimed bound of at most \(n^2\) iterations follows. A residual with positive common sum always permits another matching, so termination leaves the zero matrix. The identities for \(B\) and \(\sum_\ell\lambda_\ell=b\) therefore follow exactly as written.
This is the critical equivalence step, and it is correct.
The transfers \(x_{t,\pi}=y_t\lambda_\pi/b\), restricted to \(\pi\ne t\), satisfy source capacities because their total from source \(t\) is \(y_t(b-\lambda_t)/b\le\mu_t\).
The temporary inclusion of self-assignments is valid bookkeeping. Assigning mass from \(t\) back to \(t\) has no effect on its ranking or score contribution. Omitting that assignment increases retained mass by exactly the omitted amount, leaving the resulting distribution unchanged.
The displayed score calculation consequently proves that the legal output plan realizes every \(F_i\) and makes \(p\) a co-winner.
Its cost is at most \(v\). Section 2’s lower bound applies to this same legal plan, forcing its cost to equal \(v\). Thus \(K=v\), with an attained rational optimum. Allowing self-assignments in the LP does not create an invalid relaxation gap.
The LP dimensions and encoding bounds are correct. Exact sums of binary rational input masses have polynomial encoding length; their denominators need not be numerically small.
The invoked rational LP theorem is stated adequately: exact optimization and a polynomial-length rational optimal solution are available in polynomial time for explicitly encoded rational LPs with an attained finite optimum. The proof verifies those hypotheses.
The decomposition bound of \(O(n^5)\) combinatorial operations follows from at most \(n^2\) matching computations, each taking \(O(n^3)\) operations.
The common-denominator argument correctly controls arithmetic growth: residual entries and extracted weights remain multiples of \(1/Q\), with polynomial-length numerators and denominator.
There are at most \(\tau n^2\) transfers. Each transfer weight has polynomial encoding length, and each destination ranking has polynomial encoding length. Therefore the explicit output, as well as its computation, fits the requested \(\operatorname{poly}(m,\tau,L)\) bound.
Exact cost \(K\) gives zero additive error, including when \(K=0\). Determinism gives zero failure probability, which satisfies the requested exponential bound.
The peripheral comparison with the discrete algorithm is accurate: the cited paper’s Theorem 7 states the decomposition result, and Algorithm 1 samples permutations from its weights. This citation is not needed for the self-contained continuous proof. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/11476/11335).
Required repair or clarification: none.
⟨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.