The Complexity of Nash Equilibria
| COMPUTER SCIENCE/DISCRETE MATH I | |
| Topic: | The Complexity of Nash Equilibria |
| Speaker: | Christos Papadimitriou |
| Affiliation: | University of California at Berkeley |
| Date: | Monday, April 9 |
| Time/Room: | 11:15am - 12:15pm/S-101 |
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 these two important existence theorems.