Answer: Polynomial-time solvable: the decision and minimum-cost optimization problems are in \(\mathrm{P}\), and the decision problem is fixed-parameter tractable with parameter \(\tau\).
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateParameterized by the number of voters, \Borda \ShiftBribery is $\w[1]$-hard (even for unit price functions).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), preferred candidate \(p\), finite voter types \(T\), where each \(t\in T\) consists of a complete ranking \(\rho_t\) and price function \(\pi_t\), and rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), choose masses \(x_{t,j}\ge 0\) for \(j=0,\ldots,\operatorname{pos}_{\rho_t}(p)-1\) satisfying \(\sum_j x_{t,j}=\mu_t\). Each mass \(x_{t,j}\) receives exactly \(j\) upward shifts of \(p\); decide whether the total cost \(\sum_{t,j}\pi_t(j)x_{t,j}\) is at most \(b\) and makes \(p\) a Borda winner, or compute the minimum cost.
Let \(C\) contain \(m\geq1\) candidates and let \(p\in C\). A society is given by its support: a list of \(\tau\) types \(t=(\rho_t,\pi_t)\) with positive binary-rational masses \(\mu_t\) summing to \(1\); \(\tau\) is the support size, not the number of possible types.
Each \(\rho_t\) is a strict complete ranking, with positions numbered from \(1\). Write \(r_t=\operatorname{pos}_{\rho_t}(p)\). The explicitly tabulated prices \(\pi_t:\{0,\ldots,r_t-1\}\to\mathbb{Z}_{\geq0}\) are nondecreasing and satisfy \(\pi_t(0)=0\). The budget \(b\in\mathbb{Q}_{\geq0}\) is binary encoded; \(L\) is the total input bit length.
An action chooses real masses \(x_{t,j}\geq0\) with \(\sum_{j=0}^{r_t-1}x_{t,j}=\mu_t\). Mass \(x_{t,j}\) moves \(p\) upward exactly \(j\) positions, preserving all other candidates' relative order, at cost \(\pi_t(j)x_{t,j}\).
Borda scores are aggregated by mass. Success means that \(p\) is a co-winner, allowing ties, and \(\sum_{t,j}\pi_t(j)x_{t,j}\leq b\).
Is this continuous Borda shift-bribery decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard? If it is \(\mathrm{NP}\)-hard, is it nevertheless fixed-parameter tractable with parameter \(\tau\), in time \(f(\tau)\operatorname{poly}(m,L)\)?
Discrete Borda shift bribery is [NP-complete](https://www.math.auckland.ac.nz/~slinko/Research/swap.pdf); it is also \(\mathrm{W[1]}\)-hard parameterized by the number of voters, even with unit prices.
The exact continuous problem above is already covered by a [polynomial-time result](https://arxiv.org/html/2608.25444v1) for scoring-rule shift bribery with rational populations and nondecreasing rational prices, including minimum-cost optimization. Thus the target is already settled.
The problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). Consequently, it is also fixed-parameter tractable with parameter \(\tau\). This agrees with the cited paper’s polynomial-size LP result for continuous shift bribery. [Continuous Computational Social Choice, Section 3](https://arxiv.org/html/2608.25444v1#S3)
Here is a direct proof for the exact model in the question.
Use the Borda convention that position \(k\) receives \(m-k\) points. For each type \(t\) and opponent \(c\ne p\), write \(q_t(c)=\operatorname{pos}_{\rho_t}(c)\).
After shifting \(p\) upward by \(j\) positions, its position is \(r_t-j\). An opponent \(c\) moves down exactly one position if and only if \(p\) passes it, equivalently,
\(r_t-j\le q_t(c)<r_t.\)
Every other opponent retains its position. Define the indicator
\(I_{t,j,c}=\begin{cases}1,&r_t-j\le q_t(c)<r_t,\\0,&\text{otherwise}.\end{cases}\)
Thus, on one unit of mass receiving this shift, the Borda score difference between \(p\) and \(c\) is
\(a_{t,j,c}=(m-r_t+j)-(m-q_t(c)-I_{t,j,c})=q_t(c)-r_t+j+I_{t,j,c}.\)
These are explicitly computable integers. As differences of two Borda scores, they satisfy \(\lvert a_{t,j,c}\rvert\le m-1\).
Introduce one real variable \(x_{t,j}\) for each listed type \(t\) and each \(j\in\{0,\ldots,r_t-1\}\). Consider the following rational linear feasibility problem:
\(x_{t,j}\ge0\qquad\text{for every }t,j,\)
\(\displaystyle\sum_{j=0}^{r_t-1}x_{t,j}=\mu_t\qquad\text{for every }t,\)
\(\displaystyle\sum_t\sum_{j=0}^{r_t-1}a_{t,j,c}x_{t,j}\ge0\qquad\text{for every }c\in C\setminus\{p\},\)
\(\displaystyle\sum_t\sum_{j=0}^{r_t-1}\pi_t(j)x_{t,j}\le b.\)
Equivalence. Any permitted action satisfies the nonnegativity and mass constraints. By additivity of mass-weighted Borda scores, its final score difference between \(p\) and \(c\) is exactly the left-hand side of the corresponding winning inequality. Hence all winning inequalities hold precisely when \(p\) is a co-winner. The final inequality is exactly the action’s budget requirement.
Conversely, every feasible LP vector specifies a permitted action by assigning mass \(x_{t,j}\) to shift \(j\). The same score calculation and cost expression prove that this action succeeds within budget.
Therefore, the instance is a yes-instance if and only if this LP is feasible. No integrality assumption or rounding is involved.
The number of variables is
\(\displaystyle N=\sum_t r_t\le\tau m.\)
Besides nonnegativity, there are \(\tau\) mass equalities, \(m-1\) winning inequalities, and one budget inequality. Equalities may be replaced by pairs of inequalities.
All coefficients are rational:
Positions and indicators can be computed directly from the listed rankings, and all winning coefficients can be constructed in \(O(\tau m^2)\) elementary operations. Consequently, the full LP has encoding length polynomial in \(m,\tau,L\).
The standard polynomial-time theorem for rational linear programming decides feasibility over the reals in time polynomial in the explicitly encoded system’s length. Its hypotheses hold here: finitely many variables and constraints, explicit rational coefficients, and non-strict linear inequalities. In particular, exact ties and exact budget equality are covered.
For \(m=1\), there are no winning inequalities, and choosing \(x_{t,0}=\mu_t\) succeeds at zero cost, consistently with the formulation.
Minimum-cost optimization is also polynomial-time solvable: omit the budget constraint and minimize
\(\displaystyle\sum_t\sum_{j=0}^{r_t-1}\pi_t(j)x_{t,j}.\)
The feasible region is nonempty because shifting all mass of every type to place \(p\) first makes \(p\) a co-winner. It is closed and bounded because \(0\le x_{t,j}\le\mu_t\). Therefore, the linear objective attains its minimum, and rational LP optimization computes it exactly in polynomial time.
Finally, a bound polynomial in \(m,\tau,L\) is bounded by \(f(\tau)\operatorname{poly}(m,L)\) for a suitable polynomial function \(f\), proving fixed-parameter tractability. NP-hardness would therefore imply \(\mathrm{P}=\mathrm{NP}\).
The argument does not require price monotonicity. The decisive features are divisible masses and an explicitly enumerable set of at most \(m\) shifts per support type.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly and rigorously. Its explicit rational LP establishes polynomial-time decision and minimum-cost optimization, and therefore fixed-parameter tractability with parameter \(\tau\). No major or minor mathematical issues were found.
The shift calculation is correct. Moving \(p\) from position \(r_t\) to position \(r_t-j\) displaces precisely the candidates originally occupying positions from \(r_t-j\) through \(r_t-1\). Thus the condition
\[
r_t-j\le q_t(c)<r_t
\]
correctly identifies the opponents that move down one position.
Under the stated Borda convention, the resulting scores are \(m-r_t+j\) for \(p\) and \(m-q_t(c)-I_{t,j,c}\) for \(c\). Their difference is therefore exactly
\[
a_{t,j,c}=q_t(c)-r_t+j+I_{t,j,c}.
\]
Both the sign and the indicator contribution are correct.
The coefficient bound \(\lvert a_{t,j,c}\rvert\le m-1\) is valid because each resulting Borda score lies between \(0\) and \(m-1\). The formulas also cover \(j=0\) and \(r_t=1\).
There is exactly one variable for each action allowed by the task. Nonnegativity and the equality
\[
\sum_{j=0}^{r_t-1}x_{t,j}=\mu_t
\]
express precisely that each type’s entire mass is allocated among its allowed shifts.
The formulation introduces no additional restriction on divisibility, rationality, or integrality of the chosen masses. It matches the task’s real-valued action space.
The winning inequality for each opponent correctly sums the final score differences, rather than merely the improvements relative to the original election. Consequently, no initial-score term is missing.
Additivity of mass-weighted Borda scores justifies the expression \(\sum_{t,j}a_{t,j,c}x_{t,j}\). Requiring it to be nonnegative for every \(c\ne p\) is exactly the co-winner condition, including ties.
The budget inequality uses precisely the stipulated per-unit costs. Both directions of the claimed equivalence are established: every successful action gives a feasible LP vector, and every feasible vector gives a successful permitted action.
The variable count \(N=\sum_t r_t\le\tau m\) is correct and depends on the listed support, not on the number of possible types.
The stated constraint counts are correct. Converting equalities into pairs of inequalities preserves feasibility and increases the size only polynomially.
The encoding analysis is sufficient:
Thus the explicitly constructed rational LP has encoding length polynomial in \(m,\tau,L\).
The invoked standard theorem is stated sufficiently precisely for this application: feasibility of an explicitly encoded rational linear system is decidable in time polynomial in its binary encoding length.
Its hypotheses are checked correctly. All constraints are non-strict, all coefficients are rational, and the system is finite and explicit. Real-valued variables pose no obstacle to this theorem. Exact ties and exact budget equality are therefore handled without an approximation or rounding gap.
The separately checked case \(m=1\) is correct: the zero-shift allocation costs zero and there are no opponents.
Removing the budget constraint gives the appropriate optimization problem.
The asserted nonemptiness is valid: placing \(p\) first throughout the population makes it a co-winner. Every such shift is available at a finite tabulated price.
The mass constraints imply \(0\le x_{t,j}\le\mu_t\), so the feasible region is bounded; the non-strict linear constraints make it closed. Hence the objective attains its minimum. Exact polynomial-time rational LP optimization applies as claimed.
A polynomial running-time bound in \(m,\tau,L\) can indeed be bounded by \(f(\tau)\operatorname{poly}(m,L)\). The fixed-parameter tractability conclusion follows. The qualification that NP-hardness would imply \(\mathrm{P}=\mathrm{NP}\) is also correct.
The assertion that monotonicity is unnecessary for this LP argument is justified: neither its equivalence nor its encoding analysis uses monotonicity.
The external citation is consistent with the conclusion: the cited paper’s Section 3 gives polynomial-time minimum-move optimization with rational populations and costs when the allowed output rankings are polynomially enumerable. The prover explicitly enumerates the available shifts and supplies the Borda winning inequalities. Its direct proof independently establishes the result. [Continuous Computational Social Choice, Section 3](https://arxiv.org/html/2608.25444v1#S3)
No mathematical repair or additional clarification is required.
⟨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.