2003 · 93 citations · 12 references
Social SciencesComputer ScienceMathematicsDecision TheoryGame TheoryInformation TheoryAlgorithmic Game TheoryBehavioral Game TheoryNash EquilibriumNetwork GamesNoncooperative Game TheoryComputational Game TheoryEquilibrium Analysis On NetworksGame TreesGraph GamesGraphical GamesMarkov Network ModelsMultiplayer GamesPolynomial Time Complexity
We examine correlated equilibria in the recently introduced formalism of graphical games, a succinct representation for multiplayer games. We establish a natural and powerful relationship between the graphical structure of a multiplayer game and a certain Markov network representing distributions over joint actions. Our first main result establishes that this Markov network succinctly represents all correlated equilibria of the graphical game up to expected payoff equivalence. Our second main result provides a general algorithm for computing correlated equilibria in a graphical game based on its associated Markov network. For a special class of graphical games that includes trees, this algorithm runs in time polynomial in the graphical game representation (which is polynomial in the number of players and exponential in the graph degree).
12
Correlated Equilibrium as an Expression of Bayesian Rationality
Robert J. Aumann · Econometrica · 1987 · 1.6K citations · Full text
Graphical Models for Game Theory
Michael Kearns, Michael L. Littman, Satinder Singh · arXiv (Cornell University) · 2013 · 574 citations · Full text