Christos H. Papadimitriou
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.
- R. J. Aumann "Subjectivity and correlation in randomized strategies", Journal of Mathematical Economics, 1, pp. 67--96, 1974.Google Scholar
Cross Ref
- D. Blackwell "An analog of the minimax theorem for vector payoffs," Pacific J. Math., 6, 1, pp. 1--8, 1956.Google ScholarCross Ref
- B. G. Chun, K. Chaudhuri, H. Wee, M. Barreno, C. H. Papadimitriou, J. Kubiatowicz "Selfish caching in distributed systems: a game-theoretic analysis," PODC 2004, pp. 21--30. Google ScholarDigital Library
- K. Daskalakis, C. H. Papadimitriou "The complexity of equilibria in highly regular graph games," available at www.cs.berkeley.edu/~christosGoogle Scholar
- B. C. Eaves "Polymatrix games with joint constraints," SIAM J. Appl. Math. 24,, pp. 418--423, 1973.Google ScholarDigital Library
- A. Fabrikant, C. H. Papadimitriou, K. Talwar "The Complexity of Pure-Strategy Equilibria," 2004 STOC. Google ScholarDigital Library
- D. Foster, R. Vohra "Calibrated Learning and Correlated Equilibrium," Games and Economic Behaviour, 1997Google Scholar
- D. Fotakis, S. C. Kontogiannis, E. Koutsoupias, M. Mavronicolas, P. G. Spirakis "The Structure and Complexity of Nash Equilibria for a Selfish Routing Game," ICALP 2002. Google ScholarDigital Library
- M. Grötschel, L. Lovsz, A. Schrijver Geometric Algorithms and Combinatorial Optimization, Springer, 1989.Google Scholar
- S. Hart and A. Mas-Colell "A Simple Adaptive Pocedure Leading to Correlated Equilibria," Econometrica 68, 5, 1127--1150, 2000.Google ScholarCross Ref
- S. Hart and D. Schmeidler "Existence of Correlated Equilibria," Mathematics of Operations Research 14, 1, 18--25, 1989. Google ScholarDigital Library
- J. T. Howson, Jr. "Equilibria of polymatrix games," Management Science 18, 312--318.Google ScholarDigital Library
- S. Kakade, M. Kearns, J. Langford, and L. Ortiz "Correlated Equilibria in Graphical Games," ACM Conference on Electronic Commerce, 2003. Google ScholarDigital Library
- M. Kearns, M. Littman, S. Singh "Graphical Models for Game Theory," Proceedings of UAI, 2001. Google ScholarDigital Library
- L. Khachiyan "A polynomial algorithm in linear programming," Sov. Math., Dokl., 20, 1979.Google Scholar
- R. Khandekar "Lagrangian Relaxation based Algorithms for Convex Programming Problems," PhD thesis, 2004, available at http://www.cs.berkeley.edu/~rohitk/Google Scholar
- K. Leyton-Brown, M. Tennenholtz "Local-Effect Games," IJCAI 2003. Google ScholarDigital Library
- R. B. Myerson "Dual Reduction and Elementary Games," Games and Economic Behavior, 21 (1-2), pp. 183--202, 1997.Google ScholarCross Ref
- J. Nash "Noncooperative games," Annals of Mathematics, 54, 289--295, 1951.Google ScholarCross Ref
- R. F. Nau and K. F. McCardle "Coherent Behavior in Noncooperative Games," Journal of Economic Theory 50, 2, pp. 424--444, 1990.Google ScholarCross Ref
- M. Pál, É. Tardos "Group Strategyproof Mechanisms via Primal-Dual Algorithms," FOCS 2003, pp. 584--593. Google ScholarDigital Library
- C. H. Papadimitriou "Algorithms, Games, and the Internet", 2001 STOC, pp. 749--753. Google ScholarDigital Library
- C. H. Papadimitriou, T. Roughgarden "Computing equilibria in multiplayer games," 2005 SODA. Google ScholarDigital Library
- C. H. Papadimitriou, K. Steiglitz, Combinatorial optimization: algorithms and complexity, Prentice-Hall, 1982; Dover, 1999. Google ScholarDigital Library
- T. Roughgarden, É. Tardos "Bounding the Inefficiency of Equilibria in Nonatomic Congestion Games" Games and Economic Behavior, 2004 (to appear).Google Scholar
- R. W. Rosenthal "A class of games possessing pure-strategy Nash equilibria," International Journal of Game Theory, 2, pp. 65--67, 1973.Google ScholarDigital Library
- E. B. Yanovskaya "Equilibrium points in polymatrix games," (in Russian) Litovskii Matematicheskii Sbornik, 8, 381--384, 1968. (Math. Reviews 39 #3831.)Google Scholar
- R. Savani, B. von Stengel "Exponentially many steps for finding a Nash equilibrium in a bimatrix game," FOCS 2004. Google ScholarDigital Library
Index Terms
- Computing correlated equilibria in multi-player games
Recommendations
Computing correlated equilibria in multi-player games
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 ...
Settling the complexity of computing two-player Nash equilibria
We prove that Bimatrix, the problem of finding a Nash equilibrium in a two-player game, is complete for the complexity class PPAD (Polynomial Parity Argument, Directed version) introduced by Papadimitriou in 1991.
Our result, building upon the work of ...
Computing Optimal Ex Ante Correlated Equilibria in Two-Player Sequential Games
AAMAS '19: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent SystemsWe investigate the computation of equilibria in extensive-form games when ex ante correlation is possible, focusing on correlated equilibria requiring the least amount of communication between the players and the mediator. Motivated by hardness results ...
Comments