Christos Papadimitriou (University of California, Berkeley):
Nash equilibria and complexity
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.