Foundational Models of Multi-Agent Systems

Chapter 1: Foundational Models of Multi-Agent Systems

1.1 The Definitional Problem: What is an Agent?

Any rigorous treatment of multi-agent coordination must begin by confronting a foundational question that is more difficult than it first appears: what is an agent, and what distinguishes a multi-agent system (MAS) from a conventional distributed system? The intuitive appeal of the term belies a remarkable conceptual underdetermination. In the distributed systems literature, "agent" is often used as a synonym for "process," "node," or "actor," thereby reducing the concept to a locus of computation that exchanges messages over a network. In the artificial intelligence literature, by contrast, the same word denotes an entity possessed of beliefs, desires, intentions, and the capacity to deliberate about its own actions. These two conceptions are not interchangeable: the first is purely operational, while the second imports an entire philosophical apparatus concerning rationality, intentionality, and the explanatory role of mentalistic vocabulary. The remainder of this monograph adopts the second conception, for reasons that will become apparent as the formal machinery unfolds. The first conception, while computationally convenient, leaves unexplained the very phenomena—coordination, cooperation, negotiation, trust, role allocation—that the field seeks to understand.

The philosophical underpinnings of the strong notion of agency are found in Daniel Dennett's *intentional stance*. Dennett argued that any system whose behavior can be reliably predicted by attributing to it beliefs, desires, and rational deliberation is, in a precisely defined sense, an intentional system. The stance is not a metaphysical claim about the inner life of the system; it is an instrumental commitment to a predictive strategy. When we say that a thermostat "believes" the room is too cold, we are not committing ourselves to the claim that the thermostat has phenomenal consciousness. We are committing ourselves to the claim that the simplest explanation of its behavior appeals to a representation of the world state together with a goal and an action tendency. The intentional stance, in Dennett's formulation, applies in three degrees. A *first-order intentional system* has beliefs and desires about the world but not about other intentional systems. A *second-order intentional system* has beliefs and desires about the beliefs and desires of others. A *third-order* system reasons about beliefs about beliefs. Multi-agent systems, as the name suggests, almost always involve at least second-order intentionality, because the actions of one agent are conditioned upon the anticipated actions of others. The escalation of intentional orders is one of the principal sources of computational complexity in MAS, and it is a theme to which we will return repeatedly.

The rational agent paradigm, formalized by Russell and Norvig in their canonical textbook, makes the intentional stance operational by defining an agent as anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators. Formally, an agent is a function $f : \mathcal{P}^* \to \mathcal{A}$ mapping histories of percepts to actions, where $\mathcal{P}$ is the set of possible percepts and $\mathcal{A}$ is the set of possible actions. A *performance measure* evaluates the sequence of environment states induced by this function. A *rational agent* is one whose action function maximizes the expected performance measure over the agent's prior probability distribution over environment dynamics. This definition has the virtue of precision: every term is mathematically well-defined, and the optimal agent in a given environment is in principle computable as the solution to a corresponding decision problem. It has the vice of being silent on the structure of the agent. A lookup table, a neural network, a theorem prover, and a market institution are all functions from percept histories to actions, yet their internal organization is radically different. The rational agent paradigm is therefore best understood as a specification of *what the agent does*, not *how it does it*. The question of how to organize the internals of a rational agent is the province of agent architectures, the subject of Section 1.2.

The distinction between a multi-agent system and a distributed system can now be drawn with some precision. A distributed system is a collection of computational entities whose principal concern is the reliable, efficient, and consistent manipulation of shared or partitioned state. Distributed databases, consensus protocols, and message-passing middleware exemplify the genre. A multi-agent system, by contrast, is a collection of *autonomous*, *situated*, and *socially capable* entities whose interactions are structured by norms, conventions, roles, and joint commitments rather than by a single global state machine. Three properties mark the transition:

1. Autonomy. Each agent has its own agenda, derived from its own beliefs and goals, and no external controller can unilaterally override this agenda. This is the property that distinguishes an agent from a subroutine.

2. Situatedness. Each agent is embedded in an environment whose dynamics it does not fully control, and it must act on the basis of partial information acquired through local sensors. This property distinguishes an agent from a pure reasoning engine that operates on closed-world data.

3. Social capacity. Each agent possesses some mechanism—communication, observation, shared conventions—for coordinating its behavior with that of other agents. The mechanism may be rudimentary (broadcast of intent) or sophisticated (argumentation protocols), but it must exist; otherwise the system collapses into a collection of isolated decision-makers.

These three properties together justify treating MAS as a distinct field. Distributed systems theory can handle autonomy and situatedness when the locus of decision is a single process; it falters when the decision-makers are themselves intentional systems whose behavior depends on their beliefs about one another. The remainder of this chapter builds the formal apparatus required to reason rigorously within this expanded setting.

A final definitional clarification concerns the relationship between agents and actors, agents and processes, and agents and intelligent systems. The *actor model* of Hewitt, Agha, and others shares with MAS the emphasis on autonomous message-passing entities, but actors are typically reactive—they respond to messages according to a fixed transition rule—rather than deliberative. The actor model is therefore best positioned as a substrate on which higher-level agent architectures can be implemented. *Processes* in operating systems theory are characterized by address spaces and resource ownership; they need not have any representation of their environment beyond the data structures they manipulate. *Intelligent systems* is a broader term that includes any system exhibiting some form of adaptive behavior, including single-agent machine learning systems that lack social capacity. The intersection of these sets, depicted schematically in Figure 1.1, defines the territory of multi-agent systems as the term is used throughout this book.

```mermaid flowchart LR A[Autonomous Entities] --> B{Social Capacity?} B -- Yes --> C[Multi-Agent System] B -- No --> D[Standalone Intelligent System] A --> E{Reactive vs Deliberative?} E -- Reactive --> F[Actor Model] E -- Deliberative --> G[Rational Agent] A --> H{Situated in Environment?} H -- Yes --> I[Embodied Agent] H -- No --> J[Pure Reasoner] C --> K[Focus of This Book] I --> K G --> K ```

The diagrammatic scope of multi-agent systems.

The reader should resist the temptation to regard the foregoing definitions as merely terminological. Each definitional choi