Publications

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

Exploiting Structure in Cooperative Bayesian Games

Frans A. Oliehoek, Shimon Whiteson, and Matthijs T. J. Spaan. Exploiting Structure in Cooperative Bayesian Games. In Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence, pp. 654–664, August 2012.

Download

pdf [1.2MB]  

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.

BibTeX Entry

@InProceedings{Oliehoek12UAI,
    author =    {Frans A. Oliehoek and 
                 Shimon Whiteson and
                 Matthijs T. J. Spaan},
    title =     {Exploiting Structure in Cooperative {B}ayesian Games},
    booktitle = uai12,
    month =     aug,
    year =      2012,
    pages =     {654--664},
    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.
  }
}

Generated by bib2html.pl (written by Patrick Riley) on Wed Nov 06, 2013 16:37:07 UTC