Portal de Periódicos da CAPES

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

2013; Association for Computing Machinery; Volume: 1; Issue: 2 Linguagem: Inglês

10.1145/2465769.2465774

2167-8383

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

Economic theories and models

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.