Answer: Polynomial-time solvable, in \(\mathrm{P}\). A blocking coalition exists exactly when the type graph is not complete multipartite.
Theorem 28 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem COH is CoNP-complete. Furthermore CoNP-hardness holds already for the class NDU2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of types \(T=\{1,\ldots,\tau\}\), positive rational masses \(\mu_i\) summing to \(1\), and a symmetric binary tie matrix \(A\), decide whether there is a vector \(x\) with \(0\leq x_i\leq\mu_i\) and \(\sum_i x_i>0\) such that every type with \(x_i>0\) strictly gains: \(\frac{\sum_j A_{ij}x_j}{\sum_j x_j}>\sum_j A_{ij}\mu_j\). Equivalently, decide whether the grand coalition is core stable in this type-mass popularity game.
A society is given by its support: a list of \(\tau\geq1\) types \(T=\{1,\ldots,\tau\}\), each with positive binary rational mass \(\mu_i\), with \(\sum_i\mu_i=1\). Here \(\tau\) is the support size, not the number of possible types.
The input also contains a symmetric matrix \(A\in\{0,1\}^{\tau\times\tau}\) with \(A_{ii}=0\): ties occur uniformly between types, and there are no ties within a type. No connectivity restriction is imposed.
A coalition is a divisible mass vector \(x\in\mathbb R^\tau\) with \(0\leq x_i\leq\mu_i\) and total mass \(s=\sum_i x_i>0\). Its participating type \(i\) receives popularity \(p_i(x)=\sum_j A_{ij}x_j/s\); its grand-coalition popularity is \(b_i=\sum_j A_{ij}\mu_j\).
The coalition blocks precisely when \(p_i(x)>b_i\) for every \(i\) with \(x_i>0\). The grand coalition is core stable precisely when no blocking coalition exists.
Measure running time in \(\tau\) and the total binary input length \(L\); there is no separate parameter \(m\) in this model.
Is deciding whether a blocking coalition exists solvable in polynomial time in \(\tau\) and \(L\), or is it \(\mathrm{NP}\)-hard?
For finite simple undirected networks, deciding grand-coalition core stability is \(\mathrm{coNP}\)-complete, even on connected graphs of diameter two having both universal and nonuniversal vertices; consequently blocking-coalition existence is \(\mathrm{NP}\)-complete. [Source](https://arxiv.org/pdf/1612.08351).
No complexity classification for this precise divisible type-mass problem was identified in the search.
Classification.
The problem is polynomial-time solvable. In fact, for every strictly positive mass vector, the grand coalition is core stable if and only if the type graph is complete multipartite.
Here, “complete multipartite” means that the types can be partitioned into nonempty parts, with no ties inside a part and all possible ties between different parts. A single part is allowed, covering the edgeless graph and the case \(\tau=1\).
Normalization of coalitions.
Write \(\Delta_T=\{q\in\mathbb R^\tau:q_i\geq0,\ \sum_iq_i=1\}\). A blocking coalition exists exactly when there is a vector \(q\in\Delta_T\) satisfying
\[
(Aq)_i>b_i\qquad\text{whenever }q_i>0.
\]
Indeed, any coalition \(x\) gives \(q=x/s\), and its popularity vector is \(Aq\). Conversely, given such a \(q\), set \(\lambda=\min_{i\in T}\mu_i>0\) and \(x_i=\lambda q_i\). Since \(q_i\leq1\), we have \(0\leq x_i\leq\mu_i\). Its total mass is \(\lambda\), so its popularity vector is again \(Aq\).
Thus divisibility and strictly positive masses make every probability vector available as a coalition composition.
Complete multipartite graphs are stable.
Suppose the parts are \(P_1,\ldots,P_r\). Define their society and normalized coalition masses by
\[
M_a=\sum_{i\in P_a}\mu_i,\qquad Q_a=\sum_{i\in P_a}q_i.
\]
For every type \(i\in P_a\), the multipartite adjacency rule gives
\[
b_i=1-M_a,\qquad (Aq)_i=1-Q_a.
\]
If \(q\) blocks, every part with \(Q_a>0\) contains a participating type and therefore must satisfy \(Q_a<M_a\). Summing over the participating parts yields
\[
1=\sum_{a:Q_a>0}Q_a
<
\sum_{a:Q_a>0}M_a
\leq1,
\]
a contradiction. Hence no blocking coalition exists.
Every other graph has an explicit blocking coalition.
Suppose the graph is not complete multipartite. Define a relation on types by \(i\sim j\) when \(i=j\) or \(A_{ij}=0\). It is reflexive and symmetric. If it were transitive, its equivalence classes would be independent sets, and every pair in different classes would be adjacent. That would make the graph complete multipartite.
Consequently, transitivity fails: there are three distinct types \(u,v,w\) such that
\[
A_{uw}=1,\qquad A_{uv}=A_{vw}=0.
\]
Start with the clique \(\{u,w\}\) and greedily extend it to an inclusion-maximal clique \(C\). This requires no maximum-clique computation. The type \(v\) is outside \(C\), because it is nonadjacent to both \(u\) and \(w\).
For each type \(j\), let
\[
r_j=\bigl|\{i\in C:A_{ij}=0\}\bigr|.
\]
These counts satisfy:
Define \(c_i=1-b_i\). Because the society masses sum to one,
\[
c_i=\sum_{j\in T}(1-A_{ij})\mu_j.
\]
In particular, \(c_i\geq\mu_i>0\), using \(A_{ii}=0\).
Let \(h=\sum_{i\in C}c_i\). Interchanging the finite sums gives
\[
h
=\sum_{j\in T}\mu_jr_j
\geq\sum_{j\in T}\mu_j+\mu_v
=1+\mu_v
>1.
\]
Now choose the normalized coalition
\[
q_i=
\begin{cases}
c_i/h,&i\in C,\\
0,&i\notin C.
\end{cases}
\]
Its entries are nonnegative and sum to one, and every type in \(C\) participates. Since \(C\) is a clique,
\[
(Aq)_i=1-q_i
=1-\frac{c_i}{h}
>1-c_i
=b_i
\qquad(i\in C).
\]
The strict inequality follows from \(h>1\) and \(c_i>0\). Therefore \(q\), and hence the feasible mass vector \(x_i=\lambda q_i\) constructed above, blocks.
This completes both directions of the classification.
Algorithm and binary complexity.
For decision alone, construct the complement graph, with an edge between distinct types precisely when \(A_{ij}=0\). The original graph is complete multipartite exactly when every connected component of this complement is a clique.
Finding its components and checking all pairs within them takes \(O(\tau^2)\) matrix inspections. Answer “no blocking coalition” exactly when every component passes this check. Including input reading, this is polynomial in \(\tau\) and \(L\).
A blocking witness can also be constructed in polynomial time: find the triple above by checking triples, greedily extend its edge to \(C\), and evaluate the explicit formulas.
The witness has polynomial binary length. To see this directly, write the input masses as \(\mu_j=a_j/d_j\) and take \(D=\prod_jd_j\). The binary length of \(D\) is \(O(L)\). Each \(c_i=N_i/D\) for an integer \(N_i\) satisfying \(0<N_i\leq D\), so
\[
q_i=\frac{N_i}{\sum_{k\in C}N_k}\qquad(i\in C)
\]
has binary length \(O(L+\log\tau)\). Multiplication by the input rational \(\lambda\) preserves polynomial binary length.
Relation to the finite-network result.
The cited [finite-network hardness theorem](https://arxiv.org/pdf/1612.08351) concerns coalitions that are subsets of indivisible vertices. Here, unequal fractional participation permits the clique composition constructed above. That difference yields the polynomial characterization proved here.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes that, for every admissible strictly positive mass vector, a blocking coalition exists exactly when the type graph is not complete multipartite. The resulting decision algorithm runs in polynomial time in \(\tau\) and \(L\).
No major or minor mathematical issues were found.
The equivalence between feasible blocking coalitions and normalized compositions is valid.
For a feasible coalition, \(s>0\), so \(q=x/s\) is well-defined, has nonnegative coordinates, and satisfies \(\sum_i q_i=1\). Its support equals the coalition’s participating types, and \(p_i(x)=(Aq)_i\). Thus the blocking inequalities are preserved exactly.
Conversely, strict positivity of all input masses ensures \(\lambda=\min_i\mu_i>0\). For any \(q\in\Delta_T\), the proposed vector \(x_i=\lambda q_i\) satisfies \(0\leq x_i\leq\lambda\leq\mu_i\), and its total mass is \(\lambda>0\). Its normalized composition is \(q\). This establishes the reverse implication without additional restrictions.
The identities \(b_i=1-M_a\) and \((Aq)_i=1-Q_a\) follow directly from the stated adjacency rule and the unit total masses.
If \(Q_a>0\), at least one type in that part participates. Its strict improvement requires \(Q_a<M_a\). The participating parts form a nonempty finite set, so summing these strict inequalities gives the asserted contradiction:
\(1<\sum_{a:Q_a>0}M_a\leq1\).
This argument covers all allowed multipartite graphs, including a single part, an edgeless graph, and \(\tau=1\).
The relation \(i\sim j\) is reflexive and symmetric under the input assumptions. If transitive, it is an equivalence relation whose classes are independent sets, with every pair from different classes adjacent. Therefore transitivity would imply that the graph is complete multipartite.
Failure of transitivity supplies \(u\sim v\), \(v\sim w\), and \(u\not\sim w\). These types are necessarily distinct: any equality would contradict one of these three relations. The asserted adjacency pattern follows.
This is a direct argument, with no unproved graph-theoretic characterization being invoked.
The edge \(\{u,w\}\) can be extended greedily to an inclusion-maximal clique in a finite graph. The proof correctly requires maximality by inclusion, rather than maximum cardinality.
The type \(v\) cannot belong to this clique because it is nonadjacent to both initial vertices.
All three claims about \(r_j\) are correct:
The identity \(c_i=\sum_j(1-A_{ij})\mu_j\) uses precisely \(\sum_j\mu_j=1\). The diagonal term gives \(c_i\geq\mu_i>0\).
Interchanging the finite sums correctly yields \(h=\sum_j\mu_jr_j\). The bounds on \(r_j\), together with \(\mu_v>0\), imply \(h\geq1+\mu_v>1\).
Every hypothesis needed for strictness is present. In particular, the proof uses the task’s positive masses essentially.
The proposed \(q\) is supported on \(C\), is strictly positive there, and sums to one because its denominator is \(h=\sum_{i\in C}c_i\).
For each participating type, clique adjacency gives \((Aq)_i=1-q_i\). Since \(h>1\) and \(c_i>0\), the claimed strict inequality \(1-c_i/h>1-c_i=b_i\) holds.
There is no blocking requirement for types outside \(C\). The normalization argument already supplies a feasible positive-mass coalition with exactly this composition. Consequently, the construction proves instability for every graph outside the stated class.
The complement characterization is correct: independent parts in the original graph correspond exactly to clique components in its complement.
With an adjacency matrix, finding complement components and checking all pairs within them requires \(O(\tau^2)\) matrix inspections. Including input reading gives polynomial running time in \(\tau\) and \(L\). The algorithm introduces no separate population-size parameter.
The witness construction is also polynomial: checking triples, greedily extending a clique, and evaluating rational formulas all have polynomial cost.
The bit-length argument is valid. For \(D=\prod_jd_j\), its binary length is bounded by the sum of denominator lengths, hence \(O(L)\). Each \(c_i\) has denominator \(D\) and numerator satisfying \(0<N_i\leq D\). Therefore \(\sum_{k\in C}N_k\leq\tau D\), giving the asserted polynomial coordinate lengths. Multiplication by \(\lambda\) preserves polynomial bit length. These operations can be performed with standard polynomial-time integer arithmetic.
The distinction is accurate. The cited paper defines coalitions as subsets of vertices and popularity using the cardinality of those subsets; it does not permit the fractional compositions used here. Its hardness result therefore does not contradict this characterization. See [Definitions 2 and 4 in the cited paper](https://arxiv.org/pdf/1612.08351).
The continuous classification is established independently of that citation.
No repair or additional clarification is required. The proof addresses the full specified domain, including disconnected graphs and the smallest support sizes.
⟨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.