Skip to content
Tutorials Center
My learning

Topics

Lesson 4 of 46 ยท Intelligent Agents

Multi-Agent Systems

Learn how several agents share a world: cooperation vs competition, communication, contract net task allocation, auctions, voting and Nash equilibria, with Python.

So far an agent has lived alone in its environment. In the real world it rarely does. Warehouse robots share aisles, trading programs bid against each other, traffic lights coordinate along a road and the players in a game all want different things. A multi-agent system (MAS) is a set of agents that act in a shared environment, each with its own goals, knowledge and abilities. The interesting new questions are social ones: who does what, how do they talk, how do they avoid blocking each other and what happens when their interests clash?

This lesson builds on Agents and Environments and Environment Types (a multi-agent environment is one of the dimensions listed there). You will see the main kinds of multi-agent setups, then code three classic coordination tools (task allocation by contract net, an auction and voting) and the basic idea of game theory.

Why use several agents?

A single powerful agent is not always the best design. Splitting a problem across agents helps when:

  • the problem is naturally distributed (sensors, robots or companies in different places),
  • no single agent has all the information or skills,
  • you want robustness: if one agent fails the others carry on,
  • the parts can be developed, owned or updated independently, and
  • the work can run in parallel.

The price is complexity. Agents must communicate, their actions can interfere, and global behaviour may be hard to predict.

Cooperative, competitive and mixed

The relationship between the agents' goals shapes everything else.

Setting Goals Example Typical tools
Cooperative Shared team goal Robots moving a heavy object together Task allocation, joint planning, consensus
Competitive Directly opposed Chess, poker, auctions Minimax, game theory (see Games and Minimax)
Mixed (self-interested) Partly aligned, partly opposed Drivers sharing a road, companies in a market Negotiation, mechanism design, equilibria

Agents can be homogeneous (identical) or heterogeneous (different abilities), and the system can be centralised (one coordinator tells everyone what to do) or decentralised (agents decide among themselves). Decentralised systems scale and survive failures better, but are harder to design.

graph LR
    subgraph Environment
    A1["Agent A<br/>sees, decides, acts"]
    A2["Agent B"]
    A3["Agent C"]
    end
    A1 <-- messages --> A2
    A2 <-- messages --> A3
    A1 -. changes shared state .-> A3

Agents influence each other in two ways: directly by messages, and indirectly because each one changes the world the others see.

Communication

Agents can exchange information in several ways:

  • Message passing: direct messages such as "request", "inform", "propose", "accept" and "refuse". Standards such as FIPA ACL define these speech acts.
  • Shared memory (blackboard): agents read from and write to a common data structure.
  • Stigmergy: agents leave marks in the environment that others follow, like ants laying pheromone trails.
  • Observation: one agent infers another's plan by watching what it does.

Coordination by task allocation: the contract net

The contract net protocol works like hiring a contractor. One agent (the manager) announces a task. Other agents (contractors) send bids saying how well or how cheaply they could do it. The manager awards the contract to the best bid and the winner performs the task.

Python Contract net: allocate delivery tasks to robots

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

No agent knows the whole plan. Each robot only computes its own bid, and a sensible allocation emerges: the load penalty stops one robot from taking everything. Change the penalty from 3 to 0 and compare. This is the principle behind real warehouse and ride-hailing dispatch systems (usually with better optimisation).

Auctions and mechanism design

When agents are self-interested, the rules of interaction matter. An auction is a rule for turning bids into an allocation and a price. In a first-price sealed-bid auction the winner pays what they bid, so smart bidders bid below their true value. In a second-price (Vickrey) auction the highest bidder wins but pays the second-highest bid, which makes bidding your true value the best strategy. Designing rules so that honest behaviour is the best policy is called mechanism design.

Python First-price versus second-price auctions

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the second-price rule, lowering Ann's bid cannot reduce the price she pays and can only risk losing, so honesty is optimal. In the first-price rule, honesty gives her nothing, and shading the bid to 85 earns a profit of 15. Same bidders, different rules, different behaviour.

Group decisions: voting

When agents must choose together, they can vote. Different rules can give different winners from the same ballots, which is a famous result in social choice theory.

Python Plurality versus Borda count

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Plurality elects A (the most first places), but 9 of the 15 voters prefer B to A, and the Borda count elects B. There is no perfect voting rule (Arrow's theorem), so the choice of rule is itself a design decision.

Game theory in a nutshell

Game theory analyses what rational self-interested agents do when each outcome depends on everybody's choices. A normal-form game lists each player's strategies and the payoff for every combination. The central idea is the Nash equilibrium: a combination of strategies where no player can do better by changing only their own strategy.

The best-known example is the prisoner's dilemma. Two suspects can cooperate (stay silent) or defect (betray the other). Payoffs are years saved, so higher is better:

B cooperates B defects
A cooperates 3, 3 0, 5
A defects 5, 0 1, 1
Python Find the Nash equilibrium of a two-player game

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Whatever the other player does, defecting pays more, so (D, D) is the only equilibrium, yet both would be better off at (C, C). That gap between individual and group rationality is the heart of many real problems (arms races, overfishing, traffic). The coordination game has two equilibria, so the agents also need a way to agree on one. When the game repeats, cooperation can pay: tit-for-tat earns 30 against itself but only 9 against a pure defector over ten rounds.

Emergent behaviour

Sometimes complex group behaviour arises from very simple local rules, with no leader. In the classic boids model each bird follows three rules (stay away from close neighbours, match their heading, move toward their average position) and realistic flocks emerge. Ant-colony optimisation and swarm robotics rely on the same idea. For AI engineers the lesson is: global performance may need to be engineered through the local rules and the environment, not just the individual agents.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What distinguishes a cooperative multi-agent system from a competitive one?

    The relationship between the agents' goals decides which tools are suitable: team planning and task allocation versus game-theoretic reasoning.
  2. 2. In the contract net protocol, what does the manager do after receiving bids?

    The manager announces a task, collects bids and awards the contract, usually to the lowest cost or best fit.
  3. 3. Why is truthful bidding the best strategy in a second-price (Vickrey) auction?

    Your bid only decides whether you win, not what you pay, so bidding your true value is a dominant strategy.
  4. 4. What is a Nash equilibrium?

    At a Nash equilibrium each player's strategy is a best response to the others, which does not mean the outcome is good for the group.
  5. 5. What does the prisoner's dilemma illustrate?

    Defection is each player's best response, but mutual defection pays less than mutual cooperation.

Summary

  • A multi-agent system has several agents with their own goals sharing one environment; the key questions are communication, coordination and conflict.
  • Settings can be cooperative, competitive or mixed, and designs centralised or decentralised.
  • The contract net protocol allocates tasks through announcements, bids and awards.
  • Auction rules shape bidder behaviour; a second-price auction makes honesty optimal.
  • Voting rules can disagree on the same ballots, and no rule is perfect.
  • Game theory uses payoff tables and Nash equilibria to predict self-interested agents; repetition can make cooperation sustainable.
  • Complex group behaviour can emerge from simple local rules.

Next: Problem Formulation for Search.