Timezone: »

Bayesian Action-Graph Games
Albert Xin Jiang · Kevin Leyton-Brown

Mon Dec 06 12:00 AM -- 12:00 AM (PST) @

Games of incomplete information, or Bayesian games, are an important game-theoretic model and have many applications in economics. We propose Bayesian action-graph games (BAGGs), a novel graphical representation for Bayesian games. BAGGs can represent arbitrary Bayesian games, and furthermore can compactly express Bayesian games exhibiting commonly encountered types of structure including symmetry, action- and type-specific utility independence, and probabilistic independence of type distributions. We provide an algorithm for computing expected utility in BAGGs, and discuss conditions under which the algorithm runs in polynomial time. Bayes-Nash equilibria of BAGGs can be computed by adapting existing algorithms for complete-information normal form games and leveraging our expected utility algorithm. We show both theoretically and empirically that our approaches improve significantly on the state of the art.

Author Information

Albert Xin Jiang (University of British Columbia)
Kevin Leyton-Brown (University of British Columbia)

More from the Same Authors