Answer: The continuous budget decision problem is in \(\mathrm P\); exact optimization takes \((m+\tau+L)^{O(1)}\) bit operations.
Theorem 4.13 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateWCCAV for 2-veto and 3-approval and WCCDV for 2-approval and 3-veto are NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), target \(p\), and a rational society distribution \(\mu\) over types \(t=(A_t,w_t)\), where \(A_t\subseteq C\), \(|A_t|=2\), and \(w_t\in\{1,2\}\), choose masses \(x_t\) with \(0\le x_t\le\mu_t\) minimizing \(\sum_t x_t\) such that \(p\) is a \(2\)-approval co-winner after removing \(x_t\) mass of each type.
Let \(C\) be a candidate set of unbounded size \(m\ge 2\), with target \(p\in C\). A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is the support size, not the number of possible types. Each type is \(t=(A_t,w_t)\), where \(A_t\subseteq C\), \(|A_t|=2\), and \(w_t\in\{1,2\}\); require \(\sum_t\mu_t=1\).
Deletion chooses divisible masses \(x_t\in\mathbb R\) with \(0\le x_t\le\mu_t\), at cost \(\sum_t x_t\), independently of voter weight. Under weighted \(2\)-approval, the remaining score of \(c\) is \(s_x(c)=\sum_{t:c\in A_t}w_t(\mu_t-x_t)\). Success means \(s_x(p)\ge s_x(c)\) for every \(c\in C\); all score ties count as wins, including after deleting the entire society.
The optimization problem minimizes deletion cost subject to success. Its budget decision version additionally receives a binary rational \(k\in[0,1]\) and asks whether successful deletion of cost at most \(k\) exists. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is this continuous budget decision problem in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite lists of indivisible voters, constructive deletion control under weighted \(2\)-approval is NP-complete even with weights restricted to \(\{1,2\}\), counting deleted voters rather than their total weight (Faliszewski, Hemaspaandra, and Hemaspaandra, 2015).
The continuous budget decision problem is in \(\mathrm P\). The optimization problem is also solvable exactly in time \((m+\tau+L)^{O(1)}\).
The essential point is that divisible deletion gives a rational linear program with one variable per supported type.
Index the supported types by \(t\in\{1,\ldots,\tau\}\). For each type, let \(y_t=\mu_t-x_t\) be its remaining mass. The deletion bounds are equivalent to
\[ 0\le y_t\le\mu_t. \]
Define the integer coefficient
\[ a_{ct}=w_t\bigl(\mathbf 1_{\{c\in A_t\}}-\mathbf 1_{\{p\in A_t\}}\bigr) \qquad(c\in C\setminus\{p\}). \]
Every coefficient belongs to \(\{-2,-1,0,1,2\}\). The score difference between a rival and the target is exactly
\[ s_x(c)-s_x(p)=\sum_{t=1}^{\tau}a_{ct}y_t. \]
Thus success is equivalent to the linear inequalities
\[ \sum_{t=1}^{\tau}a_{ct}y_t\le 0 \qquad(c\in C\setminus\{p\}). \]
Because \(\sum_t\mu_t=1\), deletion cost is
\[ \sum_{t=1}^{\tau}x_t =1-\sum_{t=1}^{\tau}y_t. \]
Consequently, the budget decision problem is precisely the feasibility problem consisting of the variable bounds, the score inequalities, and
\[ \sum_{t=1}^{\tau}y_t\ge 1-k. \]
To verify both directions explicitly:
This equivalence uses weak inequalities, exactly as required by the convention that ties count as wins.
For optimization, maximize \(\sum_t y_t\) subject to the variable bounds and score inequalities. If its optimum is \(M\), the minimum deletion cost is exactly \(1-M\).
The feasible region is nonempty: \(y_t=0\) for every type represents deleting the entire society, after which all scores are zero. It is closed and bounded by the variable bounds. Therefore the optimum is attained.
We use the standard polynomial-time theorem for rational linear programming: rational linear feasibility can be decided, and a bounded rational linear objective can be optimized exactly, in a number of bit operations polynomial in the encoded program length.
Its hypotheses hold here:
A dense encoding has length \(O(\tau(m+\tau)+L)\). Constructing and solving it therefore takes \((m+\tau+L)^{O(1)}\) bit operations. Exact rational linear programming also handles equality at the budget threshold; no numerical tolerance is needed.
The dependence on candidates can be reduced further. Let
\[ C'=\{p\}\cup\bigcup_{t=1}^{\tau}A_t. \]
Then \(|C'|\le\min\{m,2\tau+1\}\). Every candidate outside \(C'\) always has score zero, while \(p\)'s score is nonnegative, so its constraint is redundant. Using only \(C'\), the linear program has encoding length \(O(\tau^2+L)\), after identifying the supported candidates. No enumeration of unsupported types is required.
For indivisible voters, deletion decisions have integrality constraints. Those constraints are absent in the stated continuous problem. The linear program above describes the continuous feasible set exactly, so its polynomial-time solution settles the question despite the cited hardness of the indivisible version.
⟨structured verdict parsed — rendered above⟩
Verdict: The prover resolves the assigned problem correctly. The continuous budget decision problem is in \(\mathrm P\), and the exact optimization claim is justified. No major or minor issues were found.
The substitution \(y_t=\mu_t-x_t\) is valid for every supported type. The original bounds \(0\le x_t\le\mu_t\) are equivalent to \(0\le y_t\le\mu_t\), and the inverse substitution \(x_t=\mu_t-y_t\) recovers every admissible deletion.
There is one variable per supported type, so the formulation correctly uses \(\tau\), rather than the number of possible types.
The coefficient definition
\[
a_{ct}=w_t\bigl(\mathbf 1_{\{c\in A_t\}}-\mathbf 1_{\{p\in A_t\}}\bigr)
\]
correctly represents each type’s contribution to the score difference \(s_x(c)-s_x(p)\). Since the difference of the indicators belongs to \(\{-1,0,1\}\) and \(w_t\in\{1,2\}\), the stated coefficient range is correct.
Consequently, the inequalities \(\sum_t a_{ct}y_t\le0\), for every \(c\ne p\), are exactly the success conditions. Weak inequalities correctly implement the convention that ties count as wins. No constraint for \(c=p\) is needed.
The normalization \(\sum_t\mu_t=1\) gives
\[
\sum_t x_t=1-\sum_t y_t.
\]
Thus deletion cost at most \(k\) is equivalent to \(\sum_t y_t\ge1-k\).
Both directions of the correspondence are explicitly established. The formulation preserves real, divisible deletion choices and imposes no unintended integrality restriction.
The budget endpoints are also handled correctly: at \(k=1\), deleting the entire society is feasible; at \(k=0\), the bounds and budget constraint permit only zero deletion.
Maximizing remaining mass is exactly equivalent to minimizing deletion cost, so the claimed optimum \(1-M\) is correct.
The optimization feasible region contains the zero vector, is closed, and is bounded by the finite upper bounds \(\mu_t\). The linear objective therefore attains a finite maximum. The zero vector is used here for the optimization region; the prover does not incorrectly claim that it satisfies every budget constraint.
The stated rational linear programming theorem is applicable: rational feasibility and finite rational linear optimization admit exact algorithms whose bit complexity is polynomial in the explicit input encoding length.
All relevant hypotheses are verified:
The dense encoding bound \(O(\tau(m+\tau)+L)\) accounts for the score rows, bound rows, and input rational data. It supports the claimed running time \((m+\tau+L)^{O(1)}\). Exact rational linear programming also justifies deciding equality at the budget threshold without numerical tolerances.
The set \(C'=\{p\}\cup\bigcup_t A_t\) satisfies \(|C'|\le\min\{m,2\tau+1\}\), because each approval set has exactly two candidates.
Every omitted candidate has score zero for every admissible deletion, while the target has nonnegative score. Its success constraint is therefore redundant. The reduced encoding bound \(O(\tau^2+L)\) is justified, and identifying the candidates from the support requires only polynomial work.
The distinction drawn is valid. The cited indivisible problem includes discrete deletion choices; this problem allows divisible masses. The exact linear formulation establishes the continuous result independently of the discrete hardness statement.
Repair feedback: None 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.