  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-complete 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-complete 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.
