Harvard Theory of Computation Seminar
The Computational Complexity of Nash Equilibria in Concisely Represented Games
Grant Schoenebeck, UC Berkeley
Place and Time: Monday 6/5, Maxwell-Dworkin 319
Refreshments at 2:30, talk at 2:45.
Games may be represented in many different ways, and different
representations of games affect the complexity of problems
games, such as finding a Nash equilibrium. The traditional method
representing a game is to explicitly list all the payoffs, but this
an exponential blowup as the number of agents grows. We study two
concisely represented games: *circuit games*, where the payoffs are
by a given boolean circuit, and *graph games*, where each agent's
a function of only the strategies played by its neighbors in a
For these two models, we study the complexity of four questions:
if a given strategy is a Nash equilibrium, finding a Nash
determining if there exists a pure Nash equilibrium, and
there exists a Nash equilibrium in which the payoffs to a player
given guarantees. In many cases, we obtain tight results, showing
problems are complete for various complexity classes.
Joint work with Salil Vadhan.