Answer: \(\mathrm{NP}\text{-hard}\)
Proposition 5.2 — class: hardness
Given complete agent types \(\Theta\), rational masses \(\mu_\theta\), finite feasible assignment sets \(\mathcal A_\theta\), and explicitly encoded exact task, value, and cost functions, a candidate mass coalition structure \(Q=(q^1,\ldots,q^\ell)\) satisfies \(\sum_j q^j_{\theta,X}=\mu_\theta\). A deviation selects \(r^j_{\theta,X}\) with \(0\le r^j_{\theta,X}\le q^j_{\theta,X}\), sets \(q=\sum_j r^j\), and gives each participating pair \((\theta,X)\) pessimistic utility \(u^\downarrow_{\theta,X}(q)=\inf_y[v_\theta(t(A(q)+A(y)))-\operatorname{cost}_\theta(X)]\), where \(A(z)=\sum_{\theta,X}z_{\theta,X}X\) and \(y\) ranges over feasible residual mass assignments. Decide whether there is no nonzero deviation for which every participating source cell strictly improves, i.e. \(u^\downarrow_{\theta,X}(q)>u^\downarrow_{\theta,X}(q^j)\) whenever \(r^j_{\theta,X}>0\).
An instance has finitely many types \(T\), rational masses \(\mu_t\) with \(\sum_t\mu_t=1\), and finite action sets \(A_t\) of integral resource-to-task assignments; task functions \(f_j\), value functions \(v_t\), and costs \(c_t\) are polynomial-time computable.
For action-masses \(w=(w_{t,a})\), let \(B_{j,r}(w)=\sum_{t,a}w_{t,a}a_{j,r}\), and define \(P_t(a;w)\) as the infimum of \(v_t((f_j(B_j(w+y)))_j)-c_t(a)\) over \(y\ge0\) satisfying \(\sum_a y_{t,a}=\mu_t-\sum_a w_{t,a}\) for every \(t\).
A coalition structure is a finite rational family \(q_{\ell,t,a}\ge0\) with \(\sum_{\ell,a}q_{\ell,t,a}=\mu_t\). Its current utility for mass \(q_{\ell,t,a}\) is \(P_t(a;q_\ell)\).
A deviation chooses \(0\le z_{\ell,t,a}\le q_{\ell,t,a}\), has positive total mass, and sets \(\bar z_{t,a}=\sum_\ell z_{\ell,t,a}\). It blocks iff \(P_t(a;\bar z)>P_t(a;q_\ell)\) for every \((\ell,t,a)\) with \(z_{\ell,t,a}>0\).
Is continuous pessimistic-core membership—whether a given rational mass-action coalition structure has no blocking positive-mass deviation—in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard?
For finite-agent RTGs with finitely many feasible resource assignments, pessimistic-core membership is \(\Pi^p_2\)-complete.
Under any standard explicit encoding that can represent rational arithmetic circuits, continuous pessimistic-core membership is \(\mathrm{NP}\)-hard.
This remains true under the following restrictions:
The reduction is from \(3\)-SAT.
Let \(\varphi\) be a \(3\)-CNF formula with variables \(X_1,\ldots,X_n\). For a literal \(\lambda\), define its truth-value polynomial by
\[ L_{X_i}(x)=x_i,\qquad L_{\neg X_i}(x)=1-x_i. \]
Define the nonnegative polynomial
\[ F_\varphi(x) = \sum_{i=1}^n x_i^2(1-x_i)^2 + \sum_{C\in\varphi} \left( \prod_{\lambda\in C}(1-L_\lambda(x)) \right)^2. \]
Let
\[ m_\varphi=\min_{x\in[0,1]^n}F_\varphi(x). \]
Then \(m_\varphi=0\) if and only if \(\varphi\) is satisfiable. Consequently, if \(\varphi\) is unsatisfiable, then \(m_\varphi>0\).
All summands in \(F_\varphi\) are nonnegative.
Suppose first that \(F_\varphi(x)=0\). For every \(i\),
\[ x_i^2(1-x_i)^2=0, \]
so \(x_i\in\{0,1\}\). Thus \(x\) defines a Boolean assignment.
For every clause \(C\), its clause summand is zero. Hence
\[ \prod_{\lambda\in C}(1-L_\lambda(x))=0. \]
At least one literal \(\lambda\in C\) therefore satisfies \(L_\lambda(x)=1\). Thus every clause is satisfied.
Conversely, if \(x\in\{0,1\}^n\) is a satisfying assignment, all integrality summands vanish, and every clause has a true literal, making its clause summand vanish. Therefore \(F_\varphi(x)=0\).
Finally, \(F_\varphi\) is continuous and \([0,1]^n\) is compact, so the minimum is attained. If \(\varphi\) is unsatisfiable, the preceding equivalence shows that \(F_\varphi\) is strictly positive everywhere on this compact set. Hence \(m_\varphi>0\). \(\square\)
Introduce one special type \(s\) and one variable type \(t_i\) for each \(X_i\). Their masses are
\[ \mu_s=\frac12,\qquad \mu_{t_i}=\frac{1}{2n}. \]
These masses sum to one.
There are tasks \(0,1,\ldots,n\), each with one resource coordinate.
Type \(s\) has actions \(A,D\):
Type \(t_i\) has actions \(T_i,F_i\):
All assignments are integral and belong to \(\{0,1\}\).
Define
\[ f_0(B_0)=B_0, \qquad f_i(B_i)=2nB_i \]
for \(i=1,\ldots,n\).
Thus, if the entire mass of type \(t_i\) is being completed freely, then \(f_i(B_i)\) ranges over exactly \([0,1]\).
All costs are zero. For every variable type, set
\[ v_{t_i}\equiv 0. \]
For the special type, set
\[ v_s(u_0,u_1,\ldots,u_n) = \left(u_0-\frac14\right)^2 F_\varphi(u_1,\ldots,u_n). \]
This is a nonnegative rational polynomial of degree at most eight. Its arithmetic-circuit description has size polynomial in \(\lvert\varphi\rvert\).
Use three coalition indices. The nonzero entries are
\[ q_{1,s,A}=\frac14,\qquad q_{2,s,A}=\frac14, \]
and, for every \(i\),
\[ q_{3,t_i,F_i}=\frac{1}{2n}. \]
All unspecified entries are zero. The required mass equalities hold for every type.
Every positive mass in the given coalition structure has current utility zero.
Consider the special mass in coalition \(1\). The vector \(q_1\) forces exactly \(1/4\) of type \(s\) to play \(A\). In the pessimistic completion, the remaining \(1/4\) of type \(s\) may be assigned to \(D\). This gives \(u_0=1/4\), and therefore
\[ v_s(u)= \left(\frac14-\frac14\right)^2F_\varphi(u_1,\ldots,u_n)=0. \]
Because \(v_s\) is nonnegative, the infimum is exactly zero:
\[ P_s(A;q_1)=0. \]
The same argument gives \(P_s(A;q_2)=0\).
For every variable type, both the value and the costs are identically zero. Hence
\[ P_{t_i}(F_i;q_3)=0. \]
Thus every current utility is zero. \(\square\)
Any deviation containing positive mass of a variable type cannot block: that participant’s prospective utility and current utility are both zero, while blocking requires a strict improvement.
Consequently, every blocking deviation must consist solely of special-type mass taken from coalitions \(1\) and \(2\). Let its aggregate mass be
\[ s=z_{1,s,A}+z_{2,s,A}, \qquad 0<s\le\frac12. \]
In a pessimistic completion:
Therefore
\[ P_s(A;\bar z) = \min_{\substack{b\in[s,1/2]\\x\in[0,1]^n}} \left(b-\frac14\right)^2F_\varphi(x). \]
Since the variables \(b\) and \(x\) are independent and both factors are nonnegative,
\[ P_s(A;\bar z) = \gamma(s)m_\varphi, \]
where
\[ \gamma(s)= \begin{cases} 0,&s\le\frac14,\\ \left(s-\frac14\right)^2,&s>\frac14. \end{cases} \]
If \(\varphi\) is satisfiable, the constructed coalition structure has no blocking deviation.
By Lemma 1, \(m_\varphi=0\). Hence every deviation consisting only of special-type mass has prospective utility
\[ P_s(A;\bar z)=\gamma(s)m_\varphi=0. \]
Its participants therefore do not strictly improve over their current utility zero.
Any deviation containing variable-type mass also fails, because such a participant has prospective and current utility zero. These cases exhaust all positive-mass deviations. Hence no deviation blocks. \(\square\)
If \(\varphi\) is unsatisfiable, the constructed coalition structure has a blocking deviation.
By Lemma 1, \(m_\varphi>0\). Select all special-type mass from coalitions \(1\) and \(2\):
\[ z_{1,s,A}=\frac14,\qquad z_{2,s,A}=\frac14. \]
Then \(s=1/2\), and therefore
\[ P_s(A;\bar z) = \left(\frac12-\frac14\right)^2m_\varphi = \frac{m_\varphi}{16}>0. \]
Every selected participant currently receives zero by Lemma 2. Thus every selected participant strictly improves, so this deviation blocks. \(\square\)
Combining the two lemmas gives
\[ \varphi\text{ is satisfiable} \quad\Longleftrightarrow\quad q\text{ has no blocking positive-mass deviation}. \]
The construction is computable in polynomial time. It is therefore a many-one reduction from \(3\)-SAT to continuous pessimistic-core membership.
Continuous pessimistic-core membership, as defined in the question, is \(\mathrm{NP}\)-hard. Thus it cannot be polynomial-time solvable unless \(\mathrm P=\mathrm{NP}\).
The reduction uses the absence of monotonicity restrictions on value functions. It does not establish hardness for variants requiring all value and task functions to be monotone.
⟨structured verdict parsed — rendered above⟩
The reduction is substantively correct and establishes \( \mathrm{NP} \)-hardness under a natural succinct arithmetic-circuit encoding. No false central step was found. Three minor formal gaps should be clarified: the precise input encoding, attainment of the infimum used in Section 4, and the case \( n=0 \).
Lemma 1 is correct.
The claimed degree bound is also correct: integrality terms have degree four, clause terms have degree at most six, and multiplication by \( (u_0-\frac14)^2 \) gives degree at most eight.
For \( n\ge1 \), the masses are valid:
\[ \frac12+n\frac{1}{2n}=1. \]
The actions are integral \( \{0,1\} \)-assignments, every type has exactly two actions, the task functions are linear, and all costs vanish.
The arithmetic circuit for \( v_s \) has polynomial size in \( |\varphi| \). The rational numbers used in the construction have polynomial bit length.
The coalition structure assigns all special mass between coalitions \( 1 \) and \( 2 \), and all variable-type mass to coalition \( 3 \), so the required mass equalities hold.
The write-up does not address \( n=0 \), for which \( 1/(2n) \) is undefined. This is a minor domain omission because the reduction only needs to specify an NP-hard source family with \( n\ge1 \), but that restriction must be stated.
Lemma 2 is correct.
For coalition \( 1 \), the completion can place the remaining special mass on \( D \), making the total task-\( 0 \) load exactly \( 1/4 \). Therefore the special value is zero. Since the value function is globally nonnegative, the infimum cannot be negative, so \( P_s(A;q_1)=0 \). The same reasoning applies to coalition \( 2 \).
Every variable-type value and cost is identically zero, so the corresponding current utilities are zero under every completion.
The exclusion of deviations containing variable-type mass is correct. Every such selected participant has both prospective and current utility zero, whereas blocking requires strict improvement for every selected positive-mass entry.
For a special-only deviation, its aggregate action vector indeed contains mass \( s \) on \( A \). Completion of the remaining special mass makes the final \( A \)-mass range over \( [s,1/2] \).
Because no variable-type mass belongs to the deviation, completion freely allocates the full mass \( 1/(2n) \) of each variable type. Thus each normalized task output ranges independently over \( [0,1] \).
The displayed formula
\[ P_s(A;\bar z)=\gamma(s)m_\varphi \]
is correct. Both factors are nonnegative and depend on independent variables. The minimum of the first factor over \( [s,1/2] \) is zero when \( s\le1/4 \), and \( (s-1/4)^2 \) when \( s>1/4 \).
Formally, the definition uses an infimum, while this section immediately writes a minimum. The needed compactness, continuity, and exact parametrization of the feasible completion set are all present implicitly, but should be stated explicitly.
If \( \varphi \) is satisfiable, \( m_\varphi=0 \), so every special-only deviation gives prospective utility zero. Deviations containing variable mass also fail strict improvement. Hence the constructed instance is a yes-instance of core membership.
If \( \varphi \) is unsatisfiable, selecting all special mass gives \( s=1/2 \), and therefore
\[ P_s(A;\bar z)=\frac{m_\varphi}{16}>0. \]
Both selected entries previously had utility zero, so this deviation blocks.
Thus the reduction has the correct many-one orientation:
\[ \varphi\in 3\text{-SAT} \quad\Longleftrightarrow\quad q\text{ has no blocking deviation}. \]
The construction proves hardness for an explicit encoding in which rational arithmetic circuits can be written with polynomial overhead. The phrase “under any standard explicit encoding that can represent rational arithmetic circuits” is not formally justified: mere representability does not guarantee a polynomial-size serialization or a polynomial-time translation into that encoding.
This does not undermine the hardness result for the natural arithmetic-circuit encoding, but the encoding should be fixed precisely or the theorem should be limited to encodings that simulate these circuits with polynomial overhead.
⟨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.