## 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 language | English |
---|---|

Title of host publication | EC'09 - Proceedings of the 2009 ACM Conference on Electronic Commerce |

Pages | 1-10 |

DOIs | |

Publication status | Published - 1 Dec 2009 |

Externally published | Yes |

Event | 10th ACM Conference on Electronic Commerce 2009 - Stanford, United States Duration: 6 Jul 2009 → 10 Jul 2009 Conference number: 10 |

### Conference

Conference | 10th ACM Conference on Electronic Commerce 2009 |
---|---|

Abbreviated title | EC 2009 |

Country/Territory | United States |

City | Stanford |

Period | 6/07/09 → 10/07/09 |

## Keywords

- Nash equilibria
- Potential games
- Sink equilibria