Learning Nash Equilibria

Dai, Darong (2012): Learning Nash Equilibria.

Abstract

In the paper, we re-investigate the long run behavior of an adaptive learning process driven by the stochastic replicator dynamics developed by Fudenberg and Harris (1992). It is demonstrated that the Nash equilibrium will be the robust limit of the adaptive learning process as long as it is reachable for the learning dynamics in almost surely finite time. Doob’s martingale theory and Girsanov Theorem play very important roles in confirming the required assertion.

• Item Type: MPRA Paper
• Language: English
• Keywords: Stochastic replicator dynamics; Adaptive learning; Nash equilibria; Global convergence; Robustness
• Subjects: C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C72 - Noncooperative Games; C - Mathematical and Quantitative Methods > C7 - Game Theory and Bargaining Theory > C73 - Stochastic and Dynamic Games ; Evolutionary Games ; Repeated Games

References

Beggs, A., 2002. Stochastic Evolution with Slow Learning. Economic Theory 19, 379-405.

Benaïm, M. and M. W. Hirsch, 1999. Mixed Equilibria and Dynamical Systems Arising from Fictitious Play in Perturbed Games. Games and Economic Behavior 29, 36-72.

Binmore, K., L. Samuelson and R. Vaughan, 1995. Musical Chairs: Modeling Noisy Evolution. Games and Economic Behavior 11, 1-35.

Binmore, K. and L. Samuelson, 1999. Evolutionary Drift and Equilibrium Selection. Review of Economic Studies 66, 363-393.

Börgers, T. and R. Sarin, 1997. Learning Through Reinforcement and Replicator Dynamics. Journal of Economic Theory 77, 1-14.

Cabrales, A., 2000. Stochastic Replicator Dynamics. International Economic Review 41, 451-481.

Canning, D., 1992. Average Behavior in Learning Models. Journal of Economic Theory 57, 442-472.

Ellison, G. and D. Fudenberg, 2000. Learning Purified Mixed Equilibria. Journal of Economic Theory 90, 84-115.

Fudenberg, D. and D. Kreps, 1993. Learning Mixed Equilibria. Games and Economic Behavior 5, 320-367.

Fudenberg, D. and C. Harris, 1992. Evolutionary Dynamics with Aggregate Shocks. Journal of Economic Theory 57, 420-441.

Gale, J., K. Binmore and L. Samuelson, 1995. Learning to be Imperfect: The Ultimatum Game. Games and Economic Behavior 8, 56-90.

Gaunersdorfer, A. and J. Hofbauer, 1995. Fictitious Play, Shapley Polygons, and the Replicator Equation. Games and Economic Behavior 11, 279-303.

Harsanyi, J., 1973. Games with Randomly Disturbed Payoffs: A New Rationale for Mixed Strategy Equilibrium Points. International Journal of Game Theory 2, 1-23.

Higham, D. J., X. R. Mao and A. M. Stuart, 2003. Strong Convergence of Euler-Type Methods for Nonlinear Stochastic Differential Equations. SIAM Journal on Numerical Analysis 40, 1041-1063.

Hofbauer, J. and E. Hopkins, 2005. Learning in Perturbed Asymmetric Games. Games and Economic Behavior 52, 133-152.

Hofbauer, J. and L. A. Imhof, 2009. Time Averages, Recurrence and Transience in the Stochastic Replicator Dynamics. Annals of Applied Probability 19, 1347-1368.

Imhof, L. A., 2005. The Long-Run Behavior of the Stochastic Replicator Dynamics. Annals of Applied Probability 15, 1019-1045.

Imhof, L. A., 2008. Multiple-Trial Conflicts and Stochastic Evolutionary Game Dynamics. Advances in Applied Probability 40, 1174-1197.

Jordan, J., 1993. Three Problems in Learning Mixed-Strategy Nash Equilibria. Games and Economic Behavior 5, 368-386.

Kandori, M., G. Mailath and R. Rob, 1993. Learning, Mutation, and Long-run Equilibria in Games. Econometrica 61, 29-56.

Kaniovski, Y. M. and H. P. Young, 1995. Learning Dynamics in Games with Stochastic Perturbations. Games and Economic Behavior 11, 330-363.

Shapley, L. S., 1964. Some Topics in Two-Person Games. In Advances in Game Theory, ed. by M. Drescher, L. S. Shapley, and A. W Tucker. Annals of Mathematics Study 52. Princeton: Princeton University Press, 1-28.

Young, P., 1993. The Evolution of Conventions. Econometrica 61, 57-84.