Abstract
Congestion games are a fundamental class of noncooperative games possessing pure-strategy Nash equilibria. In the network version, each player wants to route one unit of flow on a path from her origin to her destination at minimum cost, and the cost of using an arc only depends on the total number of players using that arc. A natural extension is to allow for players sending different amounts of flow, which results in so-called weighted congestion games. While examples have been exhibited showing that pure-strategy Nash equilibria need not exist, we prove that it actually is strongly NP-hard to determine whether a given weighted network congestion game has a pure-strategy Nash equilibrium. This is true regardless of whether flow is unsplittable (has to be routed on a single path for each player) or not.
A related family of games are local-effect games, where the disutility of a player taking a particular action depends on the number of players taking the same action and on the number of players choosing related actions. We show that the problem of deciding whether a bidirectional local-effect game has a pure-strategy Nash equilibrium is NP-complete, and that the problem of finding a pure-strategy Nash equilibrium in a bidirectional local-effect game with linear local-effect functions (for which the existence of a pure-strategy Nash equilibrium is guaranteed) is PLS-complete. The latter proof uses a tight PLS-reduction, which implies the existence of instances and initial states for which any sequence of selfish improvement steps needs exponential time to reach a pure-strategy Nash equilibrium.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ackermann, H., Röglin, H., Vöcking, B.: On the impact of combinatorial structure on congestion games. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA (to appear, 2006a)
Ackermann, H., Röglin, H., Vöcking, B.: Pure Nash equilibria in player-specific and weighted congestion games. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol. 4286, pp. 50–61. Springer, Heidelberg (2006b)
Àlvarez, C., Gabarró, J., Serna, M.: Pure Nash equilibria in games with a large number of actions. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 95–106. Springer, Heidelberg (2005)
Anshelevich, E., Dasgupta, A., Kleinberg, J., Tardos, É., Wexler, T., Roughgarden, T.: The price of stability for network design with fair cost allocation. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, pp. 295–304 (2004)
Awerbuch, B., Azar, Y., Epstein, A.: The price of routing unsplittable flow. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, pp. 57–66 (2005)
Brandt, F., Fischer, F., Holzer, M.: Symmetries and the complexity of pure Nash equilibrium. Electronic Colloquium on Computational Complexity, TR06-091 (2006)
Chen, X., Deng, X.: 3-Nash is PPAD-complete. Electronic Colloquium on Computational Complexity, TR05-134 (2005)
Chen, X., Deng, X.: Settling the complexity of 2-player Nash-equilibrium. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, Berkeley, CA (to appear, 2006)
Daskalakis, C., Goldberg, P., Papadimitriou, C.: The complexity of computing a Nash equilibrium. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, pp. 71–78 (2006)
Daskalakis, C., Papadimitriou, C.: Three-player games are hard. Electronic Colloquium on Computational Complexity, TR05-139 (2005)
Dunkel, J.: The Complexity of Pure-Strategy Nash Equilibria in Non-Cooperative Games. Diplomarbeit, Institute of Mathematics, Technische Universität Berlin, Germany (July 2005)
Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, pp. 604–612 (2004)
Fischer, F., Holzer, M., Katzenbeisser, S.: The influence of neighbourhood and choice on the complexity of finding pure Nash equilibria. Information Processing Letters 99, 239–245 (2006)
Fotakis, D., Kontogiannis, S., Spirakis, P.: Selfish unsplittable flows. Theoretical Computer Science 348, 226–239 (2005)
Goemans, M., Mirrokni, V., Vetta, A.: Sink equilibria and convergence. In: Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, Pittsburgh, PA, pp. 142–154 (2005)
Goldberg, P., Papadimitriou, C.: Reducibility among equilibrium problems. In: Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, pp. 61–70 (2006)
Gottlob, G., Greco, G., Scarcello, F.: Pure Nash equilibria: Hard and easy games. Journal of Artificial Intelligence Research 24, 357–406 (2005)
Ieong, S., McGrew, R., Nudelman, E., Shoham, Y., Sun, Q.: Fast and compact: A simple class of congestion games. In: Proceedings of the 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, Pittsburgh, PA, pp. 489–494 (2005)
Leyton-Brown, K., Tennenholtz, M.: Local-effect games. In: Proceedings of the 18th International Joint Conference on Artificial Intelligence, Acapulco, Mexico, pp. 772–780 (2003)
Milchtaich, I.: Congestion games with player-specific payoff functions. Games and Economic Behavior 13, 111–124 (1996)
Nash, J.: Non-cooperative games. Annals of Mathematics 54, 268–295 (1951)
Rosenthal, R.: A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory 2, 65–67 (1973)
Schäffer, A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM Journal on Computing 20, 56–87 (1991)
Schoenebeck, G., Vadhan, S.: The computational complexity of Nash equilibria in concisely represented games. In: Proceedings of the 7th ACM Conference on Electronic Commerce, Ann Arbor, MI, pp. 270–279 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dunkel, J., Schulz, A.S. (2006). On the Complexity of Pure-Strategy Nash Equilibria in Congestion and Local-Effect Games. In: Spirakis, P., Mavronicolas, M., Kontogiannis, S. (eds) Internet and Network Economics. WINE 2006. Lecture Notes in Computer Science, vol 4286. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11944874_7
Download citation
DOI: https://doi.org/10.1007/11944874_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68138-0
Online ISBN: 978-3-540-68141-0
eBook Packages: Computer ScienceComputer Science (R0)