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.
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.
Joint work with Salil Vadhan.