  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 $N$ agents
can be in $\delta$ different states leads to a Markov chain with $\delta^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.
