Foundations of Multi-Agent Systems

Picture a logistics network on the night before peak season: ten thousand parcels per hour crossing thirty sortation hubs, fifteen airlines rebooking disrupted connections, two hundred delivery vans negotiating a city grid that itself is moving. No single human, and no single AI, can hold that system in mind. The defining problem of contemporary intelligent systems is no longer how to make one agent smarter; it is how to make many agents — autonomous, situated, possibly self-interested — cooperate well enough that the whole exceeds what any of them could manage alone. That problem is what this book is about, and this chapter is where we begin.

We will move from the specific to the structural. First, we argue that a class of computational problems exceeds the cognitive bandwidth of any monolithic solver and demand that we articulate exactly *why* before we engineer *how*. Second, we pin down the vocabulary: what counts as an *agent*, what an *environment* is, and what it means for multiple agents to coexist. Third, we trace the intellectual lineage of multi-agent systems (MAS) from the Distributed AI labs of the 1980s through agent-based modeling to today's LLM-driven agentic platforms, because most of the design patterns in modern agentic frameworks are inherited, knowingly or not, from thirty-year-old research. Fourth, we survey four canonical domains — RoboCup soccer, air-traffic control, supply chains, microgrids — to show how a domain's stress points map to MAS design choices. Fifth, we work through the trade-offs: coordination cost versus modularity and resilience, with a decision rule for when a MAS is genuinely the right abstraction. Finally, we build a small but extensible Python simulation of multi-agent foraging in a grid world. By the end you will have a reusable template for asking, of any problem, *is this a multi-agent system in disguise?*

When One Mind Is Not Enough

There is a temptation, especially when one has access to a very large language model, to assume that every problem can be absorbed into a single context window. The temptation is wrong, and the reasons are not merely engineering.

Cognitive bandwidth is finite. A single agent — human or artificial — has bounded working memory, bounded attention, and bounded time-to-decision. As the problem state grows, the agent's ability to track it does not scale. A logistics planner trying to hold the entire network in mind exhibits exactly the failure modes we see in pathologists or chess masters under time pressure: errors of omission, premature commitment to early cues, and brittleness at the edges.

Latency and locality matter. Many problems are not centralized in the data sense even when they are centralized in the governance sense. A warehouse robot's actions depend on what the robot *sees*, in the next ten milliseconds, from the physical location where it sits. Forcing those decisions through a remote supervisor introduces a round-trip that the physical world will not wait for. Similarly, a trading agent's edge comes from the milliseconds between exchange tick and local order book; aggregating everything to a central optimizer destroys the edge.

Robustness is a function of distribution. A monolithic solver is also a single point of failure. A MAS that degrades gracefully when one participant fails or behaves adversarially is qualitatively different from a controller that crashes when one subprocess fails. This is not an abstract point: the power grids that did not collapse during the 2003 Northeast blackout were the ones that could island themselves, and the supply chains that kept moving through the COVID-19 disruptions were the ones with redundant, locally-controlled routings.

Some problems are inherently multi-objective. When the participants in a system have different owners, different objectives, and different information, there is no privileged vantage point from which to compute the optimum. Market clearing, international negotiation, scheduling across firms, and most policy domains are like this. You cannot solve them with a single agent's utility function; you must let the agents have utilities and reconcile them.

That last point deserves a name. We will call a problem multi-agent by nature if any of the following holds: (i) the participants have different objectives; (ii) the relevant information is partially private and cannot be legally or economically centralized; (iii) the action space is intrinsically distributed in space or time, such that a central controller would either be too slow or too costly. Conversely, a problem is multi-agent by decomposition when a single owner could in principle centralize everything but chooses not to — usually for scalability, fault tolerance, or modularity reasons. MAS research serves both kinds. Confusing them is a common mistake.

The practical question — and the one this chapter is built around — is therefore not *can* a multi-agent approach outperform a monolithic one, but *under what conditions does it actually do so?* We will return to that question with a decision rule at the end of this chapter, but to apply it we first need crisp definitions.

What Is an Agent, Really?

The literature on agents is famously slippery. Almost every author who writes an introductory chapter warns the reader about this. We will skip the warnings and go straight to the operational definition that has held up best across thirty years of work.

An agent is anything that perceives its environment through sensors and acts upon that environment through actuators, where the action selection is a function of what it has perceived. That sentence does three pieces of work and we should look at each:

• *Perception via sensors* is intentionally broad. For a vacuum robot, sensors are infrared and bump detectors; for a trading system, sensors are market data feeds; for an LLM-based planning agent, the "sensor" might be a tool call returning a JSON document. The unifying claim is that the system has some channel of input from the world that it cannot fully control.

• *Action via actuators* is the dual claim: the system has some channel of output that can change the world. Text emitted into a chat is an action. A bid submitted to an exchange is an action. A wheel torque command is an action.

• *The mapping from perception to action is a function* is what separates agents from pure reactors. Even the dumbest thermostat has such a function; what makes agents interesting is whether that function is learned, deliberative, social, or any combination.

Russell and Norvig's textbook *Artificial Intelligence: A Modern Approach* (in our notes AIMA) operationalizes this further: an agent is a function from percept histories to actions. The full history matters because most interesting environments are not Markov in the raw percept — the agent needs memory. A robot that has just bumped a wall needs to remember *which* wall, and a planning agent needs to remember what it already promised. The notion of a percept history is the formal handle for memory.

```mermaid flowchart LR Env[Environment] -->|percepts| S[Sensors] S --> P[Percept] P --> H[(Percept History)] H --> R[Reasoning / Decision] R --> A[Action] A --> Ac[Actuators] Ac -->|effects| Env subgraph Agent S H R A end ```

That loop is the smallest unit of agency. Every MAS discussion eventually bottoms out in it. Notice three properties of the loop that are easy to miss. First, the loop is closed: the agent's actions feed back into its future percepts. The environment and the agent co-evolve. Second, the loop is time-stamped: a percept at $t$ and an action at $t+\Delta$ are causally connected, and in any realistic system $\Delta$ matters. Third, the loop is non-isolated: as soon as we have two agents, they share an environment, and the percept history of each now contains the *consequences of