New Results and Open Problems in Computing Nash Equilibria

COMPUTER SCIENCE/DISCRETE MATH II
Topic:New Results and Open Problems in Computing Nash Equilibria
Speaker:Christos Papadimitriou
Affiliation:University of California at Berkeley
Date:Tuesday, February 19
Time/Room:10:30am - 12:30pm/S-101

In the past few years there has been much excitement, and many positive and negative results, regarding the computation of equilibria in games. The problem of finding Nash equilibria in games was shown intractable, there is an on-going race of approximation algorithms, important special cases such as anonymous games have been solved, the complexity of equilibria in succinct games has been understood, alternative equilibrium notions have been proposed and debated, and even Nash equilibria in repeated games have been revisited. We shall review these results, and discuss some of the many open problems in this area.