The Computational Complexity of Coalition Stability Verification

198 concepts89 papers2 proposals

In cooperative game theory, multi-agent systems form coalitions to achieve shared goals, maximize collective utility, or distribute payoffs. However, these groups are only sustainable if they are stable. The gold standard of stability is the core: a state where no subgroup of agents has a rational incentive to break away and form their own independent coalition.

While the core is an elegant solution concept, verifying whether a given arrangement actually belongs to it is notoriously difficult. The fundamental bottleneck is a combinatorial explosion: to prove a system is stable, an algorithm must verify that every single possible sub-coalition cannot do better on its own.

The Combinatorial Explosion of Group Defections

To understand why stability verification is so challenging, it helps to contrast it with individual stability concepts like the Nash equilibrium. To verify if a system is Nash-stable, an algorithm only needs to check if any individual agent wants to change their position. For $N$ agents, this requires checking at most $N$ alternative states—a task that scales linearly.

Group-based stability, however, requires checking all possible subsets of players. Because a set of $N$ players has $2^N$ potential sub-coalitions, the search space grows exponentially.

As Vincent Conitzer et al. demonstrated in Complexity of Determining Nonemptiness of the Core, even determining whether a stable outcome exists is $\mathcal{NP}$-complete when games are represented concisely. The authors showed that this hardness stems directly from the strategic constraints of the grand coalition; evaluating whether a global agreement can withstand defections requires navigating an intractable number of splinter groups.

This sharp divergence between individual and group stability appears across various coalition models:

  • Hedonic Games: In games where agents only care about the identity of the members within their own coalition, Dominik Peters et al. showed in Simple Causes of Complexity in Hedonic Games that finding stable outcomes remains $\mathcal{NP}$-hard even on extremely sparse interaction networks. The authors designed cyclic agent gadgets that act as "instability engines," proving that group-level stability definitions remain intractable even when individual stability is easy to evaluate.
  • Fractional Hedonic Games: When an agent's utility is determined by the average value of their group members rather than the sum, the problem remains stubborn. In Fractional Hedonic Games, Haris Aziz 0001 et al. proved that verifying whether a specific partition is stable against group deviations is $\text{co}\mathcal{NP}$-complete, requiring an exhaustive check against all possible subsets of players to ensure no alternative coalition exists where every member is better off.

Why Compact Representations Do Not Eliminate Hardness

One might hope that representing cooperative games more efficiently—such as using graphs, logic, or rules to avoid listing the value of all $2^N$ coalitions explicitly—would make stability verification tractable. However, the complexity is baked into the mathematical logic of the solution concepts themselves, not just how the game is written down.

Gianluigi Greco et al. explored this boundary in On the Complexity of Compact Coalitional Games. The authors proved that verifying stable outcomes like the bargaining set can reach the $\Pi^P_2$ level of the polynomial hierarchy. This complexity implies that moving to succinct, graph-based representations does not bypass the fundamental difficulty of ensuring that no subgroup has a rational incentive to defect.

Furthermore, the nature of how utility is shared dictates this hardness. In Infeasibility Certificates and the Complexity of the Core in Coalitional Games, Enrico Malizia et al. showed that when moving from transferable utility (where agents can freely redistribute payoffs) to non-transferable utility (NTU) games, the complexity of verifying core non-emptiness escalates to $\Sigma^P_2$-completeness. The authors established that the inability to freely transfer utility creates a more complex search space, making it impossible to construct a small, polynomial-sized "infeasibility certificate" to easily prove that no stable distribution exists.

The Paradox of Social and Altruistic Preferences

Intuitively, it seems reasonable to assume that introducing altruism—where agents care about the happiness of their peers—would smooth over conflicts and make stable states easier to find. In algorithmic game theory, however, social interdependence introduces a new layer of computational complexity.

When agents possess interdependent utilities, verifying group stability becomes even more demanding. In Altruism in Coalition Formation Games, Anna Maria Kerkmann et al. demonstrated that while individual stability checks remain computationally efficient under altruism, verifying group-based concepts like core stability remains $\text{co}\mathcal{NP}$-hard.

This boundary was finalized by Jörg Rothe et al. in Solving Four Open Problems about Core Stability in Altruistic Hedonic Games. The authors settled long-standing open questions by proving that core stability verification in altruistic hedonic games is strictly $\text{co}\mathcal{NP}$-complete. They demonstrated that whether players weigh their own happiness equally with friends or prioritize their friends entirely, the search space for potential group defections still grows exponentially. Altruism fails to simplify the mathematical difficulty of proving an equilibrium, highlighting a stark gap between the social benefits of cooperation and the computational cost of verifying it.

Escaping Intractability via Structural Constraints

If the general problem of verifying coalition stability is fundamentally hard due to the exponential combinations of subgroups, how can multi-agent systems ever guarantee stable outcomes? The answer lies in restricting the global structure of agent interactions.

Dominik Peters demonstrated a path to tractability in Towards Structural Tractability in Hedonic Games. By shifting the focus from individual preference types to the global structure of agent interactions, he proved that by bounding the "treewidth" and "degree" of the agent dependency graph, the complexity of finding core-stable partitions collapses from the second level of the polynomial hierarchy down to linear time.

Similarly, Jiehua Chen et al. showed in Cores in Friend-Oriented Hedonic Games: Verification is Surprisingly Harder than Searching that stability verification becomes computationally efficient when both the maximum coalition size and the structural complexity of the preference graph are tightly bounded. By limiting the density of agent relationships and the size of allowed groups, the combinatorial explosion of potential deviating sub-coalitions is successfully contained, providing a clear algorithmic path to verifying stable cooperation.

Key Foundational Work

Complexity of Determining Nonemptiness of the Core (2003) — contributed 4 concept elements to this direction.
Complexity of Determining Nonemptiness of the Core (2003) — contributed 3 concept elements to this direction.
Computing Shapley Values, Manipulating Value Division Schemes, and Checking Core Membership in Multi-Issue Domains (2004) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stability_verification_complexity_0b7b613b,
  title = {stability verification complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stability-verification-complexity/rdr_0b7b613b3a3c48579e628d811784fe81},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_stability_verification_complexity_0b7b613b_v1,
  title = {stability verification complexity},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stability-verification-complexity/rdr_0b7b613b3a3c48579e628d811784fe81/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake