Georgios Chalkiadakis
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: gehalk@cs.toronto.edu
Evangelos Markakis
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: vangelis@cs.toronto.edu
Craig Boutilier
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: cebly@cs.toronto.edu
Abstract
Coalition formation is a problem of great interest in AI, allowing
groups of autonomous, rational agents to form stable teams. Fur-
thermore, the study of coalitional stability concepts and their re-
lation to equilibria that guide the strategic interactions of agents
during bargaining has lately attracted much attention. However,
research to date in both AI and economics has largely ignored the
potential presence of uncertainty when studying either coalitional
stability or coalitional bargaining. This paper is the first to relate
a (cooperative) stability concept under uncertainty, the Bayesian
core (BC), with (non-cooperative) equilibrium concepts of coali-
tional bargaining games. We prove that if the BC of a coalitional
game (and of each subgame) is non-empty, then there exists an
equilibrium of the corresponding bargaining game that produces a
BC element; and conversely, if there exists a coalitional bargain-
ing equilibrium (with certain properties), then it induces a BC
conguration. We thus provide a non-cooperative justification of
the BC stability concept. As a corollary, we establish a subgamecient
condition for the existence of the BC. Finally, for small games, we
provide an algorithm to decide whether the BC is non-empty.
To appear, AAMAS-07
Return to List of Papers