Nash Equilibria and Complexity

September 15, 2003
2:50 pm - 4:00 pm
Halligan 111


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).