Answer: Blocker existence is \(\mathrm{NP}\)-hard; continuous core-stability verification is \(\mathrm{coNP}\)-hard.
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatecore stability verification can be done in coNP for all three degrees of altruism. For the selfish-first model, core stability verification is even coNP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite symmetric type graph \(H=(T,a)\), with \(a_{ts}\in\{0,1\}\) specifying friendship between types, including within-type relations; positive rational masses \(\mu_t\) summing to \(1\); and a proposed partition \(\Pi=(p^1,\ldots,p^r)\) with \(\sum_j p_t^j=\mu_t\), decide whether \(\Pi\) is core stable. For a coalition profile \(q\), define \(f_t(q)=\sum_s a_{ts}q_s\) and \(e_t(q)=\sum_s(1-a_{ts})q_s\). Extend selfish-first preferences by lexicographically comparing \((f_t(q),-e_t(q),\sum_s a_{ts}\sum_jp_s^j f_s(p^j),-\sum_s a_{ts}\sum_jp_s^j e_s(p^j))\). A blocker is a real selection \(z_t^j\in[0,p_t^j]\) of positive total mass; it forms \(y_t=\sum_jz_t^j\), leaving residual coalitions \(p^j-z^j\). Decide whether there is no such selection for which every selected unit strictly prefers the resulting partition to \(\Pi\).
A society is given by its support: \(T\), the list of \(\tau\) types with positive binary-rational masses \(\mu_t\), with \(\sum_t\mu_t=1\). The friendship matrix satisfies \(a_{ts}=a_{st}\in\{0,1\}\); \(a_{tt}\) specifies friendship between distinct units of type \(t\). Units are nonatomic. Here \(m=|T|=\tau\), the support size, not the number of possible types.
The input also gives \(\Pi=(p^1,\ldots,p^r)\), with binary-rational \(p_t^j\geq0\), \(\sum_jp_t^j=\mu_t\), and \(\sum_tp_t^j>0\). Let \(L\) be the total input bit length; state running times in \(m,\tau,r,L\).
For a coalition profile \(q\), define \(f_t(q)=\sum_sa_{ts}q_s\) and \(e_t(q)=\sum_s(1-a_{ts})q_s\). For any finite coalition structure \(Q=(q^1,\ldots,q^k)\), define \(A_t(Q)=\sum_sa_{ts}\sum_{\ell=1}^kq_s^\ell f_s(q^\ell)\) and \(B_t(Q)=\sum_sa_{ts}\sum_{\ell=1}^kq_s^\ell e_s(q^\ell)\).
A type-\(t\) unit in coalition \(q\) of \(Q\) ranks its situation by the lexicographic vector \(U_t(q,Q)=(f_t(q),-e_t(q),A_t(Q),-B_t(Q))\), with larger vectors preferred and equal vectors indifferent.
A deviation chooses real \(0\leq z_t^j\leq p_t^j\) with \(\sum_{t,j}z_t^j>0\), forms \(y_t=\sum_jz_t^j\), and produces \(Q_z=(y,p^1-z^1,\ldots,p^r-z^r)\), omitting zero-mass coalitions. It blocks precisely when \(U_t(y,Q_z)>_{\mathrm{lex}}U_t(p^j,\Pi)\) for every \((t,j)\) with \(z_t^j>0\). The proposed structure is core stable precisely when no blocker exists.
Is continuous core-stability verification in \(\mathrm{P}\), or is its complementary problem of deciding whether a blocker exists \(\mathrm{NP}\)-hard?
Discrete sum-based selfish-first core-stability verification is \(\mathrm{coNP}\)-complete, so blocker existence is \(\mathrm{NP}\)-complete ([original result](https://www.ijcai.org/Proceedings/2020/0049.pdf), [full version](https://docserv.uni-duesseldorf.de/servlets/DerivateServlet/Derivate-74495)). Later work establishes discrete verification hardness for all three degrees of altruism and both sum-based and minimum-based aggregation ([2024 result](https://link.springer.com/chapter/10.1007/978-3-031-55601-2_21)).
No result settling this exact nonatomic mass problem was located.
Blocker existence is \(\mathrm{NP}\)-hard for the stated nonatomic model. Consequently, continuous core-stability verification is \(\mathrm{coNP}\)-hard and cannot be in \(\mathrm{P}\) unless \(\mathrm{P}=\mathrm{NP}\).
The hardness holds even when every diagonal entry is \(1\), every input mass is dyadic, and each type initially belongs entirely to one coalition. The proof allows arbitrary real deviations.
If a participating type strictly improves lexicographically, then necessarily its friend mass weakly increases. If its friend mass stays equal, its enemy mass must weakly decrease. These are necessary conditions regardless of the altruistic coordinates.
We may also perform calculations with unnormalized masses and normalize the constructed input afterward. Indeed, multiplying every mass by a positive constant \(\lambda\) gives
\[ \]
\(f_t(\lambda q)=\lambda f_t(q),\qquad e_t(\lambda q)=\lambda e_t(q),\)
\(A_t(\lambda Q)=\lambda^2A_t(Q),\qquad B_t(\lambda Q)=\lambda^2B_t(Q).\)
Thus each utility coordinate is multiplied by a positive constant, preserving every lexicographic comparison. Deviations correspond bijectively under \(z\mapsto\lambda z\), including the capacity constraints and the requirement of positive deviating mass.
We reduce from the \(\mathrm{NP}\)-complete Clique problem: given a simple graph \(G=(V,E)\) and an integer \(k\), decide whether it contains a clique of size at least \(k\). See [Karp’s original result](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9).
Write \(n=|V|\). We restrict to \(2\leq k\leq n\); the excluded cases are decidable directly and can be mapped to fixed yes or no instances within this range.
Set
\(g=n+1,\qquad \epsilon=2^{-\ell},\)
where \(\ell\) is the smallest integer satisfying \(2^\ell\geq4(n+1)\). Hence
\(0<\epsilon\leq\frac{1}{4(n+1)}.\)
For each vertex \(v\), introduce a vertex type \(v\) and a private companion type \(w_v\). Introduce four additional types \(h,b,c,d\). Their unnormalized masses and initial coalitions are:
| Type | Unnormalized mass | Initial coalition |
|---|---:|---|
| \(v\), for each \(v\in V\) | \(1\) | \(C_v\) |
| \(w_v\), for each \(v\in V\) | \(g+k-\epsilon-1\) | \(C_v\) |
| \(h\) | \(g\) | \(C_0\) |
| \(b\) | \(g\) | \(C_0\) |
| \(c\) | \(1/2\) | \(C_0\) |
| \(d\) | \(k-1/2\) | \(C_0\) |
Each listed type places its entire mass in its indicated coalition.
Every type is friends with itself. The off-diagonal friendships are precisely:
All other pairs are enemies. This specifies a symmetric binary friendship matrix.
The total mass so far is
\(S_0=2g+k+n(g+k-\epsilon).\)
Choose a power of two \(P>S_0\). Introduce a final type \(\omega\), with mass \(P-S_0\), initially alone in \(C_\omega\). It is friends only with itself.
Divide every mass by \(P\), obtaining the actual input \((\mu,\Pi)\). All masses are positive dyadic rationals, their sum is \(1\), and all initial coalitions have positive mass.
For the proof, use unnormalized units, justified by the scaling observation. Since every type initially belongs entirely to one coalition, let \(x_t\) denote its mass in the deviating coalition \(y\). Thus \(0\leq x_t\leq\widehat\mu_t\), where \(\widehat\mu_t\) is its unnormalized mass.
Suppose \(w_v\) participates in a blocker. Its only friend types are \(w_v\) and \(v\), both initially entirely in \(C_v\). Its initial friend mass therefore equals its total friend mass in the society:
\(f_{w_v}(C_v)=g+k-\epsilon.\)
Consequently, its friend mass cannot strictly increase. Blocking requires it to remain equal, which forces
\(x_{w_v}=g+k-\epsilon-1,\qquad x_v=1.\)
Its initial enemy mass is zero. Blocking therefore also requires zero enemy mass in \(y\), excluding every other type from \(y\).
Thus \(y=C_v\), and the deviation merely recreates the original coalition using all its mass. The resulting coalition structure equals \(\Pi\), up to order and omitted zero profiles. Since \(A_t\) and \(B_t\) are invariant under those changes, every utility coordinate is unchanged. This contradicts strict improvement.
Therefore no private companion can participate in a blocker.
The identical argument applies to \(\omega\): its initial singleton coalition contains all its friends and no enemies, so its participation could only recreate that coalition without changing the structure. Hence
\(x_{w_v}=0\quad\text{for every }v,\qquad x_\omega=0\)
in every blocker.
The initial friend masses of the remaining types are
\(f_h(C_0)=2g+\frac12,\qquad f_b(C_0)=2g,\)
\(f_c(C_0)=g+k,\qquad f_d(C_0)=k,\)
\(f_v(C_v)=g+k-\epsilon.\)
First, participation by \(h\) requires participation by \(b\). Otherwise,
\(f_h(y)=x_h+x_c+\sum_{v\in V}x_v \leq g+\frac12+n <2g+\frac12,\)
because \(g=n+1\). This would strictly decrease \(h\)'s friend mass.
Next, any nonempty blocker must contain \(h\). To see this, suppose \(x_h=0\).
Together with Section 3, these exclusions leave no possible participant. Therefore every blocker contains \(h\) and \(b\).
Since \(b\)'s only friends are \(h\) and itself,
\(f_b(y)=x_h+x_b\leq2g=f_b(C_0).\)
Its participation forces equality, hence
\(x_h=x_b=g.\)
Its initial enemy mass is \(k\). Writing
\(W=\sum_{v\in V}x_v,\)
the necessary enemy-mass condition for \(b\) gives
\[W+x_c+x_d\leq k.\tag{1}\]
Type \(c\)'s global maximum friend mass is \(g+k\), attained initially. Thus, if it participates, equality forces
\(x_h=g,\qquad x_c=\frac12,\qquad x_d=k-\frac12.\)
Similarly, participation by \(d\) forces \(x_c+x_d=k\), hence those same full masses.
In either case, inequality (1) forces \(W=0\). Section 4 already forces all of \(h,b\), so the deviating coalition is exactly \(C_0\). As in Section 3, this only recreates the original coalition and leaves all utilities unchanged, contradicting blocking.
Consequently, every blocker has
\[x_c=x_d=0,\qquad x_h=x_b=g,\qquad W\leq k.\tag{2}\]
It also has \(W>0\): if \(W=0\), type \(h\)'s new friend mass is \(2g\), below its initial \(2g+1/2\).
For each vertex \(v\), let \(N[v]\) be its closed neighborhood in \(G\), including \(v\).
If \(x_v>0\), its private companion is absent, and (2) gives
\(f_v(y)=g+\sum_{u\in N[v]}x_u.\)
The necessary friend-mass condition therefore implies
\[\sum_{u\in N[v]}x_u\geq k-\epsilon.\tag{3}\]
Since some vertex participates, (3) implies \(W\geq k-\epsilon\).
Define the heavy vertices by
\(H=\{v\in V:x_v>\epsilon\}.\)
These vertices form a clique. Suppose distinct \(u,v\in H\) were nonadjacent. Then \(u\notin N[v]\), so (2) would give
\(\sum_{s\in N[v]}x_s\leq W-x_u<k-\epsilon,\)
contradicting (3) for \(v\).
Moreover, every vertex outside \(H\) has mass at most \(\epsilon\). Hence
\(\sum_{v\in H}x_v \geq W-n\epsilon \geq k-(n+1)\epsilon \geq k-\frac14 >k-1.\)
Each vertex type has capacity \(1\), so
\(|H|\geq\sum_{v\in H}x_v>k-1.\)
Because \(|H|\) is an integer, \(|H|\geq k\). Thus every blocker produces a clique of size at least \(k\).
This argument applies to arbitrary real deviations.
Conversely, suppose \(G\) contains a clique \(K\) of exactly \(k\) vertices. Choose
\(x_h=x_b=g,\qquad x_v=1-\frac{\epsilon}{2k}\quad(v\in K),\)
and set all other deviating masses to zero. These masses satisfy every capacity constraint. Their total vertex mass is
\(W=k-\frac{\epsilon}{2}.\)
Every participant strictly improves:
\(f_v(y)=g+W>g+k-\epsilon=f_v(C_v)\).
Its first coordinate strictly improves.
\(f_h(y)=2g+W>2g+\frac12=f_h(C_0)\),
since \(k\geq2\) and \(\epsilon<1\). Its first coordinate strictly improves.
\(e_b(y)=W<k=e_b(C_0)\).
Its second coordinate strictly improves.
Thus every participant improves within the first two coordinates. The values of \(A_t\) and \(B_t\) cannot affect these comparisons. After dividing the chosen masses by \(P\), this is a blocker for the normalized input.
We have proved the equivalence
\(G\text{ contains a clique of size at least }k \quad\Longleftrightarrow\quad \Pi\text{ admits a blocker}.\)
The constructed instance has
\(m=\tau=2n+5,\qquad r=n+2.\)
The exponent \(\ell\) is \(O(\log n)\), and \(S_0=O(n^2)\). Choosing the smallest power of two strictly above \(S_0\) gives \(P=O(n^2)\). Therefore every normalized mass has binary encoding length \(O(\log n)\).
The dense friendship matrix and coalition-profile array yield
\(L=O(n^2\log n).\)
Using straightforward binary arithmetic, the reduction takes
\(O\bigl((m^2+mr)(\log m)^2\bigr) =O\bigl((\tau^2+\tau r)(\log\tau)^2\bigr)\)
bit operations, hence polynomial time in the total input length.
The polynomial-time reduction proves \(\mathrm{NP}\)-hardness of blocker existence for the exact problem stated. Taking complements proves \(\mathrm{coNP}\)-hardness of continuous core-stability verification.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned question: blocker existence is \(\mathrm{NP}\)-hard for the exact nonatomic model, and continuous core-stability verification is \(\mathrm{coNP}\)-hard. I found no major or minor mathematical gaps.
The preliminary lexicographic conditions are correct. Strict improvement requires weakly larger friend mass; when friend mass is equal, it requires weakly smaller enemy mass. The proof consistently uses the enemy condition only after establishing equality of friend mass.
The scaling identities are also correct: the first two utility coordinates are homogeneous of degree one, and the last two are homogeneous of degree two. Positive scaling therefore preserves lexicographic comparisons, capacities, and positive deviating mass.
The invoked theorem is precisely the standard \(\mathrm{NP}\)-completeness of deciding whether a finite simple graph contains a clique of size at least the input integer \(k\). This is the Clique problem in [Karp’s cited result](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9). The constructed reduction satisfies its graph and integer hypotheses.
Restriction to \(2\leq k\leq n\) is legitimate: excluded instances are directly decidable, and fixed yes and no instances exist within the restricted range. A clique of size at least \(k\) contains one of exactly \(k\), so Section 7 addresses the same source problem.
The friendship specification is symmetric, binary, and includes every diagonal entry. All listed masses are positive under the stated parameter restrictions. In particular, \(g+k-\epsilon-1>0\) and \(k-\tfrac12>0\).
The total unnormalized mass is correctly computed as \(S_0=2g+k+n(g+k-\epsilon)\). Choosing \(P>S_0\) makes the filler mass strictly positive. Since both the original masses and \(S_0\) are dyadic, division by the power of two \(P\) produces positive dyadic masses summing to one.
Every type initially occupies exactly one coalition. Consequently, the variables \(x_t\) describe every permitted deviation in these constructed instances, including arbitrary real deviations; no additional origin-coalition choices are being suppressed.
Each companion initially has all its possible friend mass and zero enemy mass. Equality of its friend mass forces the complete participation of itself and its corresponding vertex. Equality or improvement of its enemy coordinate then excludes every other type.
Thus the deviation recreates precisely its original coalition, with every other coalition unchanged. The resulting structure preserves all four utility coordinates, including the global altruistic coordinates, so strict improvement is impossible. The filler argument has the same valid structure.
All initial friend masses displayed in Section 4 agree with the friendship matrix.
Without \(b\), the bound on \(h\)'s new friend mass is strictly below its initial value because \(g=n+1\). Hence participating \(h\) requires participating \(b\).
The argument excluding a blocker without \(h\) covers every remaining type. The implication involving \(d\) is valid: participating \(d\) forces all of \(c\), making \(c\) a participant whose necessary friend condition then forces \(h\).
Once \(b\) participates, its friend mass cannot exceed \(2g\). Equality forces \(x_h=x_b=g\). Its initial enemy mass is exactly \(k\), so the derived inequality \(W+x_c+x_d\leq k\) is correct.
Each of these types initially attains its global maximum friend mass. Participation by either forces the full masses of both \(c\) and \(d\); the already established constraints also supply all of \(h\) and \(b\).
Their combined mass is \(k\), so the enemy constraint for \(b\) forces \(W=0\). The resulting deviation recreates \(C_0\), preserving the entire coalition structure and all utilities. This correctly excludes both types.
The resulting conditions \(x_h=x_b=g\), \(x_c=x_d=0\), and \(W\leq k\) are therefore necessary. The argument establishing \(W>0\) correctly uses the otherwise decreased friend mass of participating \(h\).
For every participating vertex, the formula \(f_v(y)=g+\sum_{u\in N[v]}x_u\) is correct, including its own mass through the diagonal friendship. Its necessary improvement condition gives the stated lower bound \(k-\epsilon\).
Every heavy vertex participates. If two heavy vertices were nonadjacent, the omitted mass of either would make the other’s neighborhood sum strictly smaller than \(k-\epsilon\), contradicting that bound.
The heavy-mass calculation has the correct constants and strictness:
\(\sum_{v\in H}x_v\geq k-(n+1)\epsilon\geq k-\tfrac14>k-1\).
Capacity \(x_v\leq1\) then implies \(|H|\geq k\). No integrality assumption on the deviating masses is used.
The proposed vertex masses lie strictly between zero and one, and their sum is \(W=k-\epsilon/2\).
Each participating vertex gains friend mass by \(\epsilon/2\). Type \(h\) gains friend mass because \(k-\epsilon/2>1/2\). Type \(b\) retains friend mass \(2g\) and strictly decreases enemy mass from \(k\) to \(k-\epsilon/2\).
These checks cover every participant. Each comparison is decided within the first two coordinates, so no calculation of \(A_t\) or \(B_t\) is required for this direction.
The counts \(m=\tau=2n+5\) and \(r=n+2\) are correct. The bounds \(\ell=O(\log n)\), \(S_0=O(n^2)\), and \(P=O(n^2)\) imply \(O(\log n)\) bits per normalized mass, including the filler.
The dense encoding bound \(L=O(n^2\log n)\) is valid. The stated construction time \(O((m^2+mr)(\log m)^2)=O((\tau^2+\tau r)(\log\tau)^2)\) is a valid conservative bound using straightforward binary arithmetic. It is polynomial in the explicit source encoding and the constructed input length.
Both directions of the reduction are established. Taking complements correctly yields \(\mathrm{coNP}\)-hardness of stability verification, and a polynomial-time verification algorithm would imply \(\mathrm{P}=\mathrm{NP}\).
No repair or additional clarification is needed. The output establishes hardness; it does not claim membership of the continuous blocker problem in \(\mathrm{NP}\), which is unnecessary for the assigned alternative.
⟨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.