The Computational Complexity of Nash Equilibria in Concisely Represented Games

Abstract

Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number of agents grows. We study two models of concisely represented games: circuit games, where the payoffs are computed by a given boolean circuit, and graph games, where each agent’s payoff is a function of only the strategies played by its neighbors in a given graph. For these two models, we study the complexity of four questions: determining if a given strategy is a Nash equilibrium, finding a Nash equilibrium, determining if there exists a pure Nash equilibrium, and determining if there exists a Nash equilibrium in which the payoffs to a player meet some given guarantees. In many cases, we obtain tight results, showing that the problems are complete for various complexity classes.

References

1. Àlvarez, C., Gabarró, J., and Serna, M. 2005. Pure Nash equilibria in games with a large number of actions. In Mathematical Foundations of Computer Science 2005, J. Jedrzejowicz and A. Szepietowski Eds., Lecture Notes in Computer Science Series, vol. 3618, Springer Berlin, 95--106.
2. Arora, S., Lund, C., Motwani, R., Sudan, M., and Szegedy, M. 1998. Proof verification and the hardness of approximation problems. J. ACM 45, 3, 501--555.
3. Arora, S. and Safra, S. 1998. Probabilistic checking of proofs: A new characterization of NP. J. ACM 45, 1, 70--122.
4. Babai, L. and Moran, S. 1988. Arthur-Merlin games: A randomized proof system and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36, 254--276.
5. Chen, X. and Deng, X. 2005. 3-Nash is PPAD-complete. Tech. rep. TR05-134, Electronic Colloquium on Computational Complexity.
6. Chen, X. and Deng, X. 2006. Settling the complexity of two-player Nash equilibrium. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, 261--272.
7. Chen, X., Deng, X., and Teng, S.-H. 2006. Computing Nash equilibria: Approximation and smoothed complexity. In Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 603--612.
8. Conitzer, V. and Sandholm, T. 2008. New complexity results about Nash equilibria. Games Econ. Behav. 63, 2, 621--641.
9. Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. 2006. The complexity of computing a Nash equilibrium. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (FOCS).
10. Daskalakis, C., Goldberg, P. W., and Papadimitriou, C. H. 2008. The complexity of computing a Nash equilibrium. SIAM J. Comput. 39, 1, 195--259.
11. Daskalakis, C. and Papadimitriou, C. 2005a. The complexity of games on highly regular graphs. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA).
12. Daskalakis, C. and Papadimitriou, C. 2005b. Three-player games are hard. Tech. rep. TR05-139, Electronic Colloquium on Computational Complexity.
13. Feige, U., Goldwasser, S., Lovász, L., Safra, S., and Szegedy, M. 1996. Interactive proofs and the hardness of approximating cliques. J. ACM 43, 2, 268--292.
14. Feigenbaum, J., Koller, D., and Shor, P. 1995. A game-theoretic classification of interactive complexity classes. In Proceedings of the 10th Annual IEEE Conference on Computational Complexity (CCC). 227--237.
15. Fortnow, L., Impagliazzo, R., Kabanets, V., and Umans, C. 2008. On the complexity of succinct zero-sum games. Computat. Complex. 17, 3, 353--376.
16. Gilboa, I. and Zemel, E. 1989. Nash and correlated equilibria: Some complexity considerations. Games Econ. Behav. 1, 80--93.
17. Goldberg, P. W. and Papadimitriou, C. H. 2006. Reducibility among equilibrium problems. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (FOCS). 21--23
18. Goldreich, O. 2005. On promise problems (a survey in memory of Shimon Even {1935--2004}). Tech. rep. TR05-018, Electronic Colloquium on Computational Complexity.
19. Goldreich, O., Micali, S., and Wigderson, A. 1991. Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38, 3, 691--729.
20. Goldwasser, S., Micali, S., and Rackoff, C. 1989. The knowledge complexity of interactive proof systems. SIAM J. Comput. 18, 1, 186--208.
21. Gottlob, G., Greco, G., and Scarcello, F. 2003. Pure Nash equilibria: Hard and easy games. In Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK). ACM Press, New York, NY, 215--230.
22. Hesse, W., Allender, E., and Barrington, D. 2002. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci. 65, 695--716.
23. Kearns, M., Littman, M. L., and Singh, S. 2001. Graphical models for game theory. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). 253--260.
24. Lipton, R., Markakis, E., and Mehta, A. 2003. Playing large games using simple strategies. In Proceedings of the ACM Conference on Electronic Commerce (EC).
25. Megiddo, N. and Papadimitriou, C. H. 1991. A note on total functions, existence theorems, and computational complexity. Theoret. Comput. Sci. 81, 1, 317--324.
26. Nash, J. 1951. Non-cooperative games. Annals Math. 54, 2, 286--295.
27. Nash, J. F. and Shapley, L. S. 1950. A simple three-person poker game. Contrib. Theor. Games 1, 24, 105--116.
28. Schoenebeck, G. 2004. The complexity of finding Nash equilibria in succinctly represented games. Undergraduate thesis, Harvard University.
29. Schoenebeck, G. and Vadhan, S. 2006. The computational complexity of Nash equilibria in concisely represented games. In Proceedings of the 7th ACM Conference on Electronic Commerce (EC). ACM, New York, NY, 270--279.

Index Terms

• Theory of computation

  • Randomness, geometry and discrete structures