Exploiting Structure in Cooperative Bayesian Games

Abstract

Problems in which a team of agents must coordinate their actions in the presence of imperfect information can be modeled as cooperative Bayesian games (BGs). Unfortunately, representing and solving such games requires space and computation time exponential in the number of agents. However, many BGs contain graphical structure such that the global payoff function decomposes as the sum of local payoff functions that depend on only a few agents. This paper demonstrates how to utilize this graphical structure to solve cooperative BGs much more efficiently. Our approach stems from the observation that these games possess two different types of structure, which we call agent and type independence. We propose a factor graph representation that captures both forms of independence and prove that solving it is tractable for small local neighborhoods. Experimental results demonstrate that this approach scales much better than existing methods and can tackle cooperative Bayesian games of unprecedented size.