Answer: \(\mathrm{P}\)
Theorem 1 — class: hardness
Given rational fixed masses \(\nu_{\rho}\) over rankings \(\rho\in S_3\), rational controllable mass \(W\), and a preferred candidate \(p\), decide whether there exist masses \(x_{\rho}\ge 0\) with \(\sum_{\rho}x_{\rho}=W\) such that \(\mu_{\rho}=\nu_{\rho}+x_{\rho}\) makes \(p\) a Borda winner under the paper's tie convention.
Let \(C=\{a,b,p\}\), with \(m=3\), and let \(S_3\) denote its strict total rankings. A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible types.
The input consists of fixed ranking masses \(\nu_\rho\geq0\), with unlisted rankings having zero mass, and a binary rational controllable mass \(W\geq0\), with \(\sum_\rho\nu_\rho+W>0\). Masses are absolute weights and need not sum to one. Let \(L\) be the total input bit length.
The coalition may distribute its mass arbitrarily among all rankings: choose real masses \(x_\rho\geq0\) with \(\sum_{\rho\in S_3}x_\rho=W\), producing \(\mu_\rho=\nu_\rho+x_\rho\). Apply Borda, with each ranking's contribution multiplied by its mass. Ties are resolved against \(p\), so success requires \(p\)'s score to strictly exceed each rival's score.
Is deciding whether such a successful mass allocation exists in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
Constructive coalitional manipulation with indivisible weighted voters under Borda is \(\mathrm{NP}\)-complete even with three candidates ([Conitzer and Sandholm](https://arxiv.org/abs/cs/0205076)). No published result settling this exact rational-input, divisible-mass decision problem was verified.
The decision problem is in \(\mathrm{P}\). In fact, three strict rational inequalities characterize feasibility, and a successful rational allocation can be constructed whenever they hold.
Use Borda scores \(2,1,0\). Let \(P,A,B\) be the scores of \(p,a,b\), respectively, contributed by the fixed masses alone. Define the fixed score deficits
\(d_a=A-P,\qquad d_b=B-P.\)
Then a successful allocation exists if and only if
\(d_a<2W,\qquad d_b<2W,\qquad d_a+d_b<3W.\)
The strict inequalities account for ties being resolved against \(p\).
Consider any ranking receiving coalition mass. Move \(p\) to first place while preserving the relative order of \(a,b\).
If \(p\) was in position \(r\), its Borda score increases by \(r-1\). Each rival originally above \(p\) loses one point, and each rival originally below \(p\) keeps its score. Consequently, for either rival \(c\), the change in the per-unit score difference between \(p\) and \(c\) is
\((r-1)+\mathbf{1}_{\{c\text{ was above }p\}}\geq 0.\)
Multiplying by the nonnegative mass assigned to that ranking preserves this inequality. Applying this transformation to every coalition ranking preserves total coalition mass and cannot decrease either winning margin.
Thus, whenever a successful allocation exists, one also exists using only the rankings \(p\succ a\succ b\) and \(p\succ b\succ a\).
Let \(t\) be the mass allocated to \(p\succ a\succ b\), with the remaining mass \(W-t\) allocated to \(p\succ b\succ a\). The allowed range is \(0\leq t\leq W\).
The resulting scores are
\(S_p=P+2W,\qquad S_a=A+t,\qquad S_b=B+W-t.\)
Therefore, success is equivalent to
\(t<2W-d_a,\qquad t>d_b-W,\qquad 0\leq t\leq W.\)
This reduction is exact by the preceding argument.
Suppose a successful allocation exists. After placing \(p\) first throughout the coalition, its parameter \(t\) satisfies the inequalities above.
Since \(t\geq 0\) and \(t<2W-d_a\), we obtain \(d_a<2W\).
Since \(t\leq W\) and \(t>d_b-W\), we obtain \(d_b<2W\).
Finally, the strict bounds on \(t\) imply
\(d_b-W<t<2W-d_a,\)
and hence \(d_a+d_b<3W\). Thus all three claimed inequalities are necessary.
Assume the three claimed inequalities hold. Put
\(\ell=d_b-W,\qquad u=2W-d_a.\)
The hypotheses give
\(0<u,\qquad \ell<W,\qquad \ell<u.\)
Together with \(0<W\), these say that each of \(0,\ell\) is strictly smaller than each of \(W,u\). Therefore
\(L_0:=\max\{0,\ell\}<U_0:=\min\{W,u\}.\)
Choose the rational number
\(t=\dfrac{L_0+U_0}{2}.\)
Then \(0\leq t\leq W\), \(t>\ell\), and \(t<u\). By Section 2, assigning mass \(t\) to \(p\succ a\succ b\) and mass \(W-t\) to \(p\succ b\succ a\) makes \(p\) strictly beat both rivals.
The first two claimed inequalities become \(d_a<0\) and \(d_b<0\). These mean \(P>A\) and \(P>B\), so the fixed society already makes \(p\) win strictly. The only coalition allocation is the zero allocation, which succeeds.
This completes both directions of the characterization, including the zero-mass case.
Compute \(P,A,B\) by summing the fixed masses multiplied by their Borda scores. Then compute \(d_a,d_b\) and check the three strict inequalities using exact rational arithmetic.
There are only six rankings, so \(\tau\leq 6\). Computing the scores requires \(O(\tau)\) rational operations, followed by a constant number of rational operations and comparisons. The numerators and denominators involved have bit lengths polynomial in the total input length \(L\): a common denominator may be formed by multiplying the input denominators, whose total bit length is at most \(L\). Integer arithmetic and exact comparisons therefore take polynomial time.
The witness constructed above also has polynomial bit length. Since \(m=3\) is fixed, this running time is polynomial in \(m,\tau,L\), as requested.
The divisibility assumption is essential to this proof: it permits every rational \(t\) in the feasible interval. With indivisible weighted voters, the possible values of \(t\) are constrained by which voters receive each ranking, so interval nonemptiness alone does not establish feasibility.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. The feasibility criterion is necessary and sufficient, handles strict victory and zero controllable mass correctly, and yields an exact polynomial-time algorithm. No mathematical gaps or errors were found.
The transformation is valid. Moving \(p\) from position \(r\) to first increases its Borda contribution by \(r-1\). Each rival previously above \(p\) moves down one position and loses one point; each rival previously below \(p\) retains its position and score.
Thus the change in the per-unit margin against a rival \(c\) is exactly
\[
(r-1)+\mathbf{1}_{\{c\text{ was above }p\}}\geq 0.
\]
Nonnegative mass preserves this inequality. Transforming and aggregating coalition masses preserves their total \(W\) and cannot reduce either winning margin.
Consequently, any successful allocation can be replaced by a successful allocation supported on the two stated rankings. Conversely, an allocation supported on those rankings is permitted by the original task. The restriction is therefore exact.
For mass \(t\) on \(p\succ a\succ b\) and mass \(W-t\) on \(p\succ b\succ a\), the coalition contributes \(2W,t,W-t\) to \(p,a,b\), respectively. Hence all three score formulas are correct.
The two strict victory conditions rearrange correctly to
\[
t<2W-d_a,\qquad t>d_b-W.
\]
Together with \(0\leq t\leq W\), these precisely describe feasible allocations after the restriction above.
Each inference is valid:
The strictness is preserved throughout, as required by the tie rule.
With \(\ell=d_b-W\) and \(u=2W-d_a\), the three proposed inequalities imply exactly
\[
0<u,\qquad \ell<W,\qquad \ell<u.
\]
Since \(W>0\), all four comparisons between an element of \(\{0,\ell\}\) and an element of \(\{W,u\}\) are strict. Therefore
\[
\max\{0,\ell\}<\min\{W,u\}.
\]
The midpoint lies strictly between these endpoints. It consequently satisfies both strict victory bounds and the permitted mass bounds. All endpoints are rational, so the constructed allocation is rational. This establishes sufficiency without assuming that arbitrary real inputs have finite representations.
When \(W=0\), the first two conditions are precisely \(A<P\) and \(B<P\). These are necessary and sufficient for the unique zero allocation to succeed.
The third condition is automatically satisfied when both deficits are negative. Thus the criterion remains exact in this case. The task’s positive-total-mass assumption introduces no additional difficulty.
The complexity argument is sound. There are six possible rankings, and score computation takes \(O(\tau)\) rational operations, followed by a constant number of operations and comparisons.
A product of the input denominators has bit length bounded by their total input bit length. Representing the score sums over such a denominator therefore requires only polynomially many bits; the constant score multipliers, additions, subtractions, and comparisons preserve polynomial bit length. Exact integer arithmetic on these representations takes polynomial time.
The midpoint construction and subtraction from \(W\) also preserve polynomial bit length. Since the task fixes \(m=3\), this establishes the requested polynomial bound in \(m,\tau,L\).
The final distinction is accurate: the midpoint allocation is permitted by divisible mass, while indivisible voters restrict attainable values of \(t\). The proof does not depend on the cited hardness result or invoke any external theorem requiring verification.
None. The argument establishes the claimed characterization, decision algorithm, and polynomial-size rational witness.
⟨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.