The complexity of homotopy methods for computing Nash equilibria
Rahul Savani ( University of Liverpool )

16:30 27th November 2012 ( week 8, Michaelmas Term 2012 )Lecture Threatre B
Homotopy methods for solving games work as follows. Given a game to be solved, construct a version where the payoffs have been changed so that there is an obvious Nash equilibrium. Then continuously adjust the payoffs towards those of the original game  the Nash equilibrium should change continuously, ending up at an equilibrium of that game. The LemkeHowson algorithm is the bestknown example of such a method. Surprisingly, the resulting equilibrium turns out to be PSPACEcomplete to compute. I will give an overview of the general proof idea, and related open problems.
Joint work with Paul W. Goldberg and Christos H. Papadimitriou