EUVIMEDEUVIMED entdecken
Crossref

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

Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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

  • Google
  • 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}
}
Kostenlos starten →