Universiteit van Amsterdam

Institute for Logic, Language and Computation

7 July 2006, Computational Social Choice Seminar, Joel Uckelman

Speaker: Joel Uckelman
Title: How Hard is it to Find Nash Equilibria?
Date: Friday 7 July 2006
Time: 16:00
Location: Room P.327, Euclides Building, Plantage Muidergracht 24, Amsterdam


Prior to last year, very little was known about the computational complexity of finding Nash equilibria for strategic games. In fall of 2005, a series of results appeared (by Daskalakis, Goldberg, and Papadimitriou; and Chen and Deng) which led to the determination that NASH is PPAD-complete. I will be discussing these results, what PPAD is, and how it is related to more familiar complexity classes.

For more information, see http://www.illc.uva.nl/~ulle/seminar/ or contact Ulle Endriss ().