On the complexity of nash dynamics and sink equilibria

ABSTRACT

Studying Nash dynamics is an important approach for analyzing the outcome of games with repeated selfish behavior of self-interested agents. Sink equilibria has been introduced by Goemans, Mirrokni, and Vetta for studying social cost on Nash dynamics over pure strategies in games. However, they do not address the complexity of sink equilibria in these games. Recently, Fabrikant and Papadimitriou initiated the study of the complexity of Nash dynamics in two classes of games. In order to completely understand the complexity of Nash dynamics in a variety of games, we study the following three questions for various games: (i) given a state in game, can we verify if this state is in a sink equilibrium or not? (ii) given an instance of a game, can we verify if there exists any sink equilibrium other than pure Nash equilibria? and (iii) given an instance of a game, can we verify if there exists a pure Nash equilibrium (i.e, a sink equilibrium with one state)?

In this paper, we almost answer all of the above questions for a variety of classes of games with succinct representation, including anonymous games, player-specific and weighted congestion games, valid-utility games, and two-sided market games. In particular, for most of these problems, we show that (i) it is PSPACE-hard to verify if a given state is in a sink equilibrium, (ii) it is NP-hard to verify if there exists a pure Nash equilibrium in the game or not, (iii) it is PSPACE-hard to verify if there exists any sink equilibrium other than pure Nash equilibria. To solve these problems, we illustrate general techniques that could be used to answer similar questions in other classes of games.

REFERENCES

• 1: H. Ackermann, H. Röglin, and B. Vöcking. Pure Nash equilibria in player-specific and weighted congestion games. In Proceedings of the 2nd International Workshop on Internet and Network Economics (WINE), pages 50--61, 2006.
• 2: Heiner Ackermann and Alexander Skopalik. On the complexity of pure Nash equilibria in player-specific network congestion games. In Proceedings of 3nd International Workshop on Internet and Network Economics (WINE), pages 419--430, 2007.
• 3: Felix Brandt, Felix A. Fischer, and Markus Holzer. Symmetries and the complexity of pure nash equilibrium. In Wolfgang Thomas and Pascal Weil, editors, STACS, volume 4393 of Lecture Notes in Computer Science, pages 212--223. Springer, 2007.
• 4: Xi Chen , Xiaotie Deng, Settling the Complexity of Two-Player Nash Equilibrium, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.261-272, October 21-24, 2006 [doi>10.1109/FOCS.2006.69]
• 5: Xi Chen , Xiaotie Deng , Shang-Hua Teng, Computing Nash Equilibria: Approximation and Smoothed Complexity, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, p.603-612, October 21-24, 2006 [doi>10.1109/FOCS.2006.20]
• 6: Constantinos Daskalakis , Christos Papadimitriou, Computing Equilibria in Anonymous Games, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.83-93, October 21-23, 2007 [doi>10.1109/FOCS.2007.19]
• 7: C. Daskalakis and C.H. Papadimitriou. On the exhaustive algorithm for nash equilibria. page Unpublished Manuscript, 2007.
• 8: Constantinos Daskalakis , Paul W. Goldberg , Christos H. Papadimitriou, The complexity of computing a Nash equilibrium, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132527]
• 9: Juliane Dunkel and Andreas S. Schulz. On the complexity of pure-strategy Nash equilibria in congestion and local-effect games. In Proceedings of 2nd International Workshop on Internet and Network Economics (WINE), pages 62--73, 2006.
• 10: 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]
• 11: Alex Fabrikant , Christos H. Papadimitriou, The complexity of game dynamics: BGP oscillations, sink equilibria, and beyond, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.844-853, January 20-22, 2008, San Francisco, California
• 12: Lisa Fleischer , Michel X. Goemans , Vahab S. Mirrokni , Maxim Sviridenko, Tight approximation algorithms for maximum general assignment problems, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.611-620, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109624]
• 13: D. Gale and L. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9--15, 1962.
• 14: Michel Goemans , Li Erran Li , Vahab S. Mirrokni , Marina Thottan, Market sharing games applied to content distribution in ad-hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989467]
• 15: Michel Goemans , Vahab Mirrokni , Adrian Vetta, Sink Equilibria and Convergence, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.142-154, October 23-25, 2005 [doi>10.1109/SFCS.2005.68]
• 16: Albert Xin Jiang and Kevin Leyton-Brown. Computing pure nash equilibria in symmetric Action-Graph Games. In Association for the Advancement of Artificial Intelligence (AAAI), pages 79--85, 2007.
• 17: F. Kojima and Ü. Unver. Random paths to pairwise stability in many-to-many matching problems: a study on market equilibration. International Journal of Game Theory, 2006.
• 18: I. Milchtaich. Congestion games with player-specific payoff functions. Games and Economics Behavior, 13:111--124, 1996.
• 19: R.W. Rosenthal. A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65--67, 1973.
• 20: A.E. Roth and J.H. Vande Vate. Random paths to stability in two-sided matching. Econometrica, 58(6):1475--1480, 1990.
• 21: Alexander Skopalik , Berthold Vöcking, Inapproximability of pure nash equilibria, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374428]
• 22: 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

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

General Terms:
Algorithms, Economics, Theory

Keywords:
nash equilibria, potential games, sink equilibria