The computational complexity of Nash equilibria in concisely represented games


Schoenebeck, Grant, and Salil Vadhan. “The computational complexity of Nash equilibria in concisely represented games.” ACM Transactions on Computation Theory 4, no. 2 (2012).
ACM2012.pdf954 KB
EC2006.pdf280 KB
ECCC2005.pdf473 KB


Version History: Preliminary versions as ECCC TOR05-52 (; attached as ECCC2005.pdf) and in EC '06 (; attached as EC2006.pdf).

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.

Publisher's Version

Last updated on 06/03/2020