Answer: Polynomial-time solvable.
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateCSW-Max is PE and weakly UP.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite target set \(T\), attacker utilities \(u^a\), a distribution over \(\tau\) defender types with rational masses \(\mu_\ell>0\) summing to \(1\), rational type utilities \(u_{\theta_\ell}\), normalized pooled capacity \(R\), and a supplied benchmark \((c^0,t_0)\), find \((c,t)\) maximizing \(\sum_{\ell=1}^{\tau}\mu_\ell u_{\theta_\ell}(c,t)\). Require \(t\in\arg\max_{j\in T}u^a(c,j)\), \(c\in[0,1]^T\), \(\sum_{j\in T}c_j\le R\), and \(u_{\theta_\ell}(c,t)\ge u_{\theta_\ell}(c^0,t_0)\) for every supported type; the stated mass-allocation model treats these coverage vectors as feasible.
Let \(C\) be a nonempty target set with \(m=|C|\). A society is given by its support: a list \(R\) of \(\tau\) defender types with positive binary-rational masses \(\mu_r\), normalized by \(\sum_{r\in R}\mu_r=1\). Here \(\tau=|R|\) is the support size, not the number of possible types.
Each defender type specifies rational payoffs \(r^d_r(j)>p^d_r(j)\) for every \(j\in C\); the attacker type specifies rational payoffs \(r^a(j)>p^a(j)\). Payoffs may have either sign. Define \(U^d_r(c,j)=c_jr^d_r(j)+(1-c_j)p^d_r(j)\) and \(U^a(c,j)=(1-c_j)r^a(j)+c_jp^a(j)\).
The pooled supply \(K\) is a nonnegative integer. Coverage is feasible when \(0\le c_j\le1\) and \(\sum_{j\in C}c_j\le K\); resources may remain unused. An outcome specifies a target \(t\) maximizing attacker utility, with any tied best response available for selection.
The input includes rational feasible status-quo coverage \(c^0\) and an attacker best response \(t^0\). Set \(b_r=U^d_r(c^0,t^0)\). No equilibrium condition on the status quo is required.
Find an outcome \((c,t)\) maximizing \(\sum_{r\in R}\mu_rU^d_r(c,t)\), subject to coverage feasibility, \(U^a(c,j)\le U^a(c,t)\) for every \(j\in C\), and \(U^d_r(c,t)\ge b_r\) for every \(r\in R\). Let \(L\) be the total binary input length.
Is this exact optimization problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finitely many defenders, CSW-Max runs in polynomial time and produces a Pareto-efficient outcome guaranteeing each defender at least their utility in a computed Nash–Stackelberg equilibrium, hence weak utility preservation. That result does not separately state a complexity theorem for this mass-input formulation.
The exact optimization problem is solvable in polynomial time in \(m,\tau,L\). We prove this by giving an explicit rational-arithmetic algorithm. It examines each possible attacked target and solves the resulting problem in one variable.
Write \(a_j=r^a(j)\) and \(d_j=r^a(j)-p^a(j)>0\). Thus \(U^a(c,j)=a_j-d_jc_j\).
Fix a target \(t\), and write \(x=c_t\). For every \(j\ne t\), the attacker best-response constraint is equivalent to
\(a_j-d_jc_j\le a_t-d_tx\),
and hence to
\(c_j\ge (a_j-a_t+d_tx)/d_j\).
Combining this with nonnegative coverage, define the minimum required coverage
\(q_{tj}(x)=\max\{0,(a_j-a_t+d_tx)/d_j\}\).
Consequently, whenever an outcome attacking \(t\) has coverage \(x\) at \(t\), replacing every other coverage by \(q_{tj}(x)\) preserves the attacker best-response constraints and weakly reduces resource consumption. It also preserves every defender’s utility, because that utility depends only on \(c_t\) and \(t\).
Thus we may restrict attention to the canonical coverage vector with \(c_t=x\) and \(c_j=q_{tj}(x)\) for \(j\ne t\).
For each defender type, let \(\Delta_{rt}=r^d_r(t)-p^d_r(t)>0\). Its preservation constraint is equivalent to
\(p^d_r(t)+\Delta_{rt}x\ge b_r\),
or \(x\ge (b_r-p^d_r(t))/\Delta_{rt}\). Define
\(\ell_t=\max\bigl(\{0\}\cup\{(b_r-p^d_r(t))/\Delta_{rt}:r\in R\}\bigr)\).
The coverage upper bound at \(t\) requires \(x\le1\). For \(j\ne t\), the condition \(q_{tj}(x)\le1\) is equivalent to
\(a_j-a_t+d_tx\le d_j\),
which, since \(a_j-d_j=p^a(j)\), is equivalent to
\(x\le (a_t-p^a(j))/d_t\).
Define
\(h_t=\min\bigl(\{1\}\cup\{(a_t-p^a(j))/d_t:j\ne t\}\bigr)\).
Finally, define the minimum total coverage needed to make \(t\) a best response:
\(g_t(x)=x+\sum_{j\ne t}q_{tj}(x)\).
An outcome attacking \(t\) with \(c_t=x\) exists if and only if
\(\ell_t\le x\le h_t\quad\text{and}\quad g_t(x)\le K\).
Necessity follows from the constraints derived above and from \(c_j\ge q_{tj}(x)\). For sufficiency, use the canonical coverage vector: these inequalities guarantee all coverage bounds, the resource constraint, every preservation constraint, and every attacker best-response constraint.
Each \(q_{tj}\) is continuous and nondecreasing. Therefore \(g_t\) is continuous and strictly increasing: for \(y>x\),
\(g_t(y)-g_t(x)=(y-x)+\sum_{j\ne t}(q_{tj}(y)-q_{tj}(x))\ge y-x>0\).
It follows that target \(t\) admits a feasible outcome exactly when \(\ell_t\le h_t\) and \(g_t(\ell_t)\le K\).
For fixed \(t\), the objective is
\(F_t(x)=\sum_{r\in R}\mu_rp^d_r(t)+x\sum_{r\in R}\mu_r\Delta_{rt}\).
Its slope is strictly positive because every mass and every \(\Delta_{rt}\) is positive. Therefore the optimal outcome attacking \(t\) uses the largest feasible \(x\).
If \(g_t(h_t)\le K\), this largest value is \(x_t^*=h_t\).
Otherwise, assuming \(t\) is feasible, continuity and strict monotonicity imply that there is a unique \(x_t^*\in[\ell_t,h_t)\) satisfying \(g_t(x_t^*)=K\). We now show how to compute it exactly.
For \(j\ne t\), define the rational breakpoint
\(\beta_{tj}=(a_t-a_j)/d_t\).
Then
\(q_{tj}(x)=(d_t/d_j)\max\{0,x-\beta_{tj}\}\).
Sort the distinct breakpoints strictly between \(\ell_t\) and \(h_t\), together with these two endpoints. Evaluate \(g_t\) at the sorted points. Since \(g_t(\ell_t)\le K<g_t(h_t)\), there are consecutive points \(u<v\) satisfying
\(g_t(u)\le K<g_t(v)\).
Let \(S=\{j\ne t:\beta_{tj}\le u\}\). There are no breakpoints strictly inside \([u,v]\). An index with breakpoint \(v\) contributes zero at \(v\), so throughout the entire closed interval,
\(g_t(x)=A+Bx\),
where
\(A=\sum_{j\in S}(a_j-a_t)/d_j\),
and
\(B=1+\sum_{j\in S}d_t/d_j>0\).
Thus the exact solution is
\(x_t^*=(K-A)/B\).
The inequalities at \(u\) and \(v\) imply \(u\le x_t^*<v\), verifying that this formula lies in the interval on which it was derived.
Apply this procedure to each \(t\in C\), discarding infeasible targets. For every remaining target, construct its canonical optimal coverage and evaluate \(F_t(x_t^*)\). Return one with largest value.
Every feasible outcome attacks some target \(t\). By the feasibility characterization, its coverage at that target is at most \(x_t^*\). Since \(F_t\) is increasing, its objective is at most \(F_t(x_t^*)\). Taking the largest of these per-target optima therefore yields a global optimum.
At least one target survives: the supplied status-quo outcome \((c^0,t^0)\) is feasible, satisfies the attacker best-response constraints, and satisfies every preservation constraint with equality. Hence the optimization domain is nonempty.
All calculations use rational arithmetic and exact comparisons.
For each target, computing the preservation lower bound takes a number of arithmetic operations linear in \(\tau\). There are at most \(m-1\) breakpoints. Sorting them, evaluating \(g_t\) at their endpoints, and constructing the optimum require polynomially many operations in \(m\). Comparing the objectives across all targets also requires polynomially many operations in \(m,\tau\).
The bit lengths remain polynomial as well. Each initial bound or breakpoint uses only a constant number of arithmetic operations on input rationals, so has bit length \(O(L)\). A sum of at most \(m\) such rationals has bit length \(O(mL)\): a common denominator can be taken as the product of their denominators, whose bit lengths add. The coefficients \(A,B\), their quotient defining \(x_t^*\), and the resulting coverages therefore have bit length \(O(mL)\). Summing the \(\tau\) weighted defender utilities gives objective values of bit length \(O(\tau mL)\). Standard exact integer arithmetic and rational comparison consequently implement the entire algorithm in polynomial bit complexity.
This proves the polynomial-time result directly for the support-and-mass input formulation. It requires no equilibrium property of the status quo and no separate application of the CSW-Max guarantee.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The algorithm solves the exact optimization problem in polynomial time in \(m,\tau,L\). The feasibility characterization, optimization for each target, and binary complexity argument are correct. No major or minor issues were found.
The definition \(d_j=r^a(j)-p^a(j)>0\) follows from the strict payoff inequality in the task. Consequently,
\[
U^a(c,j)=a_j-d_jc_j.
\]
Dividing the attacker best-response constraint by \(d_j\) preserves the inequality direction and gives exactly the stated lower bound on \(c_j\).
Combining that bound with \(c_j\ge0\) gives \(q_{tj}(x)\). For any feasible outcome with \(c_t=x\), one has \(q_{tj}(x)\le c_j\le1\). Replacing \(c_j\) by \(q_{tj}(x)\) therefore preserves coverage bounds, preserves the best-response constraints, and weakly reduces total coverage.
Every defender’s utility for an outcome attacking \(t\) depends only on \(c_t\) and \(t\). Thus this replacement preserves both individual utilities and the objective. The restriction to canonical coverage is justified.
Each \(\Delta_{rt}>0\), so the preservation constraint is equivalent to the stated lower bound on \(x\). Taking the maximum with zero correctly incorporates \(c_t\ge0\).
For other targets, the equivalence
\[
q_{tj}(x)\le1
\quad\Longleftrightarrow\quad
a_j-a_t+d_tx\le d_j
\]
is valid: for any real \(z\), \(\max\{0,z\}\le1\) is equivalent to \(z\le1\). Using \(a_j-d_j=p^a(j)\) and \(d_t>0\) yields the stated upper bound. Hence \(h_t\) correctly includes all coverage upper bounds.
The resource inequality \(g_t(x)\le K\) is necessary because every feasible coverage vector uses at least the canonical total coverage. It is sufficient because the canonical vector meets every other constraint whenever \(\ell_t\le x\le h_t\).
The calculation establishing strict increase of \(g_t\) is correct. Therefore a target is feasible precisely when \(\ell_t\le h_t\) and \(g_t(\ell_t)\le K\): these conditions make \(\ell_t\) itself feasible, and any feasible \(x\) implies them.
The objective \(F_t(x)\) is affine with strictly positive slope, since every \(\mu_r\) and \(\Delta_{rt}\) is positive. Maximizing it is therefore equivalent to selecting the largest feasible \(x\).
For a feasible target, if \(g_t(h_t)\le K\), then \(h_t\) is feasible and is the largest allowable value.
Otherwise,
\[
g_t(\ell_t)\le K<g_t(h_t).
\]
Continuity supplies a solution of \(g_t(x)=K\), and strict increase makes it unique. These same properties establish that this solution is the largest feasible value. The possibility \(g_t(\ell_t)=K\) is included.
The identity
\[
q_{tj}(x)=\frac{d_t}{d_j}\max\{0,x-\beta_{tj}\}
\]
follows directly from the definition of \(\beta_{tj}\).
The sorted endpoints and distinct interior breakpoints provide consecutive points \(u<v\) with \(g_t(u)\le K<g_t(v)\). On this interval, the active terms are exactly those indexed by \(S\), except that terms with breakpoint \(v\) vanish throughout the interval including at \(v\). Terms with breakpoint \(u\) are correctly included: their affine expression is zero at \(u\).
Thus the displayed coefficients \(A\) and \(B\) correctly express \(g_t(x)=A+Bx\) throughout \([u,v]\). Since \(B>0\), solving this equation gives the stated rational value. The endpoint inequalities imply \(u\le x_t^*<v\), so the solution lies within the interval where the formula applies.
Every feasible outcome attacks some enumerated target. Its attacked-target coverage is feasible for that target and cannot exceed \(x_t^*\). The positive slope of \(F_t\) then gives the claimed objective upper bound.
Each retained canonical optimum is itself feasible. Selecting the largest objective among them therefore attains the global optimum.
The supplied status quo satisfies coverage feasibility, the best-response constraints, and preservation with equality. It consequently guarantees that at least one target survives.
The operation count is polynomial. Even evaluating \(g_t\) separately at every breakpoint requires only polynomially many operations.
The bit-length bounds also hold:
Exact rational comparisons and arithmetic on these polynomial-length integers take polynomial time. There is no numerical approximation or precision assumption.
The argument covers \(m=1\), \(K=0\), coincident breakpoints, singleton feasible intervals, negative payoffs, and unused resources. In particular, empty sums and the explicit elements \(0\) and \(1\) in the bound definitions handle the single-target case.
Tied attacker best responses are allowed by the task and are correctly represented by non-strict inequalities. The algorithm uses the support size \(\tau\) directly and imposes no equilibrium condition on the status quo.
No additional clarification or repair is needed.
⟨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.