Skip to main content
SpringerLink
Log in

Agent-Based Modeling, Mathematical Formalism for

  • Living reference work entry
  • First Online:
Encyclopedia of Complexity and Systems Science

  • 1031 Accesses

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

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

    Article  Google Scholar 

  • Barrett CL, Reidys CM (1999) Elements of a theory of simulation I: sequential CA over random graphs. Appl Math Comput 98:241–259

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • Barrett CL, Mortveit HS, Reidys CM (2001b) Elements of a theory of simulation III: equivalence of SDS. Appl Math Comput 122:325–340

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Article  MATH  MathSciNet  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  MathSciNet  Google Scholar 

  • Bartlett R, Garzon M (1993) Monomial cellular automata. Complex Syst 7(5):367–388

    MATH  MathSciNet  Google Scholar 

  • Bernaschi M, Castiglione F (2002) Selection of escape mutants from immune recognition during hiv infection. Immunol Cell Biol 80:307–313

    Article  Google Scholar 

  • Bernaschi M, Succi S, Castiglione F (2000) Large-scale cellular automata simulations of the immune system response. Phys Rev E 61:1851–1854

    Article  ADS  Google Scholar 

  • Booch G, Rumbaugh J, Jacobson I (2005) Unified modeling language user guide, 2nd edn. Addison-Wesley, Reading

    Google Scholar 

  • Brand D, Zafiropulo P (1983) On communicating finite-state machines. J ACM 30:323–342

    Article  MATH  MathSciNet  Google Scholar 

  • Cartier P, Foata D (1969) Problemes combinatoires de commutation et reárrangements, vol 85, Lecture Notes in Mathematics. Springer, Berlin

    MATH  Google Scholar 

  • 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

    Google Scholar 

  • 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

    Article  ADS  Google Scholar 

  • 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

    Article  Google Scholar 

  • Celada F, Seiden P (1992a) A computer model of cellular interactions in the immune system. Immunol Today 13(2):56–62

    Article  Google Scholar 

  • Celada F, Seiden P (1992b) A model for simulating cognate recognition and response in the immune system. J Theor Biol 158:235–270

    Google Scholar 

  • Celada F, Seiden P (1996) Affinity maturation and hypermutation in a simulation of the humoral immune response. Eur J Immunol 26(6):1350–1358

    Article  Google Scholar 

  • Chaudhuri PP (1997) Additive cellular automata. Theory and applications, vol 1. IEEE Computer Society Press, Washington, DC

    Google Scholar 

  • Colón-Reyes O, Laubenbacher R, Pareigis B (2004) Boolean monomial dynamical systems. Ann Comb 8:425–439

    Article  MATH  MathSciNet  Google Scholar 

  • Colón-Reyes O, Jarrah A, Laubenbacher R, Sturmfels B (2006) Monomial dynamical systems over finite fields. Complex Syst 16(4):333–342

    Google Scholar 

  • Dawson D (1974) Synchronous and asynchronous reversible Markov systems. Canad Math Bull 17(5):633–649

    Article  MathSciNet  Google Scholar 

  • Ebeling W, Schweitzer F (2001) Swarms of particle agents with harmonic interactions. Theor Biosci 120–3(4):207–224

    Article  Google Scholar 

  • Elspas B (1959) The theory of autonomous linear sequential networks. IRE Trans Circuit Theor 1:45–60

    Article  Google Scholar 

  • Farmer J, Packard N, Perelson A (1986) The immune system, adaptation, and machine learning. Phys D 2(1–3):187–204

    Article  MathSciNet  Google Scholar 

  • Frish U, Hasslacher B, Pomeau Y (1986) Lattice-gas automata for the Navier-Stokes equations. Phys Rev Lett 56:1505–1508

    Article  ADS  Google Scholar 

  • Fukś H (2004) Probabilistic cellular automata with conserved quantities. Nonlinearity 17:159–173

    Article  ADS  MATH  MathSciNet  Google Scholar 

  • Garcia LD, Jarrah AS, Laubenbacher R (2006) Sequential dynamical systems over words. Appl Math Comput 174(1):500–510

    Article  MATH  MathSciNet  Google Scholar 

  • Gardner M (1970) The fantastic combinations of John Conway’s new solitaire game “life”. Sci Am 223:120–123

    Article  Google Scholar 

  • Gouda M, Chang C (1986) Proving liveness for networks of communicating finite-state machines. ACM Trans Program Lang Syst 8:154–182

    Article  MATH  Google Scholar 

  • 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

    Google Scholar 

  • Gupta A, Katiyar V (2005) Analyses of shock waves and jams in traffic flow. J Phys A 38:4069–4083

    Article  ADS  MATH  MathSciNet  Google Scholar 

  • Hansson AÅ, Mortveit HS, Reidys CM (2005) On asynchronous cellular automata. Adv Complex Syst 8(4):521–538

    Article  MATH  MathSciNet  Google Scholar 

  • Hedlund G (1969) Endomorphisms and automorphisms of the shift dynamical system. Math Syst Theory 3:320–375

    Article  MATH  MathSciNet  Google Scholar 

  • Hernández-Toledo A (2005) Linear finite dynamical systems. Commun Algebra 33(9):2977–2989

    Article  MATH  Google Scholar 

  • Hopcroft JE, Motwani R, Ullman JD (2000) Automata theory, languages and computation. Addison Wesley, Reading

    Google Scholar 

  • Hopfield J (1982) Neural networks and physical systems with emergent collective computational properties. Proc Natl Acad Sci U S A 79:2554–2588

    Article  ADS  MathSciNet  Google Scholar 

  • Ilachinsky A (2001) Cellular automata: a discrete universe. World Scientific, Singapore

    Google Scholar 

  • 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)

    Google Scholar 

  • Jefferson DR (1985) Virtual time. ACM Trans Program Lang Syst 7(3):404–425

    Article  MathSciNet  Google Scholar 

  • Kari J (2005) Theory of cellular automata: a survey. Theory Comput Sci 334:3–33

    Article  MATH  MathSciNet  Google Scholar 

  • Keyfitz BL (2004) Hold that light! Modeling of traffic flow by differential equations. Stud Math Libr 26:127–153

    MathSciNet  Google Scholar 

  • Kozen DC (1997) Automata and computability. Springer, New York

    Book  MATH  Google Scholar 

  • Laubenbacher R, Pareigis B (2003) Decomposition and simulation of sequential dynamical systems. Adv Appl Math 30:655–678

    Article  MATH  MathSciNet  Google Scholar 

  • Lidl R, Niederreiter H (1997) Finite fields. Cambridge University Press, Cambridge

    Google Scholar 

  • Liggett TM (2005) Interacting particle systems. Classics in mathematics. Springer, Berlin, Reprint of the 1985 original

    Google Scholar 

  • Lind DA (1984) Applications of ergodic theory and sofic systems to cellular automata. Phys D 10D:36–44

    Article  ADS  MathSciNet  Google Scholar 

  • Lindgren K, Moore C, Nordahl M (1998) Complexity of two-dimensional patterns. J Stat Phys 91(5–6):909–951

    Article  MATH  MathSciNet  Google Scholar 

  • Mac Lane S (1998) Category theory for the working mathematician, 2nd edn. Springer, New York, No 5. in GTM

    Google Scholar 

  • 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

    Google Scholar 

  • Martin O, Odlyzko A, Wolfram S (1984) Algebraic properties of cellular automata. Commun Math Phys 93:219–258

    Article  ADS  MATH  MathSciNet  Google Scholar 

  • Milligan D, Wilson M (1993) The behavior of affine Boolean sequential networks. Connect Sci 5(2):153–167

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Mortveit HS, Reidys CM (2001) Discrete, sequential dynamical systems. Discret Math 226:281–295

    Article  MATH  MathSciNet  Google Scholar 

  • Mortveit HS, Reidys CM (2004) Reduction of discrete dynamical systems over graphs. Adv Complex Syst 7(1):1–20

    Article  MATH  MathSciNet  Google Scholar 

  • Nagel K, Schreckenberg M (1992) A cellular automaton model for freeway traffic. J Phys I 2:2221–2229

    Google Scholar 

  • Nagel K, Wagner P (2006) Traffic flow: approaches to modelling and control. Wiley, Hoboken, NJ

    Google Scholar 

  • Nagel K, Schreckenberg M, Schadschneider A, Ito N (1995) Discrete stochastic models for traffic flow. Phys Rev E 51:2939–2949

    Article  ADS  Google Scholar 

  • Nagel K, Rickert M, Barrett CL (1997) Large-scale traffic simulation, vol 1215, Lecture notes in computer science. Springer, Berlin, pp 380–402

    Book  Google Scholar 

  • Nance RE (1993) A history of discrete event simulation programming languages. ACM SIGPLAN Not 28:149–175

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Orponen P (1994) Computational complexity of neural networks: a survey. Nord J Comput 1:94–110

    MathSciNet  Google Scholar 

  • Orponen P (1996) The computational power of discrete hopfield networks with hidden units. Neural Comput 8:403–415

    Article  Google Scholar 

  • Park JK, Steiglitz K, Thruston WP (1986) Soliton-like behavior in automata. Phys D 19D:423–432

    Article  ADS  Google Scholar 

  • Reidys C (1998) Acyclic orientations of random graphs. Adv Appl Math 21:181–192

    Article  MATH  MathSciNet  Google Scholar 

  • Reidys CM (2001) On acyclic orientations and sequential dynamical systems. Adv Appl Math 27:790–804

    Article  MATH  MathSciNet  Google Scholar 

  • Reidys CM (2005) On certain morphisms of sequential dynamical systems. Discret Math 296(2–3):245–257

    Article  MATH  MathSciNet  Google Scholar 

  • Reidys CM (2006) Sequential dynamical systems over words. Ann Comb 10(4):481–498

    Article  MATH  MathSciNet  Google Scholar 

  • Rickert M, Nagel K, Schreckenberg M, Latour A (1996) Two lane traffic simulations using cellular automata. Phys A 231:534–550

    Article  Google Scholar 

  • Rothman DH (1988) Cellular-automaton fluids: a model for flow in porous media. Geophysics 53:509–518

    Article  ADS  Google Scholar 

  • Russell S, Norwig P (2003) Artificial intelligence: a modern approach. Prentice-Hall, Upper Saddle River

    Google Scholar 

  • Schönfisch B, de Roos A (1999) Synchronous and asynchronous updating in cellular automata. BioSystems 51:123–143

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • 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

    Article  Google Scholar 

  • Sipser M (1997) Introduction to the theory of computation. PWS Publishing Co, Boston

    MATH  Google Scholar 

  • Vasershtein L (1969) Markov processes over denumerable products of spaces describing large system of automata. Probl Peredachi Inf 5(3):64–72

    MathSciNet  Google Scholar 

  • von Neumann J, Burks AW (eds) (1966) Theory of self-reproducing automata. University of Illinois Press, Champaign

    Google Scholar 

  • 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

    Book  Google Scholar 

  • Wolfram S (1983) Statistical mechanics of cellular automata. Rev Mod Phys 55:601–644

    Article  ADS  MATH  MathSciNet  Google Scholar 

  • Wolfram S (1986) Theory and applications of cellular automata, vol 1, Advanced series on complex systems. World Scientific Publishing Company, Singapore

    MATH  Google Scholar 

  • Wolfram S (2002) A new kind of science. Wolfram Media, Champaign Books and Reviews, Champaign

    MATH  Google Scholar 

  • Wooldridge M (2002) Introduction to multiagent systems. Wiley, Chichester

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Virginia Bioinformatics Institute, Virginia Polytechnic Institute and State University, Virginia, USA

    Reinhard Laubenbacher & Henning S. Mortveit

  2. Department of Mathematics and Statistics, American University of Sharjah, Sharjah, United Arab Emirates

    Abdul S. Jarrah

  3. Department of Computer Science, University at Albany – State University of New York, New York, USA

    S. S. Ravi

Authors
  1. Reinhard Laubenbacher
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Abdul S. Jarrah
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Henning S. Mortveit
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. S. S. Ravi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Reinhard Laubenbacher .

Editor information

Editors and Affiliations

  1. Ramtech Ltd., Larkspur, California, USA

    Robert A. Meyers

Rights and permissions

Reprints 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

Publish with us

Policies and ethics

Search

Navigation