Advanced Search
Article Contents
Article Contents

Replicator dynamics: Old and new

Part of this work was presented at "Journées Franco-Chiliennes d'Optimisation", Toulouse, July 2017, and dedicated to the memory of Felipe Alvarez. This research was partially supported by a PGMO grant COGLED. The author thanks Josef Hofbauer for many constructive comments and a referee for an extremely precise and helpful report

Abstract Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by
  • We introduce the unilateral version associated to the replicator dynamics and describe its connection to on-line learning procedures, in particular to the multiplicative weight algorithm. We show the interest of handling simultaneously discrete and continuous time analysis.

    We then survey recent results on extensions of this dynamics as maximization of the cumulative outcome with alternative regularization functions and variable weights. This includes no regret algorithms, time average version and link to best reply dynamics in two person games, application to equilibria and variational inequalities, convergence properties in potential and dissipative games.

    Mathematics Subject Classification: Primary:91A22.


    \begin{equation} \\ \end{equation}
  • 加载中
  • 0 1 -1
    -1 0 1
    1 -1 0
     | Show Table
    DownLoad: CSV
    0 0
    0 0
    0 0
     | Show Table
    DownLoad: CSV
  • [1] E. Akin, The Geometry of Population Genetics, Springer, 1979.
    [2] E. Akin and J. Hofbauer, Recurrence of the unfit, Mathematical Biosciences, 61 (1982), 51-62.  doi: 10.1016/0025-5564(82)90095-5.
    [3] F. AlvarezJ. Bolte and O. Brahic, Hessian Riemannian gradient flows in convex programming, SIAM Journal on Control and Optimization, 43 (2004), 477-501.  doi: 10.1137/S0363012902419977.
    [4] S. AroraE. Hazan and S. Kale, The multiplicative weights update method: A meta algorithm and applications, Theory of Computing, 8 (2012), 121-164.  doi: 10.4086/toc.2012.v008a006.
    [5] P. Auer, N. Cesa–Bianchi, Y. Freund and R. E. Shapire, The nonstochastic multiarmed bandit problem, SIAM J. Comput., 32 (2002), 48–77. doi: 10.1137/S0097539701398375.
    [6] R. J. Aumann, Subjectivity and correlation in randomized strategies, Journal of Mathematical Economics, 1 (1974), 67-96.  doi: 10.1016/0304–4068(74)90037–8.
    [7] M. Benaim, Dynamics of stochastic approximation algorithms, Séminaire de Probabilités, XXXIII, 1709 (1999), 1–68. doi: 10.1007/BFb0096509.
    [8] M. Benaim and M. Faure, Consistency of vanishingly smooth fictitious play, Mathematics of Operations Research, 38 (2013), 437–450. doi: 10.1287/moor.1120.0568.
    [9] M. Benaim, J. Hofbauer and S. Sorin, Stochastic approximations and differential inclusions, SIAM J. Opt. and Control, 44 (2005), 328–348. doi: 10.1137/S0363012904439301.
    [10] M. Benaim, J. Hofbauer and S. Sorin, Stochastic approximations and differential inclusions. Part Ⅱ: Applications, Mathematics of Operations Research, 31 (2006), 673–695. doi: 10.1287/moor.1060.0213.
    [11] M. Benaim, J. Hofbauer and S. Sorin, Perturbations of set–valued dynamical systems, with applications to game theory, Dynamic Games and Applications, 2 (2012), 195–205. doi: 10.1007/s13235–012–0040–0.
    [12] D. Blackwell, An analog of the minimax theorem for vector payoffs, Pacific Journal of Mathematics, 6 (1956), 1–8. doi: 10.2140/pjm.1956.6.1.
    [13] A. Blum and Y. Mansour, From external to internal regret, Journal of Machine Learning Reserach, 8 (2007), 1307–1324. doi: 10.1007/11503415_42.
    [14] I. M. Bomze, Dynamic aspects of evolutionary stability, Monatshefte Math., 110 (1990), 189–206. doi: 10.1007/BF01301675.
    [15] G. W. Brown, Some notes on computation of games solutions, Report P–78, The Rand Corporation, 1949.
    [16] G. W. Brown, Iterative solution of games by fictitious play, in Koopmans T.C. (ed.), Activity Analysis of Production and Allocation, Wiley, (1951), 374–376.
    [17] S. Bubeck, Convex optimization: Algorithms and complexity, Fondations and Trends in Machine Learning, 8 (2015), 231-357. 
    [18] N. Cesa–Bianchi and G. Lugosi, Potential–based algorithms in on–line prediction and game theory, Computational Learning Theory (Amsterdam, 2001), 48–64, Lecture Notes in Comput. Sci., 2111, Lecture Notes in Artificial Intelligence, Springer, Berlin, 2001. doi: 10.1007/3–540–44581–1_4.
    [19] N. Cesa–Bianchi and  G. LugosiPrediction, Learning and Games, Cambridge University Press, 2006.  doi: 10.1017/CBO9780511546921.
    [20] M.–W. Cheung, Imitative dynamics for games with continuous strategy space, Games and Economic Behavior, 99 (2016), 206-223.  doi: 10.1016/j.geb.2016.08.003.
    [21] P. CoucheneyB. Gaujal and P. Mertikopoulos, Penalty–regulated dynamics and robust learning procedures in games, Mathematics of Operations Research, 40 (2015), 611-633.  doi: 10.1287/moor.2014.0687.
    [22] T. Cover, Universal portfolios, Math. Finance, 1 (1991), 1-29.  doi: 10.1111/j.1467–9965.1991.tb00002.x.
    [23] S. C. Dafermos, Traffic equilibrium and variational inequalities, Transportation Sci., 14 (1980), 42-54.  doi: 10.1287/trsc.14.1.42.
    [24] P. Dupuis and A. Nagurney, Dynamical systems and variational inequalities, Ann. Oper. Res., 44 (1993), 9-42.  doi: 10.1007/BF02073589.
    [25] M. FaureP. GaillardB. Gaujal and V. Perchet, Online learning and game theory. A quick overview with recent results and applications, ESAIM: Proceedings and Surveys, 51 (2015), 246-271.  doi: 10.1051/proc/201551014.
    [26] D. Foster and R. Vohra, A randomization rule for selecting forecasts, Operations Research, 41 (1993), 704-707. 
    [27] D. Foster and R. Vohra, Regret in the on–line decision problem, Games and Economic Behavior, 29 (1999), 7–35. doi: 10.1006/game.1999.0740.
    [28] Y. Freund and R. E. Schapire, Adaptive game playing using multiplicative weights, Games and Economic Behavior, 29 (1999), 79–103. doi: 10.1006/game.1999.0738.
    [29] D. Fudenberg and D. K. Levine, Consistency and cautious fictitious play, Journal of Economic Dynamics and Control, 19 (1995), 1065–1089. doi: 10.1016/0165–1889(94)00819–4.
    [30] D. Fudenberg and  D. K. LevineThe Theory of Learning in Games, MIT Press, 1998. 
    [31] D. Fudenberg and D. K. Levine, Conditional universal consistency, Games and Economic Behavior, 29 (1999), 104–130. doi: 10.1006/game.1998.0705.
    [32] A. Gaunersdorfer and J. Hofbauer, Fictitious play, Shapley polygons and the replicator equation, Games and Economic Behavior, 11 (1995), 279-303.  doi: 10.1006/game.1995.1052.
    [33] I. Gilboa and A. Matsui, Social stability and equilibrium, Econometrica, 59 (1991), 859–867. doi: 10.2307/2938230.
    [34] J. Hannan, Approximation to Bayes risk in repeated plays, Contributions to the Theory of Games, III, Drescher M., A.W. Tucker and P. Wolfe eds., Princeton University Press, (1957), 97–139.
    [35] C. Harris, On the rate of convergence of continuous time fictitious play, Games and Economic Behavior, 22 (1998), 238–259. doi: 10.1006/game.1997.0582.
    [36] S. Hart, Adaptive heuristics, Econometrica, 73 (2005), 1401–1430. doi: 10.1111/j.1468–0262.2005.00625.x.
    [37] S. Hart and A. Mas–Colell, A simple adaptive procedure leading to correlated equilibria, Econometrica, 68 (2000), 1127–1150. doi: 10.1111/1468–0262.00153.
    [38] S. Hart and A. Mas–Colell, A general class of adaptive strategies, Journal of Economic Theory, 98 (2001), 26–54. doi: 10.1006/jeth.2000.2746.
    [39] S. Hart and A. Mas–Colell, Regret–based continuous time dynamics, Games and Economic Behavior, 45 (2003), 375–394. doi: 10.1016/S0899–8256(03)00178–7.
    [40] S. Hart and A. Mas–Colell, Uncoupled dynamics do not lead to Nash equilibria, American Economic Review, 93 (2003), 1830–1836.
    [41] S. Hart and A. Mas Colell, Simple Adaptive Strategies: From Regret–Matching to Uncoupled Dynamics, World Scientific Publishing, 2013. doi: 10.1142/8408.
    [42] E. Hazan, The convex optimization approach to regret minimization, Optimization for machine learning, S. Sra, S. Nowozin, S. Wright eds, MIT Press, (2011), 287–303.
    [43] E. Hazan, Optimization for Machine Learning, https://arxiv.org/pdf/1909.03550.pdf, 2019.
    [44] J. Hofbauer, From Nash and Brown to Maynard Smith: Equilibria, dynamics and ESS, Selection, 1(2000), 81–88.
    [45] J. Hofbauer, Deterministic evolutionary game dynamics, in Evolutionary Game Dynamics, K. Sigmund ed., Proceedings of Symposia in Applied Mathematics, A.M.S., 69 (2011), 61–79. doi: 10.1090/psapm/069/2882634.
    [46] J. Hofbauer and W. H. Sandholm, On the global convergence of stochastic fictitious play, Econometrica, 70 (2002), 2265–2294.
    [47] J. Hofbauer and W. H. Sandholm, Stable games and their dynamics, Journal of Economic Theory, 144 (2009), 1665–1693, 1693.e4. doi: 10.1016/j.jet.2009.01.007.
    [48] J. Hofbauer and K. Sigmund, Evolutionary Games and Population Dynamics, Cambridge U.P., 1998. doi: 10.1017/CBO9781139173179.
    [49] J. Hofbauer and K. Sigmund, Evolutionary game dynamics, Bulletin of the A.M.S., 40 (2003), 479–519. doi: 10.1090/S0273–0979–03–00988–1.
    [50] J. Hofbauer and S. Sorin, Best response dynamics for continuous zero–sum games, Discrete and Continuous Dynamical Systems–series B, 6 (2006), 215–224. doi: 10.3934/dcdsb.2006.6.215.
    [51] J. Hofbauer, S. Sorin and Y. Viossat, Time average replicator and best reply dynamics, Mathematics of Operations Research, 34 (2009), 263–269. doi: 10.1287/moor.1080.0359.
    [52] A. Kalai and S. Vempala, Efficient algorithms for online decision problems, Journal of Computer and System Sciences, 71 (2005), 291-307.  doi: 10.1016/j.jcss.2004.10.016.
    [53] J. Kwon and P. Mertikopoulos, A continuous time approach to on–line optimization, Journal of Dynamics and Games, 4 (2017), 125-148.  doi: 10.3934/jdg.2017008.
    [54] N. Littlestone and M. K. Warmuth, The weighted majority algorithm, Information and Computation, 108 (1994), 212–261. doi: 10.1006/inco.1994.1009.
    [55] J. Maynard Smith, Evolution and the Theory of Games, Cambridge U.P., 1982.
    [56] P. Mertikopoulos and W. H. Sandholm, Learning in games via reinforcement and regularization, Mathematics of Operations Research, 41 (2016), 1297-1324.  doi: 10.1287/moor.2016.0778.
    [57] P. Mertikopoulos and W. H. Sandholm, Riemannian game dynamics, Journal of Economic Theory, 177 (2018), 315-364.  doi: 10.1016/j.jet.2018.06.002.
    [58] P. Mertikopoulos and Z. Zhou, Learning in games with continuous action sets and unknown payoff functions, Mathematical Programming, 173 (2019), 465-507.  doi: 10.1007/s10107–018–1254–8.
    [59] D. Monderer and L. S. Shapley, Potential games, Games Econom. Behav., 14 (1996), 124-143.  doi: 10.1006/game.1996.0044.
    [60] Y. Nesterov, Primal–dual subgradient methods for convex problems, Mathematical Programming, 120 (2009), 221-259.  doi: 10.1007/s10107–007–0149–x.
    [61] V. Perchet, Approachability, regret and calibration: Implications and equivalences, Journal of Dynamics and Games, 1 (2014), 181-254.  doi: 10.3934/jdg.2014.1.181.
    [62] V. Perchet, Exponential weight approachability, applications to calibration and regret minimization, Dynamic Games and Applications, 5 (2015), 136-153.  doi: 10.1007/s13235–014–0119–x.
    [63] J. Robinson, An iterative method of solving a game, Annals of Mathematics, 54 (1951), 296–301. doi: 10.2307/1969530.
    [64] R. T. RockafellarConvex Analysis, Princeton University Press, 1970. 
    [65] R. T. Rockafellar, Monotone operators associated with saddle–functions and minmax problems, Nonlinear Functional Analysis, F. Browder, ed., Proceedings of Symposia in Pure Math, AMS, 18 (1970), 241–250.
    [66] A. Rustichini, Optimal properties of stimulus–response learning models, Games and Economic Behavior, 29 (1999), 244-273.  doi: 10.1006/game.1999.0712.
    [67] W. H. Sandholm, Potential games with continuous player sets, Journal of Economic Theory, 97 (2001), 81-108.  doi: 10.1006/jeth.2000.2696.
    [68] W. H. Sandholm, Large population potential games, Journal of Economic Theory, 144 (2009), 1710-1725.  doi: 10.1016/j.jet.2009.02.004.
    [69] W. H. SandholmPopulation Games and Evolutionary Dynamics, MIT Press, 2010. 
    [70] W. H. SandholmPopulation Games and Deterministic Evolutionary Dynamics,, Economic Learning and Social Evolution. MIT Press, Cambridge, MA, 2010. 
    [71] S. Shahshahani, A new mathematical framework for the study of linkage and selection, Memoirs of the American Mathematical Society, 17 (1979), ix+34 pp. doi: 10.1090/memo/0211.
    [72] S. Shalev–Shwartz, Online Learning and Online Convex Optimization, Foundations and Trends in Machine Learning, 4 (2012), 107-194. 
    [73] M. J. Smith, The existence, uniqueness and stability of traffic equilibria, Transportation Res., Part B, 13 (1979), 295-304.  doi: 10.1016/0191–2615(79)90022–5.
    [74] M. J. Smith, The stability of a dynamic model of traffic assignment – an application of a method of Lyapunov, Transportation Sci., 18 (1984), 245-252.  doi: 10.1287/trsc.18.3.245.
    [75] S. Sorin, Exponential weight algorithm in continuous time, Mathematical Programming, Ser. B, 116 (2009), 513–528. doi: 10.1007/s10107–007–0111–y.
    [76] S. Sorin, On some global and unilateral adaptive dynamics, Evolutionary Game Dynamics, K. Sigmund (ed.), Proceedings of Symposia in Applied Mathematics, 69 (2011), 81–109. doi: 10.1090/psapm/069/2882635.
    [77] S. Sorin and C. Wang, Finite composite games: Equilibria and dynamics, Journal of Dynamics and Games, 3 (2016), 101-120.  doi: 10.3934/jdg.2016005.
    [78] G. Stoltz and G. Lugosi, Internal regret in on–line portfolio selection, Machine Learning, 59 (2005), 125-159. 
    [79] J. M. Swinkels, Adjustment dynamics and rational play in games, Games and Economic Behavior, 5 (1983), 455-484.  doi: 10.1006/game.1993.1025.
    [80] P. Taylor and L. Jonker, Evolutionary stable strategies and game dynamics, Mathematical Biosciences, 40 (1978), 145–156. doi: 10.1016/0025–5564(78)90077–9.
    [81] Y. Viossat, The replicator dynamics does not lead to correlated equilibria, Games and Economic Behavior, 59 (2007), 397–407. doi: 10.1016/j.geb.2006.09.001.
    [82] Y. Viossat, Evolutionary dynamics may eliminate all strategies used in correlated equilibrium, Mathematical Social Sciences, 56 (2008), 27–43. doi: 10.1016/j.mathsocsci.2007.12.001.
    [83] Y. Viossat and A. Zapechelnyuk, No–regret dynamics and fictitious play, Journal of Economic Theory, 148 (2013), 825-842.  doi: 10.1016/j.jet.2012.07.003.
    [84] V. Vovk, Aggregating strategies, Proceedings of the 3rd Annual Conference on Computational Learning Theory, (1990), 371–383.
    [85] G. Wardrop, Some theoretical aspects of road traffic research, Proc. Inst. Civ. Eng., 1 (1952), 325–362.
  • 加载中



Article Metrics

HTML views(733) PDF downloads(762) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint