Answer: \(\mathrm P\), with running time polynomial in \(m,\tau,L\).
Theorem 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateConsider an election of the scoring sys- tem (α1, . . . , αk) and candidates c1, . . . , ck with initial scores s1, . . . , sk. Let the set of manipulative voters be V ′ of cardi- nality ||V ′|| = m with weights w1, . . . , wm. There exists a manipulation ensuring the victory of c1 iffthere exists a (k −1)-way permutation partition of the tuples {{s2, . . . , sk}} ∪{{w1α2, . . . , w1αk} , . . . , {wmα2, . . . , wmαk}} with maximum subset sum of at most s1 + α1 X 1≤i≤m wi.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a rational scoring vector \(\alpha\), target \(p\), established masses \(\mu_{\pi,w}\) over ranking–weight types, and strategic masses \(\rho_j\) with per-agent weights \(\beta_j\), define \(B(c)=\sum_{(\pi,w)}\mu_{\pi,w}w\alpha_{\operatorname{pos}_{\pi}(c)}\). Decide whether there are allocations \(x_{j,\sigma}\ge 0\) over complete rankings \(\sigma\), with \(\sum_{\sigma}x_{j,\sigma}=\rho_j\) for every \(j\), such that \(B(p)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_{\sigma}(p)}\ge B(c)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_{\sigma}(c)}\) for every \(c\in C\).
Let \(C\) contain \(m\ge 2\) candidates, with target \(p\in C\), and let the input scoring vector satisfy \(\alpha\in\mathbb Q^m\) and \(\alpha_1\ge\cdots\ge\alpha_m\ge0\). Rankings are complete strict orders; all candidates attaining the maximum score are winners.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types are tagged as established ranking–weight pairs \((\pi,w)\) or strategic weight types \(j\), with masses \(\mu_{\pi,w}\) and \(\rho_j\), respectively; \(w,\beta_j\in\mathbb Z_{\ge0}\). Masses need not sum to one. The support size \(\tau\) counts both lists, not all possible rankings.
Let \(\Sigma(C)\) be the complete strict rankings and define \(B(c)=\sum_{(\pi,w)}\mu_{\pi,w}w\alpha_{\operatorname{pos}_{\pi}(c)}\), where positions start at \(1\).
Strategic mass is divisible: feasibility means there exist real \(x_{j,\sigma}\ge0\) with \(\sum_{\sigma\in\Sigma(C)}x_{j,\sigma}=\rho_j\) for every \(j\), satisfying \(B(p)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_{\sigma}(p)}\ge B(c)+\sum_{j,\sigma}x_{j,\sigma}\beta_j\alpha_{\operatorname{pos}_{\sigma}(c)}\) for every \(c\in C\).
Is this continuous weighted coalitional manipulation problem in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard, where \(L\) is the total binary input length and the scoring vector is part of the input?
Discrete manipulation is equivalent to independently permuting the initial rival-score tuple and each manipulator's weighted score tuple for positions \(2,\ldots,m\), so every column sum is at most the target's score when all manipulators rank it first. [Lin](https://www.ifaamas.org/Proceedings/aamas2011/papers/C4_G60.pdf)
For each fixed integer scoring vector, discrete weighted manipulation is \(\mathrm{NP}\)-complete when \(\alpha_2,\ldots,\alpha_m\) are not all equal, and polynomial-time otherwise. [Hemaspaandra–Hemaspaandra](https://arxiv.org/abs/cs/0504075)
Related work uses fractional manipulation in approximation algorithms for indivisible weighted voters; no exact classification for the support-encoded mass problem above was verified. [Keller–Hassidim–Hazon](https://www.jair.org/index.php/jair/article/view/11538)
The problem is in \(\mathrm P\), with running time polynomial in \(m,\tau,L\), even when the rational scoring vector is part of the input.
We prove this by constructing an exact linear program with \((m-1)^2\) variables. Its feasibility is equivalent to the existence of the required manipulation.
Given a ranking \(\sigma\), let \(T(\sigma)\) move \(p\) to first place while preserving the relative order of all other candidates.
The position of \(p\) improves or remains unchanged. Every rival previously above \(p\) moves down one position, and every other rival retains its position. Because the scoring vector is nonincreasing, \(p\)'s score weakly increases and each rival's score weakly decreases. Multiplication by the nonnegative weight \(\beta_j\) preserves these inequalities.
For any feasible allocation, replace it by
\( x'_{j,\sigma'}=\sum_{\sigma:T(\sigma)=\sigma'}x_{j,\sigma}. \)
This preserves each type's total mass and weakly improves every score difference between \(p\) and a rival. Thus:
A feasible manipulation exists if and only if one exists in which every strategic ranking places \(p\) first.
Define the total strategic mass times weight by
\( W=\sum_j\rho_j\beta_j. \)
When all strategic rankings place \(p\) first, its final score is
\( S_p=B(p)+W\alpha_1. \)
If \(W=0\), all strategic score contributions vanish: every summand \(\rho_j\beta_j\) is nonnegative and their sum is zero. Hence feasibility is exactly the condition \(B(p)\ge B(c)\) for every rival \(c\). We henceforth assume \(W>0\).
We need the following fact, including its converse interpretation as fractional rankings.
Lemma. Let \(D\) be a nonnegative \(n\times n\) real matrix whose row sums and column sums all equal \(1\). Then
\( D=\sum_{\ell=1}^{q}\lambda_\ell P_\ell, \qquad \lambda_\ell>0, \qquad \sum_{\ell=1}^{q}\lambda_\ell=1, \)
where each \(P_\ell\) is a permutation matrix and \(q\le n^2\).
Proof. Start with the residual matrix \(R=D\), whose common row and column sum is \(r=1\). Whenever \(r>0\), form a bipartite graph with rows on one side, columns on the other, and an edge wherever \(R_{ik}>0\).
For any set \(U\) of rows, let \(N(U)\) be its neighboring columns. Nonnegativity and the common column sum give
\( |U|r =\sum_{i\in U}\sum_{k\in N(U)}R_{ik} \le \sum_{k\in N(U)}\sum_iR_{ik} =|N(U)|r. \)
Since \(r>0\), this implies \(|U|\le |N(U)|\). Hall's matching theorem therefore supplies a perfect matching. Let \(P\) be its permutation matrix and set
\( \delta=\min\{R_{ik}:P_{ik}=1\}>0. \)
Replace \(R\) by \(R-\delta P\). The new matrix is nonnegative, all its row and column sums equal \(r-\delta\), and at least one positive entry becomes zero. No zero entry becomes positive.
Consequently, after at most \(n^2\) such steps, the residual must have common sum zero: otherwise the same argument would permit another step that eliminates a positive entry. A nonnegative matrix with row sums zero is the zero matrix. Summing the subtracted matrices yields the asserted decomposition, and the row sums show that the coefficients sum to \(1\). \(\square\)
Let \(R=C\setminus\{p\}\) and \(n=m-1\). For each \(c\in R\) and \(k\in\{1,\ldots,n\}\), introduce a variable \(y_{c,k}\). Its intended meaning is the aggregate strategic mass times weight assigning \(c\) to position \(k+1\).
Consider the following rational linear system:
\( \begin{aligned} y_{c,k}&\ge0 && (c\in R,\ 1\le k\le n),\\ \sum_{k=1}^{n}y_{c,k}&=W && (c\in R),\\ \sum_{c\in R}y_{c,k}&=W && (1\le k\le n),\\ B(c)+\sum_{k=1}^{n}\alpha_{k+1}y_{c,k} &\le B(p)+W\alpha_1 && (c\in R). \end{aligned} \)
We prove both directions of its equivalence to manipulation.
By Section 1, take a feasible manipulation placing \(p\) first. Define
\( y_{c,k} =\sum_j\beta_j \sum_{\sigma:\operatorname{pos}_{\sigma}(c)=k+1} x_{j,\sigma}. \)
These entries are nonnegative. Each rival occupies exactly one of the remaining positions in every ranking, so
\( \sum_k y_{c,k} =\sum_j\beta_j\sum_\sigma x_{j,\sigma} =\sum_j\beta_j\rho_j=W. \)
Similarly, each remaining position contains exactly one rival, giving \(\sum_c y_{c,k}=W\).
The strategic contribution to \(c\)'s score is exactly \(\sum_k\alpha_{k+1}y_{c,k}\). Thus the winning inequalities are precisely the last constraints of the linear system.
Conversely, suppose \(y\) satisfies the system. The matrix \(D=y/W\) has nonnegative entries and all row and column sums equal to \(1\). Apply the lemma to write
\( D=\sum_{\ell=1}^{q}\lambda_\ell P_\ell. \)
For each \(P_\ell\), define a complete strict ranking \(\sigma_\ell\) by placing \(p\) first and placing rival \(c\) at position \(k+1\) whenever \((P_\ell)_{c,k}=1\). A permutation matrix assigns every rival and every remaining position exactly once, so these rankings are valid.
For every strategic type \(j\), set
\( x_{j,\sigma} =\rho_j\sum_{\ell:\sigma_\ell=\sigma}\lambda_\ell. \)
This is an admissible allocation: its entries are nonnegative and sum to \(\rho_j\). Its aggregate mass times weight assigning \(c\) to position \(k+1\) is
\( \begin{aligned} \sum_j\beta_j \sum_{\sigma:\operatorname{pos}_{\sigma}(c)=k+1}x_{j,\sigma} &=\sum_j\beta_j\rho_j \sum_{\ell=1}^{q}\lambda_\ell(P_\ell)_{c,k}\\ &=W D_{c,k}\\ &=y_{c,k}. \end{aligned} \)
Therefore its candidate scores satisfy the linear system's winning inequalities, and \(p\) is a winner.
This construction also handles types of weight zero: they receive their prescribed masses without contributing scores.
The established scores \(B(c)\) require at most \(m\tau\) rational products and additions. Computing \(W\) requires at most \(\tau\) products and additions.
These computations have polynomial bit complexity. Each product combines only a constant number of input numbers. For a sum of at most \(\tau\) such rational products, the product of their denominators is a common denominator with \(O(\tau L)\) bits; the resulting numerators likewise have polynomially many bits. Thus all coefficients and right-hand sides of the linear system can be computed and encoded in polynomial time in \(m,\tau,L\).
The system has \(n^2\) variables, \(2n\) equalities, \(n\) winning inequalities, and \(n^2\) nonnegativity constraints. Its total rational encoding length is polynomial in \(m,\tau,L\).
The polynomial-time rational linear programming theorem decides feasibility of a rational linear system in time polynomial in its binary encoding length. Equalities can be replaced by pairs of weak inequalities; no strict feasibility or full-dimensionality assumption is needed. This is the standard polynomial solvability result originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319).
Applying that theorem to the exact system above proves the claimed running-time bound.
Divisibility permits convex combinations of rival-position permutations. The matrix constraints capture those combinations exactly, and all strategic types can use the same distribution over rankings. Consequently, their individual weights and masses affect feasibility only through \(W\).
The continuous, support-encoded problem is therefore polynomial-time solvable for every scoring vector satisfying the stated hypotheses.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the stated continuous, support-encoded problem. Both directions of the linear-program equivalence are correct, and the polynomial bit-complexity argument is sufficient. No major or minor mathematical issues were found.
The transformation preserves complete strict rankings. The target’s position weakly improves; every rival’s position either stays unchanged or worsens by one. Monotonicity of the scoring vector and nonnegativity of each \(\beta_j\) therefore give the claimed score inequalities.
Aggregating allocations over the preimages of the transformation preserves nonnegativity and each type’s prescribed mass. Thus every target–rival score difference weakly increases. The reverse implication is immediate because allocations placing the target first are allowed by the original problem.
Each \(\rho_j\beta_j\) is nonnegative. Consequently, \(W=0\) implies that every strategic type contributes zero score under every allocation. The condition \(B(p)\ge B(c)\) for every rival is therefore necessary and sufficient.
This also covers an empty strategic support. Prescribed masses for zero-weight types impose no obstruction because complete strict rankings exist.
The graph is finite and has equally many row and column vertices. For every row subset \(U\), the displayed calculation correctly establishes Hall’s condition \(|N(U)|\ge |U|\), using \(r>0\). These are precisely the hypotheses needed for a perfect matching.
The chosen \(\delta\) is positive because every matching edge corresponds to a positive residual entry. Subtraction preserves nonnegativity and reduces every row and column sum by the same amount. It removes at least one positive entry and introduces none.
The termination bound \(q\le n^2\) follows from this strict decrease in the number of positive entries. A residual with common sum zero is indeed the zero matrix. Summing the subtractions recovers \(D\), and comparison of row sums establishes that the coefficients sum to one.
The definition of \(y_{c,k}\) correctly aggregates mass multiplied by strategic weight. Each rival appears exactly once in each ranking, giving row sums \(W\). Each remaining position contains exactly one rival, giving column sums \(W\).
The expression \(\sum_k\alpha_{k+1}y_{c,k}\) is exactly the strategic contribution to rival \(c\). Since the target receives \(W\alpha_1\), the final inequalities match the task’s winning condition, including ties.
Division by \(W\) is justified by the explicit assumption \(W>0\). The resulting matrix satisfies every hypothesis of the proved decomposition lemma.
Each permutation matrix defines a complete strict ranking with the target first. The allocation formula gives nonnegative masses summing to \(\rho_j\) separately for every strategic type.
The displayed calculation correctly recovers \(y_{c,k}\). In particular, using the same ranking distribution for every type satisfies the individual mass constraints despite differing weights. Zero-weight types also receive their required masses. No additional compatibility condition is missing.
Computing all established scores requires polynomially many rational operations over the listed support; no enumeration of unlisted rankings is involved.
Each product involves only a constant number of input numbers. A common denominator formed from at most \(\tau\) such products has polynomial bit length, as do the resulting numerators. The stated \(O(\tau L)\) bound is loose but valid.
The variable and constraint counts are correct. Together with the coefficient-size bounds, they give a rational linear system of polynomial total encoding length.
The invoked theorem is stated in the needed form: feasibility of a rational linear system is decidable in time polynomial in its binary encoding length. The constructed system meets those hypotheses. Replacing equalities by pairs of weak inequalities is exact, and neither full dimensionality nor strict feasibility is required. The cited attribution identifies [Khachiyan’s polynomial linear-programming result](https://www.mathnet.ru/eng/dan42319).
For \(m=2\), the matrix has size one and the argument still applies. Equal scoring entries, an identically zero scoring vector, absent established types, and masses that do not sum to one cause no failure. All steps concern real divisible allocations, as required.
The decomposition is used to establish equivalence, so the decision algorithm need not enumerate rankings or compute a decomposition. The proof therefore establishes the claimed polynomial-time classification.
Actionable feedback: No 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.