Computing Nash equilibria: The plot thickens

Friday, 20th August, 2010, Room 3.2.14

Roger Myerson argued in 1999 that the Nash equilibrium lies at the foundations of modern economic thought.  Seven years later, it was proven (by Daskalakis, Goldberg, and the speaker) that the concept's universality, famously established by Nash in 1950, is problematic, in that the problem of finding a Nash equilibrium is computationally intractable.  Since then many more aspects of Nash equilibria in games and markets have been explored from the complexity standpoint, and the dark computational side of the concept keeps getting gloomier.   We review several recent results establishing that playing repeated games, or playing games under considerations of risk, or disambiguating games via equilibrium selection a`-la Harsanyi-Selten, or computing equilibria by the homotopy method, are all rife with more and more serious complexity impediments. 

Short bio

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 the National Academy of Sciences of the USA, and a fellow of the ACM. His novel Turing was published by MIT Press in 2003, and his graphic novel Logicomix (with Apostolos Doxiadis) by Bloomsbury in 2008.