---

Discontinuity, Nonlinearity, and Complexity 3(3) (2014) 281--292 | DOI:10.5890/DNC.2014.09.005

Sven Banisch

Mathematische Physik, Universität Bielefeld, Universitätsstraße 25 D-33615 Bielefeld, Germany

Download Full Text PDF

 

Abstract

This paper describes a formalization of agent-based models (ABMs) as random walks on regular graphs and relates the symmetry group of those graphs to a coarse-graining of the ABM that is still Markovian. An ABM in which Nagents can be inδdifferent states leads to a Markov chain with δN states. In ABMs with a sequential update scheme by which one agent is chosen to update its state at a time, transitions are only allowed between system configurations that differ with respect to a single agent. This characterizes ABMs as random walks on regular graphs. The non-trivial automorphisms of those graphs make visible the dynamical symmetries that an ABM gives rise to because sets of micro configurations can be interchanged without changing the probability structure of the random walk. This allows for a systematic loss-less reduction of the state space of the model.

References

1. [1]	Galán, J.M., Izquierdo, L.R., Izquierdo, S.S., Santos, J.I., del Olmo, R., López-Paredes, A., and Edmonds, B. (2009), Errors and Artefacts in Agent-Based Modelling, Journal of Artificial Societies and Social Simulation, 12(1), 1.

2. [2]

   Grimm, V., Berger, U., Bastiansen, F., Eliassen, S., Ginot, V., Giske, J., Goss-Custard, J., Grand, T., Heinz, S.K., Huse, G., Huth, A., Jepsen, J.U., Jorgensen, C., Mooij,W.M., Muller, B., Pe'er, G., Piou, C., Railsback, S.F., Robbins, A.M., Robbins,M.M., Rossmanith, E., Ruger, N., Strand, E., Souissi, S., Stillman, R.A., Vabo, R., Visser, U., and Deangelis, D.L (2006), A standard protocol for describing individual-based and agent-based models, Ecological Modelling, 198, 115-126.

3. [3]	Hales, D., Rouchier, J., and Edmonds, B. (2003), Model-to-ModelAnalysis, Journal of Artificial Societies and Social Simulation, 6(4).

4. [4]	Laubenbacher, R.C., Jarrah, A.S., Mortveit, H.S., and Ravi, S.S. (2009), Agent Based Modeling, Mathematical Formalism for, in Encyclopedia of Complexity and Systems Science, 160-176.

5. [5]	Izquierdo, L.R., Izquierdo, S.S., Galán, J.M., and Santos, J.I. (2009), Techniques to Understand Computer Simulations: Markov Chain Analysis, Journal of Artificial Societies and Social Simulation, 12(1), 6.

6. [6]	Banisch, S., Lima, R., and Araújo, T. (2014), Agent Based Models and Opinion Dynamics as Markov Chains, Social Networks, 34, 549-561.

7. [7]

   Banisch, S., Lima, R., and Araújo, T. (2013), Aggregation and Emergence in Agent-Based Models: A Markov Chain Approach, in Gilbert, T., Kirkilionis, M., and Nicolis, G., editors, Proceedings of the European Conference on Complex Systems 2012, Springer Proceedings in Complexity, pages 3-7. Springer International Publishing.

8. [8]	Buchholz, P. (1994), Exact and Ordinary Lumpability in Finite Markov Chains, Journal of Applied Probability, 31(1), 59-75.

9. [9]	Burke, C.J., and Rosenblatt, M. (1958), A Markovian Function of a Markov Chain, The Annals of Mathematical Statistics, 29(4), 1112-1122.

10. [10]	Görnerup, O. and Jacobi, M.N. (2008), A Method for Inferring Hierarchical Dynamics in Stochastic Processes, Advances in Complex Systems, 11(1), 1-16.

11. [11]	Kemeny, J.G., and Snell, J.L. (1976), Finite Markov Chains, Springer.

12. [12]	Rogers, L.C.G., and Pitman, J.W. (1981), Markov Functions, The Annals of Probability, 9(4), 573-582.

13. [13]	Rosenblatt, M. (1959), Functions of a Markov Process that are Markovian, Journal of Mathematics and Mechanics, 8(4), 134 -145.

14. [14]	Castellano, C., Fortunato, S., and Loreto, V. (2009), Statistical physics of social dynamics, Reviews ofModern Physics, 81(2), 591-646.

15. [15]	Kimura, M. and Weiss, G.H. (1964), The stepping stone model of population structure and the decrease of genetic correlation with distance, Genetics, 49, 561-576.

16. [16]	Flajolet, P. and Odlyzko, A.M. (1990), Random Mapping Statistics, in Advances in Cryptology, 329-354, Springer Verlag.

17. [17]	Levin, D.A., Peres, Y., and Wilmer, E.L. (2009), Markov chains and mixing times, American Mathematical Society.

18. [18]	Banisch, S. and Lima, R. (2013), Markov Chain Aggregation for Simple Agent-Based Models on Symmetric Networks: The Voter Model, Submitted to Advances in Complex Systems.

19. [19]	Banisch, S. (2014), From Microscopic Heterogeneity to Macroscopic Complexity in the Contrarian Voter Model. Submitted to ACS Special Issue on Cultural and Opinion Dynamics.

20. [20]	Moran, P.A.P. (1958), Random processes in genetics, in Proceedings of the Cambridge Philosophical Society, 54, 60-71.