Abstract
We introduce coalitional games with beliefs (CGBs),a natural generalization of coalitional games to environ-ments 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 coali-tional stability in this setting. Specifically, we introduce a notion of the core for CGBs, both with and without coali-tion structures. For simple games without coalition struc-tures, 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 non-emptiness. 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 inter-est. Finally, we discuss connections between our model and other classes of coalitional games.