Answer: Polynomial-time solvable: \(\mathrm P\). For \(m=3\), the decision takes \(O(\tau L^2)\) bit operations; the corresponding unrestricted divisible-mass problem for variable \(m\) takes \(\operatorname{poly}(m,\tau,L)\) time.
Proposition 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet P be a sensitive scoring protocol. Then CWM in P is NP-hard, even with 3 candidates. Definition 11. In the Partition problem, we are given a set of integers {ki}i∈[t], summing to 2K, and are asked whether a subset of these integers sum to K. It is well-known that Partition is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(3\) candidates \(C=\{p,a,b\}\), a sensitive scoring vector, rational nonmanipulator types with masses \(\nu_r\), weights \(w_r\), and fixed rankings \(\rho_r\), and rational manipulator types with masses \(\mu_t\) and weights \(u_t\), does there exist \(x_{t,\pi}\ge 0\) for rankings \(\pi\in\mathcal{L}(C)\) such that \(\sum_{\pi}x_{t,\pi}=\mu_t\) for every \(t\), and \(p\) wins under adversarial tie-breaking when \(S_x(c)=\sum_r\nu_rw_rs(\rho_r,c)+\sum_{t,\pi}x_{t,\pi}u_ts(\pi,c)\)?
Let \(C=\{p,a,b\}\) and \(m=|C|=3\). The input scoring vector is \(\alpha=(\alpha_1,\alpha_2,0)\), with binary-encoded integers \(\alpha_1\ge\alpha_2>0\); this is called sensitive.
A society is given by its support: a list of \(\tau\) types with positive binary-rational masses. Here \(\tau\) counts the listed types, including their manipulator/nonmanipulator labels, not the number of possible rankings.
Nonmanipulator type \(r\) has mass \(\nu_r\), rational weight \(w_r\in[0,1]\), and fixed strict ranking \(\rho_r\); manipulator type \(t\) has mass \(\mu_t\) and rational weight \(u_t\in[0,1]\). Require \(\sum_r\nu_r+\sum_t\mu_t=1\).
Manipulator mass is divisible: choose real \(x_{t,\pi}\ge0\) for every strict ranking \(\pi\in\mathcal L(C)\), with \(\sum_{\pi\in\mathcal L(C)}x_{t,\pi}=\mu_t\). All rankings are permitted, and nonmanipulator ballots remain fixed.
Write \(s(\pi,c)=\alpha_{\operatorname{pos}_{\pi}(c)}\) and \(S_x(c)=\sum_r\nu_rw_rs(\rho_r,c)+\sum_{t,\pi}x_{t,\pi}u_ts(\pi,c)\). Adversarial tie-breaking means success requires \(S_x(p)>S_x(a)\) and \(S_x(p)>S_x(b)\).
Is deciding whether such a successful mass allocation exists in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and the total input bit length \(L\).
Discrete weighted coalitional manipulation is NP-hard with three candidates for every fixed sensitive scoring vector (Procaccia–Rosenschein, 2007).
[Durand (2025)](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p658.pdf) studies continuous profiles with coalitions constrained by voters’ preferences, a different manipulation problem; no result settling the exact decision problem above was located.
The decision problem is in \(\mathrm P\). For \(\mathit m=3\), success is characterized by three strict rational inequalities. They can be checked in \(O(\tau)\) arithmetic operations, or \(O(\tau L^2)\) bit operations using elementary integer arithmetic.
The corresponding unrestricted divisible-mass problem also admits a polynomial-size linear program for variable \(m\), giving running time \(\operatorname{poly}(m,\tau,L)\).
Write \(A=\alpha_1\), \(B=\alpha_2\), and define the fixed nonmanipulator scores by
\( F_c=\sum_r \nu_r w_r s(\rho_r,c),\qquad c\in\{p,a,b\}. \)
Define the total effective manipulator mass by
\( W=\sum_t\mu_tu_t. \)
For any allocation, let \(y_\pi=\sum_tu_tx_{t,\pi}\). Then \(y_\pi\ge0\), \(\sum_\pi y_\pi=W\), and the manipulators contribute \(\sum_\pi y_\pi s(\pi,c)\) to candidate \(c\).
Conversely, if \(W>0\), every nonnegative vector satisfying \(\sum_\pi y_\pi=W\) is realizable: set
\( x_{t,\pi}=\mu_t\frac{y_\pi}{W}. \)
Indeed, its row sums are \(\mu_t\), and
\( \sum_tu_tx_{t,\pi} =\frac{y_\pi}{W}\sum_tu_t\mu_t =y_\pi. \)
If \(W=0\), all manipulators have zero score contribution, regardless of their allocations.
Thus the manipulator types influence feasibility only through \(W\). This argument uses the stated permission to split every type among all rankings.
Given a manipulator ballot, move \(p\) to first place while preserving the relative order of the other candidates.
Because \(A\ge B>0\), this operation weakly increases \(p\)'s score. Every candidate passed by \(p\) moves down one position, so its score weakly decreases; other candidates’ scores remain unchanged. Multiplication by the nonnegative weight \(u_t\) preserves these inequalities.
Apply this operation to every allocated portion of every manipulator type. Each margin \(S_x(p)-S_x(c)\) weakly increases. Therefore, any successful allocation yields a successful allocation supported on the two rankings
\( p\succ a\succ b,\qquad p\succ b\succ a. \)
Let \(y\in[0,W]\) be the effective mass assigned to the first ranking. The resulting scores are
\( S(p)=F_p+AW,\qquad S(a)=F_a+By,\qquad S(b)=F_b+B(W-y). \)
For \(W>0\), every such \(y\) is realizable by assigning each type the same fraction \(y/W\) to the first ranking.
Theorem. A successful allocation exists if and only if all three inequalities hold:
\( F_p+AW>F_a, \)
\( F_p+AW>F_b, \)
\( 2F_p+(2A-B)W>F_a+F_b. \)
Proof. Put
\( D_a=F_p+AW-F_a,\qquad D_b=F_p+AW-F_b,\qquad H=BW. \)
Writing \(z=By\), success is equivalent to finding \(z\in[0,H]\) such that
\( z<D_a,\qquad H-z<D_b. \)
If such a \(z\) exists, then
\( D_a>z\ge0,\qquad D_b>H-z\ge0, \)
and adding the strict inequalities gives \(D_a+D_b>H\). These are precisely the theorem’s three inequalities.
Conversely, assume \(D_a>0\), \(D_b>0\), and \(D_a+D_b>H\).
If \(H=0\), choose \(z=0\). Both required inequalities hold.
If \(H>0\), define
\( \ell=\max\{0,H-D_b\},\qquad r=\min\{H,D_a\}. \)
Both quantities defining \(\ell\) are strictly below both quantities defining \(r\):
Consequently, \(\ell<r\). Choose \(z=(\ell+r)/2\). Then \(z\in[0,H]\), \(z<D_a\), and \(z>H-D_b\), as required.
Since \(B>0\), the case \(H>0\) also has \(W>0\). A concrete successful allocation is
\( x_{t,p\succ a\succ b}=\mu_t\frac{z}{H},\qquad x_{t,p\succ b\succ a}=\mu_t\left(1-\frac{z}{H}\right), \)
with all other entries zero. Its effective mass on the first ranking is \(Wz/H=z/B\), so it produces the scores used above.
This proves necessity, sufficiency, and an explicit rational construction. In particular, equality in any of the three tests means failure under adversarial tie-breaking. \(\square\)
For three candidates, computing \(F_p,F_a,F_b,W\) takes \(O(\tau)\) arithmetic operations. The final three comparisons take constant additional arithmetic work. The algorithm processes the actual listed support; it assumes no bound on \(\tau\) from the number of possible rankings.
Here is an explicit bit-complexity bound. Let \(D\) be the product of all denominators appearing in the input masses and weights. Its bit length is \(O(L)\). Each denominator of a product \(\nu_rw_r\) or \(\mu_tu_t\) divides \(D\), so all aggregation can use this common denominator.
Moreover, normalization and weights in \([0,1]\) imply
\( 0\le W\le1,\qquad 0\le F_c\le A. \)
Thus the scaled numerators and the final comparison expressions have \(O(L)\) bits. Computing \(D\), converting the terms, and aggregating them requires \(O(\tau)\) integer operations on \(O(L)\)-bit integers. Elementary multiplication and division therefore give a bound of \(O(\tau L^2)\) bit operations.
No numerical tolerance or guessed positive margin is needed: all three comparisons are exact.
For completeness, consider the corresponding problem with \(m\) candidates and an explicitly supplied nonnegative positional scoring vector. Aggregation to \(W\) still applies.
Introduce \(q_{c,j}\ge0\), representing effective manipulator mass placing candidate \(c\) in position \(j\). Require
\( \sum_jq_{c,j}=W\quad\text{for every candidate }c, \qquad \sum_cq_{c,j}=W\quad\text{for every position }j. \)
These constraints exactly characterize realizable position marginals. To justify this, suppose \(W>0\) and set \(M=q/W\). Then \(M\) is nonnegative with every row and column sum equal to one.
Here is the required permutation decomposition. In the bipartite graph of positive entries of \(M\), any set \(R\) of rows has neighboring columns \(N(R)\) satisfying
\( |R| =\sum_{c\in R}\sum_{j\in N(R)}M_{c,j} \le\sum_{j\in N(R)}\sum_cM_{c,j} =|N(R)|. \)
Hall’s marriage theorem therefore supplies a perfect matching, hence a permutation matrix \(P\) supported on positive entries. Let \(\varepsilon\) be the smallest matched entry. If \(\varepsilon=1\), row sums force \(M=P\). Otherwise,
\( M'=\frac{M-\varepsilon P}{1-\varepsilon} \)
is again nonnegative with unit row and column sums, and has fewer positive entries. Repetition terminates and expresses \(M\) as a convex combination of permutation matrices. Each permutation describes a strict ranking. Assigning these combination probabilities to every manipulator type realizes \(q\).
If \(W=0\), the row sums force \(q=0\), which is also realizable.
Now maximize \(\delta\) subject to these marginal constraints and
\( F_p+\sum_j\alpha_jq_{p,j} \ge F_c+\sum_j\alpha_jq_{c,j}+\delta \quad\text{for every }c\ne p, \)
together with \(-\alpha_1\le\delta\le\alpha_1\).
Every total score lies in \([0,\alpha_1]\), so the lower bound permits a feasible \(\delta\) for any realizable marginal matrix. The feasible region is nonempty and compact. Its optimum is positive exactly when a successful allocation exists.
This rational linear program has \(m^2+1\) variables and \(O(m^2)\) constraints. Its coefficients have \(O(L)\) bits. The standard polynomial-time theorem for rational linear programming applies: it computes the optimum exactly in time polynomial in the encoded program size, allowing an exact positivity test.
Computing the fixed scores takes \(O(m\tau)\) arithmetic operations, or \(O(m\tau L^2)\) elementary bit operations. Including the linear program, the total running time is
\( O(m\tau L^2)+\operatorname{poly}(m,L) =\operatorname{poly}(m,\tau,L). \)
With indivisible weighted manipulators, the effective mass assigned to one ranking must be a subset sum of their weights. Here it can be every value in \([0,W]\), as the explicit proportional allocation proves. That changes the feasibility question underlying discrete hardness.
The proof above settles the stated model directly. Durand’s preference-dependent coalition definition concerns a different feasible set. See [Durand (2025), Section 2.3](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p658.pdf).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The prover resolves the stated decision problem: it is in \(\mathrm P\), with \(\mathit m=3\), using \(O(\tau)\) arithmetic operations and \(O(\tau L^2)\) elementary bit operations. The feasibility criterion correctly handles strict victory and degenerate cases. No major or minor issues were found.
The variable-\(m\) extension is also valid under the conventional meaning of a positional scoring vector: \(\alpha_1\ge\cdots\ge\alpha_m\ge0\). This convention is relevant to its score bounds.
Correct. For every admissible allocation, the quantities \(y_\pi=\sum_tu_tx_{t,\pi}\) are nonnegative and sum to \(W\). They determine all manipulator score contributions.
The converse construction is valid when \(W>0\):
Types with zero weight cause no difficulty: their mass constraints are still satisfied, and their score contributions vanish.
When \(W=0\), nonnegativity of every \(\mu_tu_t\) ensures that every manipulator contribution is zero. The argument therefore covers both zero-weight manipulators and an empty manipulator list. It does not assume that the number of listed types is bounded by the number of rankings.
Correct. Moving \(p\) upward weakly increases its score because \(A\ge B>0\). Every candidate passed by \(p\) moves downward and weakly loses score. Nonnegative weights preserve these comparisons.
Applying this transformation to allocated portions preserves each type’s total mass. Every relevant score margin weakly increases, so strict success remains strict success.
Consequently, restricting to the two displayed rankings loses no successful allocation. The resulting score formulas are correct:
\[ S(p)=F_p+AW,\qquad S(a)=F_a+By,\qquad S(b)=F_b+B(W-y). \]
The boundary case \(A=B\) is covered: weak improvement is sufficient.
Correct in both directions.
With \(z=By\) and \(H=BW\), the required conditions are precisely
\[ z\in[0,H],\qquad z<D_a,\qquad H-z<D_b. \]
Necessity. These inequalities imply \(D_a>0\), \(D_b>0\), and \(D_a+D_b>H\). Expanding the last inequality gives exactly the third stated test:
\[ 2F_p+(2A-B)W>F_a+F_b. \]
Sufficiency when \(H=0\). Choosing \(z=0\) satisfies both strict inequalities because \(D_a,D_b>0\). Since \(B>0\), this case is exactly \(W=0\).
Sufficiency when \(H>0\). The four comparisons given in the proof establish that every quantity defining \(\ell\) is strictly below every quantity defining \(r\). Thus \(\ell<r\). Their midpoint lies in \([0,H]\), strictly below \(D_a\), and strictly above \(H-D_b\), as required.
Allocation witness. The displayed allocation is nonnegative, has the correct row sums, and places effective mass \(Wz/H=z/B\) on the first ranking. All quantities in the construction are rational.
Tie-breaking. Equality in any test indeed prevents success, because necessity requires all three inequalities to be strict.
Correct.
For three candidates, each listed type contributes to only a constant number of aggregates. Thus computing the fixed scores and \(W\) requires \(O(\tau)\) arithmetic operations.
The common-denominator argument is sound. The product \(D\) includes denominators with their occurrences, so even repeated denominators create no divisibility problem. Its bit length is \(O(L)\), and each denominator of a mass–weight product divides it.
Normalization and the weight restrictions justify
\[ 0\le W\le1,\qquad 0\le F_c\le A. \]
Together with the binary encoding of \(A\), these bounds ensure \(O(L)\)-bit scaled numerators and comparison expressions. Intermediate products also have \(O(L)\) bits. Elementary multiplication and division therefore support the claimed \(O(\tau L^2)\) bound.
The decision uses exact rational comparisons; no approximation issue arises.
Correct under the conventional scoring-vector ordering stated above.
Marginal realizability. When \(W>0\), the normalized marginal matrix has unit row and column sums. The displayed calculation verifies Hall’s condition for every row subset. The graph has equally many row and column vertices, so Hall’s marriage theorem supplies the required perfect matching.
Subtracting the smallest matched entry and renormalizing preserves nonnegativity and unit row and column sums. At least one positive entry disappears, and no new positive entry appears. Thus the decomposition terminates. The resulting convex combination of permutation matrices gives realizable ranking probabilities. The case \(W=0\) is handled separately and correctly.
Strict victory through optimization. Under normalization, nonnegative weights, and \(\alpha_j\le\alpha_1\), every total score belongs to \([0,\alpha_1]\). Therefore the lower bound on \(\delta\) does not eliminate all feasible solutions. The marginal constraints and bounds on \(\delta\) give a nonempty compact feasible region.
For finitely many opponents, strict victory is equivalent to a positive minimum score margin. Hence the optimum is positive exactly when manipulation succeeds.
Polynomial-time theorem. The invoked rational linear-programming theorem applies: the program has rational coefficients, polynomial encoded size, and a finite attained optimum. Exact optimization and an exact positivity test are available in polynomial time.
The counts of \(m^2+1\) variables and \(O(m^2)\) constraints are correct, including nonnegativity constraints. The claimed total running time \(\operatorname{poly}(m,\tau,L)\) follows.
Correct. The proportional allocation establishes that the effective mass assigned to either ranking can vary continuously throughout \([0,W]\). This removes the indivisibility restriction responsible for the subset-sum feasibility constraint in the discrete setting. The prover does not incorrectly transfer discrete hardness.
The characterization of Durand’s different manipulation model is supported by its preference-dependent restriction on which voters may change ballots. [Durand (2025), Section 2.3](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p658.pdf).
No repair is required for the stated three-candidate problem. For maximum clarity, the optional variable-\(m\) extension could explicitly repeat the conventional ordering \(\alpha_1\ge\cdots\ge\alpha_m\ge0\).
⟨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.