The complexity of homotopy methods for computing Nash equilibria

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 Lemke-Howson algorithm is the best-known example of such a method. Surprisingly, the resulting equilibrium turns out to be PSPACE-complete 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