Publications

• Sorted by Date • Classified by Publication Type • Classified by Research Category •

Heuristic Search for Identical Payoff Bayesian Games

Frans A. Oliehoek, Matthijs T. J. Spaan, Jilles Dibangoye, and Christopher Amato. Heuristic Search for Identical Payoff Bayesian Games. In Proceedings of the Ninth International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pp. 1115–1122, May 2010.

Download

pdf [179.3kB]  

Abstract

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 the coordination of 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 speed ups of up to 3 orders of magnitude for synthetic random games, and reaching 10 orders of magnitude speed ups for games in a Dec-POMDP 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

@InProceedings{Oliehoek10AAMAS,
    author =    {Frans A. Oliehoek and 
                Matthijs T. J. Spaan and
                Jilles Dibangoye and
                Christopher Amato},
    title =     {Heuristic Search for Identical Payoff {B}ayesian Games},
    booktitle = AAMAS10,
    month =     may,
    year =      2010,
    pages =     {1115--1122},
    url =       {http://www.ifaamas.org/Proceedings/aamas2010/pdf/01%20Full%20Papers/23_02_FP_0490.pdf},
    abstract = 	 {
    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 the coordination of 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 speed ups of up to 3 orders of
    magnitude for synthetic random games, and reaching 10 orders of
    magnitude speed ups for games in a Dec-POMDP 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. 
  }
}

Generated by bib2html.pl (written by Patrick Riley) on Mon Apr 08, 2024 20:28:07 UTC