Multi-Agent Systems: Coordination and Negotiation

1. What is a multi-agent system

A multi-agent system (MAS) is a set of autonomous agents that share an environment, perceive it through local sensors, and act on it through local actuators, without any single agent holding complete global state. Each agent pursues its own goal — deliver a package, harvest a resource, defend territory — yet the system as a whole must avoid chaos: agents must not collide, waste resources, or work at cross purposes.

MAS research sits at the intersection of distributed computing, game theory and artificial intelligence. It underlies swarm robotics, algorithmic trading, disaster-response robot teams, traffic-signal networks and multiplayer game AI. The central question is always the same: how do we get emergent, useful, global behaviour from purely local decisions?

2. Coordination mechanisms

Every real system mixes these mechanisms. A fleet of delivery robots might use an auction to assign parcels, a negotiation protocol to swap parcels when routes change, and a consensus algorithm to agree on a shared map of blocked roads.

Centralised vs decentralised coordination

A centralised coordinator has full visibility and issues optimal (or near-optimal) commands but is a single point of failure and does not scale past a few hundred agents. A decentralised protocol scales to thousands of agents and tolerates individual failures, at the cost of provably-optimal guarantees — decentralised solutions are usually only locally optimal.

3. Contract Net Protocol

The Contract Net Protocol (CNP), proposed by Reid G. Smith in 1980, is the archetypal negotiation protocol for task allocation in distributed systems. It works in four stages:

1. Announcement — a manager agent broadcasts a call for proposals (CFP) describing a task and its constraints.
2. Bidding — every capable agent that receives the CFP computes its cost or utility for the task and replies with a bid.
3. Award — the manager compares all bids and awards the contract to the best one (lowest cost or highest utility).
4. Execution & reporting — the winning contractor performs the task and reports the result back to the manager.

4. Auctions and task allocation

Auctions generalise the Contract Net idea with well-studied game-theoretic properties. The three most common formats in MAS literature:

• English auction — ascending price, bidders openly outbid each other until only one remains.
• Sealed-bid first-price — each agent submits one hidden bid; the highest bidder wins and pays their own bid.
• Vickrey (second-price) auction — the highest bidder wins but pays the second-highest bid, which makes truthful bidding the dominant strategy.

In combinatorial auctions, agents bid on bundles of tasks rather than single items, which better captures synergies (e.g. two deliveries on the same street are cheaper together) but makes winner-determination NP-hard in general.

5. Consensus algorithms

Consensus protocols let a group of agents agree on a single value — a rendezvous point, an average sensor reading, a leader — using only local communication with neighbours, without any agent broadcasting to everyone.

This simple update rule underlies flocking velocity alignment (see our Boids article), distributed sensor fusion, and blockchain-style agreement (albeit with much stronger fault-tolerance requirements in the Byzantine case, where some agents may lie).

6. Communication and speech acts

For agents to negotiate they need a shared vocabulary. The FIPA-ACL (Agent Communication Language) standard defines a set of performatives — speech acts borrowed from linguistics — that give every message an unambiguous intent:

• cfp — call for proposals (start of a Contract Net round)
• propose — a bid or counter-offer
• accept-proposal / reject-proposal — the manager's decision
• inform — sharing a fact or observation
• request — asking another agent to perform an action

Structuring messages this way lets heterogeneous agents — built by different teams, in different languages — interoperate, because the meaning of a message is standardised even when its content is not.

7. Pseudocode: Contract Net Protocol

function runContractNet(manager, contractors, task):

  // 1. Announcement
  manager.broadcast(cfp(task), contractors)

  // 2. Bidding
  bids = []
  for each agent in contractors:
    if agent.canPerform(task):
      cost = agent.estimateCost(task)
      bids.push({agent, cost})

  // 3. Award — pick the lowest cost bid
  if bids.length == 0:
    return null  // no one can do it
  winner = minBy(bids, b => b.cost)
  manager.send(accept-proposal, winner.agent)
  for each other in bids if other != winner:
    manager.send(reject-proposal, other.agent)

  // 4. Execution and reporting
  result = winner.agent.execute(task)
  winner.agent.send(inform(result), manager)
  return result

Real-world variants add timeouts (bids must arrive within a deadline), re-announcement (if the winner fails, re-run the protocol among remaining contractors), and nested contracts (a contractor can become a manager for sub-tasks).