Markov Chain Aggregation for Agent-Based Models

We analyze the dynamics of agent-based models (ABMs) from a Markovian perspective and derive explicit statements about the possibility of linking a microscopic agent model to the dynamical processes of macroscopic observables.

On the basis of a formalization of ABMs as random walks on graphs, we use well-known conditions for lumpability to establish the cases where the macro model is still Markov.

For such a purpose a crucial role is played by the type of probability distribution used to implement the stochastic part of the model.

The symmetries of this distribution translate into regularities of the micro chain corresponding to the ABM, and this means that certain ensembles of agent configurations can be interchanged without affecting the probabilistic structure.

If a favored level of observation is compatible with the symmetries of the distribution, we obtain a complete picture of the macro dynamics including the transient stage.

If it is not, a certain amount of memory is introduced by the transition from the micro to the macro level, and this is the fingerprint of emergence in ABMs.

We describe our analysis in detail with some specific models of opinion dynamics.