Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePossibleWinner is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a finite support \(\mathcal T\) of incomplete total-order types with positive rational masses \(\mu_P\) summing to \(1\), a target \(c^\star\), and a fixed elimination tie priority, is there an allocation \(x_{P,\pi}\ge 0\) over consistent complete rankings \(\pi\in\mathcal L(P)\), satisfying \(\sum_{\pi\in\mathcal L(P)}x_{P,\pi}=\mu_P\) for every \(P\), such that STV on the resulting ranking masses elects \(c^\star\), using a strict-majority quota of \(1/2\)?
Let \(C\) be a nonempty candidate set of unbounded size \(m\), with target \(c^\star\in C\) and a given strict elimination priority. Each incomplete ranking type \(P\) specifies a strict partial order of known comparisons; unknown comparisons may be completed, but preference ties and declared incomparability are excluded. Let \(\mathcal L(P)\) be its consistent complete strict rankings.
A society is given by its support: the list \(\mathcal T\) of the \(\tau\) types with positive mass, each mass \(\mu_P\) a binary rational, with \(\sum_{P\in\mathcal T}\mu_P=1\). Here \(\tau\) is the support size, not the number of possible types; \(L\) is the total input bit length. State running times in \(m,\tau,L\).
An allocation consists of real masses \(x_{P,\pi}\geq0\) for \(\pi\in\mathcal L(P)\), satisfying \(\sum_{\pi\in\mathcal L(P)}x_{P,\pi}=\mu_P\). The allocation is fixed throughout the election.
Use single-winner STV on these masses: each ranking contributes its mass to its highest remaining candidate. Elect a candidate whose tally is strictly greater than \(1/2\); otherwise eliminate one candidate of minimum tally, choosing the earliest in the elimination priority among tied minima, and repeat. Transfers preserve each ranking's entire mass.
Is deciding whether some such allocation elects \(c^\star\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For discrete unweighted voters and unboundedly many candidates, STV possible-winner decision is NP-complete, even with only one unknown vote; the result does not depend on tie-breaking ([Pini–Rossi–Venable–Walsh](https://cgi.cse.unsw.edu.au/~tw/prvwaij11.pdf)).
No result settling this exact divisible-mass completion problem was identified in the literature search.
The problem is \(\mathrm{NP}\)-complete. This holds even when every incomplete type has exactly two consistent rankings, differing only in the order of its first two candidates.
The hardness proof below allows arbitrary real allocations. Its Boolean choices are encoded by which candidates are eliminated, so fractional splitting does not invalidate the reduction.
Let a \(\mathrm{3SAT}\) instance have variables \(z_1,\ldots,z_n\) and clauses \(D_1,\ldots,D_q\), with \(n,q\geq1\). Each clause has three literal occurrences; repetitions are allowed.
We construct an election with target \(p=c^\star\), rival \(r\), variable candidates \(a_i,b_i\), and clause candidates \(h_j,g_j\). Thus
\[ m=2n+2q+2. \]
We first specify unnormalized rational weights. Dividing every weight by their total \(W\) gives the required masses. During the proof, tallies refer to unnormalized weights, so the majority threshold is \(W/2\).
Set
\[ \delta=\frac{1}{100(n+q+1)},\qquad A=\frac34. \]
Let \(d_i^+\) and \(d_i^-\) count the positive and negative occurrences of \(z_i\). In particular,
\[ d_i^+,d_i^-\leq3q,\qquad q\delta<\frac1{100},\qquad \delta\leq\frac1{300}. \]
In every ranking below, append all unlisted candidates in an arbitrary fixed strict order after \(p\). Consequently, these tails cannot affect transfers while \(p\) remains.
For each variable \(z_i\), introduce:
| Weight | Ranking or partial ranking |
|---|---|
| \(A-d_i^+\delta\) | \(a_i>b_i>p>\cdots\) |
| \(A-d_i^-\delta\) | \(b_i>a_i>p>\cdots\) |
| \(\delta\), for each positive occurrence in \(D_j\) | \(a_i>h_j>p>\cdots\) |
| \(\delta\), for each negative occurrence in \(D_j\) | \(b_i>h_j>p>\cdots\) |
| \(\delta\) | Both \(a_i,b_i\) precede \(p\); only their mutual comparison is unknown; the tail is fixed |
The last type has exactly two linear extensions:
\[ a_i>b_i>p>\cdots,\qquad b_i>a_i>p>\cdots. \]
All weights are positive, since
\[ A-d_i^\pm\delta>\frac34-\frac3{100}>0. \]
For each clause \(D_j\), introduce:
| Weight | Ranking |
|---|---|
| \(1-\delta/2\) | \(h_j>g_j>p>\cdots\) |
| \(1-\delta\) | \(g_j>h_j>p>\cdots\) |
| \(\delta\) | \(g_j>p>\cdots\) |
Finally introduce:
| Weight | Ranking |
|---|---|
| \(1+4\delta\) | \(p>\cdots\) |
| \(1+(q+7/2)\delta\) | \(r>p>\cdots\) |
Choose any strict elimination priority. The proof works for every such choice.
Identical types can be merged by adding their weights. The support size satisfies
\[ \tau\leq3n+6q+2. \]
The total weight is
\[ W=\frac{3n}{2}+2q+2+ \left(n+\frac q2+\frac{15}{2}\right)\delta. \]
In particular, \(W\geq11/2\). All normalized masses have bit length \(O(\log(n+q+1))\), and all rankings and partial orders have polynomial-size descriptions. This is therefore a polynomial-time construction.
Fix an arbitrary allocation, including allocations using nonrational real masses.
For variable \(i\), let \(y_i\in[0,\delta]\) be the mass assigned to the completion beginning \(a_i>b_i\). Initially,
\[ t(a_i)=A+y_i,\qquad t(b_i)=A+\delta-y_i. \]
Both lie in \([A,A+\delta]\).
When the first member of this pair is eliminated:
If the eliminated member has \(d\) literal occurrences, the survivor consequently has tally
\[ 2A+\delta-d\delta. \]
Hence its tally lies strictly between \(147/100\) and \(8/5\).
Meanwhile, every clause candidate has tally at least \(1-\delta/2\), and \(p,r\) each have tally greater than \(1\). Since
\[ A+\delta<1-\delta/2, \]
as long as an untouched variable pair exists, the minimum-tally candidate belongs to an untouched pair. A surviving member cannot be eliminated during this phase.
Thus exactly one member of every variable pair is eliminated before any other candidate. Define
\[ z_i=\mathrm{true}\quad\text{if }a_i\text{ is eliminated first}, \]
and define \(z_i=\mathrm{false}\) if \(b_i\) is eliminated first.
Equal splits cause no difficulty: the given priority determines the first elimination and therefore the assignment.
Conversely, every Boolean assignment is realizable. To eliminate \(a_i\) first, assign all incomplete mass to the completion beginning \(b_i>a_i\); to eliminate \(b_i\) first, use the opposite completion. These choices make the desired elimination strict.
At the end of this phase, let \(k_j\) be the number of true literal occurrences in clause \(D_j\). Exactly those occurrences have sent their packets to \(h_j\). Therefore,
\[ t(h_j)=1-\delta/2+k_j\delta,\qquad t(g_j)=1. \]
In particular, \(k_j\geq1\) precisely when the induced assignment satisfies \(D_j\).
Consider a clause pair before either member has been eliminated.
If \(D_j\) is unsatisfied, then \(k_j=0\), and
\[ t(h_j)=1-\delta/2<1=t(g_j). \]
Thus \(h_j\) is eliminated first. Its entire mass transfers to \(g_j\), giving
\[ t(g_j)=2-\delta/2. \]
No mass transfers to \(p\).
If \(D_j\) is satisfied, then \(k_j\geq1\), and
\[ t(h_j)=1+(k_j-1/2)\delta>1=t(g_j). \]
Thus \(g_j\) is eliminated first. Its mass \(1-\delta\) transfers to \(h_j\), while its mass \(\delta\) transfers directly to \(p\). The surviving \(h_j\) has tally
\[ t(h_j)=2+(k_j-3/2)\delta. \]
Since \(1\leq k_j\leq3\), every processed clause survivor has tally between \(2-\delta/2\) and \(2+3\delta/2\).
These pairwise conclusions describe the actual global elimination order. Indeed:
\[ t(p)=1+(4+s)\delta>1; \]
\[ t(r)=1+(q+7/2)\delta>1. \]
Both finalist tallies remain below \(11/10\). Therefore, while an unprocessed clause pair exists, the next eliminated candidate belongs to such a pair. Within that pair, the strict comparison above determines which member is eliminated.
After exactly one member of every clause pair has been eliminated, if the assignment satisfies \(s\) clauses, then
\[ t(p)=1+(4+s)\delta,\qquad t(r)=1+(q+7/2)\delta. \]
Until this point, every candidate’s tally is at most \(2+3\delta/2<21/10\). Since
\[ W/2\geq11/4, \]
no candidate has achieved a strict majority. Thus the election has indeed performed all the eliminations just described.
If \(s\leq q-1\), then
\[ t(r)-t(p)=(q-s-1/2)\delta\geq\delta/2>0. \]
Every remaining variable candidate has tally greater than \(147/100\), and every remaining clause candidate has tally at least \(2-\delta/2\). Both finalists have tally below \(11/10\).
Consequently, \(p\) is the unique minimum-tally candidate and is eliminated next. It cannot win.
If \(s=q\), then
\[ t(p)-t(r)=\delta/2>0. \]
The rival is now the unique minimum-tally candidate. Its entire mass transfers to \(p\), giving the target tally
\[ H=2+(2q+15/2)\delta. \]
We check that subsequent transfers cannot endanger \(p\).
All remaining clause candidates are \(h_j\), since every \(g_j\) has been eliminated. While \(h_j\) remains, the only masses it can hold are:
Thus, throughout the remainder of the election,
\[ t(h_j)\leq2+3\delta/2<H. \]
Each variable survivor has tally at most \(3/2+\delta<H\). It receives no further transfers from other candidates: every relevant ranking places \(p\) before unrelated variable candidates.
The target’s tally is nondecreasing. Therefore, it remains strictly above every other remaining candidate. It cannot be eliminated. Nor can another candidate obtain a strict majority: that candidate and the still-higher target would together exceed the total weight.
The process therefore elects \(p\), either at an earlier majority or when it is the sole remaining candidate.
Combining both directions,
\[ \text{some allocation elects }p \quad\Longleftrightarrow\quad \text{the formula is satisfiable}. \]
This proves \(\mathrm{NP}\)-hardness, with arbitrary real splitting and the stated majority and priority rules.
The remaining issue is that an allocation may use real masses and exponentially many rankings. We show that every yes-instance has a polynomial-size rational certificate.
Temporarily continue eliminating minimum-tally candidates even after a strict majority appears.
If candidate \(w\) has tally greater than \(1/2\), every other candidate has smaller tally. Moreover, \(w\)’s tally cannot decrease. Thus \(w\) survives every subsequent elimination and is the sole final survivor.
Hence the original rule elects \(c^\star\) exactly when this continued elimination process leaves \(c^\star\) last.
Suppose a real allocation leaves \(c^\star\) last, with elimination order \(e_1,\ldots,e_{m-1}\). For each round \(r\), let \(S_r\) be its remaining candidate set and let \(t_{r,a}(x)\) denote candidate \(a\)’s tally. These are linear functions of the allocation variables, with coefficients in \(\{0,1\}\).
Introduce a slack variable \(\varepsilon\), constrained by \(0\leq\varepsilon\leq1\). Impose the type-mass equations and nonnegativity constraints. For every opponent \(a\in S_r\setminus\{e_r\}\), impose:
\[ t_{r,a}(x)-t_{r,e_r}(x)\geq\varepsilon \]
if \(a\) precedes \(e_r\) in elimination priority, and otherwise impose
\[ t_{r,a}(x)-t_{r,e_r}(x)\geq0. \]
These are exactly the required minimum-tally comparisons, with strictness wherever a tie would eliminate \(a\) instead.
The given allocation satisfies every required strict inequality. Since there are finitely many such inequalities, a positive common slack exists. If none requires strictness, take \(\varepsilon=1\).
Maximize \(\varepsilon\). The feasible set is a bounded rational polytope: each allocation coordinate is between zero and its type mass, and \(\varepsilon\in[0,1]\). Therefore an optimal vertex exists, with positive objective value.
There are \(\tau\) type equations, \(\binom m2\) tally comparisons, and the upper bound on \(\varepsilon\). Set
\[ K=\tau+\binom m2+1. \]
At a vertex, at most \(K\) coordinates can be positive. To justify this, if more were positive, the active equations and inequalities restricted to those coordinates would have a nonzero null direction. A sufficiently small perturbation in either direction would preserve positivity and all inactive inequalities, contradicting extremality.
Thus the optimal vertex uses at most \(K\) positive allocation masses.
After restricting to its positive coordinates, choose an independent square system of active constraints. Its coefficients belong to \(\{-1,0,1\}\). The right-hand sides are input masses or zero or one. A common denominator has bit length \(O(L)\). Cramer’s rule and the determinant bound give each coordinate bit length
\[ O\!\left(L+K\log(K+1)\right). \]
Hence a certificate consists of at most \(K\) consistent complete rankings, their type identifiers, and rational masses of polynomial bit length.
A verifier checks consistency with each partial order, checks the type-mass sums, and simulates STV using exact rational arithmetic. Its running time is \(\operatorname{poly}(m,\tau,L)\).
Therefore the problem belongs to \(\mathrm{NP}\).
The problem is \(\mathrm{NP}\)-complete, so a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
For completeness, an exact deterministic upper bound is
\[ 2^{O(m\log(m+1))}\operatorname{poly}(\tau,L). \]
Enumerate the at most \(m!\) rankings for each supported type and the \((m-1)!\) elimination orders ending in \(c^\star\). For each order, solve the rational linear program above and test whether its maximum slack is positive. Each program has at most \(\tau m!+1\) variables and polynomial explicit encoding length in \(\tau m!,m,L\); polynomial-time rational linear programming therefore gives the stated bound.
⟨structured verdict parsed — rendered above⟩
The reduction is correct in substance and handles arbitrary real splitting. The membership argument also establishes a polynomial-size rational certificate. I found no false step or major gap. There is one minor omission: the determinant bound used for certificate bit lengths is neither identified nor stated precisely.
Adjudication: proved with minor gaps. The output establishes \(\mathrm{NP}\)-completeness, subject to that routine clarification.
The construction uses \(2n+2q+2\) candidates, as claimed. The incomplete variable type has exactly two consistent rankings, provided the description fixes all comparisons except \(a_i\) versus \(b_i\); the output explicitly specifies this.
Positivity of the fixed variable weights follows from \(d_i^\pm\leq3q\) and \(q\delta<1/100\). All other weights are positive as well.
The weight accounting is correct:
These sum to the stated
\(W=3n/2+2q+2+(n+q/2+15/2)\delta\).
In particular, \(W\geq11/2\).
Before merging, there are \(3n\) variable base and incomplete types, \(3q\) occurrence packets, \(3q\) clause types, and two finalist types. Thus the support bound \(\tau\leq3n+6q+2\) is valid. Merging identical types preserves the available allocations and election behavior.
The normalized masses have the claimed logarithmic bit length. The rankings and partial orders have polynomial descriptions, so the reduction has polynomial output size.
For every real split \(y_i\in[0,\delta]\), the initial tallies are correctly computed as
\(t(a_i)=A+y_i\) and \(t(b_i)=A+\delta-y_i\).
When the first member of a pair is eliminated, its occurrence packets leave the pair, while its fixed base mass and all incomplete mass remain with the survivor. The resulting tally \(2A+\delta-d\delta\) is correct and independent of the split.
The stated bounds hold throughout the permitted parameter range:
the survivor has tally strictly above \(147/100\) and below \(8/5\), whereas an untouched pair has both tallies at most \(A+\delta<1-\delta/2\).
Clause candidates cannot fall below their initial tallies during this phase, and both finalists start above \(1\). Consequently, whenever an untouched pair remains, the next eliminated candidate belongs to such a pair. Exactly one member of each pair is eliminated.
Equal splits are correctly handled by the prescribed elimination priority. For either desired Boolean value, assigning the entire incomplete mass to the specified completion gives a strict comparison within that pair. Other pairs may affect the order in which variables are processed, but cannot change the selected member of a pair.
The induced assignment and the literal-packet accounting agree: positive packets transfer precisely when \(a_i\) is eliminated, and negative packets transfer precisely when \(b_i\) is eliminated. Hence the stated \(k_j\) really counts true literal occurrences, including repeated occurrences.
At the start of this phase, the tallies
\(t(h_j)=1-\delta/2+k_j\delta\) and \(t(g_j)=1\)
are correct.
For an unsatisfied clause, \(k_j=0\), so \(h_j\) is strictly smaller. Its entire mass consists of its original ranking type and transfers to \(g_j\), yielding \(2-\delta/2\). There are no occurrence packets at \(h_j\) in this case, so the assertion that nothing transfers to \(p\) is correct.
For a satisfied clause, \(g_j\) is strictly smaller. Its two ranking types transfer \(1-\delta\) to \(h_j\) and \(\delta\) to \(p\), respectively. The survivor tally \(2+(k_j-3/2)\delta\) is correct.
The global-order justification is sufficient. Every unprocessed clause pair contains a candidate of tally at most \(1\), while every variable survivor, processed clause survivor, and finalist has tally strictly above \(1\). Thus the next elimination must occur in an unprocessed pair, and its strict internal comparison determines the eliminated member.
The formulas for the finalist tallies after processing \(s\) satisfied clauses are correct. Both remain below \(11/10\).
The bound \(2+3\delta/2\) covers all candidate tallies through the variable and clause phases, including unprocessed satisfied-clause candidates and processed survivors.
Since \(2+3\delta/2<21/10<11/4\leq W/2\), no majority interrupts these phases. The argument therefore justifies the actual STV eliminations, rather than only a hypothetical sequence without majority stopping.
If \(s\leq q-1\), the difference
\(t(r)-t(p)=(q-s-1/2)\delta\geq\delta/2\)
is correct. Both finalists are below every remaining variable or clause survivor. Therefore \(p\) is the unique minimum and is eliminated next.
If \(s=q\), \(r\) is instead the unique minimum. Its ranking puts \(p\) next, so its entire tally transfers to \(p\), giving the correctly computed
\(H=2+(2q+15/2)\delta\).
The subsequent transfer analysis is valid. Every remaining clause candidate is \(h_j\), and it can receive only its original mass, the specified mass from \(g_j\), and its three occurrence packets. Its tally remains at most \(2+3\delta/2<H\). Each variable survivor remains below \(H\) and receives no additional transfers while \(p\) remains, because all relevant rankings place \(p\) before unrelated variable candidates.
Thus \(p\) remains strictly above every competitor. It cannot be eliminated, and a competitor cannot obtain a strict majority while \(p\) has a larger tally. When \(p\) is alone, it holds the entire mass and satisfies the majority condition.
Both directions of the satisfiability equivalence are established. Fractional allocations introduce no unintended successful case, and the proof does not rely on a particular elimination priority.
Continuing elimination after a strict majority preserves the winner: a majority candidate has larger tally than every other candidate, and its tally cannot decrease. The equivalence with being the final survivor is correct.
For a fixed elimination order, the tally functions are linear with coefficients in \(\{0,1\}\). The priority-dependent inequalities have the correct orientation:
A successful real allocation supplies positive slack for all required strict comparisons because there are finitely many. If no strict comparisons are required, the proposed choice \(\varepsilon=1\) is valid.
The feasible region is nonempty, bounded, and defined by rational constraints. Maximizing \(\varepsilon\) therefore admits an optimal vertex, and its objective is positive.
The support argument is correct. The count \(K=\tau+\binom m2+1\) includes all non-coordinate constraints. At a vertex, more than \(K\) positive coordinates would admit a nonzero perturbation preserving the active constraints and, for sufficiently small perturbations, all remaining constraints.
Here “coordinates” includes \(\varepsilon\). Consequently, the conclusion that there are at most \(K\) positive allocation masses is a valid, slightly loose bound.
Minor issue: the subsequent reference to “the determinant bound” does not identify or state the bound being used. The integer coefficient restriction, rational right-hand sides, and common-denominator estimate supply the necessary hypotheses, and the claimed bit-length estimate is correct in substance. Nevertheless, under the requested standard for cited results, this bound should be explicit.
Minimum clarification: state the determinant bound used for the restricted square system, specify its dimension, and explain how it combines with the common denominator and Cramer’s rule to give the displayed coordinate bit length. No new mathematical argument is needed.
With that clarification, the proposed certificate has polynomial size, and checking ranking consistency, type-mass sums, and exact STV simulation takes \(\operatorname{poly}(m,\tau,L)\) time.
There are at most \(m!\) rankings per type and \((m-1)!\) elimination orders ending in the target. Explicit rational linear programming with the stated variables and constraints consequently fits the claimed bound
\(2^{O(m\log(m+1))}\operatorname{poly}(\tau,L)\).
Testing whether the optimum slack is positive correctly handles strict comparisons, including orders requiring no strict comparisons.
The general membership and enumeration arguments also cover \(m=1\): there are no elimination comparisons, and the sole candidate wins. The reduction’s restriction to \(n,q\geq1\) creates no hardness issue.
The output supplies genuine hardness and membership proofs for the exact continuous problem. The only requested repair is an explicit statement of the determinant estimate used in the certificate-size calculation.
⟨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.