Answer: —
Theorem 0.20 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateThere is an algorithm for deciding whether a coalition structure is in the ϵ-core or not that runs in time O(2λ poly(m, n)), where λ is the number of defender types. Conclusion We provide a model of a coalitional multi-defender security game that enables defenders to form coalitions and distribute their resources jointly. We focus on the solution concept of the core. We prove that the 0+-core is none-empty, give a polynomial-time algorithm for computing a grand coalition structure in the 0+-core, and show that it is NP-hard to com- pute the entire core even when there is a fixed number of defenders.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a population scale \(N\), a target set \(T_N\) whose size grows proportionally to \(N\), rational payoff data, and \(\epsilon>0\), let defender types \(\Theta\) have rational shares \(\mu_\theta\) summing to one and per-defender resource rates \(\rho_\theta\). The input includes a finite candidate coalition structure \((q^j,x^j)_{j=1}^r\), with rational type-mass vectors satisfying \(\sum_j q^j=\mu\), coverage vectors \(x^j\in[0,1]^{T_N}\), and \(\sum_{t\in T_N}x_t^j\le N\sum_\theta\rho_\theta q_\theta^j\). Its overall coverage is \(c_t=1-\prod_j(1-x_t^j)\), which gives each type its baseline utility \(u_\theta\) under the paper's attacker response and pessimistic tie-breaking. Decide whether there is no nonzero deviating mass vector \(d\le\mu\) and feasible deviation coverage \(x\), with \(\sum_t x_t\le N\sum_\theta\rho_\theta d_\theta\), such that every type with \(d_\theta>0\) gains at least \(\epsilon\) for every feasible revenger coverage \(y\), where \(\sum_t y_t\le N\sum_\theta\rho_\theta(\mu_\theta-d_\theta)\) and the resulting coverage is \(c'_t=1-(1-x_t)(1-y_t)\).
A society is given by its support: the list of \(\tau\) types with positive binary-rational masses \(\mu_\theta\), summing to one; \(\tau\) is the support size, not the number of possible types. Each type has a positive rational resource rate \(\rho_\theta\).
The input includes a binary-encoded integer population scale \(N\ge1\), an explicitly listed target set \(T_N\) of size \(m\ge1\), and rational \(\epsilon>0\). Fix constants \(0<a\le b\) and require \(aN\le m\le bN\). Let \(L\) be the total input bit length.
Payoffs \(r^a(t),p^a(t),r^d_\theta(t),p^d_\theta(t)\) are arbitrary signed rationals satisfying \(r^a(t)>p^a(t)\) and \(r^d_\theta(t)>p^d_\theta(t)\). For coverage \(z\), define \(A(z,t)=(1-z_t)r^a(t)+z_tp^a(t)\), \(D_\theta(z,t)=z_tr^d_\theta(t)+(1-z_t)p^d_\theta(t)\), \(B(z)=\arg\max_{t\in T_N}A(z,t)\), and \(U_\theta(z)=\min_{t\in B(z)}D_\theta(z,t)\); pessimistic tie-breaking is evaluated separately for each type.
For any real mass vector \(v\ge0\), write \(K(v)=N\sum_\theta\rho_\theta v_\theta\) and \(C(v)=\{z\in[0,1]^m:\sum_tz_t\le K(v)\}\). Restrict to canonical instances: there exists \(\bar c\in C(\mu)\) with \(\sum_t\bar c_t=K(\mu)\) and \(\bar c_t=0\) whenever \(t\notin B(\bar c)\).
The candidate structure consists of \(r\ge1\) rational pairs \((q^j,x^j)\), with \(q^j\ge0\), \(\sum_\theta q^j_\theta>0\), \(\sum_jq^j=\mu\), and \(x^j\in C(q^j)\). Types may split their mass across coalitions; overall coverage is \(c_t=1-\prod_j(1-x_t^j)\), and baseline utility is \(u_\theta=U_\theta(c)\).
A successful deviation consists of real \(0\ne d\le\mu\) and \(x\in C(d)\) such that, for every \(y\in C(\mu-d)\) and every \(\theta\) with \(d_\theta>0\), \(U_\theta(c')\ge u_\theta+\epsilon\), where \(c'_t=1-(1-x_t)(1-y_t)\). The entire society may deviate; \(C(0)=\{0\}\). The structure belongs to the mass \(\epsilon\)-core exactly when no successful deviation exists.
Is deciding membership in this mass \(\epsilon\)-core in \(\mathrm{P}\), with runtime polynomial in \(m,\tau,r,L\), or is it \(\mathrm{NP}\)-hard?
Discrete \(\epsilon\)-core membership admits an \(O(2^\lambda\operatorname{poly}(m,n))\) algorithm, where \(\lambda\) counts payoff types; testing a specified deviating coalition is polynomial-time. [Source](https://jgan.xyz/papers/AAAI21.coalition.pdf)
Existence of a nongrand structure in the discrete \(0^+\)-core is \(\mathrm{NP}\)-hard even with two defenders. [Source](https://jgan.xyz/papers/AAAI21.coalition.pdf) No hardness claim for discrete membership or result settling this exact mass problem was located.
For every nonempty size promise in the question, mass $\epsilon$-core membership is $\mathrm{coNP}$-complete under polynomial-time many-one reductions. Its complement, existence of a successful deviation, is $\mathrm{NP}$-complete.
The hardness holds even when the candidate has one coalition, $\epsilon=1$, the masses are dyadic rationals, and all payoffs are nonnegative.
This distinguishes two meanings of the question’s hardness alternative:
I prove the classification below. The final status is conservatively marked partial relative to the literal many-one “$\mathrm{P}$ or $\mathrm{NP}$-hard” alternative.
Compute the candidate’s coverage and utilities exactly:
$$
c_t=1-\prod_{j=1}^r(1-x_t^j),
\qquad
u_\theta=\min_{t\in B(c)}D_\theta(c,t).
$$
Write
$$
W_\theta=u_\theta+\epsilon,
\qquad
\Delta_t=r^a(t)-p^a(t)>0,
\qquad
\delta_{\theta t}=r^d_\theta(t)-p^d_\theta(t)>0.
$$
Thus
$$
A(z,t)=r^a(t)-\Delta_tz_t,
\qquad
D_\theta(z,t)=p^d_\theta(t)+\delta_{\theta t}z_t.
$$
For a nonempty set $S$ of participating types, define
$$
s_t=\max\left\{
0,\;
\max_{\theta\in S}
\frac{W_\theta-p^d_\theta(t)}{\delta_{\theta t}}
\right\}.
$$
For coverage $z_t\in[0,1]$, all participating types meet their improvement requirements at $t$ exactly when $z_t\ge s_t$. In particular, thresholds exceeding one must remain uncapped.
Lemma 1. Every successful deviation can be replaced by one using the entire mass of every participating type.
Proof. Suppose $(d,x)$ is successful, and let $S=\{\theta:d_\theta>0\}$. Define $d^S_\theta=\mu_\theta$ for $\theta\in S$ and zero otherwise. Then $d^S\ge d$, so
$$
K(d^S)\ge K(d),
\qquad
K(\mu-d^S)\le K(\mu-d).
$$
Consequently, $x$ remains feasible, and the remaining society’s feasible set contracts:
$$
C(\mu-d^S)\subseteq C(\mu-d).
$$
The participating types are unchanged. Every remaining-society strategy that must be checked after replacement was already covered by the original universal quantifier. Hence $(d^S,x)$ is successful. $\square$
For a fixed nonempty $S$, put
$$
k=N\sum_{\theta\in S}\rho_\theta\mu_\theta,
\qquad
R=N\sum_{\theta\notin S}\rho_\theta\mu_\theta.
$$
This section proves the upper bound used in the classification.
For $x\in[0,1]^m$ and a payoff bound $v$, define
$$
H_t(x,v)=
\begin{cases}
0,&A(x,t)\le v,\\
+\infty,&A(x,t)>v\text{ and }p^a(t)>v,\\
\dfrac{A(x,t)-v}{\Delta_t(1-x_t)},
&A(x,t)>v\text{ and }p^a(t)\le v.
\end{cases}
$$
This is the minimum remaining-society coverage at $t$ needed to reduce its attacker payoff to at most $v$. Indeed, combined coverage is $x_t+(1-x_t)y_t$, so
$$
A(c',t)=A(x,t)-\Delta_t(1-x_t)y_t.
$$
In the third case, $x_t<1$, and the displayed quotient belongs to $(0,1]$. If $p^a(t)>v$, even full coverage cannot attain the bound.
A target $t$ can be a best response under some feasible remaining-society strategy exactly when
$$
\sum_{j\ne t}H_j(x,A(x,t))\le R.
$$
To prove this, first observe that replacing $y_t$ by zero increases the attacker payoff at $t$, leaves the others unchanged, and reduces expenditure. Thus a reachable best response remains reachable with $y_t=0$. With that coordinate fixed, making $t$ a best response requires every other target’s payoff to be at most $A(x,t)$. The independent minimum costs are exactly the summands above.
It follows that a rational feasible $x$ is successful precisely when every target satisfying this reachability inequality has $x_t\ge s_t$. This is a polynomial-time verification procedure.
If every $s_t\le1$ and
$$
\sum_ts_t\le k,
$$
then $x=s$ is successful.
Otherwise, let
$$
I=\{t:s_t>1\}.
$$
When $I$ is nonempty, put $P=\max_{t\in I}p^a(t)$ and restrict the following construction to $v\ge P$. When $I$ is empty, there is no lower restriction on $v$.
Define
$$
h_t(v)=\max\left\{0,\frac{r^a(t)-v}{\Delta_t}\right\},
\qquad
f(v)=\sum_t\min\{s_t,h_t(v)\}.
$$
Every coordinate $\min\{s_t,h_t(v)\}$ lies in $[0,1]$ on the permitted domain. For $s_t\le1$ this is immediate; for $s_t>1$, the restriction $v\ge P\ge p^a(t)$ gives $h_t(v)\le1$.
Let $v_*$ be the smallest permitted value satisfying $f(v_*)\le k$, and set
$$
x_t^*=\min\{s_t,h_t(v_*)\}.
$$
The minimum exists. The function $f$ is continuous and nonincreasing, and it is zero for $v\ge\max_t r^a(t)$. A finite lower endpoint is included. If there is no lower endpoint, failure of the initial case gives $\sum_ts_t>k$, and $f(v)$ tends to this larger value as $v$ tends to $-\infty$.
Partition the targets into
$$
G=\{t:x_t^*=s_t\},
\qquad
V=\{t:x_t^*<s_t\},
$$
and define
$$
g=\sum_{t\in G}H_t(x^*,v_*).
$$
Lemma 2. In this remaining case, $S$ admits a successful deviation if and only if $g>R$.
Proof. Three properties of the construction will be used.
First, for every $t\in V$,
$$
A(x^*,t)\le v_*.
$$
If $x_t^*>0$, then $x_t^*=h_t(v_*)$, giving equality. If $x_t^*=0$, then $r^a(t)\le v_*$.
Second, whenever $x_t^*>0$,
$$
A(x^*,t)\ge v_*.
$$
For $t\in V$ this was just proved. For $t\in G$, the inequality $h_t(v_*)\ge s_t=x_t^*$ gives the result.
Third, there is $t_0\in V$ with $A(x^*,t_0)=v_*$, and either $\sum_tx_t^*=k$ or such a target can be chosen with $x_{t_0}^*=1$. To see this, if $v_*=P$ at a finite lower endpoint, choose $t_0\in I$ with $p^a(t_0)=P$. Then
$$
x_{t_0}^*=h_{t_0}(P)=1<s_{t_0}.
$$
Otherwise, continuity and minimality imply $f(v_*)=k$. If no unsafe target had payoff $v_*$, every unsafe coordinate would be zero with $r^a(t)<v_*$. A sufficiently small decrease of $v_*$ would keep those coordinates zero and every safe coordinate saturated at $s_t$. It would therefore preserve $f(v_*)=k$, contradicting minimality. This proves the third property.
Suppose first that $g>R$. If an unsafe target became a best response, its payoff would be at most $v_*$. Every safe target would then also have payoff at most $v_*$, requiring remaining-society expenditure at least $g$. This exceeds $R$. Therefore every best response is safe, and $x^*$ is successful.
Now suppose $g\le R$, and write
$$
\beta_t=H_t(x^*,v_*)\quad(t\in G).
$$
All these costs are finite and belong to $[0,1]$.
Consider any feasible alternative deviator strategy $z$, and put
$$
Q=\{t:z_t<x_t^*\}.
$$
If $Q$ is nonempty, choose $t_*\in Q$ maximizing $A(z,t)$ over $Q$. The second property gives
$$
A(z,t_*)>A(x^*,t_*)\ge v_*.
$$
Assign remaining coverage $\beta_t$ on $G\setminus\{t_*\}$ and zero elsewhere. This costs at most $g\le R$. Every target outside $Q$ has combined attacker payoff at most $v_*$: safe targets are suppressed, and unsafe targets satisfy the first property. Targets inside $Q$ have combined payoffs at most their payoffs under $z$, hence at most $A(z,t_*)$. Target $t_*$ receives no remaining coverage, so it is a best response. But
$$
c'_{t_*}=z_{t_*}<x_{t_*}^*\le s_{t_*}.
$$
Some participating type therefore receives less than its required utility at this best response.
If $Q$ is empty, then $z\ge x^*$ coordinatewise. Assign $\beta_t$ on $G$ and zero on $V$. All attacker payoffs are at most $v_*$. If $\sum_tx_t^*=k$, feasibility forces $z=x^*$. Otherwise, the third property supplies an unsafe coordinate equal to one, which remains one under $z\ge x^*$. In either case an unsafe target retains payoff $v_*$ and is a best response. Its coverage is below its threshold.
Thus every feasible $z$ is defeated when $g\le R$. $\square$
The function $f$ is piecewise affine. Its breakpoints in the permitted domain occur among
$$
r^a(t),
\qquad
r^a(t)-\Delta_ts_t,
$$
together with the finite endpoint $P$, when present. There are $O(m)$ breakpoints. Sorting them and solving an affine equation on the relevant interval computes the smallest feasible $v_*$ exactly, including flat intervals.
All constructed rationals have polynomial bit length: they result from polynomially many rational additions, multiplications, comparisons, and divisions. Baseline computation, the fixed-subset test, and suppression-cost evaluation therefore take time polynomial in $m,\tau,r,L$.
By Lemma 1, a successful deviation exists exactly when some nonempty subset passes this test. That subset is a polynomial-size certificate of nonmembership. Hence
$$
\text{mass }\epsilon\text{-core membership}\in\mathrm{coNP}.
$$
The same proof gives the exact algorithm
$$
2^\tau\operatorname{poly}(m,\tau,r,L).
$$
The canonical promise can be checked directly.
Define
$$
P_{\max}=\max_t p^a(t),
\qquad
F(v)=\sum_t\max\left\{0,\frac{r^a(t)-v}{\Delta_t}\right\}.
$$
Lemma 3. Since $K(\mu)>0$, the society is canonical exactly when
$$
K(\mu)\le F(P_{\max}).
$$
Proof. Suppose $\bar c$ is canonical, and let $v=\max_tA(\bar c,t)$. Every attacker payoff is at least its fully covered payoff, so $v\ge P_{\max}$.
Whenever $\bar c_t>0$, canonicality gives $A(\bar c,t)=v$, and hence
$$
\bar c_t=\frac{r^a(t)-v}{\Delta_t}.
$$
Whenever $\bar c_t=0$, we have $r^a(t)\le v$. Therefore
$$
\bar c_t=\max\left\{0,\frac{r^a(t)-v}{\Delta_t}\right\},
\qquad
K(\mu)=F(v)\le F(P_{\max}).
$$
Conversely, assume $0<K(\mu)\le F(P_{\max})$. Continuity gives a value $v\ge P_{\max}$ with $F(v)=K(\mu)$, because $F$ vanishes at $\max_t r^a(t)$. Set
$$
\bar c_t=\max\left\{0,\frac{r^a(t)-v}{\Delta_t}\right\}.
$$
The condition $v\ge P_{\max}$ ensures $\bar c_t\le1$. Every positive coordinate has attacker payoff $v$, while every zero coordinate has payoff at most $v$. Since $K(\mu)>0$, a positive coordinate exists. Thus $\bar c$ spends exactly $K(\mu)$ and assigns positive coverage only to best responses. $\square$
I use the classical $\mathrm{NP}$-completeness of PARTITION with positive binary-encoded integer weights. See [Karp, “Reducibility Among Combinatorial Problems”](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
We may restrict to instances with $\ell\ge3$ weights and even total sum. Odd-total instances are automatically negative; instances with fewer than three weights can be decided directly. These exceptional instances can be mapped to fixed positive or negative instances satisfying the restrictions, for example $(1,1,2)$ and $(1,1,4)$.
Let the weights be
$$
w_1,\ldots,w_\ell>0,
\qquad
A=\sum_{i=1}^{\ell}w_i,
\qquad
W=A/2.
$$
The PARTITION question is whether some subset has weight sum $W$.
If $[a,b]$ contains no positive rational, there are no integer pairs satisfying the size promise, so the promised class is empty. We henceforth consider the intended nonempty case.
Choose a fixed positive rational $u/v\in[a,b]$, with positive integers $u,v$. Choose $n\ge\ell$, $n\ge3$, so that $n+1$ is divisible by $u$. Define
$$
m=n+1,
\qquad
N=\frac{v(n+1)}{u}.
$$
Then $m/N=u/v\in[a,b]$. Because $u,v$ are fixed, $n$ and $N$ are polynomially bounded in $\ell$.
There are item targets $1,\ldots,n$ and a control target $0$. For auxiliary item targets $i>\ell$, set $w_i=0$. These auxiliary targets have no associated item type.
Define
$$
\beta=\frac1{8n},
\qquad
\gamma=\frac1{16A},
\qquad
\alpha=\frac{\gamma}{2},
\qquad
v_0=\frac{\gamma}{4},
$$
$$
\Delta_0=\frac{\gamma}{2n(1-\beta)},
\qquad
\eta=\alpha\Delta_0
=\frac{\gamma^2}{4n(1-\beta)},
$$
$$
E=\frac{n(1-\beta)}{\gamma}-A=(16n-3)A,
\qquad
k_0=\frac58,
$$
and prescribe the total resource budget
$$
K_\star=k_0+n-v_0E+\eta W^2-\frac{\eta}{2}.
$$
For each item target, let
$$
\Delta_i=
\frac{\gamma}{(1-\beta)(1-\beta-\gamma w_i)},
\qquad
r^a(i)=\Delta_i,
\qquad
p^a(i)=0.
$$
At the control target, let
$$
r^a(0)=v_0+\frac{\Delta_0}{2},
\qquad
p^a(0)=v_0-\frac{\Delta_0}{2}.
$$
These are valid strict payoff pairs. The item denominators are positive because
$$
\beta+\gamma w_i\le\frac1{24}+\frac1{16}=\frac5{48}<1.
$$
Also,
$$
p^a(0)
=\frac{\gamma}{4}
\left(1-\frac1{n(1-\beta)}\right)>0,
$$
since $n(1-\beta)=n-\frac18>1$. Thus every attacker payoff is nonnegative.
There are $\ell$ item types, a sponsor type $\sigma$, and a type $\omega$. Their full-mass resource budgets are
$$
\kappa_i=\alpha w_i\quad(1\le i\le\ell),
\qquad
\kappa_\sigma=k_0,
\qquad
\kappa_\omega=K_\star-k_0-\alpha A.
$$
All are positive. For the last one, use
$$
n-v_0E=\frac{3n}{4}+\frac3{64},
\qquad
\alpha A=\frac1{32},
$$
to obtain
$$
\kappa_\omega
=\frac{3n}{4}+\frac1{64}
+\eta\left(W^2-\frac12\right)>0.
$$
To realize these budgets with dyadic masses, choose $h$ such that $2^h\ge\ell+2$. Give every item type and the sponsor mass $2^{-h}$, and give $\omega$ the remaining mass
$$
\mu_\omega=1-(\ell+1)2^{-h}>0.
$$
Set
$$
\rho_\theta=\frac{\kappa_\theta}{N\mu_\theta}.
$$
Then all rates are positive rational numbers and $K(\mu)=K_\star$.
Define positive numbers $s_{\theta t}$ as follows:
Set defender payoffs to
$$
p^d_\theta(t)=0,
\qquad
r^d_\theta(t)=\frac1{s_{\theta t}}.
$$
Thus
$$
D_\theta(z,t)=\frac{z_t}{s_{\theta t}}.
$$
The candidate consists of one coalition with $q=\mu$ and coverage $x=0$. It is feasible. Set $\epsilon=1$.
Every type’s baseline utility is zero, because all defender payoffs at zero coverage are zero. Therefore improvement requires utility at least one, and the numbers $s_{\theta t}$ are exactly the coverage thresholds.
The largest fully covered attacker payoff is
$$
P_{\max}=p^a(0)=v_0-\frac{\Delta_0}{2}>0.
$$
Every item target has $\Delta_i>\gamma>P_{\max}$, so its contribution to $F(P_{\max})$ is $1-P_{\max}/\Delta_i$. The control target contributes one.
From the item definitions,
$$
\sum_{i=1}^n\frac1{\Delta_i}=(1-\beta)E.
$$
Hence
$$
F(P_{\max})=1+n-P_{\max}(1-\beta)E.
$$
Subtracting the prescribed budget gives
$$
F(P_{\max})-K_\star
=
\frac38
+v_0\beta E
+\frac{\Delta_0}{2}(1-\beta)E
-\eta W^2+\frac{\eta}{2}.
$$
All terms except $-\eta W^2$ are positive, and
$$
\eta W^2
=
\frac{(\gamma A)^2}{16n(1-\beta)}
=
\frac1{4096n(1-\beta)}
<\frac1{4096}.
$$
Consequently,
$$
0<K_\star<F(P_{\max}).
$$
Lemma 3 proves that every constructed society is canonical.
By Lemma 1, it suffices to consider full-mass participating sets.
For every target and every feasible coverage,
$$
D_\omega(z,t)=\frac{z_t}{2}\le\frac12<1.
$$
Thus $\omega$ can never meet its required improvement, and no successful coalition contains it.
Consider a nonempty coalition of item types without the sponsor. Its budget satisfies
$$
k\le\alpha A=\frac1{32}.
$$
For any strategy $x$ of this coalition, let $G$ be the targets where every participant meets its threshold under $x$. The control target is outside $G$. Every target in $G$ is an item target with $x_i\ge\beta$, so
$$
|G|\beta\le\sum_tx_t\le k,
\qquad
|G|\le\frac{k}{\beta}\le\frac n4.
$$
Meanwhile, $K_\star>3n/4$, so the remaining budget satisfies
$$
R=K_\star-k>\frac{3n}{4}-\frac1{32}>\frac n4.
$$
The remaining society can therefore assign coverage one on every target in $G$ and zero elsewhere. Every such covered item target then has attacker payoff zero. The control target has attacker payoff at least $p^a(0)>0$, so every best response lies outside $G$.
At targets outside $G$, remaining coverage is zero. Hence some participating type receives less than one at a best response. Pessimistic tie-breaking defeats the deviation.
Therefore every successful coalition contains the sponsor.
Let a coalition consist of the sponsor and item types in $J$. Define
$$
Z=\sum_{j\in J}w_j.
$$
Its budget and thresholds are
$$
k=k_0+\alpha Z,
\qquad
s_i=
\begin{cases}
\beta+\gamma w_i,&i\in J,\\
\beta,&i\notin J,
\end{cases}
\qquad
s_0=2.
$$
Consider the strategy
$$
x_i^*=s_i\quad(1\le i\le n),
\qquad
x_0^*=\frac12-\alpha Z,
$$
and the payoff value
$$
v=v_0+\eta Z.
$$
Since $\alpha Z\le\alpha A=1/32$, the control coverage is in $[0,1]$. Moreover,
$$
\sum_tx_t^*
=n\beta+\gamma Z+\frac12-\alpha Z
=k_0+\alpha Z=k.
$$
The control target’s attacker payoff is $v$. Each item target’s attacker payoff is strictly larger:
$$
A(x^*,i)=\Delta_i(1-s_i)\ge\gamma>v.
$$
For the last inequality, observe that $\Delta_0<\gamma$ and
$$
v=v_0+\Delta_0\alpha Z
\le\frac{\gamma}{4}+\frac{\Delta_0}{32}
<\gamma.
$$
We now check that this is precisely the distinguished strategy in Lemma 2. Here the sole threshold exceeding one is the control threshold, so the permitted lower endpoint is $p^a(0)$. We have $v>p^a(0)$, every item coordinate is saturated at $s_i$, and the control coordinate equals $h_0(v)$. Therefore $f(v)=k$.
In a neighborhood of $v$, the item coordinates remain saturated while the control coordinate decreases with slope $-1/\Delta_0$. Thus $f$ is strictly decreasing there. Since $f$ is globally nonincreasing, every smaller permitted value has $f>k$. Hence $v=v_*$.
The safe targets are exactly the item targets. Their total suppression cost is
$$
g=\sum_{i=1}^n
\left(1-\frac{v}{\Delta_i(1-s_i)}\right).
$$
For an unselected item target,
$$
\frac1{\Delta_i(1-\beta)}
=\frac{1-\beta-\gamma w_i}{\gamma}.
$$
Selecting its associated type increases this reciprocal by exactly $w_i$, because
$$
\frac1{\Delta_i(1-\beta-\gamma w_i)}
=\frac{1-\beta}{\gamma}.
$$
Consequently,
$$
\sum_{i=1}^n\frac1{\Delta_i(1-s_i)}=E+Z,
$$
and therefore
$$
g=n-(v_0+\eta Z)(E+Z).
$$
Lemma 2 says that the coalition succeeds exactly when
$$
g>R=K_\star-k,
$$
or equivalently $k+g-K_\star>0$.
The decisive calculation is
$$
\begin{aligned}
k+g
&=k_0+n-v_0E
+(\alpha-v_0-\eta E)Z-\eta Z^2.
\end{aligned}
$$
Since
$$
\eta E
=\frac{\gamma}{4}-\eta A
=v_0-\eta A,
$$
we have
$$
\alpha-v_0-\eta E=\eta A=2\eta W.
$$
Substituting the definition of $K_\star$ yields
$$
k+g-K_\star
=\eta\left(\frac12-(Z-W)^2\right).
$$
Both $Z$ and $W$ are integers, and $\eta>0$. Thus
$$
k+g-K_\star>0
\quad\Longleftrightarrow\quad
Z=W.
$$
We have proved:
$$
\boxed{
\text{A successful deviation exists}
\quad\Longleftrightarrow\quad
\text{the PARTITION instance is positive}.
}
$$
The full-mass lemma ensures that real partial-mass deviations cannot introduce additional positive instances.
The construction has polynomial size. The number of targets and types is polynomial in $\ell$. All parameters have bit length polynomial in $\log A+\log n$; divisions by the dyadic masses and $N$ preserve polynomial bit length. The explicitly listed payoff matrices therefore also have polynomial size.
The reduction maps positive PARTITION instances to nonmembership, and negative instances to membership. Every output satisfies canonicality and the population-size promise.
Together with the upper bound in Section 2, this proves
$$
\text{nonmembership is }\mathrm{NP}\text{-complete},
$$
and
$$
\boxed{
\text{mass }\epsilon\text{-core membership is }\mathrm{coNP}\text{-complete}.
}
$$
In particular, a runtime polynomial in $m,\tau,r,L$ exists exactly when $\mathrm{P}=\mathrm{NP}$: such an algorithm would decide the complement of the constructed membership instance and thereby solve PARTITION. Conversely, $\mathrm{P}=\mathrm{NP}$ implies $\mathrm{coNP}=\mathrm{P}$.
For many-one hardness, membership is $\mathrm{NP}$-hard exactly when $\mathrm{NP}=\mathrm{coNP}$. Necessity follows from its $\mathrm{coNP}$ upper bound and closure of $\mathrm{coNP}$ under polynomial-time many-one reductions. Sufficiency follows from its $\mathrm{coNP}$-completeness.
Under Turing reductions, there is an unconditional $\mathrm{NP}$-hardness statement: construct the instance, query membership once, and negate the answer to decide PARTITION.
Thus the complete classification is proved. What remains open under the literal many-one dichotomy is precisely the corresponding general complexity-class equality.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed $\mathrm{coNP}$-completeness classification. I found no false central step or substantive mathematical gap. There is one minor gap in the justification of bit complexity.
The distinction between many-one and Turing hardness is correct: the reduction proves many-one hardness of nonmembership, and therefore $\mathrm{coNP}$-hardness of membership. It also proves $\mathrm{NP}$-hardness of membership under polynomial-time Turing reductions.
The baseline formulas correctly implement the candidate’s combined coverage and type-specific pessimistic tie-breaking. Products of rational candidate coordinates remain rational, so the baselines can be computed exactly.
Because $\delta_{\theta t}>0$, the condition
$$
D_\theta(z,t)\ge W_\theta
$$
is equivalent, on the coverage domain, to the stated threshold condition. Taking the maximum over participating types is correct. Keeping thresholds above one uncapped is essential and is handled correctly.
Lemma 1 is valid. Replacing each positive participating mass by that type’s entire mass:
Thus the original strategy remains feasible and its universal guarantee remains valid. The argument applies to real partial masses and includes the case where the remaining mass becomes zero.
There is no assumption here that types are indivisible in the original problem. Indivisibility of participation is a consequence of the monotonicity argument.
The three cases defining $H_t(x,v)$ are correct.
When suppression is required and attainable, the denominator is positive: $A(x,t)>v$ together with $p^a(t)\le v$ excludes $x_t=1$. The quotient lies in $(0,1]$. When $p^a(t)>v$, suppression is impossible even at full coverage.
The best-response reachability criterion is also correct:
$$
\sum_{j\ne t}H_j(x,A(x,t))\le R.
$$
Setting the remaining society’s coverage at the proposed best response to zero preserves its best-response status and decreases expenditure. The other coordinates can then be suppressed independently to the required bound.
The success criterion correctly incorporates pessimistic ties. If a reachable target has $x_t<s_t$, the reachability construction with remaining coverage zero at that target exposes a utility failure for at least one participant. Conversely, coverage can only increase under the remaining society’s action, so a reachable target with $x_t\ge s_t$ satisfies every participant’s requirement.
The discussion of rational strategies does not restrict the underlying deviation problem improperly: Lemma 2 subsequently treats arbitrary real alternative strategies and produces a rational successful strategy whenever one exists.
The initial case is sufficient: if every threshold is attainable and their sum fits the budget, setting $x=s$ protects every possible best response.
In the remaining case, the restriction $v\ge P$ correctly ensures feasible coordinates at targets whose thresholds exceed one. The existence of a smallest feasible $v_*$ follows from the stated continuity, monotonicity, and endpoint behavior.
When there is no finite lower endpoint, the failed initial case indeed implies
$$
\sum_t s_t>k,
$$
so the feasible set cannot extend arbitrarily far toward negative payoff values.
All three properties used in Lemma 2 follow as written.
For the third property, the cases are exhaustive:
The argument also handles zero thresholds: such coordinates cannot belong to the unsafe set.
Every unsafe target has combined attacker payoff at most $v_*$. If one were a best response, all safe targets would have to be suppressed to at most that same bound. The cost is at least $g$, which exceeds the remaining budget.
This argument remains valid when a suppression cost is infinite.
The proof examines every feasible real strategy $z$.
If $Q$ is nonempty, the chosen target has strictly larger payoff than under $x^*$ and hence payoff above $v_*$. The proposed remaining coverage:
The chosen target is consequently a best response and has coverage strictly below its threshold. This is sufficient to defeat success, even if other targets tie with it.
If $Q$ is empty, either budget equality forces $z=x^*$, or the third property supplies an unsafe coordinate already equal to one. In the latter case it remains unchanged under $z\ge x^*$ and remains below its unattainable threshold. The remaining strategy makes such a target a best response.
Lemma 2 is therefore valid, including the boundary case $g=R$. The strict success inequality $g>R$ is necessary.
The breakpoint list for $f$ is correct. Each summand changes form only at
$$
r^a(t)
\quad\text{or}\quad
r^a(t)-\Delta_t s_t,
$$
with the permitted-domain endpoint included separately. Sorting these values and examining the affine pieces determines $v_*$, including cases involving flat pieces.
Lemma 1 and the fixed-subset test give a polynomial-size certificate consisting only of the participating subset. The verifier computes the strategy and suppression comparison itself. Thus the continuous choices and universal quantifier do not obstruct the claimed $\mathrm{coNP}$ upper bound.
Where: Section 2.3, “All constructed rationals have polynomial bit length: they result from polynomially many rational additions, multiplications, comparisons, and divisions.”
Issue: A polynomial number of rational arithmetic operations does not, by itself, imply polynomial bit length. Repeated squaring is a counterexample to that general justification.
The explicit formulas here do not exhibit that obstruction, so this is an expositional gap rather than a failure of the algorithm.
Minimum clarification needed: Give explicit polynomial bit-length bounds for the baseline products, breakpoint values, affine coefficients, computed $v_*$, and suppression-cost sums. The justification should refer to the structure of these particular computations, rather than merely their operation count.
Lemma 3 is correct.
For a canonical coverage, the maximum attacker payoff is at least every fully covered attacker payoff. Positive coordinates must attain that maximum; zero coordinates have uncovered payoff no larger than it. These facts give the stated expression for every coordinate and establish necessity.
For sufficiency, continuity supplies the required payoff level. The lower bound on that level ensures coordinates do not exceed one. Positive total resource expenditure ensures at least one positive coordinate, so the payoff level is actually attained and the support condition follows.
The criterion also excludes total budgets above feasible full expenditure. There is no missing assumption that canonicality permits overspending.
The reduction uses the standard binary integer PARTITION problem. Its restriction to positive weights, even total sum, and at least three weights is legitimate; the exceptional cases are decidable and the two displayed replacement instances have the claimed answers. The cited completeness result is the classical one in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
The population-size construction is valid for each fixed nonempty promise. A fixed rational ratio can be hardcoded, and the padding required for divisibility has constant overhead relative to the number of weights.
The parameter calculations check out:
The zero-coverage candidate is feasible and gives baseline zero to every type, regardless of which targets are initial best responses.
The canonicality computation is correct. In particular,
$$
\sum_{i=1}^n\frac1{\Delta_i}=(1-\beta)E
$$
and the displayed subtraction from $F(P_{\max})$ is accurate. The bound on $\eta W^2$ establishes the required strict inequality. Consequently, every output satisfies the canonical promise.
Type $\omega$ cannot participate because its utility is always at most $\frac12$, below the required improvement level.
For a coalition containing only item types, the bound on the number of currently safe targets follows from their minimum coverage requirement. The remaining budget can fully cover all such targets.
After that action, each formerly safe target has attacker payoff zero, whereas the control target has strictly positive attacker payoff. Thus every best response lies outside the formerly safe set, where remaining coverage is zero. At least one participant fails its requirement at such a best response.
The argument correctly uses type-specific pessimistic tie-breaking; the same type need not fail at every best response.
These exclusions leave exactly the sponsor-containing coalitions analyzed in Section 6.3.
The proposed sponsor-containing strategy has the claimed coverage sum and control payoff. Every item target has strictly larger attacker payoff than the control target.
The identification with $x^*$ is valid: the item coordinates are saturated, the control coordinate follows its affine branch, and local strict decrease together with global monotonicity establishes minimality of $v$.
The reciprocal suppression-cost calculations are correct. They yield
$$
g=n-(v_0+\eta Z)(E+Z).
$$
The decisive algebra also checks:
$$
\eta E=v_0-\eta A,
$$
and therefore
$$
k+g-K_\star
=\eta\left(\frac12-(Z-W)^2\right).
$$
Since $Z$ and $W$ are integers, the strict positivity condition holds exactly when $Z=W$. Padding targets contribute correctly without introducing associated types.
Together with Lemma 1 and the excluded coalition cases, this establishes the equivalence for all allowed deviations, including real partial-mass deviations.
The construction has polynomial output size. The number of targets, types, and explicitly listed payoff entries is polynomial, and the reduction parameters have polynomial bit length.
The reduction orientation is correctly stated:
$$
\text{positive PARTITION instance}
\quad\Longleftrightarrow\quad
\text{nonmembership}.
$$
Consequently, nonmembership is $\mathrm{NP}$-complete and membership is $\mathrm{coNP}$-complete.
The further conclusions are correct:
The prover’s final “partial” designation reflects the literal many-one dichotomy, not an unresolved mathematical step in its classification. The write-up establishes the refined classification, subject only to the minor bit-complexity clarification identified above.
⟨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.