Heuristic Search for Identical Payoff Bayesian Games

Frans A. Oliehoek, Matthijs T. J. Spaan, Jilles S. Dibangoye, and Christopher Amato. Heuristic Search for Identical Payoff Bayesian Games. In Proc. of Int. Conference on Autonomous Agents and Multi Agent Systems, pp. 1115–1122, 2010.


pdf [179.3kB]  


Bayesian games can be used to model single-shot decision problems in which agents only possess incomplete information about other agents, and hence are important for multiagent coordination under uncertainty. Moreover they can be used to represent different stages of sequential multiagent decision problems, such as POSGs and DEC-POMDPs, and appear as an operation in many methods for multiagent planning under uncertainty. In this paper we are interested in coordinating teams of cooperative agents. While many such problems can be formulated as Bayesian games with identical payoffs, little work has been done to improve solution methods. To help address this situation, we provide a branch and bound algorithm that optimally solves identical payoff Bayesian games. Our results show a marked improvement over previous methods, obtaining speedups of up to 3 orders of magnitude for synthetic random games, and reaching 10 orders of magnitude speedups for games in a DECPOMDP context. This not only allows Bayesian games to be solved more efficiently, but can also improve multiagent planning techniques such as top-down and bottom-up algorithms for decentralized POMDPs.

BibTeX Entry

  author =       {Frans A. Oliehoek and Matthijs T. J. Spaan and Jilles
                  S. Dibangoye and Christopher Amato},
  title =        {Heuristic Search for Identical Payoff {Bayesian} Games},
  booktitle =    {Proc. of Int. Conference on Autonomous Agents
                  and Multi Agent Systems},
  year =         2010,
  pages =        {1115--1122}

Note: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.

Generated by (written by Patrick Riley) on Tue Sep 06, 2011 11:22:28 UTC