The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
ACM Transactions on Economics and Computation · 2013
DOI: 10.1145/2465769.2465774 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Economics and Computation, 2013. Verfasst von Paul W. Goldberg und 2 weiteren Autor:innen. Die Arbeit wurde bisher 17-mal zitiert (Crossref) und nennt 22 Literaturangaben. Gefördert von: Google, National Science Foundation, Engineering and Physical Sciences Research Council.
Abstract (Originalsprache)
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 [2006]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle.
Förderung
- National Science Foundation
- Engineering and Physical Sciences Research Council
Zitieren
APA
Goldberg, P. W., Papadimitriou, C. H., & Savani, R. (2013). The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Transactions on Economics and Computation. https://doi.org/10.1145/2465769.2465774
Vancouver
Goldberg PW, Papadimitriou CH, Savani R. The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. ACM Transactions on Economics and Computation. 2013. doi:10.1145/2465769.2465774
BibTeX
@article{Goldberg2013,
author = {Goldberg, Paul W. and Papadimitriou, Christos H. and Savani, Rahul},
title = {The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions},
journal = {ACM Transactions on Economics and Computation},
year = {2013},
doi = {10.1145/2465769.2465774}
}
EUVIMED