Answer: Under dense explicit-vector encoding the problem is \(\mathrm{P}\); under sparse-support encoding it is \(\mathrm{NP}\)-complete.
Theorem 4 — class: hardness
For any 0 ≤α ≤1, GNSP-STV is NP- complete to compute, where the tie-breaking mechanism is LEX, FA, MPSR+LEX or MPSR+FA.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), ranking types \(T=L(C)\), a rational society \(\mu\in\mathbb{Q}_{\ge 0}^{T}\) with \(\sum_t\mu_t=1\), and lexicographic tie-breaking, let \(a=\mathrm{STV}(\mu)\). Decide whether there exist \(b\ne a\) and rational abstention masses \(\nu_t\) such that \(0\le\nu_t\le\mu_t\), \(\sum_t\nu_t>0\), \(\nu_t>0\Rightarrow b\succ_t a\), and \(\mathrm{STV}(\mu-\nu)=b\).
Given a finite candidate set \(C\) with a fixed lexicographic order, let \(L(C)\) be its strict rankings. A rational society is \(\mu\in\mathbb{Q}_{\ge0}^{L(C)}\) with \(\sum_t\mu_t=1\). Under STV, repeatedly eliminate the candidate with least current first-place mass among remaining candidates, transferring each ranking's mass to its highest remaining candidate; lexicographic tie-breaking resolves every tie.
Target. Is deciding whether there exist \(b e a=\mathrm{STV}(\mu)\) and \( u\in\mathbb{Q}_{\ge0}^{L(C)}\) such that \(0\le u_t\le\mu_t\), \(\sum_t u_t>0\), \( u_t>0\Rightarrow b\succ_t a\), and \(\mathrm{STV}(\mu- u)=b\), NP-hard or in \(\mathrm{P}\)?
Nearest known results. For finite profiles of individual voters, the analogous STV group no-show problem is NP-complete under lexicographic tie-breaking. No result for the rational-mass version was verified.
The answer depends on how the society \(\mu\) is encoded.
Thus the literal full-vector formulation in the question is polynomial-time solvable. The sparse-support formulation, which is usually the more succinct representation, remains hard despite allowing fractional abstention.
If \(C\) is a constant rather than part of the input, both encodings give a polynomial-time problem.
Let \(m=|C|\), and let \(\triangleleft\) denote the lexicographic elimination priority: \(c\triangleleft d\) means that when \(c\) and \(d\) have equal least tally, \(c\) is eliminated first.
Compute \(a=\operatorname{STV}(\mu)\). Fix \(b\neq a\) and an elimination order
\[ \sigma=(c_1,\ldots,c_{m-1},c_m) \]
with \(c_m=b\). For round \(i\), let
\[ S_i=C\setminus\{c_1,\ldots,c_{i-1}\}. \]
For a ranking \(t\), write \(h_t(S_i)\) for its highest-ranked candidate in \(S_i\). Given abstention masses \(\nu\), define the round-\(i\) tally
\[ F_{i,c}(\nu)=\sum_{\substack{t\in L(C)\\h_t(S_i)=c}}(\mu_t-\nu_t). \]
The order \(\sigma\) is exactly the STV elimination order of \(\mu-\nu\) if, for every \(i<m\) and every \(d\in S_i\setminus\{c_i\}\),
Indeed, equality is permitted precisely when the lexicographic rule chooses \(c_i\) rather than \(d\).
The abstention restrictions are linear:
All strict inequalities can be handled by one common slack variable \(\varepsilon\). Consider the rational linear program maximizing \(\varepsilon\), subject to
This program has optimum greater than \(0\) if and only if there is a valid positive abstention realizing \(\sigma\).
For the forward direction, take a feasible abstention. Its total abstention and all finitely many required strict tally gaps are positive, so their minimum supplies a positive \(\varepsilon\). The reverse direction follows directly from the constraints.
Consequently, feasibility for a prescribed winner and elimination order is decidable by rational linear programming in polynomial time.
Suppose all \(m!\) coordinates of \(\mu\) are explicitly represented. Let \(N\) be the bit length of this representation. Then \(m!\leq N\).
There are exactly \(m!\) possible elimination orders. For every order whose last candidate differs from \(a\), solve the linear program above. Each program has
Exact rational linear programming is polynomial-time solvable. Since the number \(m!\) of linear programs is itself at most \(N\), the total running time is polynomial in \(N\).
Soundness follows because an accepted program explicitly realizes an STV elimination order ending at a preferred new winner. Conversely, any successful abstention induces one of the enumerated elimination orders and therefore makes the corresponding program attain a positive value of \(\varepsilon\).
Hence the dense explicit-vector problem belongs to \(\mathrm{P}\).
Suppose instead that the input lists only the \(\tau\) rankings having positive mass.
A nondeterministic algorithm guesses \(b\neq a\) and an elimination permutation ending at \(b\), then solves the corresponding linear program with only the \(\tau\) supported rankings as variables. The guessed permutation has polynomial length, and the linear program has polynomial size.
Therefore the sparse-support problem belongs to \(\mathrm{NP}\).
We give a reduction from restricted exact cover by \(3\)-sets, denoted \(\mathrm{RXC3}\). This is the endpoint-forcing construction underlying the finite-profile STV hardness proof in [Theorem 4 of the IJCAI 2024 paper](https://www.ijcai.org/proceedings/2024/0328.pdf), with the additional argument showing that fractional abstention creates no new solutions.
An instance consists of
\[ X=\{x_1,\ldots,x_q\},\qquad \mathcal S=\{S_1,\ldots,S_q\}, \]
where every \(S_i\) has three elements and every element occurs in exactly three sets. We may assume \(q\geq6\) and \(q\) is divisible by \(3\).
Use candidates
\[ \{w,c,d_0,d_1,\ldots,d_q\} \cup \{b_i,\bar b_i:1\leq i\leq q\}. \]
Choose the lexicographic labels so that \(\bar b_i\triangleleft b_i\) for every \(i\). Each displayed ranking is completed by placing all unlisted candidates after the displayed prefix in any fixed order.
The unnormalized profile consists of the following types.
| Multiplicity | Ranking prefix |
|---:|---|
| \(12q\) | \(c\succ w\succ\text{others}\) |
| \(12q-1\) | \(w\succ c\succ\text{others}\) |
| \(10q+\frac{2q}{3}\) | \(d_0\succ w\succ c\succ\text{others}\) |
| \(12q-2\), for each \(j\) | \(d_j\succ w\succ c\succ\text{others}\) |
| \(6q+4i-2\), for each \(i\) | \(b_i\succ\bar b_i\succ w\succ c\succ\text{others}\) |
| \(2\), for each \(i\) | \(b_i\succ d_0\succ w\succ c\succ\text{others}\) |
| \(6q+4i-6\), for each \(i\) | \(\bar b_i\succ b_i\succ w\succ c\succ\text{others}\) |
| \(2\), for each \(i\) and \(x_j\in S_i\) | \(\bar b_i\succ d_j\succ w\succ c\succ\text{others}\) |
| \(1\), for each \(i\) | \(\bar b_i\succ b_i\succ c\succ w\succ\text{others}\) |
There are at most \(8q+3\) supported rankings. Divide every multiplicity by the total mass \(W\) to obtain a rational society of total mass \(1\). Since STV is homogeneous under positive scaling, we may continue working with the displayed unnormalized masses.
Initially,
\[ \operatorname{sc}(c)=12q,\qquad \operatorname{sc}(w)=12q-1, \]
\[ \operatorname{sc}(d_0)=10q+\frac{2q}{3},\qquad \operatorname{sc}(d_j)=12q-2, \]
and
\[ \operatorname{sc}(b_i)=6q+4i,\qquad \operatorname{sc}(\bar b_i)=6q+4i+1. \]
Thus \(b_1,b_2,\ldots,b_q\) are eliminated in that order. When \(b_i\) is eliminated, its two ballots of the second \(b_i\)-type transfer to \(d_0\), while its other ballots transfer to \(\bar b_i\).
After these \(q\) rounds, every \(d_j\) still has tally \(12q-2\), whereas \(w\) has tally \(12q-1\). Hence some \(d_j\) is eliminated and transfers its entire tally to \(w\). Candidate \(w\) then has at least \(24q-3\).
No pair candidate can ever accumulate \(20q\), \(d_0\) can never accumulate \(13q\), and no \(d_j\) can ever accumulate \(13q\). Candidate \(c\), while \(w\) remains, can receive at most its initial \(12q\) mass and the \(q\) unit ballots ranking \(c\succ w\). Thus \(w\) is never subsequently eliminated and wins. Therefore \(a=w\).
Consider any successful abstention with new winner \(y\neq w\). Suppose first that \(y\neq c\).
The \(12q\) ballots beginning \(c\succ w\) and the \(12q-1\) ballots beginning \(w\succ c\) both rank \(w\) above \(y\). They therefore cannot abstain.
Since \(y\) wins, one of \(c,w\) must eventually be eliminated. They are adjacent in every ranking. When the first of them is eliminated, all its current mass transfers to the other. The surviving candidate then contains the two undeleted blocks above and hence has tally at least \(24q-1\).
Before reaching \(c\) or \(w\), the total mass that can accumulate at any other candidate is bounded by
\[ \operatorname{sc}(b_i)\leq12q+8i-5<20q, \]
\[ \operatorname{sc}(\bar b_i)\leq12q+8i-1<20q, \]
\[ \operatorname{sc}(d_0)\leq12q+\frac{2q}{3}<13q, \qquad \operatorname{sc}(d_j)\leq12q+4<13q. \]
These bounds include every ballot that can ever transfer to the indicated candidate. Hence the survivor of \(c,w\), with at least \(24q-1\), can never be eliminated and must win. This contradicts \(y\notin\{c,w\}\).
Therefore every successful no-show deviation has new winner \(c\).
The only rankings preferring \(c\) to \(w\) are
Let \(r\in[0,12q]\) be the deleted mass of the first type, and let \(z_i\in[0,1]\) be the deleted mass of the \(i\)-th unit type.
During the first \(q\) relevant rounds, the two candidates of pair \(i\) have tallies
\[ 6q+4i \quad\text{and}\quad 6q+4i+1-z_i. \]
If \(z_i<1\), then \(b_i\) is strictly lower and is eliminated. If \(z_i=1\), the tallies are equal and the chosen lexicographic order eliminates \(\bar b_i\).
Thus a fractional value \(0<z_i<1\) has exactly the same combinatorial effect as \(z_i=0\). Define
\[ I=\{i:z_i=1\},\qquad k=|I|. \]
Conditional on \(c\) eventually winning, the first \(q\) eliminations must be one candidate from each pair in increasing order of \(i\). Indeed, the eliminated member of an unprocessed pair has tally at most \(10q\), while \(d_0,d_j,w\) and every processed pair survivor have strictly larger tallies. If \(c\) were selected instead, it could not win.
After these \(q\) rounds, the tallies are
\[ \operatorname{sc}(w)=12q-1,\qquad \operatorname{sc}(c)=12q-r, \]
\[ \operatorname{sc}(d_0) = 12q+\frac{2q}{3}-2k, \]
and
\[ \operatorname{sc}(d_j) = 12q-2+2r_j, \]
where
\[ r_j=|\{i\in I:x_j\in S_i\}|. \]
Every surviving pair candidate has tally strictly greater than \(12q\).
If some \(d_j\) or \(d_0\) has tally below \(w\), then either \(c\) is eliminated first, or such a \(d\)-candidate is eliminated and transfers all its mass to \(w\). In the latter case \(w\)'s tally becomes greater than \(20q\), while every rival remains below \(20q\). Consequently \(w\) wins. Therefore, for \(c\) to win, \(w\) must be eliminated before every \(d\)-candidate.
The inequalities necessary for this are
\[ 12q-2+2r_j\geq12q-1 \]
for every \(j\), and
\[ 12q+\frac{2q}{3}-2k\geq12q-1. \]
The first family gives \(r_j\geq1\), so the sets indexed by \(I\) cover every element. The second gives
\[ k\leq\frac q3. \]
Because every selected set contains exactly three elements,
\[ 3k=\sum_{j=1}^q r_j\geq q, \]
and hence \(k\geq q/3\). Therefore \(k=q/3\), and every \(r_j=1\). The sets indexed by \(I\) form an exact cover.
Conversely, suppose \(I\) indexes an exact cover. Delete the entire unit ballot \(\bar b_i\succ b_i\succ c\succ w\) for every \(i\in I\), and delete no other mass.
After the first \(q\) pair eliminations,
\[ \operatorname{sc}(d_0)=\operatorname{sc}(d_j) =\operatorname{sc}(c)=12q \]
for every \(j\), while
\[ \operatorname{sc}(w)=12q-1. \]
Thus \(w\) is uniquely eliminated. Its \(12q-1\) ballots transfer to \(c\), giving \(c\) tally \(24q-1\). All remaining candidates have tally below \(20q\), and subsequent transfers reach \(c\) before any unlisted candidate. Hence \(c\) wins.
Every deleted ballot ranks \(c\) above \(w\), and the deleted mass is positive. This is a valid rational-mass group no-show witness.
We have proved that the constructed rational society admits a successful abstention if and only if the \(\mathrm{RXC3}\) instance has an exact cover. The reduction has polynomially many supported rankings and polynomial bit length. Therefore the sparse-support problem is \(\mathrm{NP}\)-hard and, together with Section 3, \(\mathrm{NP}\)-complete.
The continuous relaxation does not by itself remove the discrete hardness: the STV gadget forces every relevant fractional variable to reach an endpoint before it affects the elimination order. Nevertheless, the full \(L(C)\)-coordinate representation is factorially padded, making exhaustive enumeration of elimination orders polynomial in that representation size.
⟨structured verdict parsed — rendered above⟩
The prover correctly distinguishes two non-equivalent input encodings:
The fixed-elimination-order linear program is correct, and the RXC3 reduction successfully prevents genuinely fractional choices from bypassing the discrete exact-cover condition. I found no false central step.
The only gap is a minor complexity-theoretic omission concerning the restriction \(q\ge 6\).
Let \(\sigma=(c_1,\ldots,c_m)\) be a proposed elimination order.
The stated comparison constraints correctly encode lexicographic elimination:
Comparing \(c_i\) separately with every remaining \(d\) is sufficient to ensure that \(c_i\) is the candidate eliminated in that round.
The abstention constraints also match the target:
The common slack variable \(\varepsilon\) is valid. For any feasible witness, the total abstention and the finitely many strict tally gaps are positive rational numbers, so their minimum is positive. Conversely, \(\varepsilon>0\) enforces both nonempty abstention and every required strict comparison.
Thus a fixed elimination order is realizable exactly when the corresponding rational LP has positive optimum.
If all \(m!\) coordinates are explicitly encoded, then the input length \(N\) satisfies \(m!\le N\), up to the fixed overhead of the encoding.
There are \(m!\) possible elimination orders. Each associated LP has polynomial size in \(N\), and exact rational linear programming is polynomial-time solvable. Running at most \(m!\le N\) such LP computations is therefore polynomial in \(N\).
The completeness argument is also correct: every successful abstention produces one of the enumerated elimination orders.
Hence the dense problem is in \(\mathrm P\).
A certificate may specify the proposed new winner and elimination permutation. Once these are fixed, the existence of suitable abstention masses is decided by a polynomial-size rational LP over the supported rankings.
Using a deterministic polynomial-time LP algorithm inside a nondeterministic computation is legitimate. Therefore the sparse problem belongs to \(\mathrm{NP}\).
The initial tallies were computed correctly:
The \(b_i\) candidates are eliminated in increasing order. Their large blocks transfer to \(\bar b_i\), while their two special ballots transfer to \(d_0\). After these rounds, a \(d_j\) is below \(w\), is eliminated, and transfers to \(w\).
The claimed global capacity bounds also check out:
After receiving one \(d_j\) tally, \(w\) has at least \(24q-3\), so it cannot subsequently be eliminated. Thus the original winner is indeed \(w\).
The construction has \(3q+3\) candidates, at most \(8q+3\) supported rankings, and polynomial-size rational weights after normalization.
Suppose the new winner is \(y\notin\{c,w\}\). The blocks beginning \(c\succ w\) and \(w\succ c\) both rank \(w\) above \(y\), so none of their combined mass \(24q-1\) is eligible to abstain.
Because \(c\) and \(w\) are adjacent in every completed ranking, when the first of them is eliminated its mass transfers to the other. The survivor then has at least \(24q-1\), while every other candidate has capacity below \(20q\). It therefore cannot be eliminated.
This correctly rules out every new winner other than \(c\).
For a deviation making \(c\) win, the only eligible ranking types are precisely:
Writing their deleted masses as \(r\) and \(z_i\), the pair tallies are correctly given by \(6q+4i\) and \(6q+4i+1-z_i\).
Thus:
A fractional value strictly between \(0\) and \(1\) cannot reproduce the branch obtained at \(z_i=1\). Moreover, its small effect on the surviving pair tally does not affect the later critical round because every survivor remains strictly above \(12q\).
Conditional on \(c\) winning, the first \(q\) eliminations must process the pairs in increasing order. The stated comparisons are sufficient: every unprocessed eliminand has tally at most \(10q\), while every \(d\)-candidate, \(w\), and every processed survivor is strictly higher; eliminating \(c\) would contradict the assumed outcome.
After the pair rounds, the tallies are correctly calculated as:
If a \(d\)-candidate is eliminated before \(w\), its mass transfers to \(w\), placing \(w\) above \(20q\); the previously verified capacity bounds then ensure that \(w\) wins. Therefore a successful deviation requires every \(d\)-candidate to have tally at least that of \(w\).
These necessary inequalities yield \(r_j\ge1\) for every element and \(k\le q/3\). Since each selected set contains exactly three elements, \(\sum_j r_j=3k\ge q\), giving \(k\ge q/3\). Hence \(k=q/3\) and every \(r_j=1\), exactly the required exact cover.
No unjustified integrality is imposed on the abstention variables here: integrality enters only through the endpoint set \(I=\{i:z_i=1\}\).
For an exact cover, deleting the corresponding unit ballots gives, after the pair rounds:
Therefore \(w\) is uniquely eliminated and transfers its \(12q-1\) mass to \(c\). Candidate \(c\) then has \(24q-1\), above the global capacity of every rival. Every deleted ballot prefers \(c\) to \(w\), so the witness satisfies the target conditions.
The proof says “we may assume \(q\ge6\)” without explaining why RXC3 remains NP-hard under this restriction. The cited source defines RXC3 with \(q\) divisible by \(3\) and identifies it as NP-complete, so the intended restriction is harmless: excluding the finitely many instances with \(q<6\) does not affect NP-hardness. Nevertheless, that justification should be stated explicitly. See the [cited IJCAI paper](https://www.ijcai.org/proceedings/2024/0328.pdf).
Minimum clarification needed: add one sentence explaining that an algorithm for instances with \(q\ge6\), combined with brute force on the finitely many smaller instances, would solve unrestricted RXC3.
⟨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.