Abstract
The PPAD-completeness of Nash equilibrium computation is taken as evidence that the problem is computationally hard in the worst case. This evidence is necessarily rather weak, in the sense that PPAD is only know to lie “between P and NP”, and there is not a strong prospect of showing it to be as hard as NP. Of course, the problem of finding an equilibrium that has certain sought-after properties should be at least as hard as finding an unrestricted one, thus we have for example the NP-hardness of finding equilibria that are socially optimal (or indeed that have various efficiently checkable properties), the results of Gilboa and Zemel [6], and Conitzer and Sandholm [3]. In the talk I will give an overview of this topic, and a summary of recent progress showing that the equilibria that are found by the Lemke-Howson algorithm, as well as related homotopy methods, are PSPACE-complete to compute. Thus we show that there are no short cuts to the Lemke-Howson solutions, subject only to the hardness of PSPACE. I mention some open problems.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Brandt, F., Fischer, F., Harrenstein, P.: On the Rate of Convergence of Fictitious Play. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P. (eds.) SAGT 2010. LNCS, vol. 6386, pp. 103–114. Springer, Heidelberg (2010)
Conitzer, V.: Approximation Guarantees for Fictitious Play. In: Proceedings of the 47th Annual Allerton Conference on Communication, Control and Computing (Allerton 2009), pp. 636–643 (2009)
Conitzer, V., Sandholm, T.: Complexity results about Nash equilibria. In: 18th International Joint Conference on Artificial Intelligence, IJCAI (2003)
Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The Complexity of Computing a Nash Equilibrium. SIAM Journal on Computing 39(1), 195–259 (2009)
Fudenberg, D., Levine, D.K.: The Theory of Learning in Games. MIT Press, Cambridge (1998)
Gilboa, I., Zemel, E.: Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior 1, 80–93 (1989)
Goldberg, P.W., Papadimitriou, C.H., Savani, R.: The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions, Arxiv technical report 1006.5352 (2010)
Herings, P.J.-J., Peeters, R.: Homotopy methods to compute equilibria in game theory. Economic Theory 42(1), 119–156 (2010)
Savani, R., von Stengel, B.: Hard-to-Solve Bimatrix Games. Econometrica 74(2), 397–429 (2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldberg, P.W. (2010). How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard?. In: Kontogiannis, S., Koutsoupias, E., Spirakis, P.G. (eds) Algorithmic Game Theory. SAGT 2010. Lecture Notes in Computer Science, vol 6386. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-16170-4_2
Download citation
DOI: https://doi.org/10.1007/978-3-642-16170-4_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-16169-8
Online ISBN: 978-3-642-16170-4
eBook Packages: Computer ScienceComputer Science (R0)