Answer: \(\mathrm{NP}\text{-complete}\), even for dyadic rational masses; an exact deterministic algorithm runs in \(O(2^{\min\{m,\tau\}}m\tau L^2)\) bit operations.
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateIn the unique-winner model, veto-CCPV-TP is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a distinguished candidate \(p\), and a society supported on \(\tau\) strict rankings \(\pi_t\) with rational masses \(\mu_t\ge 0\) summing to \(1\), decide whether there are split masses \(x_t\in[0,\mu_t]\) such that \(x_t\) goes to the first subelection and \(\mu_t-x_t\) to the second, and \(p\) is the unique winner of the runoff among the union of the two ties-promote veto winner sets. The runoff uses the original society restricted to those finalists; an empty subelection promotes all candidates.
Let \(C\) be a nonempty candidate set, \(m=|C|\), and \(p\in C\). A society is given by its support: a list of \(\tau\) distinct strict rankings \(\pi_t\) over \(C\), each with a positive binary rational mass \(\mu_t\), where \(\sum_{t=1}^{\tau}\mu_t=1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
A partition chooses real masses \(x_t\in[0,\mu_t]\), assigning \(x_t\) to the first subelection and \(\mu_t-x_t\) to the second. Both subelections use veto on \(C\), with scores weighted by mass and without renormalizing either subelection.
All tied winners of each subelection advance; an empty subelection promotes all candidates. Let \(F\) be the union of the two winner sets. The runoff uses veto on \(F\), with every original ranking restricted to \(F\) and its original mass retained. A sole finalist wins uniquely.
The decision problem asks whether such a partition makes \(p\) the unique runoff winner.
Is this continuous decision problem solvable in polynomial time, or is it NP-hard under polynomial-time many-one reductions? State running times in \(m\), \(\tau\), and \(L\).
For indivisible, explicitly listed voters, constructive control by partition into two veto subelections with ties promoted is NP-complete in the unique-winner model ([Maushagen and Rothe, 2017](https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2017/pdfs/p615.pdf)). No result settling exactly the divisible-mass formulation above was located.
The continuous decision problem is \(\mathrm{NP}\)-complete under polynomial-time many-one reductions, even when all masses are dyadic rationals.
An exact deterministic algorithm runs in \(O(2^{\min\{m,\tau\}}m\tau L^2)\) bit operations. Thus polynomial-time solvability in the general case would imply \(\mathrm{P}=\mathrm{NP}\).
For each supported ranking, let \(\ell_t\) be its last-ranked candidate. Define the original veto mass of candidate \(c\) by
\(v_c=\sum_{t:\ell_t=c}\mu_t.\)
For a partition, define its first-subelection veto masses by
\(y_c=\sum_{t:\ell_t=c}x_t.\)
The second-subelection veto mass is then \(v_c-y_c\).
In a subelection of total mass \(s\), candidate \(c\)'s veto score is \(s-y_c\). Consequently, the first-subelection winners are exactly the minimizers of \(y_c\), and the second-subelection winners are exactly the minimizers of \(v_c-y_c\). This statement includes empty subelections: all their veto masses are zero, so all candidates advance.
Every vector satisfying \(0\leq y_c\leq v_c\) is realizable. Indeed, for every ranking \(t\), its bottom candidate has \(v_{\ell_t}>0\), and we may set
\(x_t=\mu_t\,y_{\ell_t}/v_{\ell_t}.\)
These assignments satisfy the mass bounds and give the prescribed aggregate veto masses.
Let \(Z=\{c\in C:v_c=0\}\).
Lemma. A nonempty set \(F\subseteq C\) is attainable as the union of the two winner sets exactly under the following conditions:
Proof.
If \(z\in Z\), then \(y_z=v_z-y_z=0\). All veto masses are nonnegative, so \(z\) wins both subelections. Thus every attainable set contains \(Z\).
Conversely, suppose \(Z\neq\varnothing\) and \(Z\subseteq F\). Set \(y_c=0\) for \(c\in F\), and \(y_c=v_c/2\) for \(c\notin F\). The first winner set is exactly \(F\). The second winner set is exactly \(Z\), because every candidate outside \(Z\) has positive second-subelection veto mass. Their union is \(F\).
Now suppose \(Z=\varnothing\) and \(|F|\geq2\). Partition \(F\) into two nonempty disjoint sets \(A,B\). Set
\(y_c=0\) for \(c\in A\), \(y_c=v_c\) for \(c\in B\), and \(y_c=v_c/2\) for \(c\notin F\).
All original veto masses are positive. Therefore the first winner set is exactly \(A\), and the second winner set is exactly \(B\).
Finally, if \(F=\{c\}\), both subelections must have \(c\) as their sole winner. For every \(d\neq c\), this requires
\(y_d>y_c\quad\text{and}\quad v_d-y_d>v_c-y_c.\)
Adding gives \(v_d>v_c\). Conversely, if these strict inequalities hold for the original veto masses, setting \(y_d=v_d/2\) for every candidate makes \(c\) the unique winner of both subelections. This also covers \(m=1\), when there are no competing candidates. \(\square\)
All constructions in this lemma can use \(x_t\in\{0,\mu_t/2,\mu_t\}\).
A certificate is simply a proposed finalist set \(F\) containing \(p\).
First, verify attainability using the lemma. Then define each finalist's runoff veto mass by
\(V_F(c)=\sum_{t:\,c\text{ is last in }\pi_t|_F}\mu_t.\)
The certificate succeeds exactly when
\(V_F(p)<V_F(c)\quad\text{for every }c\in F\setminus\{p\}.\)
For \(F=\{p\}\), this condition is vacuous, as required.
All checks use exact rational arithmetic. Taking the product of the input denominators gives a common denominator with \(O(L)\) bits. After scaling, veto totals are integer sums with \(O(L)\) bits. Scanning the rankings and performing the comparisons takes at most \(O(m\tau L^2)\) bit operations using elementary arithmetic. This proves membership in \(\mathrm{NP}\), without assuming that arbitrary real partitions themselves are certificates.
For a deterministic algorithm, enumerate the attainable sets containing \(p\).
If \(Z=\varnothing\), enumerate subsets of \(C\); moreover, every candidate must occur last in some supported ranking, so \(m\leq\tau\).
If \(Z\neq\varnothing\), enumerate only the optional candidates \(D=C\setminus Z\), because every finalist set contains \(Z\). Each candidate in \(D\) occurs last in some supported ranking, so \(|D|\leq\tau\), and also \(|D|\leq m\).
Thus at most \(2^{\min\{m,\tau\}}\) sets need examination. Including preprocessing, a conservative running-time bound is
\(O(2^{\min\{m,\tau\}}m\tau L^2).\)
We reduce from Vertex Cover: given a simple undirected graph \(G=(V,E)\) and an integer \(k\), decide whether some \(U\subseteq V\) with \(|U|\leq k\) meets every edge. This is a standard \(\mathrm{NP}\)-complete problem; see [CMU’s theorem and reduction](https://www.cs.cmu.edu/~lblum/flac/Lectures_pdf/Lecture19.pdf).
We may restrict to \(E\neq\varnothing\) and \(1\leq k<|V|\). The excluded cases are decidable immediately and can be mapped to fixed restricted yes- and no-instances: a single edge with bound one, and a triangle with bound one, respectively. Hence this restriction remains \(\mathrm{NP}\)-hard.
Write \(V=\{v_1,\ldots,v_r\}\), let \(q=|E|\), and introduce candidates
\(C=\{p,w\}\cup V.\)
For a vertex set \(S\), let \(\operatorname{ord}(S)\) denote its vertices in increasing index order. In the rankings below, this notation expands into that ordered list; an empty list contributes nothing.
Set
\(b=2(r-k)-1,\qquad H=2(r+1).\)
Because \(1\leq k<r\), we have \(b>0\) and \(b<H\).
Construct the following weighted rankings, initially with integer weights:
| Type | Ranking | Weight |
|---|---|---|
| Baseline | \(w\succ\operatorname{ord}(V)\succ p\) | \(b\) |
| Vertex protection, for each \(i\) | \(w\succ p\succ\operatorname{ord}(V\setminus\{v_i\})\succ v_i\) | \(H\) |
| Size constraint, for each \(i\) | \(p\succ\operatorname{ord}(V\setminus\{v_i\})\succ w\succ v_i\) | \(2\) |
| Edge constraint, for each \(\{v_i,v_j\}\in E\), \(i<j\) | \(w\succ\operatorname{ord}(V\setminus\{v_i,v_j\})\succ p\succ v_i\succ v_j\) | \(H\) |
The total weight is
\(W=b+rH+2r+qH.\)
Let \(N\) be the least power of two satisfying \(N\geq W\), and put \(\Delta=N-W\). Increase the weight of the vertex-protection ranking for \(v_1\) by \(\Delta\). Divide every weight by \(N\).
All masses are now positive dyadic rationals summing to one. Merge identical rankings by adding their masses. This produces the required distinct-ranking support and does not change any election outcome.
The output has
\(m=r+2,\qquad \tau\leq2r+q+1,\)
and
\(L=O((r+q)r\log(r+q+2)).\)
Indeed, \(W=O((r+q)(r+1))\), so the denominator and all weights have logarithmic bit length. Constructing and merging the rankings takes polynomial time.
Candidate \(w\) is never last in an original ranking. Candidate \(p\) is last in the positive-weight baseline ranking, and every vertex is last in its positive-weight protection ranking. Therefore
\(Z=\{w\}.\)
By the lemma, every attainable finalist set contains \(w\), and every set containing \(w\) is attainable.
For \(p\) to win, it must also advance. Consequently, the relevant finalist sets are exactly
\(F=\{p,w\}\cup U,\qquad U\subseteq V.\)
This characterization applies to arbitrary real partitions.
Fix such a finalist set. For convenience, measure runoff veto totals in integer units:
\(D_c=N\,V_F(c).\)
Define the number of uncovered edges by
\(z(U)=|\{e\in E:e\cap U=\varnothing\}|.\)
Candidate \(w\). Only size-constraint rankings can veto \(w\). The ranking indexed by \(v_i\) vetoes \(w\) exactly when \(v_i\notin U\). Hence
\(D_w=2(r-|U|).\)
Candidate \(p\). The baseline contributes \(b\). An edge-constraint ranking vetoes \(p\) exactly when neither endpoint survives, contributing \(H\) for each uncovered edge. Protection rankings veto \(p\) exactly when \(U=\varnothing\). Thus
\(D_p=b+Hz(U)+(rH+\Delta)\mathbf{1}_{\{U=\varnothing\}}.\)
Surviving vertices. Each \(v_i\in U\) remains last in its own protection ranking. Therefore
\(D_{v_i}\geq H>b.\)
These calculations give both directions of the reduction.
If \(U\) fails to cover an edge, then \(z(U)\geq1\), so
\(D_p\geq b+H>2r\geq D_w.\)
Thus \(p\) cannot be the unique runoff winner.
If \(U\) covers every edge, then \(z(U)=0\). Since \(E\neq\varnothing\), such a cover is nonempty, so \(D_p=b\). Every surviving vertex has strictly more veto mass than \(p\). Therefore \(p\) wins uniquely exactly when
\(b<D_w.\)
Substituting the definitions gives
\(2(r-k)-1<2(r-|U|)\quad\Longleftrightarrow\quad 2|U|<2k+1\quad\Longleftrightarrow\quad |U|\leq k.\)
The last equivalence uses the integrality of \(|U|\) and \(k\).
Consequently,
\(p\text{ wins uniquely on }\{p,w\}\cup U\quad\Longleftrightarrow\quad U\text{ is a vertex cover with }|U|\leq k.\)
Every finalist set on the left is attainable by a valid divisible-mass partition, and every successful partition produces a set of this form. This proves the required polynomial-time many-one reduction.
The reduction establishes \(\mathrm{NP}\)-hardness for the exact continuous formulation, including arbitrary real splits, ties promoted, empty subelections, and normalized dyadic masses. Together with the finalist-set certificate, it proves \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output establishes NP-completeness for the stated divisible-mass problem, including dyadic masses, and supports the claimed deterministic running-time bound. I found no major or minor mathematical issues requiring repair.
The definitions of \(v_c\) and \(y_c\) correctly aggregate original and first-subelection veto masses. In a subelection of mass \(s\), every candidate receives score \(s\) minus its veto mass, so maximizing score is equivalent to minimizing veto mass.
This remains valid for an empty subelection: every veto mass and score is zero, and all candidates advance.
The realization formula \(x_t=\mu_t y_{\ell_t}/v_{\ell_t}\) is well-defined because \(v_{\ell_t}\geq\mu_t>0\). The assumed bounds \(0\leq y_{\ell_t}\leq v_{\ell_t}\) imply \(0\leq x_t\leq\mu_t\), and summing over rankings with bottom candidate \(c\) gives precisely \(y_c\). Candidates with \(v_c=0\) necessarily have \(y_c=0\). Thus the aggregate description loses no feasible partitions.
All three cases are correct and exhaustive for nonempty finalist sets.
The singleton argument covers \(m=1\), with vacuous comparisons. The claimed choices \(x_t\in\{0,\mu_t/2,\mu_t\}\) also follow from the constructions actually given.
A finalist set containing \(p\) is a polynomial-size certificate. The lemma verifies whether it is attainable, and the runoff depends only on that set and the original weighted rankings.
The strict comparison \(V_F(p)<V_F(c)\) for every other finalist is exactly the unique-winner condition: the runoff gives every finalist the same total participating mass, minus its own veto mass. For a sole finalist, the condition is correctly vacuous.
The rational-arithmetic bound is valid:
The enumeration bound is also correct. When \(Z=\varnothing\), every candidate occurs last in at least one supported ranking, implying \(m\leq\tau\). When \(Z\neq\varnothing\), only candidates in \(C\setminus Z\) are optional, and their number is at most both \(m\) and \(\tau\).
Consequently, the stated bound \(O(2^{\min\{m,\tau\}}m\tau L^2)\) is justified.
The reduction uses the standard NP-complete Vertex Cover decision problem. The cited source states Vertex Cover NP-completeness on slide 107. [CMU lecture notes](https://www.cs.cmu.edu/~lblum/flac/Lectures_pdf/Lecture19.pdf)
The restriction to \(E\neq\varnothing\) and \(1\leq k<|V|\) preserves hardness as explained. The excluded instances are immediately decidable, and the supplied fixed restricted yes- and no-instances have the stated outcomes.
Under this restriction, \(r\geq2\), so the protection ranking for \(v_1\) exists. The constants satisfy \(b>0\), \(b<H\), and \(H>2r\).
Each constructed ranking lists every candidate exactly once. All initial weights are positive integers. Adding \(\Delta=N-W\geq0\) to an existing protection ranking makes the total weight exactly \(N\), without creating a zero mass. Dividing by the power of two \(N\) gives positive dyadic masses summing to one.
Merging identical rankings preserves every relevant weighted total, including after restriction to any finalist set. Thus possible coincidences between ranking types do not invalidate the reduction.
The bounds \(m=r+2\), \(\tau\leq2r+q+1\), and \(L=O((r+q)r\log(r+q+2))\) are valid for the explicit support encoding. Construction and merging require polynomial time.
Candidate \(w\) is never last in an original ranking. Candidate \(p\) is last in the baseline ranking, and each vertex is last in its own protection ranking. All these rankings have positive weight, including after merging.
Hence \(Z=\{w\}\). The lemma then establishes exactly the claimed relevant finalist sets: \(F=\{p,w\}\cup U\), with \(U\subseteq V\). This accounts for all arbitrary real partitions that could make \(p\) win.
The stated totals are correct.
If an edge is uncovered, \(D_p\geq b+H>2r\geq D_w\), so \(p\) cannot win uniquely.
If every edge is covered, \(U\neq\varnothing\) because \(E\neq\varnothing\). The protection contribution to \(D_p\) therefore vanishes, giving \(D_p=b\). Every surviving vertex has greater veto mass, leaving only the comparison with \(w\).
The algebra is correct: \(b<D_w\) is equivalent to \(2|U|<2k+1\), which is equivalent to \(|U|\leq k\) because both quantities are integers. The strict inequality correctly enforces unique victory.
Both directions of the many-one reduction follow from the verified runoff calculation and attainability lemma. The proof addresses the exact continuous formulation rather than importing hardness from indivisible voters.
No additional mathematical clarification is needed. NP membership and NP-hardness together establish NP-completeness, even for dyadic input masses.
⟨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.