Abstract
Can learning algorithms find a Nash equilibrium? This is a natural question for several reasons. Learning algorithms resemble the behavior of players in many naturally arising games, and thus results on the convergence or non-convergence properties of such dynamics may inform our understanding of the applicability of Nash equilibria as a plausible solution concept in some settings. A second reason for asking this question is in the hope of being able to prove an impossibility result, not dependent on complexity assumptions, for computing Nash equilibria via a restricted class of reasonable algorithms. In this work, we begin to answer this question by considering the dynamics of the standard multiplicative weights update learning algorithms (which are known to converge to a Nash equilibrium for zero-sum games). We revisit a 3×3 game defined by Shapley [10] in the 1950s in order to establish that fictitious play does not converge in general games. For this simple game, we show via a potential function argument that in a variety of settings the multiplicative updates algorithm impressively fails to find the unique Nash equilibrium, in that the cumulative distributions of players produced by learning dynamics actually drift away from the equilibrium.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Blum, A., Hajiaghayi, M., Ligett, K., Roth, A.: Regret minimization and price of total anarchy. In: STOC 2008 (2008)
Friedman, E., Shenker, S.: Learning and implementation on the Internet. Working paper (1997)
Freund, Y., Schapire, R.E.: Adaptive game playing using multiplicative weights. Games and Economic Behavior 29, 79–103 (1999)
Hart, S., Mansour, Y.: The communication complexity of uncoupled Nash equilibrium procedures. In: STOC 2007 (2007)
Hart, S., Mas-Colell, A.: A simple adaptive procedure leading to correlated equilibrium. Econometrica 68(5), 1127–1150 (2000)
Karlin, S.: Mathematical Methods and Theory in Games, Programming and Economics. Dover, New York (1994)
Kleinberg, R., Piliouras, G., Tardos, É.: Multiplicative updates outperform generic no-regret learning in congestion games. In: STOC 2009 (2009)
Robinson, J.: An iterative method of solving a game. In: Annals of Mathematics (1951)
Roughgarden, T.: Intrinsic robustness of the price of anarchy. In: STOC 2009 (2009)
Shapley, L.S.: Some topics in two-person games. In: Dresher, M., Aumann, R.J., Shapley, L.S., Tucker, A.W. (eds.) Advances in Ame Theory (1964)
Auer, P., Cesa-Bianchi, N., Freund, Y., Schapire, R.E.: The Nonstochastic Multiarmed Bandit Problem. SIAM J. Comput. 32(48), 77 (2002)
Arora, S., Hazan, E., Kale, S.: The Multiplicative Weights Update Method: a Meta Algorithm and Applications (2005) (Manuscript)
Abernethy, J., Rakhlin, A.: Beating the adaptive bandit with high probability. In: COLT 2009 (2009)
Zinkevich, M.: Theoretical guarantees for algorithms in multi-agent settings. Tech. Rep. CMU-CS-04- 161, Carnegie Mellon University (2004)
Benaim, M., Hirsch, M.W.: Mixed Equilibria and Dynamical Systems Arising from Fictitious Play in Perturbed Games. Games and Economic Behavior 29, 36–72 (1999)
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
Daskalakis, C., Frongillo, R., Papadimitriou, C.H., Pierrakos, G., Valiant, G. (2010). On Learning Algorithms for Nash Equilibria. 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_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-16170-4_11
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)