Answer: \(\mathrm{NP}\text{-complete}\)
Theorem 2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCCAV and CCDV for 1-Approval THEN 1-Approval are NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a candidate set \(C\), a finite set \(T\) of ranking types, registered masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), available unregistered masses \(\nu_t\ge 0\), a target \(p\in C\), and a rational budget \(\kappa\ge 0\), decide whether there are additions \(x_t\in[0,\nu_t]\) with \(\sum_{t\in T}x_t\le\kappa\) such that \(p\) wins under \(1\text{-Approval THEN }1\text{-Approval}\). In the first round, the finalists are the candidates maximizing \(\sum_{t:\,t\text{ ranks }c\text{ first}}(\mu_t+x_t)\). In the runoff among those finalists, each mass unit supports its highest-ranked finalist; \(p\) must receive at least as much runoff mass as every other finalist. What is the complexity in \(m=|C|\), \(\tau=|T|\), and the input bit length?
Let \(C\) be a nonempty candidate set, \(m=|C|\), and \(p\in C\). Types are strict total rankings of \(C\).
Each society is given by its support: types with positive mass, each mass a binary rational. Let \(T\) be the union of the registered and available supports, with missing masses set to zero; \(\tau=|T|\) counts listed types, not all possible rankings.
The input gives registered masses \(\mu_t\geq0\) with \(\sum_{t\in T}\mu_t=1\), available masses \(\nu_t\geq0\), and a binary rational budget \(\kappa\geq0\). Let \(L\) be the total input bit length.
An addition chooses divisible masses \(x_t\in\mathbb R\) with \(0\leq x_t\leq\nu_t\) and \(\sum_t x_t\leq\kappa\); the resulting masses are \(w_t=\mu_t+x_t\).
Under \(1\text{-Approval THEN }1\text{-Approval}\), the finalist set \(F\) consists of all candidates maximizing \(\sum_{t:\,c\text{ is first in }t}w_t\). All resulting mass participates in the runoff, with unchanged rankings restricted to \(F\).
An addition succeeds precisely when \(p\in F\) and \(p\) receives strictly more runoff mass than every member of \(F\setminus\{p\}\); a sole finalist wins automatically.
Is deciding whether a successful addition exists solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For indivisible, unweighted voters, constructive control by adding or deleting votes under this rule is NP-hard, with a unique final winner required ([Guo–Shrestha, 2014](https://www.researchgate.net/publication/265476940_Controlling_Two-Stage_Voting_Rules)).
No result settling this exact divisible-mass problem was identified in the literature search.
The decision problem is \(\mathrm{NP}\text{-complete}\). Hardness holds even when every input mass and the budget are dyadic rationals.
The reduction below handles arbitrary real additions: partial additions cannot bypass the combinatorial requirement.
We use the standard \(\mathrm{NP}\)-complete Set Cover problem: given a nonempty universe \(U=\{e_1,\ldots,e_r\}\), sets \(S_1,\ldots,S_n\subseteq U\), and an integer \(0\leq k\leq n\), decide whether at most \(k\) of the sets cover \(U\). We may assume \(n\geq1\), since instances with no sets are trivial. See [Karp, *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Let \(Q\) be the smallest power of two satisfying \(Q\geq12r+4\), and define
\[
b=\frac Q2-2r-1.
\]
Consequently,
\[
b\geq4r+1,
\qquad
2b+4r+2=Q.
\]
We initially describe unnormalized mass units. Every registered and available mass, and the budget, will then be divided by \(Q\).
The candidates are \(p\), a fixed rival \(q\), one candidate \(c_j\) for each set \(S_j\), and a collection \(D\) of dummy candidates.
For each element \(e_i\), let \(A_i\) be the list of candidates \(c_j\) such that \(e_i\in S_j\), ordered by increasing \(j\).
Every ranking prefix below is completed by appending all unlisted candidates in a fixed order. Thus every listed type is a strict total ranking.
The registered types are:
| Number of types | Ranking prefix | Mass per type |
|---:|---|---:|
| \(1\) | \(p\succ q\) | \(2\) |
| \(1\) | \(q\succ p\) | \(2\) |
| \(b\) | \(d\succ p\succ q\) | \(1\) |
| \(b-2\) | \(d\succ q\succ p\) | \(1\) |
| Four for each \(e_i\in U\) | \(d\succ A_i\succ q\succ p\) | \(1\) |
Each occurrence of \(d\) denotes a different dummy candidate. Hence
\[
|D|=b+(b-2)+4r=Q-4.
\]
The total registered mass is
\[
2+2+b+(b-2)+4r=Q.
\]
For each \(j\), the available support contains one type with ranking prefix
\[
c_j\succ q\succ p
\]
and available mass \(2\). There are no other available types. The unnormalized budget is \(2k\).
Divide all masses and the budget by \(Q\). The resulting registered mass sums to \(1\), exactly as required. Since \(Q\) is a power of two, all numerical inputs are dyadic rationals.
Because \(Q<2(12r+4)\), the number of dummy candidates is \(O(r)\). In fact,
\[
m=n+Q-2,
\qquad
\tau=n+Q-2.
\]
The equality for \(\tau\) holds because every listed type has a different first-ranked candidate. Each ranking has length \(m\), and the numerical parameters have polynomial encoding length. Thus this is a polynomial-time construction from an explicitly represented Set Cover instance.
Let \(x_j\) be the actual added mass of the available type headed by \(c_j\), and put \(a_j=Qx_j\). Feasibility is equivalent to
\[
0\leq a_j\leq2,
\qquad
\sum_{j=1}^{n}a_j\leq2k.
\]
All scores below are multiplied by \(Q\); this preserves both equality and strict comparison.
The first-round scores are:
Therefore, for every feasible addition, the finalist set is exactly
\[
F=\{p,q\}\cup\{c_j:j\in J\},
\qquad
J=\{j:a_j=2\}.
\]
In particular, no dummy can reach the runoff, and a partially added set candidate cannot reach it.
The budget gives
\[
2|J|\leq\sum_{j=1}^{n}a_j\leq2k,
\]
so \(|J|\leq k\).
Let
\[
u=\left|U\setminus\bigcup_{j\in J}S_j\right|,
\qquad
A=\sum_{j\notin J}a_j.
\]
Thus \(u\) counts uncovered elements and \(A\geq0\) is the total mass of partial additions.
The runoff score of \(p\) is exactly
\[
R_p=2+b.
\]
Indeed, \(p\) receives its own initial mass \(2\) and the \(b\) dummy-headed types with \(p\) second. Every other type places either \(q\) or a selected set candidate above \(p\).
The runoff score of \(q\) is exactly
\[
R_q=2+(b-2)+4u+A=b+4u+A.
\]
To verify every term:
Every selected candidate \(c_j\) receives its own added mass \(2\) and possibly some element-associated mass. The total element-associated mass is \(4r\), so
\[
R_{c_j}\leq2+4r<2+b=R_p.
\]
Thus \(p\) always strictly beats every selected set candidate. Its comparison with \(q\) is decisive:
\[
R_p>R_q
\quad\Longleftrightarrow\quad
4u+A<2.
\]
Because \(u\) is a nonnegative integer and \(A\geq0\), success necessarily implies \(u=0\).
Suppose an arbitrary feasible real addition succeeds.
The runoff calculation implies \(u=0\), so the sets indexed by \(J\) cover \(U\). The budget calculation gives \(|J|\leq k\). Hence the Set Cover instance is a yes-instance.
This argument permits every fractional value \(a_j\in[0,2]\); it makes no integrality assumption about additions.
Conversely, suppose \(J\subseteq\{1,\ldots,n\}\) indexes a cover with \(|J|\leq k\). Choose
\[
a_j=
\begin{cases}
2,&j\in J,\\
0,&j\notin J.
\end{cases}
\]
This addition respects all capacities and uses mass \(2|J|\leq2k\). Since the selected sets cover \(U\), we have \(u=0\); since there are no partial additions, \(A=0\).
Therefore,
\[
R_p=b+2>b=R_q.
\]
The previously proved bound also gives \(R_p>R_{c_j}\) for every selected set candidate. Consequently, \(p\) is the unique runoff winner.
The reduction proves \(\mathrm{NP}\)-hardness.
Although additions may be real, membership in \(\mathrm{NP}\) follows by guessing the finalist set and solving a rational linear program.
Fix a guessed set \(F\subseteq C\) containing \(p\). For each type \(t\), let \(h_F(t)\) be its highest-ranked candidate in \(F\). Define the linear score functions
\[
s_c(x)=\sum_{t:\,c\text{ is first in }t}(\mu_t+x_t),
\]
and, for \(c\in F\),
\[
r_c^F(x)=\sum_{t:\,h_F(t)=c}(\mu_t+x_t).
\]
Introduce a variable \(\delta\), and maximize \(\delta\) subject to:
This program has polynomially many variables and constraints and rational coefficients of polynomial encoding length. Its feasible region is closed and bounded.
It has a feasible solution with \(\delta>0\) if and only if an addition succeeds with exactly the finalist set \(F\):
Rational linear programming can be solved, and its optimum compared exactly with zero, in polynomial time; this is the standard polynomial-time linear programming theorem of [Khachiyan](https://www.mathnet.ru/eng/dan42319). Thus an \(\mathrm{NP}\) verifier can guess \(F\) using \(m\) bits and accept precisely when this program has positive optimum.
Combining membership with the reduction, the target problem is \(\mathrm{NP}\text{-complete}\). A polynomial-time algorithm in \(m,\tau,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated divisible-mass problem: it establishes \(\mathrm{NP}\)-completeness, including when all masses and the budget are dyadic rationals. I found no major or minor mathematical issues.
The prover precisely states the decision version of Set Cover used in the reduction. Its restrictions to a nonempty universe, at least one set, and \(0\leq k\leq n\) exclude only trivial cases and preserve the standard hardness result. The cited source is [Karp’s *Reducibility among Combinatorial Problems*](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
The construction addresses the actual target: additions are divisible real masses, the finalist set contains every first-round maximizer, and success requires a strict runoff victory.
From \(Q\geq12r+4\), the stated definition gives
\(b=Q/2-2r-1\geq4r+1\).
Thus \(b\) and \(b-2\) are positive integers, so all registered-type multiplicities are valid.
The identities
\(2b+4r+2=Q\) and
\(|D|=b+(b-2)+4r=Q-4\)
are correct. The registered masses consequently total exactly \(Q\).
Every ranking prefix contains distinct candidates. In particular, each dummy is distinct from every set candidate, and each \(A_i\) lists distinct set candidates. Appending unlisted candidates therefore produces strict total rankings. An empty \(A_i\) causes no ambiguity: the corresponding prefix becomes \(d\succ q\succ p\).
Dividing by \(Q\) gives registered total mass \(1\), nonnegative available masses, and nonnegative budget \(2k/Q\). Because \(Q\) is a power of two, all these quantities are dyadic rationals. Scaling comparisons by \(Q>0\) preserves ties and strict inequalities.
There are \(Q-2\) registered types and \(n\) available types. Every listed type has a distinct first-ranked candidate, so no types merge when the support union is formed. Hence both stated counts,
\(m=n+Q-2\) and \(\tau=n+Q-2\),
are correct.
The least-power-of-two choice gives \(Q<2(12r+4)\). Consequently, the candidate count, support count, full ranking descriptions, and numerical encoding lengths are polynomial in the explicitly represented Set Cover input. The construction satisfies the task’s support-based representation requirement.
The transformation \(a_j=Qx_j\) correctly translates feasibility into
\(0\leq a_j\leq2\) and \(\sum_j a_j\leq2k\).
The first-round scores are exactly those stated: \(2\) for each of \(p,q\), \(1\) for each dummy, and \(a_j\) for \(c_j\). Therefore the maximum score is always \(2\), and the finalist set is exactly
\(F=\{p,q\}\cup\{c_j:a_j=2\}\).
This conclusion uses no integrality assumption. Every addition strictly below capacity leaves its set candidate outside the runoff. Each selected candidate consumes exactly \(2\) units, so
\(2|J|\leq\sum_j a_j\leq2k\)
correctly implies \(|J|\leq k\).
The claimed score \(R_p=2+b\) is exact. Its contributors are its own registered type and the \(b\) dummy-headed types placing \(p\) before \(q\). All remaining types place a finalist above \(p\).
The claimed score \(R_q=b+4u+A\) is also exact:
Appended ranking suffixes cannot change these assignments because each displayed prefix already contains the relevant surviving candidate.
A selected candidate receives its own \(2\) units and at most all \(4r\) element-associated units. Thus
\(R_{c_j}\leq2+4r<2+b=R_p\)
follows from \(b\geq4r+1\).
Accordingly, success is equivalent to \(4u+A<2\). Since \(u\) is a nonnegative integer and \(A\geq0\), success implies \(u=0\). Fractional additions cannot invalidate this implication.
A successful real addition produces a cover indexed by \(J\), with \(|J|\leq k\). This proves the required soundness direction.
Conversely, fully adding exactly the candidates of a cover of size at most \(k\) respects capacities and budget, gives \(u=A=0\), and yields strict victories over \(q\) and every selected set candidate. This proves completeness.
The edge cases are handled by the same calculations: \(k=0\) cannot cover the nonempty universe, and an element belonging to no set remains uncovered under every addition. Empty or duplicate input sets do not disrupt the construction.
A guessed finalist set containing \(p\) has a polynomial-length encoding. For this fixed set, the first-round and runoff scores are rational linear functions computable from the listed rankings.
The linear program correctly enforces the exact finalist set: its equalities include every member of \(F\), while positive \(\delta\) strictly excludes every candidate outside \(F\). Its runoff inequalities enforce precisely the required strict victories.
Conversely, a successful addition supplies finitely many positive comparison gaps. Their minimum with \(1\) gives a valid positive \(\delta\). The write-up explicitly handles the case with no comparison gaps, covering the one-candidate instance. A sole finalist in a larger election is handled by the first-round exclusion inequalities.
The capacities and the bound on \(\delta\) make the feasible region bounded; all constraints are closed. An infeasible program is rejected, and a feasible program has an attained optimum. The stated rational linear-programming theorem applies because the program has polynomial dimension and rational coefficients of polynomial encoding length. Exact optimization and comparison with zero provide a polynomial-time verifier; guessing \(F\) does not require enumerating all finalist sets. The cited theorem is [Khachiyan’s polynomial-time linear-programming result](https://www.mathnet.ru/eng/dan42319).
No additional clarification or repair is needed. Both the hardness reduction and the membership argument stand as written.
⟨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.