Answer: Polynomial-time solvable: feasibility and rational witness construction take \(O((\tau+1)L^2)\) bit operations, hence \(O(L^2)\) for \(m=3\) and \(\tau\leq15\).
Proposition 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing a coalition manipulation of the modified Borda count with weighted and partial votes and 3 candidates is NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(C=\{a,b,p\}\), a rational fixed society distribution \(\nu\) over the \(15\) nonempty top-truncated ballots, rational manipulator mass \(\alpha\) with \(\sum_b\nu_b+\alpha=1\), and target \(p\), choose rational masses \(x_b\ge0\) with \(\sum_b x_b=\alpha\) so that \(p\) wins under the paper's modified Borda rule, with ties favoring \(p\); output such an \(x\) if one exists.
Let \(C=\{a,b,p\}\), with \(m=3\), and let \(B\) be the \(15\) strict ordered lists of distinct candidates of lengths \(1,2,3\); empty ballots are forbidden.
Under modified Borda, a ballot of length \(k<3\) gives its candidate in position \(i\) score \(k-i+1\) and unlisted candidates score \(0\); complete ballots use ordinary Borda. Write \(s_\beta(c)\) for this score.
A society is given by its support: the list of the \(\tau\) ballot types with positive mass, each mass a binary rational. Here \(\tau\) is the support size, not the number of possible types; omitted types have mass \(0\).
The input is a fixed society \(\nu\) and a binary rational manipulator mass \(\alpha\in[0,1]\), with \(\sum_{\beta\in B}\nu_\beta+\alpha=1\). Manipulator mass may be split freely among all ballots in \(B\).
Decide whether rational masses \(x_\beta\geq0\), with \(\sum_{\beta\in B}x_\beta=\alpha\), make \(p\) win, and produce such masses when they exist. Scores are \(S(c)=\sum_{\beta\in B}(\nu_\beta+x_\beta)s_\beta(c)\); ties favor \(p\), so winning means \(S(p)\geq S(a),S(b)\).
State running times in \(m=3\), \(\tau\leq15\), and the total input bit length \(L\).
Is this continuous manipulation problem solvable in polynomial time, or is its feasibility decision problem NP-hard?
Discrete coalition manipulation with indivisible integer voter weights and these ballot options is NP-hard even with three candidates and ties favoring the target ([source](https://arxiv.org/pdf/1405.7714)).
Divisible manipulation with complete ballots is polynomial-time solvable for positional scoring rules ([source](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf)); this result does not cover the ballot-length-dependent rule above. No published result settling this exact mass problem was located.
The problem is polynomial-time solvable, both for deciding feasibility and for producing rational manipulating masses. In fact, whenever manipulation is feasible, two complete ballot types suffice.
For each candidate \(c\), define the fixed-society score
\(F(c)=\sum_{\beta\in B}\nu_\beta s_\beta(c)\).
Define the signed deficits
\(d_a=F(a)-F(p)\) and \(d_b=F(b)-F(p)\).
These deficits may be negative.
Exact criterion. A successful manipulation exists if and only if
\[ d_a\leq 2\alpha,\qquad d_b\leq 2\alpha,\qquad d_a+d_b\leq 3\alpha. \]
When these inequalities hold, set
\(t=\max\{0,d_b-\alpha\}\).
A successful assignment is
\[ x_{(p,a,b)}=t,\qquad x_{(p,b,a)}=\alpha-t, \]
with every other manipulating mass equal to zero.
For a ballot \(\beta\), define its contribution to the two winning margins by
\(g_a(\beta)=s_\beta(p)-s_\beta(a)\) and
\(g_b(\beta)=s_\beta(p)-s_\beta(b)\).
Every candidate’s ballot score lies between \(0\) and \(2\). Consequently,
\(g_a(\beta)\leq 2\) and \(g_b(\beta)\leq 2\).
We also have \(g_a(\beta)+g_b(\beta)\leq 3\). To verify this for every permitted length, write
\(T_\beta=s_\beta(a)+s_\beta(b)+s_\beta(p)\). Then
\(g_a(\beta)+g_b(\beta)=3s_\beta(p)-T_\beta\).
For any manipulating assignment of total mass \(\alpha\), let
\(G_a=\sum_\beta x_\beta g_a(\beta)\) and
\(G_b=\sum_\beta x_\beta g_b(\beta)\).
Multiplying the ballot inequalities by the nonnegative masses and summing gives
\[ G_a\leq 2\alpha,\qquad G_b\leq 2\alpha,\qquad G_a+G_b\leq 3\alpha. \]
The final margins are \(S(p)-S(a)=G_a-d_a\) and
\(S(p)-S(b)=G_b-d_b\).
Thus winning requires \(G_a\geq d_a\) and \(G_b\geq d_b\), which imply all three claimed necessary inequalities.
Assume the three inequalities hold, and choose
\(t=\max\{0,d_b-\alpha\}\).
First, \(t\geq 0\). Since \(d_b\leq 2\alpha\), we have
\(d_b-\alpha\leq\alpha\); together with \(\alpha\geq 0\), this proves \(t\leq\alpha\).
The proposed masses are therefore nonnegative and sum to exactly \(\alpha\).
The ballot \((p,a,b)\) contributes margins \((1,2)\), while
\((p,b,a)\) contributes margins \((2,1)\). Hence the constructed manipulation gives
\[ G_a=t+2(\alpha-t)=2\alpha-t,\qquad G_b=2t+(\alpha-t)=\alpha+t. \]
By the definition of \(t\), \(\alpha+t\geq d_b\), so \(G_b\geq d_b\).
To check \(G_a\geq d_a\), consider both possible values of \(t\).
\(G_a=3\alpha-d_b\geq d_a\), using \(d_a+d_b\leq3\alpha\).
Both final winning margins are nonnegative. Since ties favor \(p\), this proves sufficiency. All constructed masses are rational because the inputs are rational.
The case \(\alpha=0\) is included: the criterion reduces to
\(d_a\leq0\) and \(d_b\leq0\), and the construction assigns zero mass everywhere.
The algorithm computes the fixed scores from the \(\tau\) listed support types, tests the three inequalities, and either reports infeasibility or returns the explicit masses above. Omitted fixed ballot types require no processing.
For \(m=3\), score aggregation and construction use
\(O(m\tau+1)=O(\tau+1)\) exact arithmetic operations. This counts arithmetic operations, not unit-cost operations on arbitrarily long integers.
For an explicit bit bound, write the input masses as numerator–denominator pairs in binary. Let \(D\) be the product of all their denominators, including the denominator of \(\alpha\). Its bit length is \(O(L)\), because the sum of the input denominator lengths is at most \(L\). Convert every mass to denominator \(D\) using exact integer division.
All subsequent score sums, deficits, comparisons, and output masses can be computed with this same denominator. Since the total mass is \(1\) and ballot scores are at most \(2\), every intermediate integer has \(O(L)\) bits. Using elementary quadratic-time integer arithmetic gives a bit-operation bound of
\(O((\tau+1)L^2)\).
Therefore, with \(m=3\) and \(\tau\leq15\), both decision and construction take \(O(L^2)\) bit operations. The output has \(O(L)\) total bit length, even if all \(15\) masses are written explicitly.
The cited discrete hardness theorem requires each manipulating voter’s integer weight to remain indivisible. Its partition reduction forces equal total weight on two ballot types. Divisible mass can always be split equally, so that obstruction disappears. See [Proposition 4 of the cited paper](https://arxiv.org/pdf/1405.7714).
The proof above establishes the exact mass result directly; it does not require extending the [complete-ballot divisible-manipulation theorem](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf) to a ballot-length-dependent scoring rule.
Thus feasibility belongs to \(\mathrm{P}\). It could be NP-hard under polynomial-time many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The prover establishes an exact feasibility criterion, gives a valid rational witness whenever it holds, and justifies polynomial running time in the stated input representation. No major or minor mathematical issues were found.
The proof uses the rule in USER_TASK correctly. Length-one ballots have scores \(1,0,0\); length-two and complete ballots have scores \(2,1,0\). Thus every ballot score lies in \([0,2]\).
The fixed scores \(F(c)\) and signed deficits \(d_a=F(a)-F(p)\), \(d_b=F(b)-F(p)\) are well-defined rational numbers. The proof explicitly permits negative deficits and never assumes that either rival initially leads \(p\).
For every allowed ballot, \(g_a=s_\beta(p)-s_\beta(a)\leq2\) and \(g_b=s_\beta(p)-s_\beta(b)\leq2\). Multiplication by nonnegative manipulating masses preserves these inequalities. Summing and using \(\sum_\beta x_\beta=\alpha\) correctly gives \(G_a\leq2\alpha\) and \(G_b\leq2\alpha\).
The final margins are exactly \(G_a-d_a\) and \(G_b-d_b\). Therefore winning requires \(d_a\leq2\alpha\) and \(d_b\leq2\alpha\).
The identity \(g_a+g_b=3s_\beta(p)-T_\beta\) follows directly from the definitions.
The ballot-length check is exhaustive: for length one, \(T_\beta=1\) and \(s_\beta(p)\leq1\), giving an upper bound of \(2\); for lengths two and three, \(T_\beta=3\) and \(s_\beta(p)\leq2\), giving an upper bound of \(3\).
Consequently, \(G_a+G_b\leq3\alpha\). Together with the two winning requirements, this implies \(d_a+d_b\leq3\alpha\). These arguments apply to all fifteen permitted ballot types, including ballots that omit \(p\).
Assuming the three inequalities, the choice \(t=\max\{0,d_b-\alpha\}\) satisfies \(t\geq0\). Since \(d_b\leq2\alpha\), both arguments of the maximum are at most \(\alpha\), using \(\alpha\geq0\). Hence \(t\leq\alpha\).
The assignments \(x_{(p,a,b)}=t\) and \(x_{(p,b,a)}=\alpha-t\) are therefore nonnegative and sum to precisely \(\alpha\). Both ballot types are permitted complete ballots. Rationality follows from rational subtraction and selection of one of two rational values.
The stated ballot margins are correct: \((p,a,b)\) gives \((1,2)\), while \((p,b,a)\) gives \((2,1)\). Their weighted sums are consequently \(G_a=2\alpha-t\) and \(G_b=\alpha+t\).
The definition of \(t\) gives \(G_b\geq d_b\). The two cases for the other margin are exhaustive and correctly calculated:
Thus both final margins are nonnegative. This is exactly the winning condition because ties favor \(p\). No restriction on the signs of the deficits is needed.
The proof correctly handles \(\alpha=0\): the first two inequalities require both deficits to be nonpositive, the third is redundant, and the construction assigns zero manipulating mass.
The arguments also cover \(\alpha=1\), equality in any feasibility bound, and empty fixed support. Processing only the listed fixed types is correct because omitted types contribute zero. “Two complete ballot types suffice” correctly means at most two positive manipulating masses; either constructed mass may vanish.
With \(m=3\), aggregation requires \(O(\tau+1)\) exact arithmetic operations, followed by a constant number of comparisons and construction operations.
The common-denominator argument is valid. The product \(D\) of the input denominators has \(O(L)\) bits because their total encoding length is bounded by \(L\). Every conversion uses an exact division because each denominator divides \(D\).
Nonnegative input masses totaling one keep score numerators and partial score sums bounded by a constant multiple of \(D\). Deficits and the subsequent constant-size arithmetic expressions likewise have \(O(L)\) bits. Products used to form \(D\) and convert masses also retain \(O(L)\) bit length.
Elementary integer arithmetic therefore supports the stated bound \(O((\tau+1)L^2)\). Since \(\tau\leq15\), this becomes \(O(L^2)\). At most fifteen numerator–denominator pairs, each of \(O(L)\) bits, give the claimed \(O(L)\) total output length. Reduction to lowest terms is unnecessary for a valid rational witness.
The contextual description of the discrete reduction agrees with [Proposition 4 of the cited paper](https://arxiv.org/pdf/1405.7714): its successful manipulation forces equal total integer weight on the two relevant ballot score patterns. Freely divisible masses remove that partition obstruction.
The continuous proof is self-contained and does not apply the complete-ballot theorem to the modified rule. Its explicit algorithm establishes membership in \(\mathrm{P}\). The qualification concerning NP-hardness under polynomial-time many-one reductions is correct.
Required clarification or repair: 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.