Correlated equilibria in graphical games

ABSTRACT

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).

REFERENCES

• 1: R.J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1, 1974.
• 2: R.J. Aumann. Correlated equilibrium as an expression of Bayesian rationality. Econometrica, 55, 1987.
• 3: Adam L. Berger , Vincent J. Della Pietra , Stephen A. Della Pietra, A maximum entropy approach to natural language processing, Computational Linguistics, v.22 n.1, p.39-71, March 1996
• 4: A. P. Dawid and S. L. Lauritzen. Hyper Markov laws in the statistical analysis of decomposable graphical models. The Annals of Statistics, 21penalty0 (3):penalty0 1271--1317, September 1993.
• 5: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 6: D. Foster and R. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 1997.
• 7: D. Foster and R. Vohra. Regret in the on-line decision problem. Games and Economic Behavior, pages 7--36, 1999.
• 8: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 9: Daphne Koller and Brian Milch. Multi-agent influence diagrams for representing and solving games. Games and Economic Behavior. To appear.
• 10: Pierfrancesco La Mura, Game Networks, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.335-342, June 30-July 03, 2000
• 11: M. Littman, M. Kearns, and S. Singh. An efficient exact algorithm for singly connected graphical games. In Neural Information Processing Systems, 2002.
• 12: J. F. Nash. Non-cooperative games. Annals of Mathematics, 54:penalty0 286--295, 1951.
• 13: L. Ortiz and M. Kearns. Nash propagation for loopy graphical games. In Neural Information Processing Systems, 2003. To appear.
• 14: G. Owen. Game Theory. Academic Press, UK, 1995.
• 15: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 16: David Vickrey , Daphne Koller, Multi-agent algorithms for solving graphical games, Eighteenth national conference on Artificial intelligence, p.345-351, July 28-August 01, 2002, Edmonton, Alberta, Canada

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Economics, Theory

Keywords:
correlated equilibria, game theory, graphical games, graphical models