ECCC-Report TR05-052https://eccc.weizmann.ac.il/report/2005/052Comments and Revisions published for TR05-052en-usThu, 05 May 2005 07:02:35 +0300
Paper TR05-052
| The Computational Complexity of Nash Equilibria in Concisely Represented Games |
Grant Schoenebeck,
Salil Vadhan
https://eccc.weizmann.ac.il/report/2005/052Games 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.
Thu, 05 May 2005 07:02:35 +0300https://eccc.weizmann.ac.il/report/2005/052