Georgios Chalkiadakis
Department of Computer Science
University of Toronto
Toronto, ON M5S 3H5
email: gehalk@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, individually rational
agents to form stable teams. Automating the negotiations
underlying coalition formation is, naturally, of
special concern. However, research to date in both AI
and economics has largely ignored the potential presence
of uncertainty in coalitional bargaining. We present a
model of discounted coalitional bargaining where agents
are uncertain about the types (or capabilities) of potential
partners, and hence the value of a coalition. We cast the
problem as a Bayesian game in extensive form, and describe
its Perfect Bayesian Equilibria as the solutions to
a polynomial program. We then present a heuristic algorithm
using iterative coalition formation to approximate
the optimal solution, and evaluate its performance.
To appear, IJCAI-07