Computer Science – Computer Science and Game Theory
Scientific paper
2010-06-28
Computer Science
Computer Science and Game Theory
23 pages, 1 figure; to appear in FOCS 2011 conference
Scientific paper
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. Extending our result for the Harsanyi-Selten process, we show that several other homotopy-based algorithms for finding equilibria of games are also PSPACE-complete to implement. A further application of our techniques yields the result that it is PSPACE-complete to compute any of the equilibria that could be found via the classical Lemke-Howson algorithm, a complexity-theoretic strengthening of the result in [Savani and von Stengel]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle.
Goldberg Paul W.
Papadimitriou Christos H.
Savani Rahul
No associations
LandOfFree
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-617030