Computing Nash equilibria: The plot thickens
Myerson has argued that the Nash equilibrium lies at the foundations of modern economic thought, and yet the dark computational side of the concept keeps getting gloomier. We show that playing games under considerations of risk, disambiguating games via equilibrium selection a`-la Harsanyi-Selten, and computing equilibria by the homotopy method, are all rife with very serious complexity impediments. Joint work with Paul Goldberg and Amos Fiat.
Speaker Details
Christos H. Papadimitriou is C. Lester Hogan Professor of Computer Science at UC Berkeley. Before Berkeley he taught at Harvard, MIT, Athens Polytechnic, Stanford, and UCSD. He has written four textbooks and many articles on algorithms, 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 (Thessaloniki) and the University of Athens. 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 (a novel about computation),” was published by MIT Press in 2003.
- Date:
- Speakers:
- Christos Papadimitriou
- Affiliation:
- UC Berkeley
-
-
Jeff Running
-
