The Approximation Complexity of Win-Lose Games

COMPUTER SCIENCE/DISCRETE MATH II
Topic:The Approximation Complexity of Win-Lose Games
Speaker:Xi Chen
Affiliation:Tsinghua University, China and Member, School of Mathematics
Date:Tuesday, November 27
Time/Room:10:30am - 12:30pm/West Building Lecture Theatre

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.