Computing equilibria in multi-player games

ABSTRACT

We initiate the systematic study of algorithmic issues involved in finding equilibria (Nash and correlated) in games with a large number of players; such games, in order to be computationally meaningful, must be presented in some succinct, game-specific way. We develop a general framework for obtaining polynomial-time algorithms for optimizing over correlated equilibria in such settings, and show how it can be applied successfully to symmetric games (for which we actually find an exact polytopal characterization), graphical games, and congestion games, among others. We also present complexity results implying that such algorithms are not possible in certain other such games. Finally, we present a polynomial-time algorithm, based on quantifier elimination, for finding a Nash equilibrium in symmetric games when the number of strategies is relatively small.

REFERENCES

• 1: R. J. Aumann. Subjectivity and correlation in randomized strategies. Journal of Mathematical Economics, 1(1):67--96, 1974.
• 2: R. J. Aumann. Correlated equilibrium as an expression of Bayesian rationality. Econometrica, 55(1):1--18, 1987.
• 3: J. W. Brown and J. von Neumann. Solutions of games by differential equations. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory Games, volume 1, pages 73--79. Princeton University Press, 1950.
• 4: V. Chvátal. Linear Programming. Freeman, 1983.
• 5: V. Conitzer and T. Sandholm. Complexity results about Nash equilibria. In Proceedings of International Joint Conference on Artificial Intelligence, 2003.
• 6: A. Czumaj. Selfish routing on the Internet. In J. Leung, editor, Handbook of Scheduling. CRC Press, Boca Raton, FL, 2004, to appear.
• 7: Xiaotie Deng , Christos Papadimitriou , Shmuel Safra, On the complexity of equilibria, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509920]
• 8: Nikhil R. Devanur , Christos H. Papadimitriou , Amin Saberi , Vijay V. Vazirani, Market Equilibrium via a Primal-Dual-Type Algorithm, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.389-395, November 16-19, 2002
• 9: N. R. Devanur and V. V. Vazirani. An improved approximation scheme for computing Arrow-Debreu prices for the linear case. In 23rd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pages 149--155, 2003.
• 10: E. Even-Dar, A. Kesselman, and Y. Mansour. Convergence time to Nash equilibria. In Proceedings of the 30th Annual International Colloquium in Automata, Languages, and Programming (ICALP), volume 2719 of Lecture Notes in Computer Science, pages 502--513, 2003.
• 11: 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]
• 12: R. Feldmann, M. Gairing, T. Lücking, B. Monien, and M. Rode. Selfish routing in non-cooperative networks: A survey. In Proceedings of the Conference on Mathematical Foundations of Computer Science (MFCS), volume 2747 of Lecture Notes in Computer Science, pages 21--4, 2003.
• 13: D. Foster and R. Vohra. Calibrated learning and correlated equilibrium. Games and Economic Behavior, 21:40--55, 1997.
• 14: D. Foster and R. Vohra. Regret in the on-line decision problem. Games and Economic Behavior, 29:7--35, 1999.
• 15: D. Gale, H. W. Kuhn, and A. W. Tucker. On symmetric games. In H. W. Kuhn and A. W. Tucker, editors, Contributions to the Theory Games, volume 1, pages 81--87. Princeton University Press, 1950.
• 16: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 17: M. Grötschel, L. Lovász, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag, 1988. Second Corrected Edition, 1993.
• 18: K. Jain, M. Mahdian, and A. Saberi. Approximating market equilibria. In Proceedings of the 9th International on Approximation Algorithms for Combinatorial Optimization Problems, 2003.
• 19: 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]
• 20: 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
• 21: L. G. Khachiyan. A polynomial algorithm in linear programming. Soviet Mathematics Doklady, 20:191--194, 1979.
• 22: M. A. Khan and Y. Sun. Non-cooperative games with many players. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory, volume 3, chapter 46. North-Holland, 2002.
• 23: D. Koller and B. Milch. Multi-agent influence diagrams for representing and solving games. Games and Economic Behavior, 45:181--221, 2003.
• 24: H. W. Kuhn and A. W. Tucker. Contributions to the Theory of Games, volume 1. Princeton University Press, 1950.
• 25: R. J. Lipton and E. Markakis. Nash equilibria via polynomial equations. In Proceedings of the Sixth Conference on Latin American Theoretical Informatics (LATIN), pages 413--422, 2004.
• 26: Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
• 27: M. L. Littman, M. Kearns, and S. Singh. An efficient exact algorithm for singly connected graphical games. In Advances in Neural Information Processing Systems, volume 14, 2001.
• 28: Michael L. Littman , Peter Stone, A polynomial-time nash equilibrium algorithm for repeated games, Proceedings of the 4th ACM conference on Electronic commerce, p.48-54, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779935]
• 29: J. F. Nash, Jr. Equilibrium points in N-person games. In Proceedings of the National Academy of Science, volume 36, pages 48--49, 1950.
• 30: J. F. Nash, Jr. Non-cooperative games. Annals of Mathematics, 54(2):286--295, 1951.
• 31: G. Owen. Game Theory. Academic Press, 1995. Third Edition.
• 32: 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]
• 33: R. W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 34: R. W. Rosenthal. The network equilibrium problem in integers. Networks, 3:53--59, 1973.
• 35: Timothy Avelin Roughgarden , Eva Tardos, Selfish routing, 2002
• 36: R. Savani and B. von Stengel. Long Lemke-Howson paths. Technical Report LSE-CDAM-2003-14, London School of Economics, 2003.
• 37: Y. Shoham. Introduction to Multi-Agent Systems. 2004. In preparation.
• 38: Adrian Vetta, Nash Equilibria in Competitive Societies, with Applications to Facility Location, Traffic Routing and Auctions, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.416, November 16-19, 2002
• 39: J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. Princeton University Press, 1944.
• 40: J. W. Weibull. Evolutionary Game Theory. MIT Press, 1997.