Computer Science/Discrete Mathematics Seminar II

The computation of Nash equilibria has been a problem that spanned half a century that has attracted Economists, Operations Researchers, and most Recently, Computer Scientists. Intuitively, the complexity of a game grows along a few axes: the number of players involved, the number of choices available to each player, the complexity of the payoffs that specify the game, and the accuracy we desire for the computed equilibrium. In this talk, we will show, however, that being able to compute Nash equilibria is an all-or-nothing problem. That is, if we can even roughly approximate the Nash equilibria of the simplest imaginable games — the two-player games where the outcome for either player is either a "win" (1) or a "loss" (0) — then we can compute the Nash equilibria of arbitrary games to as much precision (exponentially small) as we desire. Our result is based on a stability analysis of a clever construction by Abbott, Kane, and Valiant. We also prove the following structural result about Nash equilibria: the set of approximate equilibria of a zero-sum game is "convex". In the talk, I will also briefly review the recent development in the approximation of Nash equilibria. Joint work with Shang-Hua Teng and Paul Valiant.