Nash Equilibria and Complexity

Christos Papadimitriou

University of California, Berkeley

February 9, 4:15pm


Using the Nash equilibrium problem as a departure point, we explore the
intricate and largely mysterious interplay between computational
complexity and existence proofs in combinatorics.  We present
polynomial-time algorithms and complexity results for congestion games.


Return to Applied Math Colloquium home page