Answer: \(\mathrm{NP}\text{-hard}\), even with \(\mathcal G=\{K_5\}\), equal payoffs, permanently accessible coalitions, \(\tau=1\), and \(m=\Theta(n)\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet G = (V, E) be an arbitrary connected graph of constant size which is neither a clique nor a star. For every n ∈N there is a local coalition formation game with n agents, m = Θ(n) coalitions, G = {G} and an ini- tial state such that every sequence to a stable state requires 2Θ(n) improvement steps.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite local coalition-formation game \(I=(V,L,\mathcal{C},w,\mathcal{G})\), an explicit rational initial distribution \(x^0\) over its coalition structures, and a round bound \(B\), can mass be routed in at most \(B\) synchronous rounds along legal local-improvement transitions so that all terminal mass is on locally stable states? Each unit of mass represents identical copies of the game, and each copy takes at most one improvement step per round.
Given an explicitly encoded game \(I=(V,L_{\mathrm{perm}},\mathcal C,w,\mathcal G)\), let \(n=|V|\) and \(m=|\mathcal C|\). Permanent links and formation graphs are simple undirected graphs; \(\mathcal C\) lists nonempty allowed coalitions, and \(w(C)>0\) is a binary rational payoff shared by every member of \(C\). Formation graphs are explicitly listed.
A state \(S\subseteq\mathcal C\) consists of pairwise disjoint coalitions; uncovered agents receive zero. Its visibility graph has edges \(L_{\mathrm{perm}}\cup\bigcup_{D\in S}E(K_D)\), where \(K_D\) is the clique on \(D\).
A coalition \(C\in\mathcal C\setminus S\) is accessible if some formation graph admits a bijection onto \(C\) carrying every edge to a visibility edge; extra visibility edges are allowed. It locally blocks when it is accessible and \(w(C)>w(D)\) for every \(D\in S\) intersecting \(C\).
A legal improvement replaces \(S\) by \(\{C\}\cup\{D\in S:D\cap C=\varnothing\}\) for one locally blocking coalition \(C\). A state is locally stable if no coalition locally blocks; equal payoffs do not permit a deviation.
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational. Here types are initial states of identical copies of \(I\), their masses sum to one, and \(\tau\) is the support size, not the number of possible states.
Given this distribution \(x^0\) and a nonnegative integer \(B\) encoded in binary, each synchronous round may split mass arbitrarily among waiting and legal outgoing improvements, conserving all mass. Each copy takes at most one improvement per round; copies do not interact and transitions have no capacities. Intermediate states and transitions are implicit, not supplied as a graph.
Is deciding whether all mass can reach locally stable states within \(B\) rounds in \(\mathrm P\), or is it \(\mathrm{NP}\)-hard? State running times in \(n,m,\tau,L\) and the formation-graph sizes, where \(L\) is the total input bit length, including the binary encoding of \(B\).
For every fixed connected formation graph that is neither a clique nor a star, discrete instances with \(m=\Theta(n)\) require \(2^{\Theta(n)}\) improvements on every path to stability; this is a path-length lower bound, not a decision-complexity classification. [Source](https://ojs.aaai.org/index.php/AAAI/article/download/9305/9164).
Reachability of a prescribed stable outcome is \(\mathrm{NP}\)-complete for two-sided socially stable matching with correlated preferences, a different terminal-state requirement. [Source](https://www.dvaz.net/files/papers/Hoefer2018Coalitions.pdf).
No result settling this exact distribution-routing problem was located.
The problem is \(\mathrm{NP}\)-hard. In fact, it is \(\mathrm{NP}\)-complete on a restricted family with:
Thus a polynomial-time algorithm for the stated problem would imply \(\mathrm P=\mathrm{NP}\). The reduction below concerns reaching any locally stable state within the deadline.
For a state \(S\), let \(d(S)\) be the minimum number of legal improvements needed to reach a locally stable state, with \(d(S)=\infty\) if no such path exists.
Lemma. If the positive-mass support consists of states \(S_1,\ldots,S_\tau\), then all mass can reach locally stable states within \(B\) rounds if and only if \(d(S_i)\le B\) for every \(i\).
Proof. Label mass by its initial state. After \(B\) rounds, every copy initially in \(S_i\) has followed a sequence containing at most \(B\) legal improvements. If no such sequence ends in a stable state, none of that type’s positive mass can finish in a stable state. Splitting cannot change this conclusion.
Conversely, choose a path of length at most \(B\) from each supported state to a stable state. Route that type’s entire mass along its chosen path, then let it wait. These routes can run simultaneously because copies do not interact and transitions have no capacities. \(\square\)
Consequently, the minimum feasible horizon is \(\max_{1\le i\le\tau}d(S_i)\). The positive masses’ numerical values do not affect feasibility.
We use the classical \(\mathrm{NP}\)-completeness of satisfiability for CNF formulas with at most three literals per clause. [Karp, *Reducibility Among Combinatorial Problems*](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf)
We first transform such a formula \(\varphi\) into an equisatisfiable formula \(\psi\) in which each positive literal and each negative literal occurs at most twice.
For an original variable \(x\) with \(d\) occurrences, replace its occurrences by distinct variables \(x_1,\ldots,x_d\), preserving their signs. When \(d\ge2\), add the clauses
\(\displaystyle (\neg x_i\lor x_{i+1})\quad\text{for }1\le i\le d,\qquad x_{d+1}=x_1.\)
For \(d=1\), add no consistency clause. Variables with no occurrences can be discarded.
These clauses force all copies of \(x\) to have the same value: if one is true, the cyclic implications force every copy to be true; otherwise every copy is false. Conversely, assigning all copies the original variable’s value satisfies all consistency clauses. Therefore \(\varphi\) is satisfiable exactly when \(\psi\) is satisfiable.
Each new variable appears once in an original clause. For a cycle of length at least two, it additionally appears once positively and once negatively in consistency clauses. Hence each sign occurs at most twice. All clauses still have at most three literals, and the transformation has polynomial size.
Write \(q\) for the number of variables of \(\psi\), and \(r\) for its number of clauses.
Construct a simple undirected graph \(H\) as follows.
For each variable \(y_i\), introduce three vertices \(t_i,f_i,h_i\), and make them a triangle. For each clause, introduce a vertex \(c_j\). Connect \(c_j\) to \(t_i\) when its clause contains \(y_i\), and to \(f_i\) when its clause contains \(\neg y_i\). Add no other edges.
Thus \(|V(H)|=3q+r\). Its maximum degree is at most four:
An independent set is maximal when no additional vertex can be added while preserving independence. Equivalently, every vertex outside it has a neighbor in it; such a set is also called an independent dominating set.
Lemma. The formula \(\psi\) is satisfiable if and only if \(H\) has a maximal independent set of size at most \(q\).
Proof, forward direction. Given a satisfying assignment, select \(t_i\) when \(y_i\) is true and \(f_i\) when it is false. The resulting set \(A\) has size \(q\) and is independent, because it selects one vertex per triangle and there are no edges between different variable triangles.
It dominates every variable triangle. It also dominates each clause vertex: a true literal in that clause supplies an adjacent selected vertex. Hence \(A\) is maximal independent.
Proof, reverse direction. Let \(A\) be a maximal independent set with \(|A|\le q\). The vertex \(h_i\) has neighbors only inside its own triangle. To dominate \(h_i\), the set \(A\) must contain a vertex of that triangle.
The \(q\) disjoint triangles therefore require at least \(q\) selected vertices. The budget forces exactly one selected vertex per triangle and no selected clause vertices.
Assign \(y_i\) true if \(t_i\in A\), false if \(f_i\in A\), and arbitrarily if \(h_i\in A\). Every clause vertex must have a selected neighbor. Such a neighbor is a \(t_i\) or \(f_i\) representing a literal made true by this assignment. Therefore every clause is satisfied. \(\square\)
Let \(U=V(H)\) and \(m=|U|\). Introduce:
All these agents are distinct. Define one allowed coalition per graph vertex:
\(\displaystyle C_u=\{a_e:e\in E(H),\ u\in e\}\ \cup\ \{p_{u,1},\ldots,p_{u,5-\deg_H(u)}\}.\)
Because \(\deg_H(u)\le4\), every coalition has exactly five agents and at least one private agent. In particular, the coalitions are distinct.
For distinct vertices \(u,v\),
\(\displaystyle C_u\cap C_v=\begin{cases}\{a_{\{u,v\}}\},&\{u,v\}\in E(H),\\ \varnothing,&\{u,v\}\notin E(H).\end{cases}\)
Indeed, private agents belong to only one coalition, and an edge agent belongs precisely to its two endpoint coalitions.
Set
\(\displaystyle L_{\mathrm{perm}}=\bigcup_{u\in U}E(K_{C_u}),\qquad \mathcal G=\{K_5\},\qquad w(C_u)=1.\)
Each allowed coalition induces a permanent clique, so it is accessible in every state. The permanent graph is simple and undirected.
Take initial state \(S_0=\varnothing\), give it mass one, and set \(B=q\).
Since all payoffs equal one, a coalition intersecting a selected coalition cannot locally block: the required strict inequality would be \(1>1\). A coalition disjoint from the entire state does locally block, because it is accessible and all its members currently receive zero.
Therefore every legal improvement simply adds a disjoint coalition and deletes nothing.
Under the correspondence
\(\displaystyle A=\{u\in U:C_u\in S\},\)
valid states correspond exactly to independent sets of \(H\). Moreover, a state is locally stable exactly when every unselected coalition intersects a selected coalition. By the intersection identity above, this is precisely maximal independence of \(A\).
Every independent set can be reached from the empty state by adding its coalitions in any order. Each addition is legal, and exactly \(|A|\) improvements are used. Consequently,
\(\displaystyle \text{a stable state is reachable within }q\text{ rounds}\ \Longleftrightarrow\ H\text{ has a maximal independent set of size at most }q.\)
Combining this equivalence with the preceding lemma and the mass-routing lemma proves
\(\displaystyle \varphi\text{ is satisfiable}\ \Longleftrightarrow\ \text{all mass can reach stability within }B.\)
This is a polynomial-time many-one reduction.
The number of agents is
\(\displaystyle n=|E(H)|+\sum_{u\in U}(5-\deg_H(u))=5m-|E(H)|.\)
Maximum degree four implies \(|E(H)|\le2m\), so
\(\displaystyle 3m\le n\le5m.\)
Thus \(m=\Theta(n)\). There are at most \(10m\) permanent links, and the formation graph has five vertices and ten edges. With indexed agents and standard explicit lists, the output bit length is \(O(m\log(m+1))\), including the binary deadline.
This restricted problem also belongs to \(\mathrm{NP}\): a certificate lists at most \(\min(B,m)\) coalitions. In polynomial time, one checks that they are pairwise disjoint and that every unselected coalition intersects a selected coalition. These conditions certify a reachable stable state. Hence the restricted problem is \(\mathrm{NP}\)-complete, establishing \(\mathrm{NP}\)-hardness of the full problem.
Order the allowed coalitions \(C_1,\ldots,C_m\) by nonincreasing payoff, breaking ties arbitrarily. Define
\(\displaystyle \Phi(S)=\sum_{C_j\in S}2^{m-j}.\)
If a legal improvement inserts \(C_j\), every deleted coalition has strictly smaller payoff and therefore an index greater than \(j\). If \(R\) is the set of deleted indices, then
\(\displaystyle \Phi(S')-\Phi(S)=2^{m-j}-\sum_{\ell\in R}2^{m-\ell}\ge1,\)
because the sum of all terms with indices greater than \(j\) is \(2^{m-j}-1\).
Thus every improvement path has length at most \(2^m-1\). A path extended whenever a blocker exists must terminate at a stable state. In particular, every valid instance is feasible whenever \(B\ge2^m-1\).
For a listed formation graph \(Q\), write \(k_Q=|V(Q)|\) and \(e_Q=|E(Q)|\). Define
\(\displaystyle \mathcal A_{\mathcal G}(n)=1+\sum_{\substack{Q\in\mathcal G\\1\le k_Q\le n}}k_Q!\,(k_Q+e_Q).\)
Given a visibility graph and a coalition, accessibility can be decided by enumerating every bijection for each formation graph of matching order. Checking one bijection requires checking its mapped edges; the expression above bounds this enumeration, up to polynomial bit-operation factors.
An exact algorithm proceeds as follows:
A valid state’s visibility graph can be constructed in \(O(n^2)\) elementary operations: disjointness gives \(\sum_{D\in S}|D|^2\le n^2\). There are at most \(m\) outgoing improvements per state. A convenient coarse deterministic running-time bound is
\(\displaystyle O\!\left(\left[1+m^2n+\tau m+2^m\bigl(n^2+m^2+m\mathcal A_{\mathcal G}(n)\bigr)\right]L^3\right).\)
The polynomial factor accommodates binary rational comparisons and manipulation of state identifiers and distances. The algorithm compares distances with the binary encoding of \(B\); it does not iterate through the numerical value of \(B\).
When formation graphs have bounded order, this becomes \(2^m\operatorname{poly}(n,m,\tau,L)\). For unrestricted explicitly listed formation graphs, the factorial enumeration gives the coarser bound \(2^{O(m+n\log(n+1))}\operatorname{poly}(L)\).
The hardness construction already has constant formation-graph size and permanently accessible coalitions. Every path in that construction uses at most \(m\) improvements; the difficulty is deciding whether stability can be reached within the smaller specified deadline.
⟨structured verdict parsed — rendered above⟩
The output resolves the task. The reduction establishes \(\mathrm{NP}\)-hardness of the distribution-routing problem and \(\mathrm{NP}\)-completeness of the stated restricted family. The general termination argument and exhaustive running-time bounds are also valid. No major or minor mathematical issues were found.
The routing lemma is correct in both directions.
For each supported initial state \(S_i\), every trajectory completed within \(B\) rounds contains at most \(B\) legal improvements. Waiting and splitting cannot produce a stable endpoint when no such improvement sequence exists. The assumption that each supported type has positive mass is essential and is explicitly satisfied.
Conversely, routing each type’s entire mass along one suitable path is permitted. The lack of interactions and capacities allows all these paths to run simultaneously; waiting accommodates different path lengths.
Thus feasibility depends precisely on whether \(d(S_i)\le B\) for every supported state. The numerical masses do not otherwise affect feasibility.
The invoked theorem is correctly stated: satisfiability of CNF formulas with at most three literals per clause is \(\mathrm{NP}\)-complete. This is the source problem identified in [Karp’s paper](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf). The reduction requires no additional promise on literal occurrences.
The transformation is valid:
The stated equisatisfiability and polynomial-size claims follow.
The graph construction and maximum-degree bound are correct. Literal vertices have two triangle neighbors and at most two clause neighbors; clause vertices have at most three distinct neighbors; helper vertices have degree two.
The forward implication is valid. Selecting the vertex representing each variable’s assigned value yields an independent set of size \(q\). It dominates every variable triangle and, because the assignment satisfies the formula, every clause vertex. Therefore it is maximal.
The reverse implication also holds:
Hence the equivalence between satisfiability and a maximal independent set of size at most \(q\) is established.
Repeated literals or clauses do not invalidate the argument. An empty clause, if permitted by the source convention, becomes an isolated clause vertex and correctly prevents a maximal independent set within the budget.
Every coalition has exactly five agents because its edge agents and private agents total \(5\). The degree bound ensures at least one private agent per coalition, so the coalitions are distinct.
The intersection identity is exact: an edge agent belongs only to its two endpoint coalitions, and private agents belong only to their designated coalition. Thus coalition disjointness corresponds precisely to independence in \(H\).
The permanent links contain all edges of each coalition’s clique. Therefore \(K_5\) admits the required bijection onto every allowed coalition in every state. Extra permanent or visibility edges are allowed by the task.
The legal-move analysis respects strict payoff comparison:
Stable states correspond exactly to maximal independent sets. Any independent set is reachable from the empty state by legally adding its coalitions in any order, using exactly its cardinality in improvements.
Together with the routing lemma and \(B=q\), this proves the required equivalence with satisfiability. The terminal requirement is reaching any stable state, exactly as requested.
The agent count is correctly computed using the degree sum:
\[ n=|E(H)|+\sum_{u\in U}(5-\deg_H(u)) =5m-|E(H)|. \]
Since the maximum degree is four, \(|E(H)|\le2m\), giving \(3m\le n\le5m\). Thus \(m=\Theta(n)\).
Each coalition contributes at most ten permanent links, so the union contains at most \(10m\) links. The fixed formation graph has five vertices and ten edges. Indexed explicit lists yield the stated asymptotic output length \(O(m\log(m+1))\); the binary deadline fits within that bound.
For the restricted family, a certificate of at most \(\min(B,m)\) coalition selections suffices. Pairwise disjointness establishes reachability from the empty state, and intersection with every unselected coalition establishes stability. These checks are polynomial in the explicit input length.
The restricted \(\mathrm{NP}\)-completeness claim is therefore justified. The output appropriately claims only \(\mathrm{NP}\)-hardness for the unrestricted problem.
The potential argument is correct, including its handling of equal payoffs.
A deleted coalition must have strictly smaller payoff than the inserted coalition, so it occurs later in the ordering regardless of tie-breaking. The inserted coalition was absent from the previous state. Consequently,
\[ \Phi(S')-\Phi(S) =2^{m-j}-\sum_{\ell\in R}2^{m-\ell} \ge1. \]
The potential is an integer between \(0\) and \(2^m-1\). Hence every improvement path has at most \(2^m-1\) improvements.
A path continued whenever a blocker exists must terminate, and its terminal state must be stable. Therefore the universal feasibility statement for \(B\ge2^m-1\) follows.
For \(m=0\), the empty state is already stable and the bound is zero, so this edge case is consistent.
The algorithm correctly enumerates all valid states, computes their legal transitions, identifies stable states, and obtains distances to stability by a backward multi-source shortest-path search. Unit improvement lengths and permitted waiting make these distances the relevant quantities.
The accessibility enumeration checks exactly the required condition: only formation graphs of matching order can admit a bijection, and only their mapped edges need to be present. Nonedges impose no restrictions.
The stated visibility-construction bound follows from disjointness:
\[ \sum_{D\in S}|D|^2\le n^2. \]
The coarse runtime
\[ O\!\left( \left[ 1+m^2n+\tau m+ 2^m\bigl(n^2+m^2+m\mathcal A_{\mathcal G}(n)\bigr) \right]L^3 \right) \]
adequately covers intersection preprocessing, state validation, visibility construction, blocker checks, transition processing, shortest-path bookkeeping, and binary arithmetic. Reading the explicit formation graphs is also covered by the input-length factor.
The bounded-order and unrestricted factorial specializations are valid. Comparing the resulting distances with \(B\) uses its binary representation and does not require iterating through its numerical value.
No repair or additional clarification is required. The proof distinguishes decision hardness from path-length lower bounds and settles the distribution-routing question through its explicit reduction.
⟨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.