Abstract | ||
---|---|---|
Games may be represented in many different ways, and different representations of games affect the complexity of problems associated with games, such as finding a Nash equilibrium. The traditional method of representing a game is to explicitly list all the payoffs, but this incurs an exponential blowup as the number of agents grows. We study two models of concisely represented games: circuit games, where the payoffs are computed by a given boolean circuit, and graph games, where each agent’s payoff is a function of only the strategies played by its neighbors in a given graph. For these two models, we study the complexity of four questions: determining if a given strategy is a Nash equilibrium, finding a Nash equilibrium, determining if there exists a pure Nash equilibrium, and determining if there exists a Nash equilibrium in which the payoffs to a player meet some given guarantees. In many cases, we obtain tight results, showing that the problems are complete for various complexity classes. |
Year | DOI | Venue |
---|---|---|
2012 | 10.1145/1134707.1134737 | Electronic Colloquium on Computational Complexity |
Keywords | Field | DocType |
different way,nash equilibrium,boolean circuit,graph games,circuit games,pure nash equilibrium,tight result,computational game theory,circuit game,exponential blowup,concise games,various complexity class,different representation,graph game,computational complexity,boolean circuits,complexity class,nash equilibria | Correlated equilibrium,Mathematical optimization,Mathematical economics,Epsilon-equilibrium,Risk dominance,Computer science,Best response,Equilibrium selection,Symmetric game,Nash equilibrium,Folk theorem | Journal |
Volume | Issue | ISSN |
4 | 052 | 1942-3454 |
ISBN | Citations | PageRank |
1-59593-236-4 | 29 | 2.18 |
References | Authors | |
24 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Grant Schoenebeck | 1 | 509 | 39.48 |
Salil P. Vadhan | 2 | 4676 | 234.84 |