Answer: Both deciding \(\delta^\star>0\) and deciding \(\delta^\star\ge 0\) are polynomial-time solvable.
Corollary 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePW and PcW are NP-complete with respect to Borda, even when the number of undetermined pairs in each vote is no more than 4.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), rational masses \(\mu_i\) over \(\tau\) partial-order types \(O_i\), each with at most \(4\) undetermined pairs, and target \(c\), choose nonnegative masses \(x_{i,V}\) over linear extensions \(V\in E_i\) satisfying \(\sum_{V\in E_i}x_{i,V}=\mu_i\), and decide whether the maximum \(\delta\) satisfying \(\sum_{i,V}x_{i,V}\bigl(s_{\mathrm{Borda}}(V,c)-s_{\mathrm{Borda}}(V,a)\bigr)\ge\delta\) for every \(a\ne c\) is \(>0\) or \(\ge0\).
Let \(C\) be a candidate set, \(O_1,\ldots,O_\tau\) partial orders on \(C\), and \(\mu_1,\ldots,\mu_\tau\) nonnegative rational masses. Each \(O_i\) has at most \(4\) incomparable candidate pairs; let \(E_i\) be its linear extensions. Choose \(x_{i,V}\ge0\) for \(V\in E_i\) with \(\sum_{V\in E_i}x_{i,V}=\mu_i\). For \(a\in C\), let \(s_{\mathrm{Borda}}(V,a)=|C|-\operatorname{rank}_V(a)\), and let \(\delta^\star\) be the maximum \(\delta\) such that \(\sum_{i,V}x_{i,V}(s_{\mathrm{Borda}}(V,c)-s_{\mathrm{Borda}}(V,a))\ge\delta\) for every \(a\ne c\).
Are the rational-mass Borda extension problems of deciding whether \(\delta^\star>0\), respectively whether \(\delta^\star\ge0\), solvable in polynomial time or NP-hard?
For finite unweighted profiles, deciding whether a designated candidate is a possible unique winner or possible co-winner under Borda is NP-complete, even when each partial order has at most \(4\) undetermined pairs.
No verified result for the stated rational-mass formulation is included here.
Both problems are polynomial-time solvable. The rational-mass formulation permits each mass to be split among linear extensions, so it is a linear program with polynomially many variables.
Write \(n=|C|\), and assume \(c\in C\) and \(n\ge 2\). For each \(i\), let \(k_i\le 4\) be the number of unordered candidate pairs incomparable in \(O_i\).
A linear extension specifies an orientation of each of these \(k_i\) pairs. Its comparisons on all other pairs are already fixed by \(O_i\). Consequently, two distinct linear extensions cannot specify the same orientations, and hence \(|E_i|\le 2^{k_i}\le 16\).
This bound also gives a polynomial-time enumeration algorithm. Compute the comparisons implied by \(O_i\), and enumerate all \(2^{k_i}\) orientations of its incomparable pairs. For each choice, form the directed graph containing the fixed comparisons and the chosen orientations. It has exactly one directed edge between every pair of distinct candidates.
If this graph contains a directed cycle, the choice cannot describe a linear order. If it is acyclic, a topological ordering exists and respects every comparison. Because every pair is compared, that ordering is unique and is a linear extension of \(O_i\). Conversely, every linear extension occurs among these choices.
Thus all the sets \(E_i\) can be enumerated in polynomial time. Each is nonempty because every finite partial order admits a linear extension.
For every \(i\), \(V\in E_i\), and \(a\ne c\), compute the integer coefficient \(d_{i,V,a}=s_{\mathrm{Borda}}(V,c)-s_{\mathrm{Borda}}(V,a)\). Since Borda scores belong to \(\{0,\ldots,n-1\}\), we have \(|d_{i,V,a}|\le n-1\).
Consider the linear program with objective \(\max\delta\), subject to:
These are exactly the choices and margin constraints in the question, so the optimum, if attained, equals \(\delta^\star\).
To verify feasibility and attainment, set \(M=\sum_{i=1}^{\tau}\mu_i\) and \(B=(n-1)M\). Choose one extension for each \(O_i\), assign its entire mass to that extension, and assign zero to the remaining extensions. This satisfies the mass constraints. For any mass allocation satisfying those constraints and any opponent \(a\),
\(\left|\sum_{i=1}^{\tau}\sum_{V\in E_i}d_{i,V,a}x_{i,V}\right|\le\sum_{i=1}^{\tau}\sum_{V\in E_i}(n-1)x_{i,V}=B.\)
Therefore \(\delta=-B\) is feasible. Moreover, because there is at least one opponent, every feasible solution satisfies \(\delta\le B\). We may impose \(-B\le\delta\le B\) without changing the optimum: all discarded feasible solutions have objective less than the already feasible value \(-B\).
The resulting feasible region is closed and bounded: in particular, \(0\le x_{i,V}\le\mu_i\). It is nonempty, so the continuous objective attains a maximum.
The linear program has at most \(16\tau+1\) variables, \(\tau\) mass equalities, and \(n-1\) margin inequalities, in addition to variable bounds. Its margin coefficients are integers of absolute value at most \(n-1\); its remaining coefficients and right-hand sides are rational numbers of polynomial encoding length. In particular, forming \(M\) and \(B\) increases the binary encoding length by at most a polynomial in the input length.
Apply the standard polynomial-time theorem for rational linear programming: a rational linear program can be solved exactly in time polynomial in its binary encoding length, including obtaining its rational optimal value when the optimum is finite and attained. All these hypotheses have been verified above.
Compute that optimal value and compare it exactly with zero. This decides both \(\delta^\star>0\) and \(\delta^\star\ge 0\) in polynomial time. No numerical tolerance or guessed positive margin is needed.
The quoted NP-completeness result concerns indivisible, unweighted votes. Even when \(\mu_i=1\), the present formulation allows that unit mass to be distributed fractionally among different extensions. Thus the integer-choice hardness result does not establish hardness for this linear program.
If \(C=\{c\}\), there are no margin constraints, so the stated maximization is unbounded and has no finite maximum. Under the extended-value convention \(\delta^\star=+\infty\), both answers are yes. Otherwise, the definition needs the hypothesis \(n\ge 2\); the polynomial-time result above applies to every instance satisfying it.
⟨structured verdict parsed — rendered above⟩
The proof is correct for every instance with \(c\in C\) and \(|C|\ge 2\). It establishes polynomial-time algorithms for both decisions in the rational-mass formulation. No substantive gap or incorrect step was found.
The prover also correctly identifies a definitional edge case: when \(C=\{c\}\), the objective is unbounded, so the literal definition using a maximum does not define \(\delta^\star\). The stated answers for that case are explicitly conditional on adopting an extended-value convention.
Every pair of distinct candidates is either comparable in \(O_i\) or one of its \(k_i\) incomparable pairs. A linear extension must preserve every fixed comparison. Consequently, its orientations of the incomparable pairs determine all pairwise comparisons, and hence determine the entire linear order.
The claimed injection into the set of orientation choices is valid, yielding \(|E_i|\le 2^{k_i}\le 16\). The proof does not incorrectly assume that every orientation choice is consistent.
Computing the comparisons implied by a finite partial order is polynomial time under the ordinary explicit representation of candidates and order relations.
After orienting every incomparable pair, the graph has exactly one directed edge between each pair of distinct candidates. Here “comparisons” correctly refers to comparisons between distinct candidates, so reflexive relations are not included as graph loops.
A cyclic graph cannot represent a linear order. An acyclic graph admits a topological ordering; because every pair is compared, that ordering is unique. It respects the original partial order and is therefore a linear extension. Conversely, every linear extension supplies one of the enumerated orientation choices.
There are at most \(16\) choices per partial order, and all graph operations are polynomial time. Both completeness and running time are justified.
The variables, nonnegativity constraints, mass equalities, and margin inequalities reproduce the task exactly. In particular, no integrality restriction is imposed or needed: the task expressly permits splitting mass.
The coefficient bound \(|d_{i,V,a}|\le n-1\) follows directly from the stated Borda score range. The variable \(\delta\) is unrestricted until the later explicit bounds are imposed.
Every finite partial order has a linear extension, so assigning each entire mass to one extension satisfies all mass constraints, including when some masses are zero.
For any feasible mass allocation, the displayed absolute-value estimate is valid by the triangle inequality, nonnegativity, and the mass equalities. Its final value is exactly \(B=(n-1)\sum_i\mu_i\).
Thus \(\delta=-B\) is feasible. Since \(n\ge 2\), at least one margin inequality exists, and every feasible objective value satisfies \(\delta\le B\).
Adding \(-B\le\delta\le B\) preserves the optimal objective value: the upper bound is already implied, and solutions removed by the lower bound have objective below an available feasible value.
Every allocation variable satisfies \(0\le x_{i,V}\le\mu_i\). The resulting region is nonempty, closed, and bounded in finite-dimensional Euclidean space, hence compact. The linear objective therefore attains its maximum. This establishes the required finite, attained optimum.
The counts of variables and constraints are correct. The enumerated rankings and all Borda coefficients have polynomial total encoding length.
Summing explicitly encoded rational masses and multiplying by \(n-1\) produces rational numbers of polynomial binary encoding length. Thus the additional bounds do not invalidate the polynomial-size claim.
The invoked rational linear-programming theorem is stated sufficiently precisely for this application: exact optimization, including a rational optimal value, is polynomial time in the binary encoding length when the optimum is finite and attained. The constructed program satisfies those hypotheses.
Comparing the exact rational optimum with zero decides both predicates, including the boundary case \(\delta^\star=0\). There is no reliance on floating-point precision or an unjustified separation from zero.
The distinction between indivisible votes and divisible masses is valid. Setting \(\mu_i=1\) does not enforce choosing a single extension. The cited discrete hardness result therefore does not establish hardness of the formulation audited here.
Zero masses, including total mass zero, are covered by the feasibility and boundedness argument. An empty profile is also covered when permitted.
For \(C=\{c\}\), there are no inequalities involving \(\delta\); the objective is indeed unbounded. The prover correctly distinguishes an extended optimum of \(+\infty\) from a finite maximum. The assumption \(c\in C\) is necessary for the task’s score expressions to be defined.
No proof repair is required. To make the problem statement define a decision problem on singleton candidate sets, specify either \(|C|\ge 2\) or the extended-value convention already identified by the prover. This is an ambiguity in the original definition, not an omitted argument in the output.
⟨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.