Computing correlated equilibria in multi-player games

ABSTRACT

We develop polynomial-time algorithms for finding correlated equilibria—a well-studied notion of rationality that generalizes the Nash equilibrium—in a broad class of succinctly representable multiplayer games, encompassing graphical games, anonymous games, polymatrix games, congestion games, scheduling games, local effect games, as well as several generalizations. Our algorithm is based on a variant of the existence proof due to Hart and Schmeidler, and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as application-specific methods for computing multivariate expectations over product distributions.

For anonymous games and graphical games of bounded tree-width, we provide a different polynomial-time algorithm for optimizing an arbitrary linear function over the set of correlated equilibria of the game. In contrast to our sweeping positive results for computing an arbitrary correlated equilibrium, we prove that optimizing over correlated equilibria is NP-hard in all of the other classes of games that we consider.

REFERENCES

• 1: Elliot Anshelevich , Anirban Dasgupta , Jon Kleinberg , Eva Tardos , Tom Wexler , Tim Roughgarden, The Price of Stability for Network Design with Fair Cost Allocation, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.295-304, October 17-19, 2004 [doi>10.1109/FOCS.2004.68]
• 2: Arora, S., Hazan, E., and Kale, S. 2005. The multiplicative weights update method: A meta algorithm and applications. Working paper.
• 3: Aumann, R. J. 1974. Subjectivity and correlation in randomized strategies. J. Math. Econ. 1, 1, 67--96.
• 4: Blackwell, D. 1956. An analog of the minimax theorem for vector payoffs. Pac. J. Math. 6, 1, 1--8.
• 5: Blonski, M. 2000. Characterization of pure-strategy equilibria in finite anonymous games. J. Math. Econ. 34, 2, 225--233.
• 6: Brandt, F., Fischer, F., and Holzer, M. 2007. Symmetries and the complexity of pure Nash equilibrium. In Proceedings of the 24th Annual Symposium on Theoretical Aspects of Computer Science (STACS). Lecture Notes in Computer Science, vol. 4393. Springer-Verlag, New York, 212--223.
• 7: Brown, J. W., and von Neumann, J. 1950. Solutions of games by differential equations. In Contributions to the Theory Games, H. W. Kuhn and A. W. Tucker, Eds. Vol. 1. Princeton University Press, Princeton, NJ, 73--79.
• 8: Nicolo Cesa-Bianchi , Gabor Lugosi, Prediction, Learning, and Games, Cambridge University Press, New York, NY, 2006
• 9: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 10: Byung-Gon Chun , Kamalika Chaudhuri , Hoeteck Wee , Marco Barreno , Christos H. Papadimitriou , John Kubiatowicz, Selfish caching in distributed systems: a game-theoretic analysis, Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing, July 25-28, 2004, St. John's, Newfoundland, Canada [doi>10.1145/1011767.1011771]
• 11: Chvátal, V. 1983. Linear Programming. Freeman.
• 12: 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]
• 13: Daskalakis, C., and Papadimitriou, C. H. 2005. The complexity of games on highly regular graphs. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA). 71--82.
• 14: Eaves, B. C. 1973. Polymatric games with joint constraints. SIAM J. Appl. Math. 24, 3, 418--423.
• 15: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 16: Lance Fortnow , Russell Impagliazzo , Valentine Kabanets , Christopher Umans, On the Complexity of Succinct Zero-Sum Games, Proceedings of the 20th Annual IEEE Conference on Computational Complexity, p.323-332, June 11-15, 2005 [doi>10.1109/CCC.2005.18]
• 17: Foster, D., and Vohra, R. 1997. Calibrated learning and correlated equilibrium. Games Econ. Behav. 21, 1--2, 40--55.
• 18: Dimitris Fotakis , Spyros C. Kontogiannis , Elias Koutsoupias , Marios Mavronicolas , Paul G. Spirakis, The Structure and Complexity of Nash Equilibria for a Selfish Routing Game, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.123-134, July 08-13, 2002
• 19: Gale, D., Kuhn, H. W., and Tucker, A. W. 1950. On symmetric games. In Contributions to the Theory Games, H. W. Kuhn and A. W. Tucker, Eds. Vol. 1. Princeton University Press, Princeton, NJ, 81--87.
• 20: Grötschel, M., Lovász, L., and Schrijver, A. 1988. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, New York (Second Edition, 1993).
• 21: Hart, S., and Mansour, Y. 2008. The communication complexity of uncoupled Nash equilibrium procedures. Games Econ. Behav. To appear.
• 22: Hart, S., and Mas-Colell, A. 2000. A simple adaptive pocedure leading to correlated equilibria. Econometrica 68, 5, 1127--1150.
• 23: S. Hart , D. Schmeidler, Existence of correlated equilibria, Mathematics of Operations Research, v.14 n.1, p.18-25, Feb. 1989 [doi>10.1287/moor.14.1.18]
• 24: Howson, J. T. 1972. Equilibria of polymatrix games. Manage. Sci. 18, 5, 312--318.
• 25: 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]
• 26: 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
• 27: Khachiyan, L. G. 1979. A polynomial algorithm in linear programming. Soviet Math. Doklady 20, 1, 191--194.
• 28: Khandekar, R. 2004. Lagrangian relaxation based algorithms for convex programming problems. Ph.D. dissertation, IIT Delhi.
• 29: Jon Kleinberg , Eva Tardos, Algorithm Design, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2005
• 30: J. K. Lenstra , D. B. Shmoys , É. Tardos, Approximation algorithms for scheduling unrelated parallel machines, Mathematical Programming: Series A and B, v.46 n.3, p.259-271, January 1990 [doi>10.1007/BF01585745]
• 31: Leyton-Brown, K., and Tennenholtz, M. 2003. Local-effect games. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI). 772--780.
• 32: Lipton, R. J., and Markakis, E. 2004. Nash equilibria via polynomial equations. In Proceedings of the 6th Conference on Latin American Theoretical Informatics (LATIN). 413--422.
• 33: Milchtaich, I. 1996. Congestion games with player-specific payoff functions. Games Econ. Behav. 13, 1, 111--124.
• 34: Myerson, R. B. 1997. Dual reduction and elementary games. Games Econ. Behav. 21, 1-2, 183--202.
• 35: Nash, Jr., J. F. 1951. Non-cooperative games. Ann. Math. 54, 2, 286--295.
• 36: Nau, R. F., and McCardle, K. F. 1990. Coherent behavior in noncooperative games. J. Econ. Theory 50, 2, 424--444.
• 37: Papadimitriou, C. H. 2007. The complexity of finding Nash equilibria. In Algorithmic Game Theory, N. Nisan, T. Roughgarden, É. Tardos, and V. V. Vazirani, Eds. Cambridge, Chapter 2, 29--51.
• 38: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 39: James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Part III: quantifier elimination, Journal of Symbolic Computation, v.13 n.3, p.329-352, March 1992
• 40: Rosenthal, R. W. 1973. A class of games possessing pure-strategy Nash equilibria. International J. Game Theory 2, 1, 65--67.
• 41: Roughgarden, T., and Tardos, É. 2004. Bounding the inefficiency of equilibria in nonatomic congestion games. Games Econ. Behav. 49, 2, 389--403.
• 42: Grant Schoenebeck , Salil Vadhan, The computational complexity of nash equilibria in concisely represented games, Proceedings of the 7th ACM conference on Electronic commerce, p.270-279, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134737]
• 43: von Stengel, B. 2001. Computational complexity of correlated equilibria for extensive games. Tech. Rep. LSE-CDAM-2001-03, Centre for Discrete and Applicable Mathematics, London School of Economics.
• 44: Yanovskaya, E. B. 1968. Equilibrium situations in multi-matrix games. Litovskii Matematicheskii Sbornik 8, 381--384 (In Russian).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Economics, Theory

Keywords:
Correlated equilibria, Nash equilibria, complexity of equilibria