Coalitional Stability in Multi-Agent Systems

40 concepts33 papers1 proposal

In multi-agent systems, cooperation often yields superior outcomes compared to individual effort. Whether it is autonomous vehicles coordinating to optimize traffic flow, cloud providers pooling computing resources, or edge devices collaboratively training a machine learning model, the collective benefit of cooperation is clear.

However, cooperation is inherently fragile. Rational, self-interested agents will only remain in a group if they receive a fair share of the collective reward or bear an acceptable fraction of the cost. If a subset of agents realizes they can achieve a better outcome by breaking away and forming an independent sub-coalition, the global system will fragment.

The challenge of preventing this defection is known as coalitional stability. To keep a global coalition intact, system designers must find a way to distribute payoffs or costs such that no sub-group has an incentive to deviate.

The Core: The Mathematical Boundary of Stability

At the heart of coalitional stability is a classic game-theoretic concept: the Core. An allocation of rewards or costs belongs to the core if, for every possible subset of agents, the total payoff allocated to that subset is at least as large as what they could obtain by acting entirely on their own. When an allocation lies within the core, the system achieves a stable equilibrium because the distribution of benefits prevents any sub-coalition from having a financial or operational incentive to deviate from the global agreement.

As Faheem Zafari et al. demonstrate in cloud resource sharing, outcomes within the core guarantee Pareto-optimal allocations while ensuring that no subgroup of players has an incentive to deviate and form their own coalition (A Game-Theoretic Framework for Resource Sharing in Clouds.).

This mathematical boundary applies across diverse domains:

  • Information Theory: In settings like communication for omniscience, Ni Ding et al. show that a non-empty core ensures users will not abandon the grand coalition, guaranteeing a stable cooperative solution where no user has an incentive to deviate (A game-theoretic perspective on communication for omniscience).
  • Market Design: In combinatorial auctions, maintaining outcomes within the core ensures that no alternative coalition of bidders can provide a higher total payoff to the seller. As Makoto Yokoo et al. demonstrate, this property prevents the auctioneer from having an incentive to abandon established rules, thereby stabilizing the market and protecting the seller's interests (Making VCG More Robust in Combinatorial Auctions via Submodular Approximation).

Why Stability Works: Convexity and Submodularity

How do we guarantee that a stable core even exists? The answer lies in the mathematical structure of the cooperation rewards, specifically convexity and submodularity.

In a convex cooperative game, the marginal benefit of adding an agent increases as the coalition grows larger. This creates a "the more, the merrier" dynamic, implying that a unified sharing framework is mathematically robust against fragmentation into smaller, less efficient groups. Faheem Zafari et al. leverage this property to prove that a stable grand coalition always exists when mobile edge cloud providers share resources (Let's Share: A Game-Theoretic Framework for Resource Sharing in Mobile Edge Clouds). Even when outcomes are uncertain, Fanyong Meng et al. show that reward distribution mechanisms can maintain structural stability by ensuring the allocation remains within the game's core if the underlying game is convex (Cooperative Fuzzy Games with a Coalition Structure and Interval Payoffs).

In information and network routing, this translates to submodularity—the property of diminishing returns in individual costs or information gain. Ni Ding et al. establish that the submodularity of underlying information-theoretic functions directly guarantees a non-empty core, ensuring that users naturally prefer global cooperation over fragmentation (A game-theoretic perspective on communication for omniscience).

Managing Instability: Least Core, Nucleolus, and Subsidies

In many real-world scenarios, a perfectly stable core does not exist, or calculating it requires evaluating an exponential number of sub-coalitions. As Onn Shehory identifies, without a stable payoff distribution, rational agents lack the incentive to remain in a coalition, leading to group fragmentation and reduced collective efficiency (Coalition Formation Methods in Multi-Agent Environments). To bypass the exponential overhead typically required to evaluate every possible group combination, Onn Shehory et al. adapt game-theoretic concepts into polynomial-time algorithms to reach stable agreements efficiently (A Kernel-Oriented Model for Coalition-Formation in General Environments: Implementation and Results).

When a perfect core allocation is mathematically impossible, researchers pivot to minimizing the incentive to defect using alternative solution concepts:

  • The Least Core: This approach minimizes the maximum dissatisfaction or potential gain any sub-coalition could achieve by defecting. Orcun Karaca et al. apply this to international power grid reserve exchanges, showing that minimizing this metric of dissatisfaction provides an approximately stable solution that encourages long-term cooperation in complex networks (A market-based approach for enabling inter-area reserve exchange).
  • The Nucleolus: The nucleolus sequentially minimizes the maximum dissatisfaction of agent sub-groups. In multi-agent reinforcement learning (MARL), Yugu Li et al. use nucleolus-based credit assignment to ensure that no subset of agents has an incentive to break away, allowing agents to autonomously partition themselves into stable sub-coalitions to focus on specific sub-tasks without deviating from the collective strategy (Nucleolus Credit Assignment for Effective Coalitions in Multi-agent Reinforcement Learning).
  • External Subsidies: When internal reallocation is insufficient, external funding can bridge the gap. Hoong Chuin Lau et al. introduce an iterative procedure ($\delta$-BSA) that identifies the least stable subset of participants and incrementally increases their total payout until the entire system reaches a stable state with the minimum possible external funding (Achieving Stable and Fair Profit Allocation with Minimum Subsidy in Collaborative Logistics). Similarly, in matching platforms where preferences must be learned dynamically from bandit feedback, Meena Jagadeesan et al. use "Subset Instability" to represent the minimum subsidy required to prevent agents from leaving a platform while their preferences are still being learned (Learning Equilibria in Matching Markets from Bandit Feedback).
  • Structural Constraints: Selecting outcomes that minimize the total number of groups can also serve as a specific tie-breaking rule to ensure stability. As Michele Flammini et al. demonstrate in hedonic coalition formation games, constraining the set of possible outcomes helps align individual incentives with social optimality and reduces susceptibility to strategic manipulation (Non-obvious Manipulability in Hedonic Games with Friends Appreciation Preferences).

Stability in Modern Distributed Paradigms

The principles of coalitional stability have become vital in modern distributed computing, machine learning, and decentralized infrastructure.

Federated Learning

Training machine learning models across heterogeneous clients introduces severe incentive misalignments. High-quality data providers might feel penalized if forced to share a model with low-quality or noisy participants. Bhaskar Ray Chaudhury et al. introduce core-stability to federated learning via the CoreFed algorithm, treating collaborative training as a cooperative game where a model is stable if no subset of participants can achieve higher utility by training independently (Fairness in Federated Learning via Core-Stability).

However, enforcing stability can come at a cost to overall efficiency. Avrim Blum et al. show that in collaborative settings with linear utilities, optimal stable allocations tend to concentrate the sampling burden on a specific subset of participants while allowing others to contribute nothing, implying that stability often requires a few agents to act as the primary data providers (One for One, or All for All: Equilibria and Optimality of Collaboration in Federated Learning).

Multi-Agent Reinforcement Learning

To motivate self-interested agents to cooperate in dynamic environments, reward structures must reflect marginal utility. Songyang Han et al. demonstrate that reallocating rewards based on the Shapley value in convex games ensures that autonomous vehicle coalitions remain stable, satisfying all participating agents' requirements for fairness and marginal utility (Stable and Efficient Shapley Value-Based Reward Reallocation for Multi-Agent Reinforcement Learning of Autonomous Vehicles).

Decentralized Networks and Markets

In intermediary-led or peer-to-peer markets, participants will bypass platforms if they perceive the cost distribution as unfair. Sreenivas Gollapudi et al. design ex-ante stable mechanisms for two-sided cost-sharing markets to ensure that no subset of buyers and sellers can achieve a better outcome by coordinating independently outside the platform (Cost Sharing in Two-Sided Markets). This challenge is equally acute in electronic marketplaces where buyers pool resources to optimize costly searches; David Sarne et al. note that without robust game-theoretic frameworks to ensure fair distribution, individual members may exit the coalition in favor of autonomous search (Cooperative Exploration in the Electronic Marketplace).

This economic insulation is mirrored in physical networks:

Key Foundational Work

A Kernel-Oriented Model for Coalition-Formation in General Environments: Implementation and Results (1996) — contributed 1 concept elements to this direction.
Coalition Formation Methods in Multi-Agent Environments (1994) — contributed 1 concept elements to this direction.
Coalition, Cryptography, and Stability: Mechanisms for Coalition Formation in Task OrientedDomains (1994) — contributed 1 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_coalition_stability_38024c85,
  title = {coalition stability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coalition-stability/rdr_38024c85a6b048a88a15e569fc771350},
  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_coalition_stability_38024c85_v1,
  title = {coalition stability},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/coalition-stability/rdr_38024c85a6b048a88a15e569fc771350/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