Answer: The continuous possible-cowinner problem is in \(\mathsf{P}\).
Proposition 7 — class: hardness
Given a candidate set \(X\), target \(x^\star \in X\), integers \(K \geq 3\) and \(k \geq 3\), and supported rankings \(\sigma_t\) of \(X\) with rational masses \(\mu_t\) summing to \(1\), let \(Y\) be \(k\) new candidates. For each full ranking \(\pi\) of \(X \cup Y\) extending \(\sigma_t\), choose \(q_{t,\pi} \geq 0\) with \(\sum_{\pi:\,\pi|_X=\sigma_t} q_{t,\pi}=\mu_t\). Is there an assignment such that \(x^\star\)’s aggregate \(K\)-approval score is at least every candidate’s score?
Let \(X\) be a candidate set with \(m=|X|\), target \(x^\star\in X\), and input integers \(3\leq K<m\) and \(k\geq3\); encode \(K\) in binary and \(k\) in unary.
A society is given by its support: the list of \(\tau\) distinct strict rankings \(\sigma_t\) of \(X\) with positive binary rational masses \(\mu_t\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
Let \(Y=\{y_1,\ldots,y_k\}\) be disjoint from \(X\). For each type, let \(E_t\) contain all strict rankings of \(X\cup Y\) whose restriction to \(X\) is \(\sigma_t\); every new candidate appears in every extension.
A completion assigns real masses \(q_{t,\pi}\geq0\) with \(\sum_{\pi\in E_t}q_{t,\pi}=\mu_t\). Its aggregate \(K\)-approval score is \(S_K(c)=\sum_t\sum_{\pi\in E_t}q_{t,\pi}\mathbf{1}\{\operatorname{rank}_{\pi}(c)\leq K\}\).
The decision problem asks whether a completion satisfies \(S_K(x^\star)\geq S_K(c)\) for every \(c\in X\cup Y\); ties count as wins.
Is this continuous possible-cowinner problem in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard? State running times in \(m,\tau,L,K,k\).
For a finite list of unweighted voters, the corresponding decision problem is \(\mathsf{NP}\)-complete for every fixed pair \(K,k\geq3\) ([source](https://arxiv.org/pdf/1111.3690)).
No published result settling this exact mass-splitting version was located in the literature search.
The continuous possible-cowinner problem is in \(\mathsf{P}\). A linear program with \(\tau(\min\{K,k\}+1)\) nonnegative variables decides it exactly.
The proof uses mass splitting to equalize the scores of the new candidates.
Write type \(\sigma_t\) as \((a_{t,1},\ldots,a_{t,m})\), and let \(p_t(c)\) be the position of \(c\in X\) in that ranking.
In any extension, let \(r\) be the number of old candidates among the first \(K\) positions. Those candidates must be exactly \(a_{t,1},\ldots,a_{t,r}\): preservation of the old ranking means that every old candidate preceding an approved old candidate is also approved.
The remaining \(K-r\) approved candidates belong to \(Y\). Consequently, the possible values of \(r\) are precisely
\(R=\{\max\{0,K-k\},\ldots,K\}\).
Necessity follows from \(0\leq K-r\leq k\). For sufficiency, choose any \(K-r\) new candidates and place them immediately after the first \(r\) old candidates, followed by the remaining old candidates and then the remaining new candidates. This is a valid extension with the required approval set.
Thus \(d:=|R|=\min\{K,k\}+1\).
For every \(t\in\{1,\ldots,\tau\}\) and \(r\in R\), introduce a nonnegative variable \(\lambda_{t,r}\). It represents type-\(t\) mass assigned to extensions approving exactly \(r\) old candidates.
Require the type-mass equations
\(\displaystyle \sum_{r\in R}\lambda_{t,r}=\mu_t\qquad(t=1,\ldots,\tau).\)
For \(c\in X\), define its resulting score by
\(\displaystyle A_c(\lambda)=\sum_{t=1}^{\tau}\sum_{r\in R}\lambda_{t,r}\mathbf{1}\{p_t(c)\leq r\}.\)
Define the total approval mass received by new candidates by
\(\displaystyle B(\lambda)=\sum_{t=1}^{\tau}\sum_{r\in R}(K-r)\lambda_{t,r}.\)
The remaining constraints are
\(\displaystyle A_c(\lambda)\leq A_{x^\star}(\lambda)\qquad(c\in X\setminus\{x^\star\}),\)
and
\(\displaystyle B(\lambda)\leq kA_{x^\star}(\lambda).\)
All these constraints are linear with rational input data.
Suppose a winning completion \(q\) exists. For each extension \(\pi\), let \(r(\pi)\) count its approved old candidates, and set
\(\displaystyle \lambda_{t,r}=\sum_{\substack{\pi\in E_t\\r(\pi)=r}}q_{t,\pi}.\)
These variables are nonnegative and satisfy the type-mass equations.
By the prefix property proved above, \(S_K(c)=A_c(\lambda)\) for every \(c\in X\). Moreover, each extension counted in \(\lambda_{t,r}\) approves exactly \(K-r\) new candidates, so
\(\displaystyle \sum_{i=1}^{k}S_K(y_i)=B(\lambda).\)
Since \(x^\star\) is a cowinner, the old-candidate inequalities hold. Summing \(S_K(y_i)\leq S_K(x^\star)\) over all new candidates also gives
\(\displaystyle B(\lambda)\leq kA_{x^\star}(\lambda).\)
Therefore every winning completion yields a feasible linear program.
Suppose \(\lambda\) is feasible. We construct a completion in which every new candidate has score \(B(\lambda)/k\).
Fix \(t,r\), and put \(b=K-r\). For \(h\in\{0,\ldots,k-1\}\), define the cyclic ordering
\(\displaystyle z_{h,j}=y_{1+((h+j-1)\bmod k)}\qquad(j=1,\ldots,k).\)
Use the extension
\(\displaystyle \pi_{t,r,h}=(a_{t,1},\ldots,a_{t,r},z_{h,1},\ldots,z_{h,b},a_{t,r+1},\ldots,a_{t,m},z_{h,b+1},\ldots,z_{h,k}),\)
with empty blocks omitted. Assign it mass \(\lambda_{t,r}/k\), adding masses if a ranking occurs more than once.
Each extension contains every candidate exactly once and restricts to \(\sigma_t\). Its first \(K=r+b\) positions approve precisely the first \(r\) old candidates and the first \(b\) candidates of the cyclic ordering.
Across the \(k\) cyclic orderings, each new candidate appears in the approved block exactly \(b\) times. Indeed, for each position \(j\in\{1,\ldots,b\}\), exactly one shift \(h\) places a specified new candidate at that position. This also covers \(b=0\) and \(b=k\).
Consequently, the contribution of this pair \(t,r\) to each new candidate is
\(\displaystyle \frac{b\lambda_{t,r}}{k}=\frac{(K-r)\lambda_{t,r}}{k}.\)
Summing over all pairs gives
\(\displaystyle S_K(y_i)=\frac{B(\lambda)}{k}\leq A_{x^\star}(\lambda)\qquad(i=1,\ldots,k).\)
Each old candidate has score \(A_c(\lambda)\), which is at most the target’s score by feasibility. Finally, the total mass assigned to type \(t\) is
\(\displaystyle \sum_{r\in R}\sum_{h=0}^{k-1}\frac{\lambda_{t,r}}{k}=\mu_t.\)
This is a valid winning completion. Hence linear-program feasibility is equivalent to the original decision problem.
Put \(n=\tau d=\tau(\min\{K,k\}+1)\). The linear program has:
After moving terms to the left, all matrix coefficients are integers of magnitude at most \(K+k\). For example, the coefficient of \(\lambda_{t,r}\) in the final inequality is \((K-r)-k\mathbf{1}\{p_t(x^\star)\leq r\}\).
A dense rational encoding therefore has bit length
\(\displaystyle B_{\mathrm{LP}}=O\!\left(L+(m+\tau)\tau(\min\{K,k\}+1)\log(K+k+2)\right).\)
Inverse positions and matrix entries can be constructed using
\(\displaystyle O\!\left(\tau m+(m+\tau)\tau(\min\{K,k\}+1)\right)\)
elementary indexing and coefficient operations, with polynomial bit cost.
The standard polynomial-time theorem for rational linear programming decides feasibility exactly in time polynomial in its encoding length. Thus, for some universal constant \(C\), a bit-operation bound is
\(\displaystyle O\!\left(\left[L+(m+\tau)\tau(\min\{K,k\}+1)\log(K+k+2)\right]^C\right).\)
Since \(K<m\), binary encoding of \(K\) causes no exponential expansion. With the stated explicit rankings and unary encoding of \(k\), this bound is polynomial in \(L\).
There is also no gap between real and rational feasibility. The feasible region is a bounded rational polytope because \(0\leq\lambda_{t,r}\leq\mu_t\). If nonempty, it has a rational vertex with polynomial encoding length. The construction above then supplies a rational completion supported on at most \(nk=\tau dk\) extensions. Writing those rankings takes \(O(\tau dk(m+k))\) candidate-symbol operations after obtaining \(\lambda\).
The finite-voter problem requires one extension for each voter; it does not allow splitting that voter among extensions. Its hardness theorem therefore does not apply to the fractional choices used here. The cited paper establishes the finite-voter result in Proposition 7. [Chevaleyre et al., *New Candidates Welcome!*](https://arxiv.org/pdf/1111.3690)
The equivalence proved above settles the mass-splitting problem independently of that result.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is correct: the continuous possible-cowinner problem is in \(\mathsf{P}\). The LP equivalence is rigorous, the construction handles the boundary cases, and the stated running-time bounds are polynomial in the given input encoding. I found no major or minor mathematical issues.
The prefix property is correct. If an old candidate receives approval, every old candidate preceding it in \(\sigma_t\) must occur earlier in the extension and therefore also receive approval. Thus the approved old candidates form exactly a prefix of \(\sigma_t\).
The range
\(R=\{\max\{0,K-k\},\ldots,K\}\)
is correct:
The proposed extension realizes every value in this range. Its first \(K\) positions consist of the first \(r\) old candidates followed by \(K-r\) new candidates. This includes \(r=0\), when permitted, and \(r=K\).
The count \(d=\min\{K,k\}+1\) is correct.
The variables \(\lambda_{t,r}\) correctly record type mass according to the number of approved old candidates. The equations \(\sum_{r\in R}\lambda_{t,r}=\mu_t\), together with nonnegativity, preserve each type’s mass.
The formula for \(A_c(\lambda)\) exactly describes old-candidate scores because of the prefix property. The formula for \(B(\lambda)\) exactly describes the sum of new-candidate scores.
The old-candidate inequalities correctly enforce the target’s comparison with every other old candidate. The additional inequality \(B(\lambda)\leq kA_{x^\star}(\lambda)\) is initially only an aggregate condition; Section 4 supplies the necessary justification that it suffices for all individual new-candidate comparisons.
There is no omitted score constraint after that construction is established.
The aggregation from \(q\) to \(\lambda\) is well-defined: each \(E_t\) is finite, and every extension has one value of \(r\) in \(R\).
Grouping masses preserves nonnegativity and the type-mass equations. The identities
\(S_K(c)=A_c(\lambda)\) for old candidates and
\(\sum_{i=1}^{k}S_K(y_i)=B(\lambda)\)
follow from the approval-set description.
Summing the \(k\) cowinner inequalities for new candidates gives exactly the final LP inequality. Consequently, every winning completion produces a feasible LP solution.
No integrality or rationality assumption on the original completion is used.
For each \(t,r,h\), the displayed ranking \(\pi_{t,r,h}\):
These assertions remain valid for empty blocks. In particular, \(b=0\) approves no new candidates, while \(b=k\) approves all new candidates.
The cyclic counting argument is correct. For any fixed new candidate and any fixed position \(j\), exactly one shift places that candidate in position \(j\). Hence each new candidate occurs in the approved block exactly \(b\) times across the \(k\) shifts.
Assigning mass \(\lambda_{t,r}/k\) therefore contributes \(b\lambda_{t,r}/k\) to each new candidate. Summing gives
\(S_K(y_i)=B(\lambda)/k\leq A_{x^\star}(\lambda)\).
Old scores remain \(A_c(\lambda)\), and the total mass assigned to each type is \(\mu_t\). Adding masses for duplicate rankings causes no difficulty. Rankings outside the construction receive zero mass, as permitted.
This proves sufficiency and completes the equivalence.
The counts are correct: \(n=\tau d\) variables, \(\tau\) mass equations, and \(m\) score inequalities, with nonnegativity imposed separately.
Old-candidate comparison coefficients belong to \(\{-1,0,1\}\). The final inequality has coefficients
\((K-r)-k\mathbf{1}\{p_t(x^\star)\leq r\}\).
Their magnitudes satisfy the stated bound \(K+k\). The mass equations have coefficients \(1\), and their rational right-hand sides are already included in \(L\).
Thus the dense encoding bound
\(B_{\mathrm{LP}}=O\!\left(L+(m+\tau)\tau d\log(K+k+2)\right)\)
is valid.
Constructing inverse positions takes \(O(\tau m)\) indexing operations. Filling the dense matrix takes \(O((m+\tau)\tau d)\) coefficient operations. The distinction between these operations and bit cost is stated appropriately.
The invoked rational-LP theorem applies: a finite system of rational linear equalities and non-strict inequalities admits exact feasibility testing in time polynomial in its binary encoding length. All its hypotheses hold here.
Accordingly, the claimed bit-operation bound
\(O\!\left([L+(m+\tau)\tau d\log(K+k+2)]^C\right)\)
for a universal constant \(C\) is justified. Explicit rankings bound \(m\) and \(\tau\) polynomially in \(L\); unary encoding bounds \(k\) polynomially in \(L\); and \(K<m\). There is no hidden exponential expansion.
Nonnegativity and the type-mass equations imply \(0\leq\lambda_{t,r}\leq\mu_t\). The feasible region is therefore a bounded rational polytope.
The stated rational-vertex property applies even if the polytope has lower affine dimension. A nonempty bounded rational polytope has a rational vertex with encoding length polynomial in its defining data.
Dividing its coordinates by \(k\) preserves rationality and polynomial encoding length. The construction uses at most \(\tau dk\) extensions, and the stated \(O(\tau dk(m+k))\) candidate-symbol cost for writing their rankings is correct. The prover appropriately describes this as symbol operations, rather than a complete bit-cost bound for the witness.
The attribution to Proposition 7 is accurate: the cited paper states the finite-voter NP-completeness result for every fixed pair \(K,k\geq3\). Its model requires one extension per voter. [Chevaleyre et al., *New Candidates Welcome!*, Proposition 7](https://arxiv.org/pdf/1111.3690)
That result does not establish hardness for the mass-splitting model. The prover’s continuous construction explicitly uses the additional splitting freedom.
No mathematical repairs or additional clarifications are 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.