Computing pure nash equilibria in graphical games via markov random fields

ABSTRACT

We present a reduction from graphical games to Markov random fields so that pure Nash equilibria in the former can be found by statistical inference on the latter. Our result, when combined with the junction tree algorithm for statistical inference, yields a unified proof of all previously known tractable cases of the NP-complete problem of finding pure Nash equilibria in graphical games, but also implies efficient algorithms for new classes, such as the games with O(log n) treewidth. Furthermore, this important problem becomes susceptible to a wealth of sophisticated and empirically successful techniques from Machine Learning.

REFERENCES

• 1: Dimitris Achlioptas , Yuval Peres, The threshold for random k-SAT is 2^k (ln 2 - O(k)), Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780577]
• 2: Stefan Arnborg , Derek G. Corneil , Andrzej Proskurowski, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, v.8 n.2, p.277-284, April 1, 1987 [doi>10.1137/0608024]
• 3: Ann Becker , Dan Geiger, A sufficiently fast algorithm for finding close to optimal clique trees, Artificial Intelligence, v.125 n.1-2, p.3-17, Jan. 2001 [doi>10.1016/S0004-3702(00)00075-8]
• 4: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• 5: H. L. Bodlaender. Discovering Treewidth. In SOFSEM, n2005.
• 6: A. Braunstein, M. Mezard and R. Zecchina. Survey Propagation: an Algorithm for Satisfiability. CoRR, cs.CC/0212002, 2002.
• 7: X. Chen and X. Deng. 3-NASH is PPAD-Complete. Electronic Colloquium in Computational Complexity TR05-134, 2005.
• 8: X. Chen and X. Deng. Settling the Complexity of 2-Player Nash-Equilibrium. Electronic Colloquium in Computational Complexity TR05-140, 2005.
• 9: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 10: C. Daskalakis and C. H. Papadimitriou. Three-Player Games Are Hard. Electronic Colloquium in Computational Complexity TR05-139, 2005.
• 11: Edith Elkind , Leslie Ann Goldberg , Paul Goldberg, Nash equilibria in graphical games on trees revisited, Proceedings of the 7th ACM conference on Electronic commerce, p.100-109, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134719]
• 12: W. Gilks, S. Richardson and D. Spiegelhalter. Markov Chain Monte Carlo in practice. Chapman and Hall, London, 1996.
• 13: Paul W. Goldberg , Christos H. Papadimitriou, Reducibility among equilibrium problems, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132526]
• 14: Georg Gottlob , Gianluigi Greco , Francesco Scarcello, Pure Nash equilibria: hard and easy games, Proceedings of the 9th conference on Theoretical aspects of rationality and knowledge, June 20-22, 2003, Univerity of Indiana, Indiana [doi>10.1145/846241.846269]
• 15: G. Gottlob, N. Leone and F. Scarcello. Hypertree Decompositions and Tractable Queries. J. Comput. Syst. Sci., 64(3):579--627, 2002.
• 16: F. Jensen, S. Lauritzen and K. Olesen. Bayesian Updating in Causal Probabilistic Networks by Local Computations. Computational Statistics Quarterly, 4:269--282, 1990.
• 17: Sham Kakade , Michael Kearns , John Langford , Luis Ortiz, Correlated equilibria in graphical games, Proceedings of the 4th ACM conference on Electronic commerce, p.42-47, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779934]
• 18: 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
• 19: S. Kirkpatrick , C. D. Gelatt, Jr. , M. P. Vecchi, Optimization by simulated annealing, Readings in computer vision: issues, problems, principles, and paradigms, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1987
• 20: T. Kloks. Treewidth: Computations and Approximations. Springer-Verlag, 1994.
• 21: D. M. Kreps. Game Theory and Economic Modelling. Oxford University Press, 1990.
• 22: S. L. Lauritzen. Graphical Models. Clarendon Press, Oxford, 1996.
• 23: S. L. Lauritzen , D. J. Spiegelhalter, Local computations with probabilities on graphical structures and their application to expert systems, Readings in uncertain reasoning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1990
• 24: M. L. Littman, M. J. Kearns and S. P. Singh. An Efficient, Exact Algorithm for Solving Tree-Structured Graphical Games. In NIPS, 2001.
• 25: Elitza Maneva , Elchanan Mossel , Martin J. Wainwright, A new look at survey propagation and its generalizations, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 26: N. Metropolis, A. Rosenbluth, M. Rosenbluth, A. Teller and E. Teller. Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21, 1953.
• 27: L. E. Ortiz and M. J. Kearns. Nash Propagation for Loopy Graphical Games. In NIPS, 2002.
• 28: M. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
• 29: Christos H. Papadimitriou, Computing correlated equilibria in multi-player games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060598]
• 30: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 31: Bruce A. Reed, Finding approximate separators and computing tree width quickly, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.221-228, May 04-06, 1992, Victoria, British Columbia, Canada [doi>10.1145/129712.129734]
• 32: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 33: M. J. Wainwright and M. I. Jordan. Graphical Models, Exponential Families, and Variational Inference. Technical Report, 64, Department of Statistics, University of California, Berkeley, 2003.
• 34: J. S. Yedidia, W. T. Freeman and Y. Weiss. Generalized Belief Propagation. In NIPS, 2000.

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:
markov random fields, nash equilibrium, treewidth