Definition of the Subject
Agent-based simulations are generative or computational approaches used for analyzing “complex systems.” What is a “system?” Examples of systems include a collection of molecules in a container, the population in an urban area, and the brokers in a stock market. The entities or agents in these three systems would be molecules, individuals, and stock brokers, respectively. The agents in such systems interact in the sense that molecules collide, individuals come into contact with other individuals, and brokers trade shares. Such systems, often called multiagent systems, are not necessarily complex. The label “complex” is typically attached to a system if the number of agents is large, if the agent interactions are involved, or if there is a large degree of heterogeneity in agent character or their interactions.
This is of course not an attempt to define a complex system. Currently, there is no generally agreed upon definition of complex systems. It is not the...
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
This is a preview of subscription content, log in via an institution.
Abbreviations
- Agent-based simulation:
-
An agent-based simulation of a complex system is a computer model that consists of a collection of agents/variables that can take on a typically finite collection of states. The state of an agent at a given point in time is determined through a collection of rules that describe the agent’s interaction with other agents. These rules may be deterministic or stochastic. The agent’s state depends on the agent’s previous state and the state of a collection of other agents with whom it interacts.
- Finite dynamical system:
-
A finite dynamical system is a time-discrete dynamical system on a finite state set. That is, it is a mapping from a Cartesian product of finitely many copies of a finite set to itself. This finite set is often considered to be a field. The dynamics is generated by iteration of the mapping.
- Mathematical framework:
-
A mathematical framework for agent-based simulation consists of a collection of mathematical objects that are considered mathematical abstractions of agent-based simulations. This collection of objects should be general enough to capture the key features of most simulations, yet specific enough to allow the development of a mathematical theory with meaningful results and algorithms.
Bibliography
Primary Literature
Bagrodia RL (1998) Parallel languages for discrete-event simulation models. IEEE Comput Sci Eng 5(2):27–38
Barrett CL, Reidys CM (1999) Elements of a theory of simulation I: sequential CA over random graphs. Appl Math Comput 98:241–259
Barrett CL, Mortveit HS, Reidys CM (2000) Elements of a theory of simulation II: sequential dynamical systems. Appl Math Comput 107(2–3):121–136
Barrett CL, Hunt III HB, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE, Tosic P (2001) Garden of eden and fixed point configurations in sequential dynamical systems. In: Proceedings of international conference on combinatorics, computation and geometry DM-CCG’. Paris, France, pp 95–110
Barrett CL, Mortveit HS, Reidys CM (2001b) Elements of a theory of simulation III: equivalence of SDS. Appl Math Comput 122:325–340
Barrett CL, Marathe MV, Smith JP, Ravi SS (2002) A mobility and traffic generation framework for modeling and simulating ad hoc communication networks. In: SAC’02. ACM, Madrid, pp 122–126
Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE (2003a) On some special classes of sequential dynamical systems. Ann Comb 7(4):381–408
Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE (2003b) Reachability problems for sequential dynamical systems with threshold functions. Theor Comput Sci 295(1–3):41–64
Barrett CL, Mortveit HS, Reidys CM (2003c) Elements of a theory of computer simulation. IV. Sequential dynamical systems: fixed points, invertibility and equivalence. Appl Math Comput 134(1):153–171
Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE (2006) Complexity of reachability problems for finite discrete sequential dynamical systems. J Comput Syst Sci 72:1317–1345
Barrett CL, Hunt III HB, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE, Thakur M (2007) Computational aspects of analyzing social network dynamics. In: Proceedings of international joint conference on artificial intelligence IJCAI. Paris, France, pp 2268–2273
Barrett CL, Hunt HB III, Marathe MV, Ravi SS, Rosenkrantz DJ, Stearns RE, Thakur M (2007b) Predecessor existence problems for finite discrete dynamical systems. Theor Comput Sci 1–2:3–37
Bartlett R, Garzon M (1993) Monomial cellular automata. Complex Syst 7(5):367–388
Bernaschi M, Castiglione F (2002) Selection of escape mutants from immune recognition during hiv infection. Immunol Cell Biol 80:307–313
Bernaschi M, Succi S, Castiglione F (2000) Large-scale cellular automata simulations of the immune system response. Phys Rev E 61:1851–1854
Booch G, Rumbaugh J, Jacobson I (2005) Unified modeling language user guide, 2nd edn. Addison-Wesley, Reading
Brand D, Zafiropulo P (1983) On communicating finite-state machines. J ACM 30:323–342
Cartier P, Foata D (1969) Problemes combinatoires de commutation et reárrangements, vol 85, Lecture Notes in Mathematics. Springer, Berlin
Castiglione F, Agur Z (2003) Analyzing hypersensitivity to chemotherapy in a cellular automata model of the immune system. In: Preziosi L (ed) Cancer modeling and simulation. Chapman and Hall/CRC, London
Castiglione F, Bernaschi M, Succi S (1997) Simulating the immune response on a distributed parallel computer. Int J Mod Phys C 8:527–545. doi:10.1142/S0129183197000424
Castiglione F, Duca K, Jarrah A, Laubenbacher R, Hochberg D, Thorley-Lawson D (2007) Simulating Epstein-Barr virus infection with C-ImmSim. Bioinformatics 23(11):1371–1377
Celada F, Seiden P (1992a) A computer model of cellular interactions in the immune system. Immunol Today 13(2):56–62
Celada F, Seiden P (1992b) A model for simulating cognate recognition and response in the immune system. J Theor Biol 158:235–270
Celada F, Seiden P (1996) Affinity maturation and hypermutation in a simulation of the humoral immune response. Eur J Immunol 26(6):1350–1358
Chaudhuri PP (1997) Additive cellular automata. Theory and applications, vol 1. IEEE Computer Society Press, Washington, DC
Colón-Reyes O, Laubenbacher R, Pareigis B (2004) Boolean monomial dynamical systems. Ann Comb 8:425–439
Colón-Reyes O, Jarrah A, Laubenbacher R, Sturmfels B (2006) Monomial dynamical systems over finite fields. Complex Syst 16(4):333–342
Dawson D (1974) Synchronous and asynchronous reversible Markov systems. Canad Math Bull 17(5):633–649
Ebeling W, Schweitzer F (2001) Swarms of particle agents with harmonic interactions. Theor Biosci 120–3(4):207–224
Elspas B (1959) The theory of autonomous linear sequential networks. IRE Trans Circuit Theor 1:45–60
Farmer J, Packard N, Perelson A (1986) The immune system, adaptation, and machine learning. Phys D 2(1–3):187–204
Frish U, Hasslacher B, Pomeau Y (1986) Lattice-gas automata for the Navier-Stokes equations. Phys Rev Lett 56:1505–1508
Fukś H (2004) Probabilistic cellular automata with conserved quantities. Nonlinearity 17:159–173
Garcia LD, Jarrah AS, Laubenbacher R (2006) Sequential dynamical systems over words. Appl Math Comput 174(1):500–510
Gardner M (1970) The fantastic combinations of John Conway’s new solitaire game “life”. Sci Am 223:120–123
Gouda M, Chang C (1986) Proving liveness for networks of communicating finite-state machines. ACM Trans Program Lang Syst 8:154–182
Guo Y, Gong W, Towsley D (2000) Time-stepped hybrid simulation (TSHS) for large scale networks. In: INFOCOM 2000. Proceedings of nineteenth annual joint conference of the IEEE computer and communications societies, vol 2. IEEE, Washington, DC, pp 441–450
Gupta A, Katiyar V (2005) Analyses of shock waves and jams in traffic flow. J Phys A 38:4069–4083
Hansson AÅ, Mortveit HS, Reidys CM (2005) On asynchronous cellular automata. Adv Complex Syst 8(4):521–538
Hedlund G (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3:320–375
Hernández-Toledo A (2005) Linear finite dynamical systems. Commun Algebra 33(9):2977–2989
Hopcroft JE, Motwani R, Ullman JD (2000) Automata theory, languages and computation. Addison Wesley, Reading
Hopfield J (1982) Neural networks and physical systems with emergent collective computational properties. Proc Natl Acad Sci U S A 79:2554–2588
Ilachinsky A (2001) Cellular automata: a discrete universe. World Scientific, Singapore
Jarrah A, Laubenbacher R, Stillman M, Vera-Licona P (2007) An efficient algorithm for the phase space structure of linear dynamical systems over finite fields (submitted)
Jefferson DR (1985) Virtual time. ACM Trans Program Lang Syst 7(3):404–425
Kari J (2005) Theory of cellular automata: a survey. Theory Comput Sci 334:3–33
Keyfitz BL (2004) Hold that light! Modeling of traffic flow by differential equations. Stud Math Libr 26:127–153
Kozen DC (1997) Automata and computability. Springer, New York
Laubenbacher R, Pareigis B (2003) Decomposition and simulation of sequential dynamical systems. Adv Appl Math 30:655–678
Lidl R, Niederreiter H (1997) Finite fields. Cambridge University Press, Cambridge
Liggett TM (2005) Interacting particle systems. Classics in mathematics. Springer, Berlin, Reprint of the 1985 original
Lind DA (1984) Applications of ergodic theory and sofic systems to cellular automata. Phys D 10D:36–44
Lindgren K, Moore C, Nordahl M (1998) Complexity of two-dimensional patterns. J Stat Phys 91(5–6):909–951
Mac Lane S (1998) Category theory for the working mathematician, 2nd edn. Springer, New York, No 5. in GTM
Macy MW, Kitts JA, Flache A (2003) Polarization in dynamic networks: a Hopfield model of emergent structure. In: Dynamic social network modeling and analysis. The National Academies Press, Washington, DC, pp 162–173
Martin O, Odlyzko A, Wolfram S (1984) Algebraic properties of cellular automata. Commun Math Phys 93:219–258
Milligan D, Wilson M (1993) The behavior of affine Boolean sequential networks. Connect Sci 5(2):153–167
Minar N, Burkhart R, Langton C, Manor A (1996) The swarm simulation system: a toolkit for building multi-agent simulations. Santa Fe Institute preprint series. http://www.santafe.edu/research/publications/wpabstract/199606042. Accessed 11 Aug 2008
Misra J (1986) Distributed discrete-event simulation. ACM Comput Surv 18(1):39–65
Moncion T, Hutzler G, Amar P (2006) Verification of biochemical agent-based models using petri nets. In: Robert T (ed) International symposium on agent based modeling and simulation, ABModSim’06. Austrian Society for Cybernetics Studies, pp 695–700. http://www.ibisc.univ-evry.fr/pub/basilic/OUT/Publications/2006/MHA06
Morpurgo D, Serentha R, Seiden P, Celada F (1995) Modelling thymic functions in a cellular automaton. Int Immunol 7:505–516
Mortveit HS, Reidys CM (2001) Discrete, sequential dynamical systems. Discret Math 226:281–295
Mortveit HS, Reidys CM (2004) Reduction of discrete dynamical systems over graphs. Adv Complex Syst 7(1):1–20
Nagel K, Schreckenberg M (1992) A cellular automaton model for freeway traffic. J Phys I 2:2221–2229
Nagel K, Wagner P (2006) Traffic flow: approaches to modelling and control. Wiley, Hoboken, NJ
Nagel K, Schreckenberg M, Schadschneider A, Ito N (1995) Discrete stochastic models for traffic flow. Phys Rev E 51:2939–2949
Nagel K, Rickert M, Barrett CL (1997) Large-scale traffic simulation, vol 1215, Lecture notes in computer science. Springer, Berlin, pp 380–402
Nance RE (1993) A history of discrete event simulation programming languages. ACM SIGPLAN Not 28:149–175
North MJ, Collier NT, Vos JR (2006) Experiences creating three implementations of the repast agent modeling toolkit. ACM Trans Model Comput Simul 16:1–25
Orponen P (1994) Computational complexity of neural networks: a survey. Nord J Comput 1:94–110
Orponen P (1996) The computational power of discrete hopfield networks with hidden units. Neural Comput 8:403–415
Park JK, Steiglitz K, Thruston WP (1986) Soliton-like behavior in automata. Phys D 19D:423–432
Reidys C (1998) Acyclic orientations of random graphs. Adv Appl Math 21:181–192
Reidys CM (2001) On acyclic orientations and sequential dynamical systems. Adv Appl Math 27:790–804
Reidys CM (2005) On certain morphisms of sequential dynamical systems. Discret Math 296(2–3):245–257
Reidys CM (2006) Sequential dynamical systems over words. Ann Comb 10(4):481–498
Rickert M, Nagel K, Schreckenberg M, Latour A (1996) Two lane traffic simulations using cellular automata. Phys A 231:534–550
Rothman DH (1988) Cellular-automaton fluids: a model for flow in porous media. Geophysics 53:509–518
Russell S, Norwig P (2003) Artificial intelligence: a modern approach. Prentice-Hall, Upper Saddle River
Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. BioSystems 51:123–143
Shmulevich I, Dougherty ER, Kim S, Zhang W (2002a) Probabilistic boolean networks: a rule-based uncertainty model for gene regulatory networks. Bioinformatics 18(2):261–274
Shmulevich I, Dougherty ER, Zhang W (2002b) From boolean to probabilistic boolean networks as models of genetic regulatory networks. Proc IEEE 90(11):1778–1792
Sipser M (1997) Introduction to the theory of computation. PWS Publishing Co, Boston
Vasershtein L (1969) Markov processes over denumerable products of spaces describing large system of automata. Probl Peredachi Inf 5(3):64–72
von Neumann J, Burks AW (eds) (1966) Theory of self-reproducing automata. University of Illinois Press, Champaign
Whitham G (1999) Linear and nonlinear waves, reprint edition edn. Pure and applied mathematics: a Wiley-Interscience series of texts, monographs and tracts. Wiley-Interscience, New York
Wolfram S (1983) Statistical mechanics of cellular automata. Rev Mod Phys 55:601–644
Wolfram S (1986) Theory and applications of cellular automata, vol 1, Advanced series on complex systems. World Scientific Publishing Company, Singapore
Wolfram S (2002) A new kind of science. Wolfram Media, Champaign Books and Reviews, Champaign
Wooldridge M (2002) Introduction to multiagent systems. Wiley, Chichester
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Science+Business Media New York
About this entry
Cite this entry
Laubenbacher, R., Jarrah, A.S., Mortveit, H.S., Ravi, S.S. (2013). Agent-Based Modeling, Mathematical Formalism for. In: Meyers, R. (eds) Encyclopedia of Complexity and Systems Science. Springer, New York, NY. https://doi.org/10.1007/978-3-642-27737-5_10-5
Download citation
DOI: https://doi.org/10.1007/978-3-642-27737-5_10-5
Received:
Accepted:
Published:
Publisher Name: Springer, New York, NY
Online ISBN: 978-3-642-27737-5
eBook Packages: Springer Reference Physics and AstronomyReference Module Physical and Materials ScienceReference Module Chemistry, Materials and Physics