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

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

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

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.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Hybrid - HSB seminar room and on zoom James Dyson Building Seminar Room - Department of Engineering. Towards a trustworthy Computing Infrastructure

Other talks

Title to be confirmed title abstract tba Climate, uncertainty, and the slippery measurement of Antarctic ice Title to be confirmed Online Causal Inference Seminar Title to be confirmed
 

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