Artificial
Intelligence

10.1 Multiagent Framework

In this chapter, we consider the case in which there are multiple agents, where

• the agents can act autonomously, each with its own information about the world and the other agents.
• the outcome depends on the actions of all of the agents. A mechanism specifies how the actions of the agents lead to outcomes.
• each agent can have its own utility that depends on the outcome.

Each agent decides what to do based on its own utilities, but it also has to interact with other agents. An agent acts strategically when it decides what to do based on its goals or utilities.

Sometimes we treat nature as an agent. Nature is defined as being a special agent that does not have values and does not act strategically. It just acts, perhaps stochastically. Nature may be seen as including of all of the agents that are not acting strategically. In terms of the agent architecture shown in Figure 1.3, nature and the other agents form the environment for an agent. A strategic agent cannot treat other strategic agents as part of nature because it should reason about their utility and actions, and because the other agents are perhaps available to cooperate and negotiate with.

There are two extremes in the study of multiagent systems:

• fully cooperative, where the agents share the same utility function, and
• fully competitive, when one agent can only win when another loses. These are often called zero-sum games when the utility can be expressed in a form such that the sum of the utilities for the agents is zero for every outcome.

Most interactions are between these two extremes, where the agents' utilities are synergistic in some aspects, competing in some, and other aspects are independent. For example, two commercial agents with stores next door to each other may both share the goal of having the street area clean and inviting; they may compete for customers, but may have no preferences about the details of the other agent's store. Sometimes their actions do not interfere with each other, and sometimes they do. Often agents can be better off if they coordinate their actions through cooperation and negotiation.

Multiagent interactions have mostly been studied using the terminology of games following the seminal work of Neumann and Morgenstern (1953). Many issues of interaction between agents can be studied in terms of games. Even quite small games can highlight deep issues. However, the study of games is meant to be about general multiagent interactions, not just artificial games.

Multiagent systems are ubiquitous in artificial intelligence. From parlor games such as checkers, chess, backgammon, and Go, to robot soccer, to interactive computer games, to having agents that act in complex economic systems, games are integral to AI. Games were one of the first applications of AI. One of the first reinforcement learning systems was for the game of checkers by Samuel (1959), with the first operating checkers program dating back to 1952. There was great fanfare when Deep Blue beat the world chess champion in 1997. Computers have also been successful at checkers and backgammon, but less so in the game Go because of the size of the search space and the availability of good heuristics. Although large, these games are conceptually simple because the agents can observe the state of the world (they are fully observable). In most real-world interactions, the state of the world is not observable. There is now much interest in partially observable games like poker, where the environment is predictable (even if stochastic), and robot soccer, where the environment is not very predictable. But all of these games are much simpler than the multiagent interactions people perform in their daily lives, let alone the strategizing needed for bartering in marketplaces or on the Internet, where the rules are less well defined and the utilities are much more multifaceted.