In cooperative game theory, the ultimate goal is to get self-interested agents to work together in a stable "grand coalition." For cooperation to be sustainable, the way the rewards are divided must be fair enough that no subgroup of agents has an incentive to break away and form their own smaller coalition. When a reward distribution satisfies this condition, it is said to belong to the core of the game.
However, in many realistic multi-agent environments, the core is completely empty.
To understand why, imagine three players trying to split a \$100 prize, where any majority vote (two out of three players) decides the allocation. If Players A and B agree to a 50/50 split (\$50, \$50, \$0), Player C can easily disrupt this by offering Player B a better deal, say (\$0, \$60, \$40). Player B accepts, but then Player A can counter-offer Player C. This cycle continues indefinitely. No single distribution can satisfy every possible sub-coalition simultaneously.
As noted by Naoki Ohta et al. in A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments, this lack of guaranteed stability makes designing automated multi-agent systems exceptionally difficult. This "empty core problem" manifests across diverse domains. For instance, Wei-Chen Lee et al. demonstrate that when multiple prizes are awarded based on ranked weights, outcomes are highly vulnerable to player deviations (k-Prize Weighted Voting Game). Similarly, in concurrent games with mean-payoff rewards, Julian Gutierrez et al. show that quantitative settings easily trigger empty solution sets for as few as three players (Cooperative concurrent games). Even in decentralized sharing economies, achieving coalition-proof outcomes remains a steep challenge (Sreenivas Gollapudi et al., You Get What You Share: Incentives for a Sharing Economy).
If an empty core implies inherent systemic instability, how can we design robust multi-agent systems? Researchers have tackled this problem from three main angles: quantifying the external force needed to stabilize the game, relaxing the mathematical definitions of stability, and engineering the game mechanics themselves to guarantee that a stable state exists.
Quantifying Instability: The Cost of Stability
When a cooperative group cannot naturally agree on a stable payoff distribution, an external authority can step in and inject a financial subsidy to incentivize agents to stay together. The minimum external funding required to eliminate the incentive for any subgroup to defect is known as the Cost of Stability (CoS).
The intuition here is simple: if the grand coalition pays out slightly more than what players could achieve on their own, defection loses its financial appeal.
Without Subsidy (Empty Core):
[Sub-Coalition Defects] <--- Higher Private Return than Grand Coalition
With Subsidy (Cost of Stability):
[Grand Coalition + External Subsidy] ---> Satisfies All Sub-Coalitions Simultaneously
The magnitude of this subsidy depends heavily on how the agents interact. Reshef Meir et al. established a formal link between the structural complexity of a game's interaction network and its required subsidy in Bounding the Cost of Stability in Games over Interaction Networks. They proved that if a network's structural complexity (measured via "treewidth") is $k$, the relative cost of stabilizing the game is at most $k+1$.
By bounding this cost mathematically, the authors provide a predictable framework for system designers to calculate exactly how much external funding is required to maintain cooperation across different network topologies (Bounds on the Cost of Stabilizing a Cooperative Game).
Relaxing the Rules of Defection
Traditional core stability operates on an aggressive threat model: it assumes that any group of agents, no matter how large or fragmented, can perfectly coordinate a defection instantly. In the real world, coordination is costly and communication is limited. By relaxing this assumption, researchers can find stable solutions that are "good enough."
One approach is to limit the size of colluding groups. Grant Schoenebeck et al. introduced the concept of Bayesian $k$-strong equilibria in Strong Equilibria in Bayesian Games with Bounded Group Size. Instead of protecting against massive, system-wide collusion, this framework calculates exact thresholds for robustness when coordination is restricted to small, manageable subsets of participants of size $k$.
Another relaxation involves tolerating a small amount of instability. In many coalition formation scenarios, such as hedonic games where agents care about who else is in their coalition, a perfectly stable partition is mathematically impossible. To circumvent this, Simone Fioravanti et al. proposed $\varepsilon$-fractional core stability in $\varepsilon$-fractional core stability in Hedonic Games.. By allowing a tiny fraction of coalitions to remain technically unstable, they designed efficient algorithms that can converge on stable partitions even when agent preferences are completely unknown and must be learned from data.
Engineering Stability Through Utility Design
Instead of paying for stability or lowering our standards, can we change the rules of the game so that a stable core naturally emerges?
In hedonic games, agents evaluate their happiness based on the average quality of their group members. Felix Brandt 0001 et al. showed that reaching these stable structures through individual agent moves is computationally hard and frequently impossible (Reaching Individually Stable Coalition Structures in Hedonic Games).
However, Gianpiero Monaco et al. discovered a striking mathematical fix in Stable outcomes in modified fractional hedonic games. By slightly altering the utility function—forcing agents to average their benefits over their peers only, excluding themselves—the empty core problem completely vanishes. Under this modified utility, a stable core outcome is guaranteed to exist for any graph structure.
Surprisingly, introducing real-world friction or unreliability can also act as a natural stabilizer. Intuitively, if network links or agents might fail, a system should become more volatile. Yet, Reshef Meir et al. demonstrated the opposite in Solving Cooperative Reliability Games. When agents have an inherent probability of failure, increasing their unreliability actually expands the core. The risk of failure dampens the expected returns of breaking away, making the safety of the grand coalition more attractive and turning an inherently unstable game into a stable one.
A similar phenomenon occurs in decentralized congestion games. Even when these games lack a "potential function"—the standard mathematical tool used to guarantee that decentralized agents can find an equilibrium—the introduction of resource failures still preserves the existence of a pure-strategy Nash equilibrium (Michal Penn et al., Congestion games with failures).
Information, Mediation, and Arbitration
Finally, core emptiness often stems from asymmetric information or a lack of trust. If agents cannot agree on the value of their collective work, they cannot agree on a payoff distribution.
Bomin Jiang et al. resolved this in Coalitional game with opinion exchange by introducing a framework where strategic players exchange opinions to reach a consensus before distributing payoffs. This communication step uncovers a stable, non-empty Bayesian core, provided that a player's influence within the group is balanced by their level of risk-aversion.
When communication alone isn't enough, structural enforcement can bridge the gap:
- Trusted Mediators: Traditional mediation fails if it only offers non-binding suggestions. However, Moshe Tennenholtz et al. proved that "routing mediators" with direct visibility into player actions can successfully enforce compliance and prevent coalitions from defecting for private gains (Routing Mediators).
- Arbitration Functions: In complex settings where coalitions can overlap, stability depends heavily on how the remaining players react when a subgroup defects. Yair Zick et al. formalized this using "arbitration functions" in Arbitration and Stability in Cooperative Games with Overlapping Coalitions, mapping out the exact boundaries of stable resource distributions based on how lenient or punitive the remaining system is to deviators.
Ultimately, these diverse approaches show that an empty core is not a dead end for system design. Whether through external subsidies, relaxed constraints, utility redesign, or structural mediation, understanding why coalitions fall apart gives us the exact mathematical tools needed to keep them together.
Key Foundational Work
A Compact Representation Scheme for Coalitional Games in Open Anonymous Environments (2006) — contributed 1 concept elements to this direction.
Congestion games with failures (2005) — contributed 1 concept elements to this direction.