Contract Net Protocol

The protocol initiates with a manager agent broadcasting a task announcement to potential contractor agents. This announcement is a structured message containing:

• A detailed task specification
• Eligibility criteria for bidders
• A deadline for bid submission
• Any necessary constraints or preconditions This broadcast mechanism eliminates the need for a central dispatcher, allowing any eligible agent in the network to respond, fostering a flexible and scalable system.

Upon receiving an announcement, eligible contractors evaluate the task against their own capabilities and current workload. They then submit a bid back to the manager. A bid typically includes:

• The contractor's proposed cost or utility for completing the task
• A timeframe for completion
• Proof of relevant capabilities or qualifications This creates a competitive market for tasks, where the manager can select the most suitable or cost-effective agent, optimizing overall system performance.

After the bid deadline, the manager evaluates all submitted bids according to its award criteria (e.g., lowest cost, fastest time, highest reliability). It then sends an award message to the winning contractor and rejection messages to the others. The award message formalizes the contract, establishing a commitment. This step transitions the relationship from negotiation to execution, creating a clear principal-agent dynamic with defined obligations.

The protocol defines a standardized set of communicative acts (speech acts) that structure the interaction. Key acts include:

• cfp (Call for Proposals): The initial task announcement.
• propose: A contractor's bid submission.
• accept-proposal: The manager's award.
• reject-proposal: The manager's rejection.
• inform: Used for reporting task completion or failure. This formal semantics ensures all agents share a common understanding of message intent, enabling interoperability between heterogeneous agents.

Agents are not statically defined as managers or contractors. Any agent can assume the manager role for a task it cannot or should not perform itself, and later act as a contractor for a different task. This role fluidity is a core strength, allowing the system to dynamically reorganize based on workload, expertise, and resource availability. It supports robust, flexible systems where control is task-driven rather than hierarchy-driven.

The protocol includes mechanisms for managing execution failures. If a contractor fails to complete a task, it may send a failure notification to the manager. The manager can then:

• Re-announce the task to find a new contractor
• Attempt the task itself
• Escalate the failure to a higher-level agent This built-in handling for contract breach makes the system fault-tolerant, as task allocation is not a one-time event but part of a continuous management process.

A market-inspired protocol where agents compete to acquire a resource or task by submitting bids according to predefined rules. Unlike Contract Net's task announcement, auctions are typically resource or item-centric.

• Common Formats: English (ascending price), Dutch (descending price), Vickrey (second-price sealed-bid).
• Key Mechanism: The winner determination problem is central, especially in combinatorial auctions where bids are on bundles of items.
• Example: Allocating cloud computing instances in a spot market, where agents bid for available capacity.

A framework for modeling multi-agent coordination where a global objective must be optimized subject to constraints distributed among agents. It provides a more general and rigorous formalism for problems Contract Net can address heuristically.

• Core Components: Variables, domains, constraints, and a global utility/objective function.
• Solution Methods: Includes algorithms like DPOP (Distributed Pseudotree Optimization Protocol) and MGM (Maximum Gain Message).
• Application: Coordinating sensor networks, scheduling meetings across multiple calendars, or smart grid load balancing.

A structured, often bilateral, framework for agents to exchange offers and counteroffers to reach a mutual agreement, typically over price or resource split. It models direct negotiation rather than a manager-contractor dynamic.

• Theoretical Basis: Heavily grounded in game theory (e.g., Rubinstein Bargaining Model).
• Key Concepts: Reservation price, utility function, Pareto optimality.
• Variants: Monotonic concession protocol, where agents must make concessions each round until an agreement zone is found.

The 'inverse game theory' of designing the rules of a protocol (the 'game') so that the self-interested, strategic behavior of participating agents leads to a desired social outcome. Contract Net is a simple example of a designed mechanism.

• Primary Goal: Elicit truthful information (strategy-proofness) or achieve efficient allocations.
• Foundational Theorem: The Revelation Principle states any mechanism's outcome can be replicated by a direct mechanism where truth-telling is optimal.
• Application: Designing ad auctions, public goods funding, or kidney exchange programs.

A negotiation process where agents form cooperative groups (coalitions) to achieve tasks or goals unattainable alone. It extends beyond single-task allocation to dynamic group structures.

• Core Challenges: Determining stable coalitions (e.g., in the core) and distributing payoffs (fair division).
• Solution Concepts: Nash Bargaining Solution, Shapley value, and the bargaining set.
• Example: Delivery robots forming convoys to save energy, or trading agents forming a bloc to get bulk discounts.

The Foundation for Intelligent Physical Agents Agent Communication Language (FIPA ACL) is a standard defining the syntax, semantics, and pragmatics of agent messages. It provides standardized interaction protocols, of which Contract Net is one canonical example.

• Message Structure: Includes performatives (e.g., cfp, propose, accept-proposal, reject-proposal), content, and conversation control.
• Standardization: Enables interoperability between heterogeneous agent platforms.
• Relation: Contract Net is formally specified as a FIPA Interaction Protocol, providing a concrete template for the announce-bid-award sequence.