Nash Equilibria and Complexity

September 15, 2003
2:50 pm - 4:00 pm
Halligan 111
Speaker: Dr. Christos H. Papadimitriou, University of California at Berkeley
Host: Roni Khardon

Abstract

Using the Nash equilibrium problem as a departure point, we explore the intricate and largely mysterious interplay between existence proofs in combinatorics and computational complexity. We present polynomial-time algorithms and complexity results for the special case of congestion games. (joint work with Alex Fabrikant).