Foundations of Multi-Agent Systems: Models, Environments, and the Coordination Problem

Foundations of Multi-Agent Systems: Models, Environments, and the Coordination Problem

A system of autonomous decision-makers operating under partial observability, bounded rationality, and unreliable communication must somehow produce globally coherent behavior. This is the coordination problem of multi-agent systems (MAS), and it is the central object of study for everything that follows. The vocabulary used to describe that problem—what counts as an agent, what counts as an environment, what counts as coordination—is not neutral. Every formalism carves the design space differently and forecloses different solution paths; choosing the wrong abstraction early can trap an entire engineering effort in a regime where the right answer is unreachable. This chapter fixes the vocabulary with precision, identifies the structural axes along which MAS scenarios genuinely differ, names the four coordination problems that recur throughout the rest of the book, and grounds each abstraction in a concrete deployment history that shows why the abstractions matter.

1.1 Formal Models of Agency: From Perception Loops to Intentional Stances

The agent abstraction begins with a deceptively simple observation: a software process that *only* consumes inputs and produces outputs is a function, but a software process that *also* maintains internal state, exercises discretion over its action selection, and produces behavior that is intelligible only by attributing goals to it is an agent. The earliest formal definition, due to Russell and Norvig in *Artificial Intelligence: A Modern Approach*, treats an agent as any entity whose behavior can be described by an agent function

$$f: \mathcal{E}^* \rightarrow \mathcal{A}$$

mapping the entire history of percepts $\mathcal{E}^*$ to a single action $\mathcal{A}$, instantiated by an agent program running on some architecture. This is what is sometimes called the *weak* notion of agency: it does not require any mentalistic vocabulary, and in principle applies to thermostats, ocean currents, and corporate bureaucracies. The weak notion is useful because it admits a uniform vocabulary for control engineering, reinforcement learning, and MAS—everywhere we have a perceiver-actuator loop we can ask the same questions about state, observability, and policy optimality.

Wooldridge's *strong* notion of agency, formalized in the late 1990s, takes the further step of admitting mentalistic concepts—beliefs, desires, intentions, goals—as legitimate elements of the agent specification. Formally, a strong agent is a tuple $\langle M, A, \text{see}, \text{next}, \text{action} \rangle$ where $M$ is a set of mental states, $A$ is a set of actions, $\text{see}: \mathcal{E} \rightarrow \text{Perc}$ translates percepts, $\text{next}: M \times \text{Perc} \rightarrow M$ updates mental state, and $\text{action}: M \rightarrow A$ selects behavior. The strong notion becomes essential when we need to reason *about* agents—for verification, explanation, negotiation, and protocol synthesis—because in those contexts we want to talk about what an agent believes and intends, not merely what it does. The BDI (Belief-Desire-Intention) architecture, the most industrially successful instantiation of the strong notion, decomposes mental state into three modal components and uses a fixed-point semantics for plan deliberation that we will return to in detail in Chapter 2.

The temptation to dismiss the strong notion as unscientific—"agents don't really have beliefs"—should be resisted on pragmatic grounds. Dennett's intentional stance is not a metaphysical claim; it is a commitment to a vocabulary that yields reliable predictions and explanations when the entity in question is sufficiently complex, sufficiently autonomous, and sufficiently opaque that no lower-level description remains tractable. In an MAS where a warehouse robot must reason about a partner robot's likely next move, the engineering model that survives is one in which "robot B believes shelf 14 is occupied" is a perfectly good state variable.

What separates an agent from a plain object, an expert system, or a distributed process? Four properties, drawn from Wooldridge's canonical list, mark the boundary:

1. Autonomy. The agent exercises control over its own internal state and action selection. An object exposes its state for external manipulation; an agent does not. A thermostat that merely forwards temperature readings to a central controller is not an agent; a thermostat that decides for itself when to fire the boiler, based on internal setpoints and learned hysteresis, is. 2. Reactivity. The agent perceives its environment and responds to changes within bounded time. An expert system consulted by a batch job is not reactive; a fraud-detection agent that revokes a transaction within 200 ms of an anomalous signal is. 3. Proactivity. The agent does not merely react; it initiates behavior in pursuit of internally generated goals. A passive database query handler is not proactive; a monitoring agent that scans ahead, predicts a stockout, and pre-emptively triggers replenishment is. 4. Social ability. The agent communicates with other agents—via message passing, shared blackboards, or environmental stigmergy—and treats those communications as inputs that may revise its own plans. A purely local reinforcement learner is not social; a learning agent that requests demonstrations from a peer and updates its policy accordingly is.

These four properties are jointly necessary for the full agent paradigm, though partial combinations remain useful. Distributed processes, the most common point of confusion, satisfy reactivity and a weak form of autonomy but lack proactivity and almost always lack the social ability needed for genuine negotiation. Expert systems satisfy proactivity and social ability at the level of human consultation but are typically not embedded in a continuous environment and do not perceive in real time. Plain objects satisfy none.

A second axis of distinction concerns *granularity*. The literature speaks variously of *cognitive* agents (rich mental states, deliberate planning, symbolic reasoning), *reactive* agents (no internal model, behavior emerges from stimulus-response rules such as Brooks's subsumption architecture), and *hybrid* agents that combine layered reactive loops with deliberative modules invoked selectively. The granularity choice has profound engineering consequences: reactive agents scale to thousands of nodes with negligible coordination overhead, but cannot represent or reason about other agents' beliefs; cognitive agents can engage in explicit negotiation and counterfactual planning, but incur computational costs that limit team size. Most production systems, from warehouse fleets to autonomous-vehicle platoons, use hybrid architectures with a thin reactive core and a thicker deliberative shell invoked only when the reactive layer signals a planning impasse.

Finally, the agent abstraction admits *agents that are not software*. Hewitt's Actors, the conceptual ancestor of every modern agent, were explicitly agnostic about substrate: a person, an organization, or a piece of code could all be modeled as actors if they exchanged asynchronous messages. The same flexibility applies today: a smart contract on a blockchain, a human operator at a control console, and an LLM running in a serverless function are all agents in the technical sense, and the same coordination machinery can in principle be applied to mixed human-AI teams. This generality is both the power of the abstraction and the source of much design confusion, because the engineering disciplines differ across substrates even when the formal model does not.

1.2 The Environment Problem: PEAS and the Six Structural Dimensions

Once the agent is defined, the environment must be defined with equal rigor, because the choice of environment dictates which coordination mechanisms are even expre