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.