Answer: For both \(\mathrm{Borda}\) and \(2\text{-approval}\), feasibility is decidable in \(\operatorname{poly}(m,\tau,L)\) time.
Theorem 6 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePW-PC w.r.t. Borda count is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a target \(c\), a scoring rule \(r\in\{\mathrm{Borda},2\text{-approval}\}\), and partial-chain types \(P_1,\ldots,P_\tau\) with positive rational masses \(\mu_t\) summing to \(1\), let \(\operatorname{Ext}(P_t)\) be the total rankings extending \(P_t\). Does there exist a nonnegative real allocation \(x_{t,\pi}\) satisfying \(\sum_{\pi\in\operatorname{Ext}(P_t)}x_{t,\pi}=\mu_t\) for each \(t\), such that \(\sum_{t,\pi}x_{t,\pi}s_r(\pi,c)\ge\sum_{t,\pi}x_{t,\pi}s_r(\pi,d)\) for every \(d\ne c\)?
Let \(C\) be a candidate set with \(m=|C|\ge 3\), let \(c\in C\), and let \(r\in\{\mathrm{Borda},2\text{-approval}\}\).
A partial-chain type \(P_t\) specifies a strict total order on a nonempty subset \(C_t\subseteq C\); candidates outside \(C_t\) have no specified comparisons. The subsets may differ across types, and complete rankings are permitted.
A society is given by its support: an explicit list of the \(\tau\) types with positive masses \(\mu_t\), each a binary rational, with \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible types. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Let \(\operatorname{Ext}(P_t)\) be the strict total rankings of \(C\) extending \(P_t\), and let \(s_r(\pi,a)\) denote candidate \(a\)'s score in ranking \(\pi\) under \(r\).
Call the instance feasible if there exist real masses \(x_{t,\pi}\ge 0\) with \(\sum_{\pi\in\operatorname{Ext}(P_t)}x_{t,\pi}=\mu_t\) for every \(t\), such that \(\sum_{t=1}^{\tau}\sum_{\pi\in\operatorname{Ext}(P_t)}x_{t,\pi}\bigl(s_r(\pi,c)-s_r(\pi,d)\bigr)\ge 0\) for every \(d\in C\setminus\{c\}\). Thus mass may split among extensions, and ties for the highest score count as wins.
For each fixed rule \(r\in\{\mathrm{Borda},2\text{-approval}\}\), is deciding feasibility solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
Discrete possible winner on partial chains is NP-complete for Borda and for \(2\)-approval. [Source](https://research.ibm.com/publications/classifying-the-complexity-of-the-possible-winner-problem-on-partial-chains)
No result settling this exact divisible-mass problem was identified in the literature search.
For both Borda and \(2\)-approval, deciding the stated divisible-mass feasibility problem is polynomial-time solvable in \(m,\tau,L\).
The essential fact is that a linear objective over the extensions of one partial chain can be optimized by sorting its unconstrained candidates and then using dynamic programming. This gives a polynomial-time separation oracle for a linear program with \(m-1+\tau\) variables.
Write the positional scoring vector as \(\beta_1\ge\cdots\ge\beta_m\), where position \(1\) is highest. For Borda, \(\beta_j=m-j\). For \(2\)-approval, \(\beta_1=\beta_2=1\) and the remaining entries are zero.
Lemma. Given a partial chain \(P\) and rational candidate weights \(w_a\), one can compute an extension maximizing \(\sum_{a\in C}w_a s_r(\pi,a)\) using \(O(m^2)\) rational arithmetic operations.
Proof. Let the prescribed chain be \(a_1\succ\cdots\succ a_k\), and let \(q=m-k\). Sort the candidates outside the chain into a list \(b_1,\ldots,b_q\) satisfying \(w_{b_1}\ge\cdots\ge w_{b_q}\).
There is an optimal extension whose outside candidates occur in this order. To prove this, suppose outside candidates \(u,v\) occur at positions \(i<j\) with \(w_u<w_v\). Swapping them preserves the prescribed chain, because neither candidate belongs to it. The change in objective is
\((w_v-w_u)(\beta_i-\beta_j)\ge 0.\)
Consequently, sorting the outside candidates while keeping the chain candidates in their existing positions cannot decrease the objective. Equal weights may be ordered arbitrarily. Thus some optimum is an interleaving of the two lists \(a_1,\ldots,a_k\) and \(b_1,\ldots,b_q\).
Define \(F(i,j)\) as the maximum contribution from the first \(i+j\) positions among interleavings of \(a_1,\ldots,a_i\) and \(b_1,\ldots,b_j\). Set \(F(0,0)=0\). Every nonempty interleaving ends with either \(a_i\) or \(b_j\), so
\(F(i,j)=\max\bigl\{F(i-1,j)+w_{a_i}\beta_{i+j},\ F(i,j-1)+w_{b_j}\beta_{i+j}\bigr\},\)
where a term is omitted when its corresponding index is zero.
The recurrence considers every possible last candidate, and hence is exact by induction on \(i+j\). Its final value \(F(k,q)\) is the required optimum; backtracking produces a maximizing extension.
Sorting costs \(O(m\log m)\) comparisons, and the table has \((k+1)(q+1)=O(m^2)\) entries. This also handles complete chains, for which \(q=0\). All arithmetic has bit complexity polynomial in the encoding length of the supplied weights and in \(m\). \(\square\)
Let \(D=C\setminus\{c\}\), and define the margin of an extension against opponent \(d\) by
\(g_{t,\pi,d}=s_r(\pi,c)-s_r(\pi,d).\)
Set \(M=m-1\) for Borda and \(M=1\) for \(2\)-approval. In either case, \(|g_{t,\pi,d}|\le M\).
Consider the following finite, potentially exponentially large linear program. Its variables are \(x_{t,\pi}\ge 0\) and an unrestricted real variable \(\lambda\):
Let its optimum be \(\lambda^\star\).
Each prescribed chain has at least one extension, so the mass constraints admit a solution. Their solution set is a product of finite-dimensional simplices and is therefore compact. The minimum opponent margin is a continuous function on this set; consequently, its maximum \(\lambda^\star\) is attained.
Because the total mass is one and every individual margin belongs to \([-M,M]\), we have \(-M\le\lambda^\star\le M\). By its definition,
\(\text{the instance is feasible}\quad\Longleftrightarrow\quad\lambda^\star\ge 0.\)
In particular, equality correctly includes instances where the best achievable outcome is a tied win.
Introduce nonnegative variables \(y_d\) for the opponent-margin inequalities and unrestricted variables \(z_t\) for the mass equalities. The dual is:
For completeness, these constraints follow from the Lagrangian
\(\lambda+\sum_d y_d\bigl(\sum_{t,\pi}x_{t,\pi}g_{t,\pi,d}-\lambda\bigr)+\sum_tz_t\bigl(\mu_t-\sum_\pi x_{t,\pi}\bigr).\)
Collecting terms gives
\(\lambda\bigl(1-\sum_dy_d\bigr)+\sum_t\mu_tz_t+\sum_{t,\pi}x_{t,\pi}\bigl(\sum_dy_dg_{t,\pi,d}-z_t\bigr).\)
Its supremum over unrestricted \(\lambda\) and nonnegative \(x\) is finite exactly when the displayed dual constraints hold. In that case the supremum equals \(\sum_t\mu_tz_t\).
The primal is a finite feasible linear program with finite optimum. Therefore, finite-dimensional linear-programming strong duality applies, and the dual optimum equals \(\lambda^\star\).
We can additionally impose \(-M\le z_t\le M\) without changing that optimum. Indeed, for a fixed feasible \(y\), put
\(h_t(y)=\max_{\pi\in\operatorname{Ext}(P_t)}\sum_{d\in D}y_dg_{t,\pi,d}.\)
Since \(y\) is a probability vector and the margins are bounded, \(h_t(y)\in[-M,M]\). Replacing \(z_t\) by \(h_t(y)\) preserves feasibility and cannot increase the objective, because \(\mu_t>0\).
Denote this bounded dual feasible region by \(Q\). It is nonempty: any probability vector \(y\), together with \(z_t=M\) for every \(t\), is feasible. It has \(n=m-1+\tau\) variables.
Given a rational query point \((y,z)\), first check the nonnegativity, normalization, and box constraints. A violated constraint immediately separates the point from \(Q\).
If those checks pass, then for every type \(t\) compute \(h_t(y)\). Its objective can be rewritten as
\(\sum_{d\in D}y_d\bigl(s_r(\pi,c)-s_r(\pi,d)\bigr)=w_cs_r(\pi,c)+\sum_{d\in D}w_ds_r(\pi,d),\)
where \(w_c=\sum_{d\in D}y_d=1\) and \(w_d=-y_d\).
The lemma computes this maximum and a maximizing extension \(\pi_t^\star\) in \(O(m^2)\) rational arithmetic operations.
If \(z_t<h_t(y)\), return the violated defining inequality
\(z_t\ge\sum_{d\in D}y_dg_{t,\pi_t^\star,d}.\)
Otherwise, if every type passes, all extension inequalities hold and the query point belongs to \(Q\).
This is an exact strong separation oracle. One call costs \(O(m+\tau+\tau m^2)\) rational arithmetic operations, with polynomial bit complexity in the query encoding length and \(m,\tau\). It never enumerates the extensions.
We use the standard rational separation–optimization theorem: a rational polyhedron with a known polynomial bound on the encoding length of each defining inequality admits exact polynomial-time linear optimization when supplied with a polynomial-time strong separation oracle. The theorem also accommodates lower-dimensional polyhedra. See the discussion of the classical bit-complexity result in [Dadush, Végh, and Zambelli, *On finding exact solutions of linear programs in the oracle model*](https://ir.cwi.nl/pub/35149/35149.pdf).
Its hypotheses hold here:
The theorem therefore computes the dual optimum exactly in \(\operatorname{poly}(m,\tau,L)\) bit operations. Accept precisely when that optimum is nonnegative. By strong duality and Section 2, this decision is equivalent to the required feasibility condition.
Thus the algorithm handles zero margins exactly, uses the explicitly supplied support size \(\tau\), and applies to arbitrary binary rational masses.
The cited discrete NP-completeness results concern choosing one extension for each indivisible vote. Here each type may distribute its mass among extensions, giving exactly the continuous variables of the primal linear program. The polynomial-time algorithm depends on that permission to split mass.
The argument resolves both requested rules. In fact, the sorting and dynamic-programming lemma applies to any nonincreasing rational positional scoring vector of polynomial encoding length.
⟨structured verdict parsed — rendered above⟩
The argument correctly establishes polynomial-time decidability for both Borda and \(2\)-approval under the stated divisible-mass model. No major or minor mathematical issues were found.
The proof addresses the supplied support representation, arbitrary positive binary rational masses, different prescribed subsets across types, complete chains, and wins by ties.
The exchange argument is correct. Candidates outside the prescribed chain have no specified comparisons, so swapping two of them preserves every required comparison. For positions \(i<j\), the objective change is exactly
\[
(w_v-w_u)(\beta_i-\beta_j).
\]
Both factors are nonnegative under the stated assumptions. This argument remains valid for negative candidate weights and for equal positional scores, including the zero-score positions of \(2\)-approval.
Consequently, fixing the positions occupied by chain candidates and sorting the remaining candidates by nonincreasing weight cannot decrease the objective. Every resulting ranking is an interleaving of the prescribed chain and the sorted outside list. Thus the restriction used by the dynamic program loses no optimum.
The recurrence is correct: the last candidate of a prefix with \(i\) chain candidates and \(j\) outside candidates must be either \(a_i\) or \(b_j\), and occupies position \(i+j\). Removing that candidate gives precisely the corresponding predecessor state. The base case and omitted terms handle both table boundaries, including \(q=0\) for complete chains.
There are \((k+1)(q+1)=O(m^2)\) states, each with at most two transitions. Sorting and backtracking fit within the claimed operation bound. Each state value is a sum of at most \(m\) supplied rational weights multiplied by integer scores of magnitude at most \(m-1\); its encoding length is polynomial in the weight encoding length and \(m\). The claimed polynomial bit complexity is therefore justified.
Assessment: Correct.
The variables and mass equalities exactly describe the permitted splitting among extensions. Each extension set is finite and nonempty, and each type’s allocation set is a nonempty compact simplex.
For any allocation, the largest admissible \(\lambda\) is its minimum opponent margin. This minimum is continuous on the product of simplices, so its maximum is attained.
The margin bounds are correct: Borda score differences lie in \([-(m-1),m-1]\), and \(2\)-approval score differences lie in \([-1,1]\). Since total mass is one, every aggregate margin obeys the same bound. Hence
\[
-M\leq\lambda^\star\leq M.
\]
The equivalence between feasibility and \(\lambda^\star\geq0\) follows exactly from the primal inequalities and attainment. In particular, equality is accepted, as required for tied wins.
Assessment: Correct.
The Lagrangian signs are correct. For a primal-feasible allocation, the terms multiplied by nonnegative \(y_d\) are nonnegative, producing the upper bounds appropriate to a maximization primal.
The supremum over unrestricted \(\lambda\) is finite precisely when
\[
\sum_d y_d=1.
\]
The supremum over nonnegative allocation variables is finite precisely when every allocation coefficient is nonpositive, giving
\[
z_t\geq\sum_d y_dg_{t,\pi,d}.
\]
The remaining objective is \(\sum_t\mu_tz_t\), as claimed.
Finite-dimensional LP strong duality applies: although the number of columns may be exponential, it is finite; the primal is feasible and has finite optimum. Thus the dual optimum equals \(\lambda^\star\).
The additional bounds on \(z_t\) preserve that optimum. For feasible \(y\), every weighted margin is a convex combination of numbers in \([-M,M]\), so \(h_t(y)\) lies in that interval. Replacing \(z_t\) by \(h_t(y)\) preserves all extension inequalities and cannot increase the objective because \(\mu_t>0\).
The exhibited point with \(z_t=M\) proves nonemptiness of \(Q\). Its probability-vector and box constraints prove boundedness.
Assessment: Correct.
The initial explicit constraint checks correctly detect violations of nonnegativity, normalization, and box bounds. A violated normalization equality supplies a separator by choosing its violated inequality direction.
After those checks pass, the objective identity is exact:
\[
\sum_dy_d\bigl(s_r(\pi,c)-s_r(\pi,d)\bigr)
=s_r(\pi,c)-\sum_dy_ds_r(\pi,d).
\]
Therefore the lemma applies with \(w_c=1\) and \(w_d=-y_d\).
If \(z_t<h_t(y)\), the maximizing extension identifies an actual defining inequality satisfied throughout \(Q\) and strictly violated by the query point. If all types pass, every extension inequality holds, so membership is established.
The operation bound accounts for the explicit checks and one dynamic program per type. Exact rational comparisons and the lemma’s bit bounds justify polynomial bit complexity in the query length, \(m\), and \(\tau\).
Assessment: Correct.
The invoked classical rational separation–optimization result is applicable. The cited paper discusses the bit-complexity results for bounded facet complexity, lower-dimensional polyhedra, and integer constraint systems with bounded coefficients. The prover invokes that classical result, rather than relying on the paper’s separate real-arithmetic algorithm. See [Dadush, Végh, and Zambelli, introduction](https://ir.cwi.nl/pub/35149/35149.pdf).
The stated hypotheses are satisfied:
Thus exact optimization takes \(\operatorname{poly}(m,\tau,L)\) bit operations. Lower dimensionality from the normalization equality is covered by the invoked theorem. Exact optimization supports the comparison with zero, including a zero optimum.
Assessment: Correct.
The distinction from discrete possible winner is valid: the supplied model permits fractional allocation among extensions, precisely as represented by the primal LP. Discrete NP-completeness does not invalidate this continuous algorithm.
Both requested rules satisfy every scoring assumption used in the proof. The argument therefore resolves the entire assigned decision problem.
Required clarification or repair: None.
⟨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.