Title :
The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions
Author :
Goldberg, Paul W. ; Papadimitriou, Christos H. ; Savani, Rahul
Author_Institution :
Dept. of Comput. Sci., Univ. of Liverpool, Liverpool, UK
Abstract :
We show that the widely used homotopy method for solving fix point 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-How son algorithm, a complexity-theoretic strengthening of the result in [24]. These results show that our techniques can be widely applied and suggest that the PSPACE-completeness of implementing homotopy methods is a general principle.
Keywords :
computational complexity; game theory; Harsanyi-Selten process; Lemke-Howson solutions; PSPACE-complete; equilibrium selection; fix point problems; game theory; homotopy method complexity; Color; Complexity theory; Games; Logic gates; Nash equilibrium; Polynomials; Search problems; computational complexity; game theory;
Conference_Titel :
Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on
Conference_Location :
Palm Springs, CA
Print_ISBN :
978-1-4577-1843-4
DOI :
10.1109/FOCS.2011.26