Timezone: »
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
-
2020 Poster: Exemplar Guided Active Learning »
Jason Hartford · Kevin Leyton-Brown · Hadas Raviv · Dan Padnos · Shahar Lev · Barak Lenz -
2020 Poster: ImpatientCapsAndRuns: Approximately Optimal Algorithm Configuration from an Infinite Pool »
Gellert Weisz · András György · Wei-I Lin · Devon Graham · Kevin Leyton-Brown · Csaba Szepesvari · Brendan Lucier -
2019 Poster: Procrastinating with Confidence: Near-Optimal, Anytime, Adaptive Algorithm Configuration »
Robert Kleinberg · Kevin Leyton-Brown · Brendan Lucier · Devon Graham -
2016 Poster: Deep Learning for Predicting Human Strategic Behavior »
Jason Hartford · James R Wright · Kevin Leyton-Brown -
2016 Oral: Deep Learning for Predicting Human Strategic Behavior »
Jason Hartford · James R Wright · Kevin Leyton-Brown