Answer: Both \(k\)-approval and positional scoring with an input binary rational vector are polynomial-time solvable. An improving report can also be produced in polynomial time, using at most \(dm\) exact rational linear-programming optimizations.
Corollary 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateOM can be solved in polynomial time for k-approval.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(O\), a finite ranking-type set \(T\subseteq L(O)\), rational focal mass \(\alpha\in(0,1]\), focal true ranking \(r\in T\), a fixed deterministic tie-break order, and a \(k\)-approval or positional scoring rule, choose a report \(r'\in T\). For every residual distribution \(\nu\in\Delta(T)\), the resulting society is \(\mu_{\nu,r'}=\alpha e_{r'}+(1-\alpha)\nu\). Define \(B_\alpha(r')\) and \(W_\alpha(r')\) as the focal type's best and worst possible winners under \(r\), over all \(\nu\). Decide whether some \(r'\) satisfies \(W_\alpha(r')\succ_r W_\alpha(r)\) or \(B_\alpha(r')\succ_r B_\alpha(r)\), and output such a report.
Let \(O\) contain \(m\geq3\) candidates, and let \(T\subseteq L(O)\) be an explicitly listed nonempty domain of \(d=|T|\) strict linear rankings. Input includes a true ranking \(r\in T\), binary rational focal mass \(0<\alpha\leq1\), and a deterministic tie-break order.
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 \(\tau\) is the support size, not the number of possible rankings or admissible types. Total society mass is \(1\); quantified distributions below may have real masses and are not input societies.
The rule is either \(k\)-approval with \(1\leq k<m\), or positional scoring with an input binary rational vector \(s_1\geq\cdots\geq s_m\), \(s_1>s_m\); scores may have either sign. Candidate scores are weighted by type masses, and the highest-scoring candidate wins, with ties resolved by the supplied order.
The focal mass reports one ranking \(r'\in T\). For every \(\nu\in\Delta(T)=\{x\in\mathbb R_{\geq0}^{T}:\sum_{t\in T}x_t=1\}\), the reported society is \(\mu_{\nu,r'}=\alpha e_{r'}+(1-\alpha)\nu\), where \(e_{r'}\) is unit mass at \(r'\).
Let \(B_\alpha(r')\) and \(W_\alpha(r')\) be the most and least preferred winners according to \(r\) attainable over these residual distributions. An improving report satisfies \(W_\alpha(r')\succ_r W_\alpha(r)\) or \(B_\alpha(r')\succ_r B_\alpha(r)\).
Is deciding whether an improving report exists polynomial-time solvable or NP-hard, separately for \(k\)-approval and input positional scoring vectors? In the polynomial-time case, can such a report also be produced in polynomial time? State running times in \(m,d,\tau,L\) and, where applicable, \(k\), with \(L\) the total input bit length.
For unrestricted discrete rankings and unweighted voters, obvious manipulation under \(k\)-approval is polynomial-time solvable; for positional scoring, it reduces in polynomial time to constructive coalitional unweighted manipulation. [Verified source](https://arxiv.org/pdf/2111.01983v3).
No result settling the exact continuous problem specified here was located.
Both \(k\)-approval and positional scoring with an input rational vector are polynomial-time solvable. An improving report, whenever one exists, can also be produced in polynomial time.
The proof uses the explicitly listed domain \(T\): there are only \(d\) reports to examine, and winner attainability for each report is an exact rational linear-programming problem. This settles the specified model for arbitrary admissible \(k\), signed scoring vectors, and deterministic tie-breaking.
For \(t\in T\) and \(c\in O\), let \(p_t(c)\) be the position of \(c\) in ranking \(t\). Define its per-unit-mass score by
Fix a report \(q\in T\). Write the residual distribution as \(x=(x_t)_{t\in T}\), where \(x_t\geq0\) and \(\sum_{t\in T}x_t=1\). Candidate \(c\)'s score is
\(S_c(q,x)=\alpha a_{cq}+(1-\alpha)\sum_{t\in T}a_{ct}x_t.\)
Define
\(A(q)=\{c\in O:\text{there exists }x\in\Delta(T)\text{ for which }c\text{ wins under report }q\}.\)
This set is nonempty: \(T\neq\varnothing\), so a residual distribution exists, and every resulting society has a unique winner after tie-breaking. Since \(A(q)\) is a finite set, its best and worst elements according to \(r\) exist. These are precisely \(B_\alpha(q)\) and \(W_\alpha(q)\). Their existence does not require the winner map to be continuous.
Let \(H(c)\) be the set of candidates preceding \(c\) in the tie-break order. For each opponent \(j\neq c\), put
\(D_{cj}(q,x)=\alpha(a_{cq}-a_{jq})+(1-\alpha)\sum_{t\in T}(a_{ct}-a_{jt})x_t.\)
Thus \(D_{cj}(q,x)=S_c(q,x)-S_j(q,x)\).
Lemma. Candidate \(c\) belongs to \(A(q)\) if and only if the following linear program is feasible and has strictly positive optimal value.
Maximize \(\varepsilon\), subject to:
Proof. Suppose first that \(c\) wins for some residual distribution \(x\). It must have a strictly larger score than every \(j\in H(c)\): equality would make the tie-break select a candidate preceding \(c\). It must have at least as large a score as every other opponent.
If \(H(c)\neq\varnothing\), choose
\(\varepsilon=\min\bigl(\{1\}\cup\{D_{cj}(q,x):j\in H(c)\}\bigr).\)
This minimum is positive because the set is finite and all its elements are positive. If \(H(c)=\varnothing\), choose \(\varepsilon=1\). In either case, the LP has a feasible point with positive objective value.
Conversely, suppose the LP has a feasible point with \(\varepsilon>0\). Then \(c\) strictly outscores every candidate preceding it in the tie-break order and weakly outscores every remaining opponent. Consequently, \(c\) is the selected winner.
Finally, the feasible region, when nonempty, is a closed subset of \(\Delta(T)\times[0,1]\), hence compact. The objective therefore attains its maximum. Thus a positive feasible margin exists exactly when the optimal value is positive. \(\square\)
All coefficients are rational. Exact rational linear programming can decide infeasibility and compute the optimal value in polynomial bit time; this is the standard polynomial-time LP theorem originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319). Its hypotheses apply here because the LP is explicitly represented, has rational coefficients, and has a bounded feasible region.
In particular, the test compares the exact optimum with zero. Replacing strict inequalities by weak inequalities, or choosing an arbitrary numerical tolerance, would not establish the lemma.
The construction also covers \(\alpha=1\): the residual terms vanish, and the LP simply checks the winner determined by the focal report.
Let \(\rho(c)=p_r(c)\), so smaller values mean greater preference according to the true ranking. For each \(q\in T\), perform the lemma's test for every \(c\in O\), thereby computing \(A(q)\). Set
\(b(q)=\min_{c\in A(q)}\rho(c),\qquad w(q)=\max_{c\in A(q)}\rho(c).\)
By definition,
\(b(q)=\rho(B_\alpha(q)),\qquad w(q)=\rho(W_\alpha(q)).\)
The algorithm returns any report \(q\in T\) satisfying
\(b(q)<b(r)\quad\text{or}\quad w(q)<w(r).\)
If there is no such report, it returns NO.
Correctness. Each set \(A(q)\) is computed exactly by the lemma. Consequently, the two comparisons are respectively equivalent to
\(B_\alpha(q)\succ_r B_\alpha(r)\quad\text{and}\quad W_\alpha(q)\succ_r W_\alpha(r).\)
Every admissible report is examined because \(T\) is explicitly listed. Hence the algorithm returns a report exactly when an improving report exists. The returned ranking itself is the requested witness. \(\square\)
Let \(\ell_\alpha\) be the binary encoding length of \(\alpha\), with \(\ell_\alpha\leq L\). To state the bounds independently of a particular LP implementation, let \(\mathsf{LP}(n,h,b)\) denote a fixed polynomial upper bound on the bit time to assemble and solve a rational LP with \(n\) variables, at most \(h\) inequalities, and coefficient encoding length at most \(b\).
Each attainability LP has:
For the coefficient bounds, approval-score differences belong to \(\{-1,0,1\}\). In the positional case, each coefficient uses a difference of two input scores and multiplication by either \(\alpha\) or \(1-\alpha\). These rational operations increase encoding length by at most a constant multiple of \(L+1\), including when scores are negative.
There are at most \(dm\) LP optimizations. A conservative bit-time bound for approval is
\(O\!\left(L+dm(L+1)^2+dm\,\mathsf{LP}\!\left(d+1,d+m+3,O(\ell_\alpha+1)\right)\right).\)
For input positional scoring, a conservative bound is
\(O\!\left(L+dm(L+1)^2+dm\,\mathsf{LP}\!\left(d+1,d+m+3,O(L+1)\right)\right).\)
The preprocessing term allows straightforward binary arithmetic and construction of the score table. Computing the best and worst attainable ranks requires another \(O(dm)\) elementary comparisons. Outputting the chosen ranking requires \(O(m\log m)\) bits under indexed candidate encoding.
Thus both decision and report construction take polynomial time in \(m,d,\tau,L\). For approval, the bound is uniform over all \(1\leq k<m\), with no additional factor exponential in \(k\).
The support size \(\tau\) has no separate algorithmic dependence beyond reading the input, already included in \(O(L)\). Under the stated definition, the attainable sets depend on \(T,\alpha,r\), the rule, and tie-breaking. They do not depend on the listed current society: residual distributions range over all of \(\Delta(T)\), rather than being constrained by that society's positive support or masses.
The cited [Aziz–Lam paper](https://arxiv.org/pdf/2111.01983v3) gives the stated approval algorithm and positional-scoring reduction for the discrete unweighted setting. The proof above directly settles the continuous problem specified here: residual masses are real LP variables, and the admissible reports are explicitly enumerable.
The running time is polynomial in the listed domain size \(d\). If one lists every ranking, then \(d=m!\); this proof does not assert a running time polynomial in \(m\) alone for an implicitly represented unrestricted domain.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output correctly resolves both rule families for the explicitly listed domain. It establishes polynomial-time decision and production of an improving report. I found no major or minor mathematical issues.
These conditions are also sufficient: \(c\) has maximal score, and every opponent with equal score follows it in the tie-break order.
If \(c\) wins and \(H(c)\neq\varnothing\), the displayed minimum defining \(\varepsilon\) is positive because it ranges over finitely many positive numbers. Its inclusion of \(1\) ensures the imposed upper bound. If \(H(c)=\varnothing\), choosing \(\varepsilon=1\) is valid because no opponent constraint involves \(\varepsilon\).
Conversely, any feasible point with \(\varepsilon>0\) satisfies every required strict and weak score comparison.
The compactness argument is valid: all constraints are closed, and the feasible region lies in the compact set \(\Delta(T)\times[0,1]\). Thus, whenever feasible, the LP attains its optimum. Infeasibility and an optimum equal to zero are correctly rejected. The proof never replaces a strict winning condition with a weak one.
Its hypotheses are satisfied as written. The constraints and objective have rational coefficients; the number of variables and constraints is finite and explicitly bounded; and the entire feasible region is bounded. Equality constraints and a feasible region of lower dimension do not invalidate the theorem. Comparing the exact optimum with zero is therefore justified, even when a positive optimum is very small.
Enumerating every \(q\in T\) exhausts the permitted reports. Including \(q=r\) causes no problem: it cannot satisfy either strict comparison against itself. Returning a listed ranking supplies the requested report witness; the task does not additionally require residual distributions witnessing attainability.
\(d+2+2+(m-1)=d+m+3\):
nonnegativity, the simplex equality represented twice, the two margin bounds, and one comparison per opponent.
The coefficient-length bounds are also correct. Approval differences are in \(\{-1,0,1\}\), so their rational coefficients have length \(O(\ell_\alpha+1)\). For positional scoring, each coefficient involves only a constant number of rational operations on input values, giving length \(O(L+1)\). Negative scores do not affect this bound or the LP argument.
There are at most \(dm\) optimizations. The definition of \(\mathsf{LP}\) explicitly includes assembly, so the displayed bounds account for constructing each constraint matrix. The preprocessing and output bounds are conservative and polynomial under the stated indexed encoding.
The absence of a separate dependence on \(\tau\), beyond reading the input, follows from the task’s quantified residual distributions. The approval bound is uniform over every permitted \(k\).
The discrete-source summary agrees with Theorem 6 and Corollary 5 of the [Aziz–Lam paper](https://arxiv.org/pdf/2111.01983v3). Those results are contextual and are not used to establish the continuous classification. The final qualification about \(d=m!\) correctly limits the claim to an explicitly represented domain.
Repair feedback: none required. The proof establishes its claimed classification and witness-production result within the requested input model.
⟨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.