CSAIL Event Calendar: Previous Series
|
The Complexity of Nash Equilibria Speaker:
Christos Papadimitriou , University of California at Berkeley Relevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.html In 1951 Nash proved that every game has a Nash equilibrium. The proof is non-constructive, reducing the existence of Nash equilibria to that of Brouwer fixpoints. Whether Nash equilibria can be computed efficiently had remained open. I shall outline our recent proof (with Daskalakis and Goldberg) that the problem is intractable (technical term: PPAD-complete). The proof is by a reduction from Brouwer, establishing a close computational link between two important existence theorems of the 20th century. See other events that are part of Theory Colloquium Spring 2007 |
