University of Cambridge > Talks.cam > Microsoft Research Cambridge, public talks > The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions

The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Microsoft Research Cambridge Talks Admins.

We show that the widely used homotopy method for solving fixpoint problems, as well as the Harsanyi-Selten equilibrium selection process for games, are PSPACE -complete to implement. A key application of our techniques yields the result that it is also PSPACE -complete to compute any of the equilibria that could be found via the classical Lemke-Howson algorithm.

Joint work with Paul W. Goldberg and Christos H. Papadimitriou.

This talk is part of the Microsoft Research Cambridge, public talks series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2019 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity