Computing Nash equilibria: The plot thickens

Speaker  Christos Papadimitriou

Affiliation  UC Berkeley

Host  Yuval Peres

Duration  01:00:30

Date recorded  10 March 2010

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.

©2010 Microsoft Corporation. All rights reserved.
> Computing Nash equilibria: The plot thickens