VI · Multi-AgentMature★★

Contract Net Protocol

also known as CNP, Bid-Based Task Allocation

Classical bid-based multi-agent task allocation: a manager broadcasts a task announcement, contractors submit bids, and the manager awards the contract to the best bid.

This pattern helps complete certain larger patterns —

  • used-byPerformative Message★★— Inter-agent messages are typed by communicative intent (request, inform, propose, accept, refuse, query) rather than by free-form prose, so receivers can dispatch on act type.

Context

A decentralized agent network has heterogeneous agents with different capabilities, capacities, and current loads. Top-down task assignment by a central scheduler doesn't scale or doesn't have visibility into per-agent state. The team needs a coordination protocol where agents self-allocate based on declared bids.

Problem

Top-down assignment requires the scheduler to know every agent's capability and current load — global state that's expensive to maintain. Random or round-robin allocation ignores capability fit and load. Without a structured bidding mechanism, decentralized agents either collide on tasks or starve.

Forces

  • Bidding rounds add latency to task allocation.
  • Agents may bid dishonestly (claim capacity they lack).
  • Bid evaluation criteria must be designed per task class.

Example

A distributed research-agent network. A task comes in: 'analyze the 2024 patent landscape for hydrogen storage'. Manager broadcasts to specialist agents. Bids: Patent Agent (capability 0.9, capacity 0.6, ETA 4h), General Research Agent (capability 0.4, capacity 0.9, ETA 2h), Chem Specialist (capability 0.8, capacity 0.2, ETA 8h). Manager awards to Patent Agent (best capability × capacity tradeoff). Other bidders get cancellation. Patent Agent commits.

Diagram

Solution

Therefore:

Define the protocol: (1) Announce — manager broadcasts task spec to capable contractors. (2) Bid — each contractor evaluates fit and submits bid {capability score, capacity available, cost, ETA}. (3) Award — manager picks best bid by configured criteria, sends acceptance. (4) Execute — winner commits and reports. (5) Cancel — bids not awarded receive cancellation. Add bid-validation to prevent dishonest bidding. Pair with decentralized-swarm-handoff, scatter-gather-saga, parallel-fan-out-gather.

What this pattern forbids. No task is assigned outside the bidding protocol; bid evaluation criteria are explicit and auditable.

And the patterns that stand alongside it, or against it —

  • complementsDecentralized Swarm Handoff★— Agents in a swarm decide handoffs to peers based on a shared protocol with no central coordinator; specifically about agent-initiated handoff protocols, not topology.
  • complementsScatter-Gather Plus Saga★— Distribute tasks across worker agents and aggregate results while maintaining distributed-transaction semantics via compensating actions on partial failure.
  • complementsParallel Fan-Out / Gather★— Multiple independent agents execute in parallel on a partitioned task; a dedicated aggregator agent reconciles their results into a single output.
  • alternative-toSupervisor★★— Place a coordinating agent above a set of specialised agents and route work to them.
  • complementsActor-Model Agents★— Implement each agent as an independent actor with its own mailbox, processing asynchronous messages one at a time and never sharing mutable state with peers.
  • complementsCoalition Formation·— Agents form temporary subgroups around a task because the coalition can achieve more value than the sum of its members acting alone, with explicit rules for who joins and how payoff or credit is shared.
  • complementsVickrey Auction Allocation★★— Allocate a task to the lowest sealed bidder but pay them the second-lowest bid, making truthful cost reporting a dominant strategy.
  • complementsDistributed Constraint Optimization·— A group of agents jointly assigns values to shared variables to minimise (or maximise) a global cost defined by inter-agent constraints, exchanging only the messages needed.
  • complementsTrust and Reputation Routing★— Maintain a per-agent reputation score updated from outcome quality and peer feedback, and route new tasks preferentially to high-reputation agents.

Neighbourhood

Click any neighbour to follow the language. Scroll to zoom, drag to pan.

Used in recipes

References

Provenance