Probabilistic Stability in Coalitional Games

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 115 papers28 conceptsfrozen 2026-10-04

In cooperative game theory, the "Core" is the gold standard for stability. A group partition is in the core if no subset of agents has an incentive to break away and form their own coalition. However, the core is notoriously difficult to work with: in many games, the core is empty (no stable partition exists), and even when it isn't, finding a stable arrangement often requires checking an exponential number of possible coalitions.

A growing body of research suggests a way out of this mathematical deadlock: Probabilistic Stability. By shifting the goal from absolute stability against all possible groups to statistical stability against likely groups, researchers have transformed coalitional games from intractable puzzles into solvable engineering problems.

The Complexity of Perfect Stability

The fundamental problem with traditional stability is its binary nature. As Hooyeon Lee and Yoav Shoham demonstrate in the "Stable Invitation Problem," even simple tasks like organizing a guest list become NP-hard when you require that no one feels excluded or wants to leave. The search space for these problems grows exponentially with the number of participants, making it impossible to evaluate every potential "blocking" coalition.

Furthermore, Saar Cohen and Noa Agmon point out that real-world participation is often stochastic. If agents only show up with a certain probability (due to traffic, illness, or other factors), a partition that was stable yesterday might become unstable today. Deterministic models fail to account for this inherent randomness.

Probably Approximately Correct Stability

To bridge this gap, Maria Florina Balcan, Ariel D. Procaccia, and Yair Zick introduced the Probably Approximately Correct (PAC) framework to coalitional games. The intuition is simple: if we cannot know every agent's preference for every possible group, we can sample a small number of coalitions and find a division of value that is "likely" to be stable against most other coalitions.

Jakub Sliwinski and Yair Zick extended this to Hedonic Games, where agents only care about the members of their own coalition. In this framework, a partition is considered "probably stable" if the probability that a randomly sampled coalition would want to deviate is below a tiny threshold. This relaxation allows us to find "good enough" solutions using only a polynomial number of samples, bypassing the exponential explosion of the core.

Efficiency through Statistical Sampling

The power of this approach lies in its scalability. In Federated Learning, for instance, Mengda Ji and colleagues use sampling to ensure that data contributors are paid fairly and have no incentive to leave the network. By sampling a subset of coalitions rather than evaluating all $2^n$ combinations, they reduce the computational complexity from exponential to linear while maintaining high-probability stability guarantees.

This same logic is being applied to mechanistic interpretability in AI. Tanya Chowdhury and Yair Zick treat neurons in Large Language Models as agents in a hedonic game. By using PAC sampling to identify "hedonic coalitions" of neurons that work together synergistically, they can map the internal structure of models that are far too large for traditional game-theoretic analysis.

The Limits of Relaxation

While probabilistic stability is powerful, it is not a magic bullet. The structure of the underlying interactions matters. Ayumi Igarashi and Yair Zick discovered a sharp phase transition in community formation: if the social network is a "forest" (no cycles), PAC stable partitions are easy to find. However, if the network contains even a single cycle, finding such a partition can become statistically impossible.

Furthermore, the "distribution" of potential coalitions is critical. Simone Fioravanti, Michele Flammini, and their colleagues have shown that we can stabilize games previously thought "impossible" if we assume a non-adversarial distribution. If every possible coalition has at least a tiny, non-zero probability of being sampled (a "bounded distribution"), we can find $\varepsilon$-fractional core stable partitions—arrangements where only a negligible fraction of potential groups would ever want to deviate.

By accepting a tiny margin of error, these frameworks move game theory from the realm of abstract impossibility into a practical tool for organizing complex, multi-agent systems.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_probabilistic_stability_in_coalitional_g_9698f3e7,
  title = {Probabilistic Stability in Coalitional Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-stability-in-coalitional-games/rdr_9698f3e7472445bfb600366c14abc830},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-18},
}

This exact version (version 1, frozen text):

@misc{lacuna_probabilistic_stability_in_coalitional_g_9698f3e7_v1,
  title = {Probabilistic Stability in Coalitional Games},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/probabilistic-stability-in-coalitional-games/rdr_9698f3e7472445bfb600366c14abc830/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-18},
}