from the semantic (who does what?). It is no surprise then to
see recursive graph algorithms play a central role and provide a dynamic version of renormalization, a technique used
in quantum mechanics and statistical physics.
• Bounded-confidence systems: In this popular model of
social dynamics10, d = 1 and xi is a real number denoting
the “opinion” of agent i. That agent is linked to j if and
only if |xi − xj| ≤ 1. The action function f instructs each
agent to move to the mass center of their neighbors.
This is the prototypical example of a bidirectional diffusive influence system.
• Sync: An instance of Kuramoto synchronization, this
diffusive influence system links each of n fireflies to the
other fireflies whose flashes it can spot. Every critter has
its own flashing oscillator, which becomes coupled with
those of its neighbors. The function f specifies how the
fireflies adjust their flashings in reaction to the graph-induced couplings3, 23. The model has been applied to
Huygens’s pendulum clocks as well as to circadian neurons, chirping crickets, microwave oscillators, yeast cell
suspensions, and pacemaker cells in the heart25.
• Swarming: The agents may be fish or birds, with states
encoding positions and velocities (for rigid 3D animal
models, d = 9). The communication graph links every
agent to some of its nearest neighbors. The function f
instructs each agent to align its velocity with those of its
neighbors, to move toward their center of gravity, and
to fly away from its perilously close neighbors21, 24.
• Chemotaxis: Some organisms can sense food gradients
and direct their motion accordingly. In the case of bacterial chemotaxis, the stimuli are so weak that the
organisms are reduced to performing a random walk
with a drift toward higher food concentrations.
Influence systems can model these processes with the
use of both motile and inert agents.c Chemotaxis is
usually treated as an asocial process (single agents
interacting only with the environment). It has been
observed, however, that schooling behavior can facilitate gradient climbing for fish, a case where living in
groups enhances foraging ability19.
Other examples of influence systems include the Ising
model, neural nets, Bayesian social learning, protein–protein
interaction networks, population dynamics, and so on.
2. 2. how expressive are influence systems?
If agent i is viewed as a computing device, then the d-tuple
xi is its memory. The system is Markovian in that all facts
about the past with bearing on the future are encoded in x.
The communication graph allows the function f to be local if
so desired. The procedure G itself might be local even when
appearance suggests otherwise: for example, to identify
c Some living systems (e.g., ants and termites) exchange information by
stig-mergy: instead of communicating directly with signals, they leave traces such
as pheromones in the environment, which others then use as cues to coordinate their collective work. Although lacking autonomy, inert components
can still be modeled as agents in an influence system.
your nearest neighbor in a crowd entails only local computation, although, mathematically, the function requires
knowledge about everyone. The ability to encode different
action/communication rules for each agent is what drives
up the descriptive complexity of the system. In return, one
can produce great behavioral richness even in the presence
of severe computational restrictions.
(i) Learning, competition, hierarchy: Agents can implement game-theoretic strategies in competitive environments (e.g., pursuit-evasion games) and learn to
cooperate in groups (e.g., quorum sensing). They can
self-improve, elect leaders, and stratify into dominance hierarchies.
(ii) Coarse-graining: Flocks are clusters of birds that
maintain a certain amount of communicative cohesion over a period of time. We can view them as
“super-agents” and seek the rules governing interaction among them. Iterating in this fashion can set the
stage for dynamic renormalization in a time-changing analog of the renormalization group of statistical mechanics (see Section 6).
(iii) Asynchrony and uncertainty: In the presence of
delayed or asynchronous communication, agents
can use their memory to implement a clock for the
purpose of time stamping. Influence systems can
also model uncertainty by limiting agents’ access to
approximations of their neighbors’ states.
A few words about our agent-based approach. Consider
the diffusion of pollen particles suspended in water.
A Eulerian approach to this process seeks a differential
equation for the concentration c (x, t) of particles at any
point x and time t. There are no agents, just density functions evolving over time18. An alternative approach, called
Lagrangian, would track the movement of all the individual
particles and water molecules by appealing to Newton’s
laws. Given the sheer number of agents, this line of attack
crashes against a wall of intractability. One way around it
is to pick a single imaginary self-propelled agent and have
it jiggle about randomly in a Brownian motion. This agent
models a typical pollen particle—typical in the “ergodic”
sense that its time evolution mimics the space distribution
of countless particles caught on film in a snapshot. Scaling
plays a key role: our pollen particles indeed can be observed
only on a timescale far larger than the molecular bumps
causing the jiggling. Luckily, Brownian motion is scale-free,
meaning that it can be observed at any scale. As we shall see
in Section 6, the ability to express a dynamical process at different scales is an important feature of influence systems.
The strength of the Eulerian approach is its privileged
access to an advanced theory of calculus. Its weakness lies
in two commitments: global behavior is implied by
infinitesimal changes; and every point is subject to identical laws.
While largely true in physics, these assumptions break
down in the living world, where diversity, heterogeneity, and
autonomy prevail. Alas, the Lagrangian answer, agent-based
modeling, itself suffers from a serious handicap: the lack of
a theory of natural algorithms.