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.