Title: On the Computation and Approximation of Two-Player Nash Equilibria
Speaker: Xi, IAS
Date: Wednesday, December 5, 2007 11:00-12:00pm
Location: DIMACS Center, CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
In 1950, Nash showed that every non-cooperative game has an equilibrium. Before his work, the result was known only for two-player zero-sum ngames. While von Neumann's minimax theorem was the mathematical foundation of the two-player zero-sum game, Brouwer's and Katutani's fixed point theorems were crucially used in Nash's proofs. His approach was later used by Arrow and Debreu in their development of the general equilibrium theory.
Fourteen years after Nash's work, Lemke and Howson designed a simplex-like path-following algorithm for finding a Nash equilibrium in a general two-player game. Despite its several appealing properties, this algorithm was recently shown to have exponential worst-case complexity. In contrast, in his groundbreaking work, Khachiyan showed that the ellipsoid algorithm can solve any linear program and hence any two-player zero-sum game in polynomial time. His success, however, has not been extended to general two-player games --- no polynomial-time algorithm has yet been found for this remarkable problem.
In this talk, I will present the recent results in characterizing the complexity of computing and approximating two-player Nash equilibria. I will also discuss the recent development in the approximation of Nash equilibria.