Answer: \(\mathrm{NP}\)-complete
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a game G = (N; ⃗b; q) and an outcome (CS, d), it is coNP-complete to decide whether (CS, d) is in the CS-core of G, even if bi(j) ≤n for all i, j ∈N.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete belief types \(\Theta\), rational masses \(\mu_\theta>0\) summing to \(1\), rational type-to-type belief weights \(b_{\theta\phi}\), a threshold \(q\), and a proposed finite coalition structure with type masses \(x_{j\theta}\) and demand rates \(d_{j\theta}\), decide whether the outcome is in the continuous CS-core. A blocking deviation selects masses \(y_{j\theta}\in[0,x_{j\theta}]\); every participating type \(\theta\) must believe it succeeds, meaning \(\sum_\phi b_{\theta\phi}Y_\phi\ge q\), where \(Y_\phi=\sum_j y_{j\phi}\), and the weighted incumbent payoff must satisfy \(\sum_{j,\theta} y_{j\theta}d_{j\theta}u_\theta(C_j)<1\). Is there such a deviation?
A society is given by its support: the list of \(\tau\) complete belief types \(\Theta\) with positive binary-rational masses \(\mu_\theta\), summing to \(1\); \(\tau\) counts supported types, not possible types.
The input includes nonnegative rational belief weights \(b_{\theta\phi}\) and a public rational threshold \(q>0\). Type \(\theta\) assigns weight \(b_{\theta\phi}\) per unit mass of type \(\phi\); its diagonal entry represents its own true weight.
A proposed structure consists of \(m\ge1\) coalitions with rational masses \(x_{j\theta}\ge0\), satisfying \(\sum_jx_{j\theta}=\mu_\theta\) and \(\sum_\theta x_{j\theta}>0\) for every \(j\). Types may be split among coalitions.
Nonnegative rational demand rates \(d_{j\theta}\) satisfy \(\sum_\theta x_{j\theta}d_{j\theta}=1\) for each coalition, including losing coalitions. Define \(u_\theta(C_j)=\mathbf{1}\{\sum_\phi b_{\theta\phi}x_{j\phi}\ge q\}\) and incumbent payoff rate \(p_{j\theta}=d_{j\theta}u_\theta(C_j)\).
A blocking deviation selects real masses \(0\le y_{j\theta}\le x_{j\theta}\), with \(Y_\theta=\sum_jy_{j\theta}\) and \(\sum_\theta Y_\theta>0\). It must satisfy \(\sum_\phi b_{\theta\phi}Y_\phi\ge q\) for every \(\theta\) with \(Y_\theta>0\), and \(\sum_{j,\theta}y_{j\theta}p_{j\theta}<1\). The entire society may deviate. An outcome is in the continuous CS-core exactly when no blocking deviation exists.
Is deciding whether a blocking deviation exists in \(\mathrm{P}\) or \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and the total binary input length \(L\).
For finite agents, CS-core membership is \(\mathrm{coNP}\)-complete, equivalently blocking-deviation existence is \(\mathrm{NP}\)-complete, even when every believed weight is at most the number of agents. [Source](https://www.ijcai.org/Proceedings/09/Papers/025.pdf)
No result settling this exact continuous problem was identified in the literature search.
Blocking-deviation existence is \(\mathrm{NP}\)-complete, even when \(m=2\)\), \(q=1\)\), all supported masses are dyadic rationals, and all belief weights are less than \(16\)\).
For general inputs, an exact deterministic algorithm runs in
\(\displaystyle 2^\tau(m\tau+L)^{O(1)}\)
bit operations, where \(L\)\) includes the society, proposed structure, and demand rates. Thus the problem is polynomial-time solvable for fixed \(\tau\)\), but remains \(\mathrm{NP}\)-hard for fixed \(m=2\)\). Continuous CS-core membership is consequently \(\mathrm{coNP}\)-complete.
The proof below handles arbitrary real deviations directly.
First compute every incumbent payoff \(p_{j\theta}\)\) using exact rational arithmetic. This requires \(O(m\tau^2)\)\) rational arithmetic operations, with polynomially bounded intermediate bit lengths.
For each nonempty \(S\subseteq\Theta\)\), consider the rational linear program minimizing
\(\displaystyle \sum_{j,\theta}p_{j\theta}y_{j\theta}\)
subject to
\(\displaystyle 0\le y_{j\theta}\le x_{j\theta}\quad\text{for every }j,\theta,\)
\(\displaystyle Y_\theta=\sum_jy_{j\theta}\quad\text{for every }\theta,\)
\(\displaystyle Y_\theta=0\quad\text{for }\theta\notin S,\)
\(\displaystyle \sum_\phi b_{\theta\phi}Y_\phi\ge q\quad\text{for }\theta\in S.\)
Let \(v_S\)\) denote its optimum, with \(v_S=+\infty\)\) when it is infeasible.
Claim. A blocking deviation exists exactly when \(v_S<1\)\) for some nonempty \(S\)\).
Proof. If a real blocking deviation exists, take its actual support \(S=\{\theta:Y_\theta>0\}\)\). Its masses satisfy this linear program and have objective less than \(1\)\), so \(v_S<1\)\).
Conversely, suppose the linear program for a nonempty \(S\)\) has a feasible solution of cost less than \(1\)\). Because \(q>0\)\), the all-zero vector violates every winning constraint indexed by \(S\)\). Thus this solution has positive total mass. Its actual support lies inside \(S\)\), and all actual participants satisfy their winning constraints. It is therefore a blocking deviation. Notice that requiring winning constraints for additional zero-mass types causes no false positive. ∎
Each linear program has \(m\tau+\tau\)\) variables, \(O(m\tau+\tau)\)\) constraints, and encoding length polynomial in \(m\tau+L\)\). Rational linear programming therefore gives the stated running time after enumerating \(2^\tau-1\)\) supports.
This also proves membership in \(\mathrm{NP}\), including the issue that deviations were allowed to be real. Indeed, every feasible linear program above is bounded: the \(y\)\)-variables have finite bounds, and the \(Y\)\)-variables are determined by them. A linear objective on a nonempty bounded polytope attains its minimum at a vertex.
Write \(M=m\tau+\tau\)\). After clearing denominators in each constraint, the integer coefficients have \(O(L)\)\) bits. A vertex is determined by \(M\)\) linearly independent active constraints. Cramer’s rule and Hadamard’s determinant bound imply that each vertex coordinate has
\(\displaystyle O\!\left(M(L+\log M)\right)\)
bits. Consequently, if a real blocking deviation exists, an optimal vertex of its support’s linear program supplies a rational blocking deviation of polynomial encoding length. Its bounds, support, winning inequalities, and strict cost inequality can all be verified by exact rational arithmetic in polynomial time.
Let \(H\)\) be a nonempty undirected simple graph, let \(A\)\) be its adjacency matrix, and let \(\omega(H)\)\) be its maximum clique size.
Lemma. For every nonnegative vector \(w\)\) satisfying \(\sum_v w_v=1\)\),
\(\displaystyle w^{\mathsf T}Aw\le 1-\frac1{\omega(H)}.\)
Proof. Suppose two positive coordinates \(w_u,w_v\)\) correspond to nonadjacent vertices. Define
\(\displaystyle a=\sum_t A_{ut}w_t,\qquad b=\sum_t A_{vt}w_t.\)
Because there are no loops and \(u,v\)\) are nonadjacent, these expressions do not depend on \(w_u,w_v\)\).
If \(a\ge b\)\), replace \(w_u\)\) by \(w_u+w_v\)\) and replace \(w_v\)\) by zero. The quadratic form changes by
\(\displaystyle 2w_v(a-b)\ge0.\)
If \(b>a\)\), the reverse transfer likewise increases the quadratic form. Each transfer preserves nonnegativity and total mass and decreases the support size.
Repeating this operation produces a vector \(w'\)\) supported on a clique of size \(s\le\omega(H)\)\), with \(w^{\mathsf T}Aw\le (w')^{\mathsf T}Aw'\)\). On this clique,
\(\displaystyle (w')^{\mathsf T}Aw'=1-\sum_v(w'_v)^2.\)
Cauchy–Schwarz gives \(\sum_v(w'_v)^2\ge1/s\)\). Hence
\(\displaystyle w^{\mathsf T}Aw\le1-\frac1s\le1-\frac1{\omega(H)}.\)
∎
This inequality applies to arbitrary real masses; it imposes no integrality assumption.
We use the standard \(\mathrm{NP}\)-hard CLIQUE problem: given an undirected simple graph \(G\)\) and an integer \(k\)\), decide whether \(\omega(G)\ge k\)\). This is also the source problem used in [Theorem 5 of the supplied paper](https://www.ijcai.org/Proceedings/09/Papers/025.pdf).
Write \(n=|V(G)|\)\). We may restrict to \(3\le k\le n\)\): cases outside this range are polynomial-time decidable and can be mapped to fixed yes- or no-instances within the restricted range.
Construct \(H\)\) by adding \(n\)\) vertices that form a clique and are adjacent to every original vertex. Set
\(\displaystyle N=2n,\qquad K=n+k.\)
Every clique in \(H\)\) contains at most \(n\)\) added vertices and at most \(\omega(G)\)\) original vertices. Conversely, all added vertices can accompany a maximum clique of \(G\)\). Therefore
\(\displaystyle \omega(H)=n+\omega(G),\)
and hence
\(\displaystyle \omega(H)\ge K\quad\Longleftrightarrow\quad\omega(G)\ge k.\)
Index the vertices of \(H\)\) by \(1,\ldots,N\)\), and let \(A\)\) be its adjacency matrix.
Define
\(\displaystyle D=2^{\lceil\log_2(2N)\rceil},\qquad \alpha=\frac1D,\qquad \delta=1-N\alpha,\qquad \lambda=\frac{2}{N\alpha},\qquad r=\frac{K-2}{K-1}.\)
We have \(2N\le D<4N\)\), so \(\delta\ge1/2\)\). Also \(r>0\)\).
There is one supported type for each vertex of \(H\)\), together with an auxiliary type \(a\)\). Their masses are
\(\displaystyle \mu_v=\alpha\quad(v\in V(H)),\qquad \mu_a=\delta.\)
These masses are positive dyadic rationals and sum to \(1\)\).
Use two coalitions. For \(j\in\{1,2\}\)\), set
\(\displaystyle x_{jv}=\frac{\alpha}{2},\qquad x_{ja}=\frac{\delta}{2},\)
and
\(\displaystyle d_{jv}=\lambda,\qquad d_{ja}=0.\)
Each coalition has mass \(1/2\)\), and its demands satisfy
\(\displaystyle \sum_\theta x_{j\theta}d_{j\theta} =N\frac{\alpha}{2}\lambda=1.\)
Set the public threshold to \(q=1\)\), and define beliefs by
\(\displaystyle b_{vw}=\frac{\lambda}{r}A_{vw}\quad(v,w\in V(H)),\)
\(\displaystyle b_{va}=\frac{2+v/N}{\delta}\quad(v\in V(H)),\)
\(\displaystyle b_{a\theta}=0\quad(\theta\in\Theta).\)
All entries are nonnegative, and all diagonal entries are zero. The distinct auxiliary-column entries also ensure that the supported graph types have distinct belief rows.
Every graph type believes that each incumbent coalition wins, because the auxiliary contribution alone is
\(\displaystyle b_{va}x_{ja} =\frac{2+v/N}{2} =1+\frac{v}{2N}>1.\)
The auxiliary type believes that every coalition loses. Thus the incumbent payoff rates are exactly
\(\displaystyle p_{jv}=\lambda,\qquad p_{ja}=0.\)
All requirements on the proposed outcome are satisfied.
The auxiliary type cannot participate in any blocking deviation: if \(Y_a>0\)\), its winning condition would require \(0\ge1\)\). Therefore every blocking deviation has \(Y_a=0\)\).
For graph types, define scaled masses
\(\displaystyle z_v=\lambda Y_v.\)
Their capacity bounds become
\(\displaystyle 0\le z_v\le\lambda\alpha=\frac2N=\frac1n.\)
A participating graph type’s winning condition becomes
\(\displaystyle \sum_w A_{vw}z_w\ge r \quad\text{whenever }z_v>0.\)
The deviation’s cost is
\(\displaystyle \sum_{j,\theta}y_{j\theta}p_{j\theta} =\lambda\sum_vY_v =\sum_vz_v.\)
Consequently, a blocking deviation exists exactly when a real vector \(z\)\) satisfies
\(\displaystyle 0\le z_v\le\frac1n,\qquad 0<T:=\sum_vz_v<1,\qquad (Az)_v\ge r\ \text{whenever }z_v>0.\)
For the converse direction of this equivalence, any such vector is implemented by
\(\displaystyle y_{1v}=y_{2v}=\frac{z_v}{2\lambda},\qquad y_{1a}=y_{2a}=0.\)
The capacity bound guarantees \(y_{jv}\le\alpha/2=x_{jv}\)\).
Suppose such a vector \(z\)\) exists. Multiply each participating type’s winning inequality by \(z_v\)\) and sum. Zero coordinates contribute nothing, so
\(\displaystyle rT\le z^{\mathsf T}Az.\)
Applying the graph lemma to \(z/T\)\) gives
\(\displaystyle rT\le z^{\mathsf T}Az \le T^2\left(1-\frac1{\omega(H)}\right).\)
Since \(0<T<1\)\) and \(r>0\)\),
\(\displaystyle 1-\frac1{\omega(H)} \ge\frac rT >r =1-\frac1{K-1}.\)
It follows that \(\omega(H)>K-1\)\). Clique sizes are integers, so \(\omega(H)\ge K\)\), and therefore \(\omega(G)\ge k\)\).
This argument covers every real fractional deviation.
Conversely, suppose \(\omega(G)\ge k\)\). Then \(H\)\) contains a clique \(S\)\) of exactly \(K\)\) vertices. Set
\(\displaystyle z_v=\frac{r}{K-1} =\frac{K-2}{(K-1)^2}\quad(v\in S),\)
and set all other coordinates to zero.
These coordinates satisfy the capacity bound, since
\(\displaystyle \frac r{K-1} <\frac1{K-1} \le\frac1n.\)
For each \(v\in S\)\), its \(K-1\)\) clique neighbors contribute exactly
\(\displaystyle (Az)_v=(K-1)\frac r{K-1}=r.\)
Finally, the total cost is
\(\displaystyle T=\frac{Kr}{K-1} =\frac{K(K-2)}{(K-1)^2} =1-\frac1{(K-1)^2}<1.\)
The vector is nonzero and therefore implements a blocking deviation.
We have proved
\(\displaystyle \text{a blocking deviation exists} \quad\Longleftrightarrow\quad \omega(G)\ge k.\)
The reduction produces \(m=2\)\) coalitions and \(\tau=2n+1\)\) supported types. Every constructed rational has \(O(\log n)\)\) bits, so the complete instance has
\(\displaystyle L=O(n^2\log n)\)
and is constructible in polynomial time.
The numerical bounds are independent of the graph size. Indeed,
\(\displaystyle \lambda=\frac{2D}{N}<8,\qquad r\ge\frac12,\)
so \(b_{vw}<16\)\). Also \(\delta\ge1/2\)\) and \(v/N\le1\)\), giving \(b_{va}\le6\)\). Thus hardness holds with bounded demand rates and bounded belief weights.
The reduction proves \(\mathrm{NP}\)-hardness, and Section 2 proves membership in \(\mathrm{NP}\). Therefore blocking-deviation existence is \(\mathrm{NP}\)-complete, and its complementary continuous CS-core membership problem is \(\mathrm{coNP}\)-complete.
⟨structured verdict parsed — rendered above⟩
The argument settles the stated continuous problem in substance: blocking-deviation existence is \(\mathrm{NP}\)-complete, including the claimed restrictions. I found no false mathematical step or substantive gap. Two minor presentation issues remain.
The proof addresses the exact decision problem in USER_TASK: the proposed structure and demand rates are part of the input, types may split, deviations may use arbitrary real masses, and the cost inequality is strict.
The reduction uses zero diagonal weights. This is permitted because the task allows nonnegative true weights. It also distinguishes all supported types by their belief rows, so its count \(\tau=2n+1\) counts genuinely distinct supported types.
The claimed \(\mathrm{coNP}\)-completeness concerns membership of a supplied outcome, as required. The proof does not conflate this with existence of some core outcome.
The computation of incumbent payoff rates is correct. Each winning test sums \(\tau\) rational terms, giving \(O(m\tau^2)\) rational arithmetic operations overall. Products and sums have polynomially bounded bit lengths in the explicit input length.
Both directions of the LP characterization are valid:
The LP need not enforce positivity for every type in \(S\). The proof explicitly handles this distinction correctly.
The LP has \(m\tau+\tau\) variables and \(O(m\tau+\tau)\) constraints. Its rational encoding length is polynomial in \(m\tau+L\). Enumerating the \(2^\tau-1\) nonempty subsets therefore gives the stated bound
\(2^\tau(m\tau+L)^{O(1)}\) bit operations, using polynomial-time rational linear programming.
Minor issue: The rational LP theorem is invoked generically rather than stated precisely, despite the requested verification standard. The minimum clarification is to state the exact theorem being used: rational LP feasibility and, for a feasible bounded objective, exact optimization are computable in time polynomial in the binary encoding length. This is a theorem-statement omission, not a missing mathematical argument.
The certificate argument correctly handles real deviations and the strict inequality.
All \(y\)-coordinates lie in finite closed intervals, and the equalities determine \(Y\). Consequently, each feasible LP polytope is compact. An optimal vertex exists even if the polytope is lower-dimensional; full dimensionality is not required.
The coefficient bound after clearing denominators is valid. Each constraint uses rational data whose total relevant encoding length is at most \(O(L)\), so the resulting integer coefficients have \(O(L)\) bits.
For \(M=m\tau+\tau\), the active-constraint characterization of a vertex, Cramer’s rule, and Hadamard’s bound give the stated coordinate bound
\(O(M(L+\log M))\). The hypotheses are satisfied: the active coefficient matrix is square and nonsingular, and its entries have the stated bit bound.
If a real deviation has cost below \(1\), the corresponding LP optimum also has cost below \(1\). An optimal rational vertex therefore supplies a polynomial-size certificate. No approximation argument is used, so the strict cost condition is preserved.
Bounds, positive total mass, participant winning conditions, and cost can all be checked by exact rational arithmetic in polynomial time.
The lemma is correct, including graphs with no edges.
For nonadjacent positive coordinates \(u,v\), both neighbor sums are independent of \(w_u,w_v\), because the graph is simple and \(A_{uv}=A_{vu}=0\). The transfer changes the quadratic form by exactly \(2w_v(a-b)\), or the corresponding expression for the reverse transfer.
Each transfer removes one positive coordinate and preserves total mass. Thus the procedure terminates with nonempty support forming a clique.
For clique support of size \(s\), the displayed identity
\((w')^{\mathsf T}Aw'=1-\sum_v(w'_v)^2\) is correct. Cauchy–Schwarz applies to its \(s\) nonnegative coordinates summing to \(1\), yielding the claimed bound. The comparison with \(\omega(H)\) has the correct direction.
No integrality assumption enters this lemma.
The restriction \(3\le k\le n\) is legitimate: the excluded CLIQUE cases are polynomial-time decidable and can be replaced by fixed restricted yes- or no-instances.
The padding identity \(\omega(H)=n+\omega(G)\) follows from the stated universal added clique. Therefore the equivalence between the original threshold \(k\) and padded threshold \(K=n+k\) is correct.
The bibliographic assertion is also accurate: [Theorem 5 of the supplied paper](https://www.ijcai.org/Proceedings/09/Papers/025.pdf) uses CLIQUE as its reduction source. The continuous proof does not rely on transferring that finite-agent reduction.
All constructed quantities are defined and have positive denominators. The restriction gives \(n\ge3\) and \(K\ge6\), so in particular \(r>0\).
The bounds \(2N\le D<4N\) imply \(0<N\alpha\le1/2\) and \(\delta\ge1/2\). Every supported mass is positive and dyadic, and the masses sum to \(1\).
Both coalitions have mass \(1/2\). Each type’s two coalition masses sum to its supported mass. The demand normalization calculation is correct:
\(N(\alpha/2)\lambda=1\).
Zero auxiliary demand is allowed.
The auxiliary-column contribution to every graph type’s incumbent winning test is strictly greater than \(1\). Hence all graph payoff rates equal \(\lambda\), while the auxiliary payoff rates are zero. These conclusions agree with the task’s definitions.
The zero auxiliary row differs from every graph row, and the distinct auxiliary-column entries distinguish graph rows from one another.
An auxiliary participant would require \(0\ge1\), so excluding auxiliary participation is justified.
The substitution \(z_v=\lambda Y_v\) correctly transforms:
The converse implementation splits each selected graph mass equally between the two incumbent coalitions. Its capacity calculation is correct, and the task permits these selected masses to be real.
Thus this equivalence covers every admissible real deviation.
Soundness is valid. Multiplying winning inequalities by positive masses and summing gives \(rT\le z^{\mathsf T}Az\). Zero coordinates contribute nothing. Applying the proved lemma to \(z/T\) is legitimate because \(T>0\).
Since \(T<1\) and \(r>0\), the strict comparison \(r/T>r\) follows. The resulting inequality implies \(\omega(H)>K-1\), hence \(\omega(H)\ge K\) by integrality. This proves the required original CLIQUE condition.
Completeness is valid. A clique of size at least \(K\) contains one of exactly \(K\). The assigned coordinate \(r/(K-1)\) is positive and satisfies capacity because \(K-1\ge n\).
Each participating vertex receives exactly \(r\) from its clique neighbors. The total-cost calculation
\(T=1-1/(K-1)^2\)
is correct and gives \(0<T<1\). The earlier implementation therefore supplies a valid blocking deviation.
The strict inequality excludes the no-case boundary and admits the constructed yes-case deviation.
There are \(2n+1\) supported types and two coalitions. Every rational has \(O(\log n)\) bits; the dense belief matrix gives \(L=O(n^2\log n)\). The reduction is polynomial-time constructible.
The numerical bounds are correct:
Combining the reduction with the certificate argument proves \(\mathrm{NP}\)-completeness. Complementation proves \(\mathrm{coNP}\)-completeness of continuous CS-core membership. The enumeration algorithm is polynomial for fixed \(\tau\), and hardness already holds for fixed \(m=2\).
Minor issue: Numerous expressions contain nested math delimiters, such as \(m=2\)\). These are malformed LaTeX delimiters. Remove the duplicated pairs throughout; this has no effect on the argument.
No new lemma, construction, or substantive 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.