Simple Coalitional Games with Beliefs

Georgios Chalkiadakis, Edith Elkind, Nicholas R. JenningsIJCAI 2009 · OpenReview

Abstract

We introduce coalitional games with beliefs (CGBs), a natural generalization of coalitional games to environments where agents possess private beliefs regarding the capabilities (or types) of others. We put forward a model to capture such agent-type uncertainty and study coalitional stability in this setting. Specifically, we introduce a notion of the core for CGBs, both with and without coalition structures. For simple games without coalition structures, we provide a characterization of the core that matches the one for the full information case and use it to derive a polynomial-time algorithm to check core nonemptiness. In contrast, we demonstrate that in games with coalition structures, allowing beliefs increases the computational complexity of stability-related problems. In doing so, we introduce and analyze weighted voting games with beliefs, which may be of independent interest. Finally, we discuss connections between our model and other classes of coalitional games.

Introduction

In multi-agent systems, agents frequently need to form coalitions to achieve collective goals. Traditional coalitional game theory typically operates under the assumption of full information, where every agent knows the exact capabilities and contributions of every other agent. However, in real-world scenarios—ranging from robotic swarms to human organizations—agents often face significant uncertainty regarding their potential partners.

While previous research has attempted to model this uncertainty using Bayesian games, these models require agents to maintain complex probability distributions over every possible "type" of every other agent. Such models are often computationally intractable and cognitively unrealistic for agents with limited bandwidth or data. This paper proposes a more practical alternative: Coalitional Games with Beliefs (CGBs). In this framework, agents operate based on "point beliefs"—single best guesses about their partners' capabilities—rather than exhaustive probabilistic models.

The CGB Framework

The authors define CGBs as a way to bridge the gap between the simplicity of full-information games and the complexity of Bayesian models. Key components of the methodology include:

  • Point Beliefs: Agents maintain a single vector representing their best estimate of other agents' types. This captures uncertainty without the exponential overhead of probability distributions.
  • Demand Vectors: Because agents may disagree on the total value of a coalition (due to differing beliefs), they cannot simply divide a fixed payoff. Instead, they agree on shares (demands) of the eventual payoff, whatever that may be.
  • Subjective Stability: An outcome is considered stable if no agent believes they can achieve a better result by defecting to a different coalition. This means a state can be stable even if agents are factually incorrect about their teammates' abilities.

Stability and the Core

The paper adapts the concept of the "core"—the set of outcomes where no group has an incentive to defect—to the belief-based setting. Two primary versions are analyzed:

  1. The Core: The standard core where all agents are expected to form one "grand coalition."
  2. The CS-Core: The core in the context of coalition structures, where agents can partition themselves into several smaller, independent teams.

Simple Games and Veto Players

For "simple games" (where coalitions either win or lose), the authors generalize the concept of a veto player. A veto player is an agent whose cooperation is perceived as essential by all other agents. The paper proves that in the grand coalition setting, the core is non-empty if and only if at least one veto player exists. This characterization allows for a polynomial-time algorithm to check for core non-emptiness, matching the efficiency of the full-information case.

Computational Complexity Gap

A central finding of the research is the sharp divide in complexity when moving from a single grand coalition to multiple coalition structures.

In Weighted Voting Games (WVGs) with beliefs, the authors demonstrate that allowing agents to split into multiple teams significantly increases the difficulty of finding stable outcomes:

  • Outcome Verification: Checking if a specific outcome belongs to the CS-core is coNP-complete.
  • Non-emptiness Checking: Determining if the CS-core is non-empty is NP-hard.

Notably, these hardness results persist even when agent weights are small (polynomially bounded). This is a significant departure from full-information games, where such problems are typically easy to solve when weights are restricted.

Conclusion and Future Work

The CGB model provides a "sweet spot" for modeling uncertainty in multi-agent systems, capturing the essence of private beliefs without the computational burden of Bayesian frameworks. However, the authors note several areas for future exploration:

  • Dynamic Beliefs: The current model assumes beliefs are static. In practice, agents would likely update their "best guesses" after observing the performance of a coalition.
  • Strategic Manipulation: The model assumes private beliefs but does not yet account for agents who might lie about their beliefs to manipulate the formation of specific coalitions.
  • Learning: Future research could integrate learning mechanisms, where agents refine their point beliefs over multiple rounds of interaction.

By establishing the computational limits and theoretical foundations of belief-based coalitional games, this work offers a robust starting point for more realistic models of cooperation in uncertain environments.

Summary updated

Abstract

We introduce coalitional games with beliefs (CGBs), a natural generalization of coalitional games to environments where agents possess private beliefs regarding the capabilities (or types) of others. We put forward a model to capture such agent-type uncertainty, and study coalitional stability in this setting. Specifically, we introduce a notion of the core for CGBs, both with and without coalition structures. For simple games without coalition structures, we then provide a characterization of the core that matches the one for the full information case, and use it to derive a polynomial-time algorithm to check core nonemptiness. In contrast, we demonstrate that in games with coalition structures allowing beliefs increases the computational complexity of stability-related problems. In doing so, we introduce and analyze weighted voting games with beliefs, which may be of independent interest. Finally, we discuss connections between our model and other classes of coalitional games.
BibTeX
@inproceedings{chalkiadakis2009simple,
  author = {Georgios Chalkiadakis and Edith Elkind and Nicholas R. Jennings},
  title = {{Simple Coalitional Games with Beliefs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2009},
  url = {https://openreview.net/forum?id=HkNkqEfObH},
}
Figure