On the complexity of nash dynamics and sink equilibria

Vahab S. Mirrokni, Alexander Skopalik

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

8 Citations (Scopus)
4 Downloads (Pure)

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.

Original languageEnglish
Title of host publicationEC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce
Pages1-10
DOIs
Publication statusPublished - 1 Dec 2009
Externally publishedYes
Event10th ACM Conference on Electronic Commerce 2009 - Stanford, United States
Duration: 6 Jul 200910 Jul 2009
Conference number: 10

Publication series

NameProceedings of the ACM Conference on Electronic Commerce

Conference

Conference10th ACM Conference on Electronic Commerce 2009
Abbreviated titleEC 2009
CountryUnited States
CityStanford
Period6/07/0910/07/09

Keywords

  • Nash equilibria
  • Potential games
  • Sink equilibria

Fingerprint Dive into the research topics of 'On the complexity of nash dynamics and sink equilibria'. Together they form a unique fingerprint.

Cite this