Computer Science – Computer Science and Game Theory
Scientific paper
2009-02-02
Computer Science
Computer Science and Game Theory
Scientific paper
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.
Mirrokni Vahab
Skopalik Alexander
No associations
LandOfFree
On the complexity of Nash dynamics and Sink Equilibria does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the complexity of Nash dynamics and Sink Equilibria, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of Nash dynamics and Sink Equilibria will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-296185