Computing correlated equilibria in multi-player games

ABSTRACT

We develop a polynomial-time algorithm for finding correlated equilibria (a well-studied notion of rationality due to Aumann that generalizes the Nash equilibrium) in a broad class of succinctly representable multiplayer games, encompassing essentially all known kinds, including all graphical 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 [11], and employs linear programming duality, the ellipsoid algorithm, Markov chain steady state computations, as well as application-specific methods for computing multivariate expectations.

REFERENCES

• 1: R. J. Aumann "Subjectivity and correlation in randomized strategies", Journal of Mathematical Economics, 1, pp. 67--96, 1974.
• 2: D. Blackwell "An analog of the minimax theorem for vector payoffs," Pacific J. Math., 6, 1, pp. 1--8, 1956.
• 3: 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]
• 4: K. Daskalakis, C. H. Papadimitriou "The complexity of equilibria in highly regular graph games," available at www.cs.berkeley.edu/~christos
• 5: B. C. Eaves "Polymatrix games with joint constraints," SIAM J. Appl. Math. 24,, pp. 418--423, 1973.
• 6: 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]
• 7: D. Foster, R. Vohra "Calibrated Learning and Correlated Equilibrium," Games and Economic Behaviour, 1997
• 8: 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
• 9: M. Grötschel, L. Lovsz, A. Schrijver Geometric Algorithms and Combinatorial Optimization, Springer, 1989.
• 10: S. Hart and A. Mas-Colell "A Simple Adaptive Pocedure Leading to Correlated Equilibria," Econometrica 68, 5, 1127--1150, 2000.
• 11: 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]
• 12: J. T. Howson, Jr. "Equilibria of polymatrix games," Management Science 18, 312--318.
• 13: 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]
• 14: 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
• 15: L. Khachiyan "A polynomial algorithm in linear programming," Sov. Math., Dokl., 20, 1979.
• 16: R. Khandekar "Lagrangian Relaxation based Algorithms for Convex Programming Problems," PhD thesis, 2004, available at http://www.cs.berkeley.edu/~rohitk/
• 17: K. Leyton-Brown, M. Tennenholtz "Local-Effect Games," IJCAI 2003.
• 18: R. B. Myerson "Dual Reduction and Elementary Games," Games and Economic Behavior, 21 (1-2), pp. 183--202, 1997.
• 19: J. Nash "Noncooperative games," Annals of Mathematics, 54, 289--295, 1951.
• 20: R. F. Nau and K. F. McCardle "Coherent Behavior in Noncooperative Games," Journal of Economic Theory 50, 2, pp. 424--444, 1990.
• 21: Martin Pál , Éva Tardo, Group Strategyproof Mechanisms via Primal-Dual Algorithms, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.584, October 11-14, 2003
• 22: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 23: Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 24: Christos H. Papadimitriou , Kenneth Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, 1982
• 25: T. Roughgarden, É. Tardos "Bounding the Inefficiency of Equilibria in Nonatomic Congestion Games" Games and Economic Behavior, 2004 (to appear).
• 26: R. W. Rosenthal "A class of games possessing pure-strategy Nash equilibria," International Journal of Game Theory, 2, pp. 65--67, 1973.
• 27: E. B. Yanovskaya "Equilibrium points in polymatrix games," (in Russian) Litovskii Matematicheskii Sbornik, 8, 381--384, 1968. (Math. Reviews 39 #3831.)
• 28: Rahul Savani , Bernhard von Stengel, Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.258-267, October 17-19, 2004 [doi>10.1109/FOCS.2004.28]

INDEX TERMS

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

General Terms:
Algorithms, Economics, Theory