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

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

• Rahul Savani, University of Liverpool
• Thursday 14 April 2011, 14:00-15:00
• Small lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge.

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.

This talk is included in these lists:

• All Talks (aka the CURE list)
• Cambridge Centre for Data-Driven Discovery (C2D3)
• Cambridge talks
• Chris Davis' list
• Guy Emerson's list
• Interested Talks
• Microsoft Research Cambridge, public talks
• Optics for the Cloud
• PMRFPS's
• School of Technology
• Small lecture theatre, Microsoft Research Ltd, 7 J J Thomson Avenue (Off Madingley Road), Cambridge
• Trust & Technology Initiative - interesting events
• bld31
• ndk22's list
• ob366-ai4er
• personal list
• rp587

Note that ex-directory lists are not shown.