Answer: The continuous decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). The minimum coalition mass is also exactly computable in polynomial time.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateUnweighted coalition manipulation for the Borda rule is NP-complete with two manipulators.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a designated candidate \(d\), and a rational baseline distribution \(\nu\) over complete ranking types \(T\), decide whether a controllable coalition of mass \(\rho\) can choose \(x_t\ge 0\), with \(\sum_{t\in T}x_t=\rho\), so that \(d\) wins under Borda in the normalized society \((\nu+x)/(1+\rho)\); the optimization version minimizes \(\rho\).
Let \(C\) contain \(m\geq 2\) candidates, let \(d\in C\), and let \(T\) be all complete strict rankings of \(C\).
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 \(m!\).
The baseline distribution \(\nu\) has total mass \(1\); the input also includes a binary rational \(\rho\geq 0\). Let \(L\) be the total input bit length.
The coalition may choose real masses \(x_t\geq 0\) for every \(t\in T\), including rankings outside the baseline support, with \(\sum_{t\in T}x_t=\rho\).
Decide whether \(d\) wins under Borda in \((\nu+x)/(1+\rho)\), with scores aggregated by mass and ties resolved in favor of \(d\). The optimization version minimizes \(\rho\).
Is this continuous decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
Discrete unweighted Borda coalitional manipulation is \(\mathrm{NP}\)-complete even with two manipulators.
The continuous question is already settled: [Xia, Conitzer, and Procaccia](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf) give polynomial-time exact algorithms for divisible weighted coalitional manipulation and minimum manipulating weight under positional scoring rules, covering this decision problem and its optimization version.
The continuous decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). The minimum coalition mass is also exactly computable in polynomial time.
This agrees with Theorem 3.4 of [Xia, Conitzer, and Procaccia, *A Scheduling Approach to Coalitional Manipulation*](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf), which gives exact polynomial-time algorithms for divisible weighted manipulation and minimum manipulating weight under positional scoring rules. Below is a direct linear-programming proof for the stated input model.
For a ranking \(t\), let \(\operatorname{pos}_t(c)\) be candidate \(c\)'s position, numbered from \(1\). Define its baseline Borda score by
\[ b_c=\sum_{t\in\operatorname{supp}(\nu)}\nu_t\bigl(m-\operatorname{pos}_t(c)\bigr). \]
Because normalization divides every score by the same positive number \(1+\rho\), it does not affect the winner. We therefore work with the unnormalized masses \(\nu+x\).
Lemma 1. If a successful coalition of mass \(\rho\) exists, one exists in which every coalition ranking puts \(d\) first.
Proof. Move \(d\) to first place in each coalition ranking, preserving the relative order of all other candidates. If \(d\) originally occupied position \(k\), its Borda score increases by \(k-1\). Each candidate formerly above \(d\) loses one point, and every other candidate's score is unchanged. Thus the score difference between \(d\) and any rival never decreases.
Applying this operation to every coalition ranking and combining masses assigned to identical resulting rankings preserves total mass and preserves \(d\)'s victory. \(\square\)
Henceforth all coalition rankings put \(d\) first. Its coalition score is then exactly \((m-1)\rho\).
Let \(R=C\setminus\{d\}\), so \(|R|=m-1\). For \(c\in R\) and \(j\in\{2,\ldots,m\}\), introduce a variable \(y_{c,j}\), interpreted as the coalition mass placing \(c\) in position \(j\).
Consider the following feasibility system:
\[ y_{c,j}\geq 0 \qquad(c\in R,\;2\leq j\leq m), \]
\[ \sum_{j=2}^{m}y_{c,j}=\rho \qquad(c\in R), \]
\[ \sum_{c\in R}y_{c,j}=\rho \qquad(2\leq j\leq m), \]
\[ b_c+\sum_{j=2}^{m}(m-j)y_{c,j} \leq b_d+(m-1)\rho \qquad(c\in R). \]
The row equations express that every rival appears once in every ranking. The column equations express that every position below \(d\) contains exactly one rival. The final inequalities express that \(d\)'s score is at least every rival's score, which suffices because ties favor \(d\).
The system has \((m-1)^2\) variables. The remaining issue is whether these marginal constraints describe actual mixtures of complete rankings.
We prove the required matrix-decomposition fact, including for real entries.
Lemma 2. Let \(Y\) be a nonnegative square matrix of order \(n\), with every row sum and column sum equal to a real number \(a\geq 0\). Then
\[ Y=\sum_{\ell=1}^{q}\lambda_\ell P_\ell, \qquad \lambda_\ell>0, \qquad \sum_{\ell=1}^{q}\lambda_\ell=a, \]
where each \(P_\ell\) is a permutation matrix and \(q\leq n^2\). When \(a=0\), the sum is empty.
Proof. If \(a=0\), nonnegativity forces \(Y=0\).
Suppose \(a>0\). Form a bipartite graph whose left vertices are rows, whose right vertices are columns, and whose edges correspond to positive matrix entries. For a subset \(A\) of rows, let \(N(A)\) be its neighboring columns. Then
\[ a|A| =\sum_{i\in A}\sum_jY_{i,j} =\sum_{i\in A}\sum_{j\in N(A)}Y_{i,j} \leq\sum_i\sum_{j\in N(A)}Y_{i,j} =a|N(A)|. \]
Dividing by \(a>0\) gives \(|N(A)|\geq|A|\).
Hall's marriage theorem states that a finite bipartite graph has a matching covering its left side if every subset of left vertices has at least as many neighbors. Its hypothesis has just been verified. Since both sides have \(n\) vertices, this matching is perfect and defines a permutation matrix \(P\) supported on positive entries.
Let \(\delta\) be the minimum entry of \(Y\) on this matching. Then \(\delta>0\), and \(Y-\delta P\) is nonnegative with every row and column sum equal to \(a-\delta\). At least one positive entry becomes zero, and no zero entry becomes positive.
Repeat while the residual common row sum is positive. Each iteration eliminates at least one positive entry, so there are at most \(n^2\) iterations. The final residual is zero: otherwise its positive common row sum would permit another iteration. The subtracted coefficients sum to \(a\), as follows by comparing any row sum. \(\square\)
Proposition. The linear system in Section 2 is feasible if and only if a successful coalition of mass \(\rho\) exists.
Proof.
If a successful coalition exists, Lemma 1 lets us assume that all its rankings put \(d\) first. Define \(y_{c,j}\) by summing the masses of rankings placing \(c\) at position \(j\). Every ranking contains each rival and fills each remaining position exactly once, so the row and column equations hold. The score inequalities follow from \(d\)'s victory.
Conversely, suppose the system is feasible. Apply Lemma 2 to its matrix \(Y=(y_{c,j})\), taking \(n=m-1\) and \(a=\rho\). Each permutation matrix assigns the rivals bijectively to positions \(2,\ldots,m\); prepend \(d\) to obtain a complete strict ranking. Assign this ranking the corresponding coefficient \(\lambda_\ell\).
The resulting coalition has total mass \(\rho\) and position masses exactly \(Y\). Its scores therefore satisfy the linear system's victory inequalities.
If \(\rho=0\), the matrix is zero, and the system simply tests whether \(d\) already has maximum baseline score. \(\square\)
These constructed rankings may lie outside the baseline support, exactly as permitted in the question.
We use the standard rational linear-programming theorem: feasibility of a finite linear system with rational coefficients can be decided in time polynomial in its binary encoding length; when feasible, a rational feasible solution can be produced.
Here its hypotheses and encoding requirements hold:
Thus the system has encoding length polynomial in \(m,\tau,L\). By the proposition, exact rational linear programming decides the original problem in polynomial time.
Although real coalition masses are allowed, they cause no additional difficulty: every feasible instance admits a rational feasible matrix, and Lemma 2 converts that matrix into rational ranking masses.
Replace the fixed parameter \(\rho\) in the system by a variable \(r\geq0\), and minimize \(r\). All constraints remain linear.
To verify feasibility and attainment, observe that mass \(r=m-1\) placed on any single ranking with \(d\) first succeeds. Indeed, for every rival \(c\),
\[ b_d-b_c\geq-(m-1), \]
while each unit of that coalition mass gives \(d\) at least one more Borda point than \(c\). Hence its final score difference is at least
\[ -(m-1)+(m-1)=0. \]
We may therefore add the bound \(0\leq r\leq m-1\) without changing the optimum. Every matrix entry then satisfies \(0\leq y_{c,j}\leq m-1\), by nonnegativity and its row equation. The feasible region is nonempty, closed, and bounded, so the continuous objective attains its minimum.
The exact rational linear-programming theorem also computes the optimum of a feasible rational linear program with bounded objective in polynomial time. Its hypotheses hold here, and the encoding remains polynomial. Thus the minimum mass is an exactly computable rational number. Lemma 2 reconstructs an optimal coalition supported on at most \((m-1)^2\) rankings.
The discrete hardness result concerns indivisible ballots. In the stated continuous problem, arbitrary nonnegative fractional coefficients make the matrix formulation exact.
⟨structured verdict parsed — rendered above⟩
The prover resolves both the decision problem and the optimization version. The argument is correct and rigorous for the stated support encoding, real coalition masses, and ties favoring \(d\). No major or minor mathematical issues were found.
The definition
\[
b_c=\sum_{t\in\operatorname{supp}(\nu)}\nu_t\bigl(m-\operatorname{pos}_t(c)\bigr)
\]
uses the stated Borda convention and only the supplied support. Because \(\rho\geq0\), the normalizing factor \(1+\rho\) is positive. Dividing every candidate’s score by it preserves all score comparisons, including ties. Working with unnormalized masses is therefore valid.
The ranking transformation is correctly described. Moving \(d\) from position \(k\) to first increases its score by \(k-1\); candidates originally above it lose one point each, and all remaining candidates retain their scores. Thus every score difference between \(d\) and a rival weakly increases.
Multiplying these changes by nonnegative ranking masses preserves the comparison after aggregation. Combining identical transformed rankings preserves total coalition mass. Consequently the transformation preserves a successful manipulation, including a victory obtained by a tie. It also applies when \(\rho=0\).
There are exactly \((m-1)^2\) variables. For rankings placing \(d\) first, each rival occupies exactly one remaining position and each remaining position contains exactly one rival. Hence the stated row and column equations are necessary.
A rival’s coalition score is exactly
\[
\sum_{j=2}^{m}(m-j)y_{c,j},
\]
while \(d\)’s coalition score is \((m-1)\rho\). The final inequalities therefore express precisely the required winning condition. Their non-strict direction correctly incorporates ties favoring \(d\).
The write-up correctly recognizes that marginal consistency alone requires a decomposition argument; it does not assume the converse without proof.
The proof is valid for the matrix order used here, namely \(n=m-1\geq1\), and for arbitrary real entries.
When \(a=0\), nonnegativity and zero row sums force every entry to vanish.
When \(a>0\), the displayed calculation proves Hall’s condition for every subset of rows. Its inequality uses nonnegativity, and its final equality uses the column-sum hypothesis. The stated version of Hall’s theorem applies to the finite support graph. Equal numbers of row and column vertices make the resulting matching perfect.
Every matched entry is positive, so their minimum \(\delta\) is positive. Subtracting \(\delta P\) preserves nonnegativity and reduces every row and column sum by exactly \(\delta\). At least one positive entry disappears, and none is introduced.
This establishes termination after at most \(n^2\) iterations even for real entries; no assumption about rationality or a minimum positive step size is needed. A residual with positive common row sum would admit another iteration by the same argument. Thus the final residual is zero, and comparison of any row sum establishes that the coefficients sum to \(a\).
Both directions are established.
A successful coalition can first be transformed using Lemma 1, after which its position marginals satisfy all the constraints.
Conversely, Lemma 2 realizes any feasible matrix as a mixture of bijections between rivals and positions below \(d\). Prepending \(d\) produces legal complete strict rankings. Their total mass and position marginals are exactly those prescribed by the LP, so their scores satisfy the winning inequalities.
The proof explicitly handles \(\rho=0\). It also correctly permits constructed rankings outside the baseline support. The edge case \(m=2\) is covered: the matrix then has order one.
The rational LP theorem is stated sufficiently precisely for the application: feasibility is decidable in time polynomial in the rational system’s binary encoding length, and a rational feasible solution can be produced.
The encoding argument is sound. The product of the supplied mass denominators has bit length at most their total bit length. Expressing baseline scores over this denominator gives numerators of polynomial bit length, using \(0\leq b_c\leq m-1\). Computing the scores requires only polynomially many operations on polynomial-length integers.
The LP has polynomially many entries; its integer coefficients have magnitude at most \(m-1\), and the supplied \(\rho\) has bounded input encoding length. Its complete encoding is therefore polynomial in \(m,\tau,L\).
Allowing real coalition masses does not invalidate rational LP feasibility. A rational feasible matrix exists whenever the rational system is feasible. The decomposition procedure preserves rationality because it uses minima of finitely many rational entries and rational subtraction.
Replacing \(\rho\) by a nonnegative variable \(r\) preserves linearity.
The feasibility bound is correct. Baseline score differences satisfy \(b_d-b_c\geq-(m-1)\). In any ranking placing \(d\) first, its per-unit advantage over every rival is at least one. Therefore mass \(r=m-1\) yields final differences at least zero.
Restricting \(r\) to \(0\leq r\leq m-1\) cannot remove an optimum: this interval contains a feasible point, and any larger value has a worse objective. The row equations and nonnegativity bound every matrix entry by \(m-1\). The resulting feasible region is nonempty, closed, and bounded, so a minimum is attained.
The stated exact rational LP optimization theorem applies. It establishes an exactly computable rational optimum in polynomial time. Lemma 2 also justifies the claimed optimal coalition support bound of \((m-1)^2\).
The attribution is accurate: Theorem 3.4 states polynomial-time exact solvability of divisible weighted coalitional manipulation and divisible coalitional optimization. The paper’s definitions use the co-winner condition, consistent with ties favoring \(d\). [Xia, Conitzer, and Procaccia, definitions 2.2–2.4 and Theorem 3.4](https://www.cs.cmu.edu/~conitzer/schedulingEC10.pdf).
The direct LP proof independently establishes the required binary-input complexity bound. The final distinction from indivisible manipulation is justified by the exact mixture representation proved above.
No additional clarification or repair is needed.
⟨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.