×

Agent-based modeling: population limits and large timescales. (English) Zbl 1459.93006

Summary: Modeling, simulation, and analysis of interacting agent systems is a broad field of research, with existing approaches reaching from informal descriptions of interaction dynamics to more formal, mathematical models. In this paper, we study agent-based models (ABMs) given as continuous-time stochastic processes and their pathwise approximation by ordinary and stochastic differential equations (SDEs) for medium to large populations. By means of an appropriately adapted transfer operator approach, we study the behavior of the ABM process on long time scales. We show that, under certain conditions, the transfer operator approach allows us to bridge the gap between the pathwise results for large populations on finite timescales, i.e., the SDE limit model, and approaches built to study dynamical behavior on long time scales like large deviation theory. The latter provides a rigorous analysis of rare events including the associated asymptotic rates on timescales that scale exponentially with the population size. We demonstrate that it is possible to reveal metastable structures and timescales of rare events of the ABM process by finite-length trajectories of the SDE process for large enough populations. This approach has the potential to drastically reduce computational effort for the analysis of ABMs.
©2021 American Institute of Physics

MSC:

93-10 Mathematical modeling or simulation for problems pertaining to systems and control theory
93A16 Multi-agent systems
60H30 Applications of stochastic analysis (to PDEs, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Kiesling, E.; Günther, M.; Stummer, C.; Wakolbinger, L. M., Agent-based simulation of innovation diffusion: A review, Cent. Eur. J. Oper. Res., 20, 183-230 (2012) · doi:10.1007/s10100-011-0210-y
[2] Eubank, S.; Guclu, H.; Kumar, V. S. A.; Marathe, M. V.; Srinivasan, A.; Toroczkai, Z.; Wang, N., Modelling disease outbreaks in realistic urban social networks, Nature, 429, 180-184 (2004) · doi:10.1038/nature02541
[3] Venkatramanan, S.; Lewis, B.; Chen, J.; Higdon, D.; Vullikanti, A.; Marathe, M. V., Using data-driven agent-based models for forecasting emerging infectious diseases, Epidemics, 22, 43-49 (2018) · doi:10.1016/j.epidem.2017.02.010
[4] The term individual-based models is predominantly used in ecology, whereas social sciences rather refer to agent-based models.
[5] Bouchaud, J.-P.; Nadal, J.-P., Foreword, C. R. Phys., 20, 241-243 (2019) · doi:10.1016/j.crhy.2019.05.001
[6] Clifford, P.; Sudbury, A., A model for spatial conflict, Biometrika, 60, 581-588 (1973) · Zbl 0272.60072 · doi:10.1093/biomet/60.3.581
[7] Holley, R. A.; Liggett, T. M., Ergodic theorems for weakly interacting infinite systems and the voter model, Ann. Probab., 3, 643-663 (1975) · Zbl 0367.60115 · doi:10.1214/aop/1176996306
[8] Jȩdrzejewski, A.; Sznajd-Weron, K., Statistical physics of opinion formation: Is it a spoof?, C. R. Phys., 20, 244-261 (2019) · doi:10.1016/j.crhy.2019.05.002
[9] Redner, S., Reality-inspired voter models: A mini-review, C. R. Phys., 20, 0 (2019) · doi:10.1016/j.crhy.2019.05.004
[10] Sîrbu, A., Loreto, V., Servedio, V. D. P., and Tria, F., “Opinion dynamics: Models, extensions and external effects,” in Participatory Sensing, Opinions and Collective Awareness (Springer, 2017), pp. 363-401.
[11] Orcutt, G. H., A new type of socio-economic system, Rev. Econ. Stat., 39, 116-123 (1957) · doi:10.2307/1928528
[12] Abar, S.; Theodoropoulos, G. K.; Lemarinier, P.; O’Hare, G. M. P., Agent based modelling and simulation tools: A review of the state-of-art software, Comput. Sci. Rev., 24, 13-33 (2017) · doi:10.1016/j.cosrev.2017.03.001
[13] Grimm, V.; Berger, U.; DeAngelis, D. L.; Polhill, J. G.; Giske, J.; Railsback, S. F., The ODD protocol: A review and first update, Ecol. Model., 221, 2760-2768 (2010) · doi:10.1016/j.ecolmodel.2010.08.019
[14] Weimer, C.; Miller, J. O.; Hill, R.; Hodson, D., Agent scheduling in opinion dynamics: A taxonomy and comparison using generalized models, J. Artif. Soc. Soc. Simul., 22, 5 (2019) · doi:10.18564/jasss.4065
[15] Weimer et al. propose the SAS (Synchrony, Actor type, Scale) classification to simplify and generalize discussions and comparisons between schedules, allowing standardization and reproduction of ABMs.
[16] Aldous, D., Interacting particle systems as stochastic social dynamics, Bernoulli, 19, 1122-1149 (2013) · Zbl 1278.60141 · doi:10.3150/12-BEJSP04
[17] Djurdjevac Conrad, N.; Helfmann, L.; Zonker, J.; Winkelmann, S.; Schütte, C., Human mobility and innovation spreading in ancient times: A stochastic agent-based simulation approach, EPJ Data Sci., 7, 24 (2018) · doi:10.1140/epjds/s13688-018-0153-9
[18] Warnke, T.; Reinhardt, O.; Klabunde, A.; Willekens, F.; Uhrmacher, A. M., Modelling and simulating decision processes of linked lives: An approach-based on concurrent processes and stochastic race, Popul. Stud., 71, sup1, 69-83 (2017) · doi:10.1080/00324728.2017.1380960
[19] Kurtz, T. G., Solutions of ordinary differential equations as limits of pure jump Markov processes, J. Appl. Probab., 7, 49-58 (1970) · Zbl 0191.47301 · doi:10.2307/3212147
[20] Ethier, S. N.; Kurtz, T. G., Markov Processes: Characterization and Convergence (2009), John Wiley & Sons
[21] Kurtz, T. G., “Limit theorems and diffusion approximations for density dependent Markov chains,” in Stochastic Systems: Modeling, Identification and Optimization, I (Springer, 1976), pp. 67-78. · Zbl 0373.60081
[22] McKane, A. J.; Newman, T. J., Stochastic models in population biology and their deterministic analogs, Phys. Rev. E, 70, 041902 (2004) · doi:10.1103/PhysRevE.70.041902
[23] Assaf, M.; Meerson, B., WKB theory of large deviations in stochastic populations, J. Phys. A: Math. Theor., 50, 263001 (2017) · Zbl 1368.92133 · doi:10.1088/1751-8121/aa669a
[24] Montefusco, A.
[25] Elgart, V.; Kamenev, A., Rare event statistics in reaction-diffusion systems, Phys. Rev. E, 70, 041106 (2004) · doi:10.1103/PhysRevE.70.041106
[26] Schütte, C. and Sarich, M., Metastability and Markov State Models in Molecular Dynamics: Modeling, Analysis, Algorithmic Approaches, Courant Lecture Notes Vol. 32 (American Mathematical Society, 2014). · Zbl 1305.60004
[27] An Introduction to Markov State Models and Their Application to Long Timescale Molecular Simulation, Advances in Experimental Medicine and Biology Vol. 797, edited by G. R. Bowman, V. S. Pande, and F. Noé (Springer, 2014). · Zbl 1290.92004
[28] Hallier, M.
[29] Gaveau, B.; Moreau, M.; Toth, J., Decay of the metastable state in a chemical system: Different predictions between discrete and continuous models, Lett. Math. Phys., 37, 285-292 (1996) · Zbl 0856.60079 · doi:10.1007/BF00343192
[30] Klus, S.; Nüske, F.; Koltai, P.; Wu, H.; Kevrekidis, I.; Schütte, C.; Noé, F., Data-driven model reduction and transfer operator approximation, J. Nonlinear Sci., 28, 985-1010 (2018) · Zbl 1396.37083 · doi:10.1007/s00332-017-9437-7
[31] Banisch, S.; Lima, R.; Araújo, T., Agent based models and opinion dynamics as Markov chains, Soc. Netw., 34, 549-561 (2012) · doi:10.1016/j.socnet.2012.06.001
[32] Gillespie, D. T., A general method for numerically simulating the stochastic time evolution of coupled chemical reactions, J. Comput. Phys., 22, 403-434 (1976) · doi:10.1016/0021-9991(76)90041-3
[33] This system description corresponds to the partition of the space of all possible configurations on which Banisch et al. then define the macrodynamics of their general opinion model; see Sec. 4.3 in Ref. 31.
[34] Herreriás-Azcué, F.; Galla, T., Consensus and diversity in multistate noisy voter models, Phys. Rev. E, 100, 022304 (2019) · doi:10.1103/PhysRevE.100.022304
[35] Biancalani, T.; Dyson, L.; McKane, A. J., Noise-induced bistable states and their mean switching time in foraging colonies, Phys. Rev. Lett., 112, 1-5 (2014) · doi:10.1103/PhysRevLett.112.038101
[36] Ohkubo, J.; Shnerb, N.; Kessler, D. A., Transition phenomena induced by internal noise and quasi-absorbing state, J. Phys. Soc. Jpn., 77, 044002 (2008) · doi:10.1143/JPSJ.77.044002
[37] Gillespie, D. T., A rigorous derivation of the chemical master equation, Physica A, 188, 404-425 (1992) · doi:10.1016/0378-4371(92)90283-V
[38] Kurtz, T. G., Strong approximation theorems for density dependent Markov chains, Stochast. Process. Appl., 6, 223-240 (1978) · Zbl 0373.60085 · doi:10.1016/0304-4149(78)90020-0
[39] Gillespie, D. T., The chemical Langevin equation, J. Chem. Phys., 113, 297-306 (2000) · doi:10.1063/1.481811
[40] McKane, A. J.; Newman, T. J., Predator-prey cycles from resonant amplification of demographic stochasticity, Phys. Rev. Lett., 94, 218102 (2005) · doi:10.1103/PhysRevLett.94.218102
[41] Thomas, P.; Straube, A. V.; Timmer, J.; Fleck, C.; Grima, R., Signatures of nonlinearity in single cell noise-induced oscillations, J. Theor. Biol., 335, 222-234 (2013) · Zbl 1397.92176 · doi:10.1016/j.jtbi.2013.06.021
[42] Grima, R.; Thomas, P.; Straube, A. V., How accurate are the nonlinear chemical Fokker-Planck and chemical Langevin equations?, J. Chem. Phys., 135, 084103 (2011) · doi:10.1063/1.3625958
[43] Zhang, W.; Hartmann, C.; Schütte, C., Effective dynamics along given reaction coordinates, and reaction rate theory, Faraday Discuss., 195, 365-394 (2016) · doi:10.1039/C6FD00147E
[44] Djurdjevac Conrad, N.; Weber, M.; Schütte, C., Finding dominant structures of nonreversible Markov processes, Multiscale Model. Simul., 14, 1319-1340 (2016) · Zbl 1352.65025 · doi:10.1137/15M1032272
[45] Djurdjevac, N.; Sarich, M.; Schütte, C., Estimating the eigenvalue error of Markov state models, SIAM J. Multiscale Model. Simul., 10, 1, 61-81 (2012) · Zbl 1253.65010 · doi:10.1137/100798910
[46] Sarich, M.; Noé, F.; Schütte, C., On the approximation quality of Markov state models, SIAM J. Multiscale Model. Simul., 8, 4, 1154-1177 (2010) · Zbl 1210.60082 · doi:10.1137/090764049
[47] Huisinga, W.; Meyn, S.; Schütte, C., Phase transitions and metastability in Markovian and molecular systems, Ann. Appl. Probab., 14, 419-458 (2004) · Zbl 1041.60026 · doi:10.1214/aoap/1075828057
[48] Schütte, C.; Noé, F.; Lu, J.; Sarich, M.; Vanden-Eijnden, E., Markov state models based on milestoning, J. Chem. Phys., 134, 204105 (2011) · doi:10.1063/1.3590108
[49] Röblitz, S.; Weber, M., Fuzzy spectral clustering by PCCA+: Application to Markov state models and data classification, Adv. Data Anal. Classif., 7, 147-179 (2013) · Zbl 1273.62145 · doi:10.1007/s11634-013-0134-6
[50] Sarich, M.; Schütte, C., Approximating selected non-dominant timescales by Markov state models, Comm. Math. Sci., 10, 1001-1013 (2012) · Zbl 1254.60082 · doi:10.4310/CMS.2012.v10.n3.a14
[51] Duncan, A.; Liao, S.; Vejchodskỳ, T.; Erban, R.; Grima, R., Noise-induced multistability in chemical systems: Discrete versus continuum modeling, Phys. Rev. E, 91, 042111 (2015) · doi:10.1103/PhysRevE.91.042111
[52] Hanggi, P.; Grabert, H.; Talkner, P.; Thomas, H., Bistable systems: Master equation versus Fokker-Planck modeling, Phys. Rev. A, 29, 371 (1984) · doi:10.1103/PhysRevA.29.371
[53] Winkelmann, S.; Schütte, C., Hybrid models for chemical reaction networks: Multiscale theory and application to gene regulatory systems, J. Chem. Phys., 147, 114115 (2017) · doi:10.1063/1.4986560
[54] Feng, J.; Kurtz, T. G., Large Deviations for Stochastic Processes (2006), AMS · Zbl 1113.60002
[55] Bouchet, F.; Gawedzki, K.; Nardini, C., Perturbative calculation of quasi-potential in non-equilibrium diffusions: A mean-field example, J. Stat. Phys., 163, 1157-1210 (2016) · Zbl 1341.82056 · doi:10.1007/s10955-016-1503-2
[56] Ellis, R. S., Large deviations for a general class of random vectors, Ann. Probab., 12, 1, 1-12 (1984) · Zbl 0534.60026 · doi:10.1214/aop/1176993370
[57] Freidlin, M. and Wentzell, A., Random Perturbations of Dynamical Systems, Grundlehren der mathematischen Wissenschaften (Springer, 1986). · Zbl 1267.60004
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.