×

zbMATH — the first resource for mathematics

Stochastic approximation to understand simple simulation models. (English) Zbl 1329.60335
Summary: This paper illustrates how a deterministic approximation of a stochastic process can be usefully applied to analyse the dynamics of many simple simulation models. To demonstrate the type of results that can be obtained using this approximation, we present two illustrative examples which are meant to serve as methodological references for researchers exploring this area. Finally, we prove some convergence results for simulations of a family of evolutionary games, namely, intra-population imitation models in \(n\)-player games with arbitrary payoffs.

MSC:
60K35 Interacting random processes; statistical mechanics type models; percolation theory
60J20 Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.)
62L20 Stochastic approximation
68U20 Simulation (MSC2010)
91A22 Evolutionary games
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Banisch, S., Lima, R., Araújo, T.: Agent based models and opinion dynamics as Markov chains. Social Networks. doi:10.1016/j.socnet.2012.06.001
[2] Barrat, A., Barthélemy, M., Vespignani, A.: Dynamical Processes on Complex Networks. Cambridge University Press, Cambridge (2008) · Zbl 1198.90005
[3] Beggs, A.W., Stochastic evolution with slow learning, J. Econ. Theory, 19, 379-405, (2002) · Zbl 0996.91017
[4] Beggs, A.W., On the convergence of reinforcement learning, J. Econ. Theory, 122, 1-36, (2005) · Zbl 1118.91025
[5] Beggs, A.W., Large deviations and equilibrium selection in large populations, J. Econ. Theory, 132, 383-410, (2007) · Zbl 1142.91315
[6] Benaïm, M.; Le Boudec, J.-Y., A class of Mean field interaction models for computer and communication systems, Perform. Eval., 65, 823-838, (2008)
[7] Benaim, M.; Weibull, J.W., Deterministic approximation of stochastic evolution in games, Econometrica, 71, 873-903, (2003) · Zbl 1152.91350
[8] Benveniste, A., Priouret, P., Metivier, M.: Adaptive Algorithms and Stochastic Approximations. Springer, New York (1990) · Zbl 0752.93073
[9] Binmore, K.G.; Samuelson, L.; Vaughan, R., Musical chairs: modeling noisy evolution, Games Econ. Behav., 11, 1-35, (1995) · Zbl 0839.90140
[10] Börgers, T.; Sarin, R., Learning through reinforcement and replicator dynamics, J. Econ. Theory, 77, 1-14, (1997) · Zbl 0892.90198
[11] Borkar, V.S.: Stochastic Approximation: A Dynamical Systems Viewpoint. Cambridge University Press, New York (2008) · Zbl 1181.62119
[12] Borrelli, R.L., Coleman, C.S.: Differential Equations: A Modeling Approach. Prentice-Hall, Englewood Cliffs (1987)
[13] Boylan, R.T., Laws of large numbers for dynamical systems with randomly matched individuals, J. Econ. Theory, 57, 473-504, (1992) · Zbl 0761.92025
[14] Boylan, R.T., Continuous approximation of dynamical systems with randomly matched individuals, J. Econ. Theory, 66, 615-625, (1995) · Zbl 0843.90019
[15] Erev, I.; Roth, A.E., Predicting how people play games: reinforcement learning in experimental games with unique, mixed strategy equilibria, Am. Econ. Rev., 88, 848-881, (1998)
[16] Ethier, S.N., Kurtz, T.G.: Markov Processes: Characterization and Convergence. Wiley Series in Probability and Statistics (2005) · Zbl 1089.60005
[17] Fudenberg, D.; Kreps, D.M., Learning mixed equilibria, Games Econ. Behav., 5, 320-367, (1993) · Zbl 0790.90092
[18] Fudenberg, D., Levine, D.K.: The Theory of Learning in Games. MIT Press, Cambridge (1998) · Zbl 0939.91004
[19] Galán, J.M.; Latek, M.M.; Rizi, S.M.M., Axelrod’s metanorm games on networks, PLoS ONE, 6, (2011)
[20] Gilbert, N., Troitzsch, K.G.: Simulation for the Social Scientist. McGraw-Hill, New York (2005)
[21] Gintis, H.: Markov models of social dynamics: theory and applications. ACM Trans. Intell. Syst. Technol. (in press). Available at http://www.umass.edu/preferen/gintis/acm-tist-markov.pdf, http://tist.acm.org/papers/TIST-2011-05-0076.R2.html · Zbl 0878.90011
[22] Gleeson, J.P.; Melnik, S.; Ward, J.A.; Porter, M.A.; Mucha, P.J., Accuracy of Mean-field theory for dynamics on real-world networks, Phys. Rev. E, 85, (2012)
[23] Hairer, E., Nørsett, S., Wanner, G.: Solving Ordinary Differential Equations I: Nonstiff Problems. Springer, Berlin (1993) · Zbl 0789.65048
[24] Hofbauer, J.; Sandholm, W.H., On the global convergence of stochastic fictitious play, Econometrica, 70, 2265-2294, (2002) · Zbl 1141.91336
[25] Hopkins, E., Two competing models of how people learn in games, Econometrica, 70, 2141-2166, (2002) · Zbl 1142.91357
[26] Huet, S.; Deffuant, G., Differential equation models derived from an individual-based model can help to understand emergent effects, J. Artif. Soc. Soc. Simul., 11, 10, (2008)
[27] Izquierdo, L.R.; Izquierdo, S.S.; Gotts, N.M.; Polhill, J.G., Transient and asymptotic dynamics of reinforcement learning in games, Games Econ. Behav., 61, 259-276, (2007) · Zbl 1275.91024
[28] Izquierdo, S.S.; Izquierdo, L.R.; Gotts, N.M., Reinforcement learning dynamics in social dilemmas, J. Artif. Soc. Soc. Simul., 11, 1, (2008)
[29] Izquierdo, L.; Izquierdo, S.; Galán, J.M.; Santos, J.I., Techniques to understand computer simulations: Markov chain analysis, J. Artif. Soc. Soc. Simul., 12, 6, (2009)
[30] Izquierdo, S.S.; Izquierdo, L.R.; Vega-Redondo, F., The option to leave: conditional dissociation in the evolution of cooperation, J. Theor. Biol., 267, 76-84, (2010) · Zbl 1410.91076
[31] Kotliar, G.; Savrasov, S.Y.; Haule, K.; Oudovenko, V.S.; Parcollet, O.; Marianetti, C.A., Electronic structure calculations with dynamical Mean-field theory, Rev. Mod. Phys., 78, 865-951, (2006)
[32] Kulkarni, V.G.: Modeling and Analysis of Stochastic Systems. Chapman & Hall/CRC, London (1995) · Zbl 0866.60004
[33] Kushner, H., Stochastic approximation: a survey, WIREs: Comput. Stat., 2, 87-96, (2010)
[34] Kushner, H.J., Yin, G.G.: Stochastic Approximation Algorithms and Applications. Springer, New York (2003) · Zbl 1026.62084
[35] Lambert, M.F.: Numerical Methods for Ordinary Differential Systems. Wiley, Chichester (1991) · Zbl 0745.65049
[36] Ljung, L., Analysis of recursive stochastic algorithms, IEEE Trans. Autom. Control, AC-22, 551-575, (1977) · Zbl 0362.93031
[37] López-Pintado, D., Diffusion in complex social networks, Games Econ. Behav., 62, 573-590, (2008) · Zbl 1137.91606
[38] Macy, M.W.; Flache, A., Learning dynamics in social dilemmas, Proc. Natl. Acad. Sci. USA, 99, 7229-7236, (2002) · Zbl 1355.91014
[39] Morozov, A.; Poggiale, J.C., From spatially explicit ecological models to Mean-field dynamics: the state of the art and perspectives, Ecol. Complex., 10, 1-11, (2012)
[40] Norman, M.F., Some convergence theorems for stochastic learning models with distance diminishing operators, J. Math. Psychol., 5, 61-101, (1968) · Zbl 0155.29303
[41] Norman, M.F.: Markov Processes and Learning Models. Academic Press, New York (1972) · Zbl 0262.92003
[42] Perc, M.; Szolnoki, A., Coevolutionary games—a mini review, Biosystems, 99, 109-125, (2010)
[43] Rozonoer, L.I., On deterministic approximation of Markov processes by ordinary differential equations, Math. Probl. Eng., 4, 99-114, (1998) · Zbl 0914.60035
[44] Sandholm, W.H.: Deterministic evolutionary dynamics. In: Durlauf, S.N., Blume, L.E. (eds.) The New Palgrave Dictionary of Economics, vol. 2. Palgrave Macmillan, New York (2008)
[45] Sandholm, W.H., Stochastic imitative game dynamics with committed agents, J. Econ. Theory, 147, 2056-2071, (2012) · Zbl 1247.91021
[46] Szabó, G.; Fáth, G., Evolutionary games on graphs, Phys. Rep., 446, 97-216, (2007)
[47] Vega-Redondo, F.: Complex Social Networks. Cambridge University Press, Cambridge (2007) · Zbl 1145.91004
[48] Vega-Redondo, F.: Economics and the Theory of Games. Cambridge University Press, Cambridge (2003)
[49] Weiss, P.: L’hypothèse du champ moléculaire et la propriété ferromagnétique. J. Phys. 6, 661-690 (1907) · JFM 38.0901.02
[50] Young, H.P.: Individual Strategy and Social Structure: An Evolutionary Theory of Institutions. Princeton University Press, Princeton (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.