30/5- HURWITZ LECTURE(2): The Computation of Equilibria

Speaker: Prof. Christos Papadimitriou

Date: Friday, May 30, 2008
Time: 14.15
Room: ETF

In 1950, John Nash proved that every game has an equilibrium, by
reducing the existence problem to that of a Brouwer fixpoint; yet
efficient algorithms for finding Nash equilibria had been elusive ever
since. It was recently proved by Daskalakis, Goldberg, and the author
that the Nash equilibrium problem is computationally equivalent to
Brouwer's fixpoint, and thus intractable. This talk is about this
result, its context, and the alternative concepts of equilibrium being
investigated in its wake.

Biographical Sketch:
Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before joining Berkeley in 1996 he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written five textbooks and many research articles on algorithms and complexity, and their applications to optimization, databases, AI, economics, and the Internet. He holds a PhD from Princeton, and honorary doctorates from ETH (Zurich), the University of Macedonia, the University of Athens, and the University of Cyprus. He is a member of the American Academy of Arts and Sciences and of the National Academy of Engineering, and a fellow of the ACM. His novel Turing was published by MIT Press in 2003, and his graphic novel Logicomix (with Apostolos Doxiadis) will be published by Bloomsbury in 2008.