Multi-Agent Collaboration & Negotiation: Orchestrating Collective Intelligence

Collaboration and negotiation are different problems

The distinction matters because it changes what can go wrong. In collaboration the risk is coordination failure: two agents doing the same subtask, nobody doing another, or one agent silently abandoning its part. The tools are task allocation and shared commitments. In negotiation the risk is strategic: an agent misreporting its costs to win better terms, two agents colluding against a third, or a negotiation that never terminates. The tools there are mechanisms whose rules make honest behaviour a good strategy, plus deadlines.

Many real systems mix both. Agents inside one company share the goal of serving customers but compete for a fixed inference budget. Treat each interaction by its incentives, not by the fact that every agent belongs to you: if an agent is evaluated on its own team's throughput, it will behave like a self-interested party, and its model will happily write whatever bid its prompt rewards.

Collaboration and negotiation are different problems

The distinction matters because it changes what can go wrong. In collaboration the risk is coordination failure: two agents doing the same subtask, nobody doing another, or one agent silently abandoning its part. The tools are task allocation and shared commitments. In negotiation the risk is strategic: an agent misreporting its costs to win better terms, two agents colluding against a third, or a negotiation that never terminates. The tools there are mechanisms whose rules make honest behaviour a good strategy, plus deadlines.

Many real systems mix both. Agents inside one company share the goal of serving customers but compete for a fixed inference budget. Treat each interaction by its incentives, not by the fact that every agent belongs to you: if an agent is evaluated on its own team's throughput, it will behave like a self-interested party, and its model will happily write whatever bid its prompt rewards.

The Contract Net Protocol

The Contract Net Protocol, introduced by Reid Smith in 1980 and later standardised by FIPA, allocates tasks the way a tender does. A manager announces a task with a call for proposals (cfp). Each potential contractor replies propose with a bid or refuse. After a deadline the manager sends accept-proposal to the winner and reject-proposal to the rest, and the winner later reports inform-done or failure. Each performative has a defined meaning, so a log of messages is also a log of obligations; multi-agent communication protocols covers that message layer.

Three details make it work in practice. The call has a deadline, so a silent contractor cannot stall the allocation. Bids are structured, not prose, so they can be validated and compared. And an award is a commitment with an expiry: if the contractor does not report by then, the manager re-announces. Below is a minimal implementation in which the LLM writes the bid fields and the code does everything else.

from dataclasses import dataclass
import asyncio, time

@dataclass
class Bid:
    agent_id: str
    cost: float          # budget credits the contractor asks for
    eta_s: int           # promised completion time in seconds
    rationale: str       # free text, logged, never used for the decision

async def contract_net(task, contractors, ledger, deadline_s=20):
    async def ask(agent):
        try:
            reply = await asyncio.wait_for(agent.on_cfp(task), timeout=deadline_s)
            return Bid(agent_id=str(reply["agent_id"]), cost=float(reply["cost"]),   # coerce or drop
                       eta_s=int(reply["eta_s"]), rationale=str(reply.get("rationale", "")))
        except Exception:
            return None
    bids = [b for b in await asyncio.gather(*(ask(a) for a in contractors)) if b]
    valid = [b for b in bids if b.cost <= task.max_cost and b.eta_s <= task.max_eta_s
             and task.skill in registry.skills(b.agent_id)]
    if not valid:
        return ledger.record(task.id, status="unallocated", bids=bids)
    valid.sort(key=lambda b: (b.cost, b.eta_s))
    winner = valid[0]
    price = valid[1].cost if len(valid) > 1 else task.max_cost   # second price, see next section
    ledger.record(task.id, status="awarded", agent=winner.agent_id, price=price,
                  due=time.time() + winner.eta_s, bids=bids)
    for b in valid[1:]:
        await registry.send(b.agent_id, "reject-proposal", task.id)
    await registry.send(winner.agent_id, "accept-proposal", task.id, price=price)

Notice what the model never touches: the deadline, the validation against the task's limits and the registry's skill list, the sort, the price and the ledger entry. A contractor agent can write anything it likes in rationale; it cannot award itself the contract by being eloquent.

Auctions and why second price is honest

The award rule in the code above is a reverse auction: the lowest cost wins. The question is what price the winner receives. In a first-price auction the winner is paid its own bid, so every bidder has a reason to shade: report a cost above its true cost and hope it still wins. That makes bids hard to interpret and rewards agents that are better at guessing the others. In a second-price, or Vickrey, auction the winner is paid the second-lowest bid. Now the bid only decides whether you win, not what you are paid, and reporting your true cost becomes a dominant strategy: no other report does better, whatever the others do.

That guarantee has conditions, and it is worth stating them precisely. It holds for a single item, when each bidder's cost is private and independent of the others, and when utility is simply payment minus cost. It does not survive collusion, where two bidders agree that one will bid high, or shill bids from a fake participant, and it says nothing about bidders who do not know their own cost. That last point is the important one for LLM agents. A model asked to estimate effort in prose is noisy. Have the contractor compute cost from something measurable, such as its queue length, expected tokens and the price of its model tier, and let the LLM only decide whether the task fits its skills.

When agents need bundles, for example a GPU slot and a dataset lock together, single-item auctions break down because winning half the bundle is worthless. Combinatorial auctions handle this but winner determination is NP-hard in general. For a handful of agents, a simpler option is to auction the bundle as one item.

Bargaining between two agents

Auctions need several competitors. When exactly two agents must agree, for example a buyer agent and a supplier agent setting a delivery date and price, the tool is bargaining. In the alternating-offers model analysed by Rubinstein in 1982, the parties take turns proposing, and delay is costly to each, modelled by a discount factor per round. With complete information the equilibrium is immediate agreement, and each party's share rises with its patience. The practical lesson is that deadlines and the cost of delay shape outcomes more than eloquence does.

The Nash bargaining solution gives a target for a fair outcome. Each party has a disagreement payoff, what it gets if talks fail. Among the feasible agreements, choose the one that maximises the product of the two parties' gains over their disagreement payoffs. It is Pareto efficient: no other agreement improves one party without hurting the other. The Zeuthen strategy is a concession protocol in which, each round, the party less willing to risk breakdown concedes; Harsanyi showed that it leads to the Nash bargaining solution. For LLM agents, the safe pattern is a bounded protocol in code with each agent's reservation value held outside the model's context, so persuasion cannot move it.

def negotiate(buyer, seller, max_rounds=6):
    """Alternating offers on price. Reservation values live in code, not in prompts."""
    offer = buyer.open()                                   # LLM drafts, code clamps
    for rnd in range(max_rounds):
        proposer, responder = (buyer, seller) if rnd % 2 == 0 else (seller, buyer)
        offer = proposer.clamp(offer)                      # never beyond its own reservation value
        if responder.utility(offer) >= responder.utility(responder.next_offer(rnd)):
            return Agreement(offer, rounds=rnd + 1)        # accept: better than what it would ask next
        offer = responder.next_offer(rnd)                  # concession schedule, monotone by construction
    return NoDeal(rounds=max_rounds)                      # each side falls back to its disagreement option

The language model's job here is narrow and useful: turn a messy request into an offer structure, explain an offer to a human, or spot an issue the schema missed. The acceptance test and the concession schedule are functions.

Joint commitments: keeping a team plan alive

Collaboration needs one more thing that allocation does not provide: what happens when a plan changes. Cohen and Levesque's work on joint intentions in the early 1990s gave the answer still used today. A team holding a joint goal is committed not only to pursuing it but to telling the others when a member comes to believe the goal is achieved, impossible or no longer relevant. Without that obligation, one agent finishes or gives up and the others keep working on a dead plan.

In an LLM system this becomes a rule on the shared ledger. Every commitment has an owner, a due time and a status, and any agent that changes its belief about a commitment must write the change there. A watcher that is not an LLM expires overdue commitments and re-opens them for bidding. The agent orchestrator article shows how a scheduler loop enforces those deadlines.

Worked example: allocating a translation job

Suppose a platform team runs a translation service with three contractor agents, each wrapping a different model tier, and a manager agent receives “translate 40 support articles into German by 18:00” with a ceiling of 30 credits. The manager issues a call for proposals with a 20-second deadline.

Both proposals pass validation, A has the lowest cost and wins, and under the second-price rule it is paid 15 credits, B's bid. Had A inflated its bid to 14 hoping for more, it would still win and still be paid 15; had it inflated to 16 it would lose a job it could do profitably. That is the truthfulness property at work. The ledger records the award with a due time of 55 minutes. At minute 40, A's quality check finds that its model handles product terminology poorly; under the joint-commitment rule it writes failure to the ledger instead of shipping weak output, and the manager re-announces the remaining 12 articles. B wins that round. Total cost is known at every step because it is the sum of ledger entries, not of model claims.

Failure modes with LLM agents

• Persuasion moves reservation values. A counterpart's message says the deal expires in a minute and the model concedes. Fix: keep reservation values and concession schedules in code.
• Hallucinated commitments. An agent says it has reserved a slot that it has not. Fix: a commitment exists only when the mechanism writes it to the ledger.
• Collusion and shill agents. Agents controlled by one principal coordinate bids. Fix: authenticate bidders, cap bidders per principal, monitor bid correlation.
• Injection through proposals. A bid's free text tells the manager model to ignore the others. Fix: free text is logged and shown to humans, never parsed for decisions.
• Endless negotiation. Fix: round limits, deadlines and a defined fallback.
• Over-coordination. Running an auction for every small subtask costs more than it saves. Fix: allocate cheap tasks with a static rule and reserve mechanisms for scarce resources.

What to do next

1. List the interactions in your system and mark each as shared-goal or competing-interest.
2. Define bids and offers as schemas; reject anything that does not parse.
3. Compute costs from measurable signals such as queue length, tokens and tier price, not from model estimates.
4. Use a second-price reverse auction for single-task allocation and state its assumptions in your design doc.
5. Keep reservation values, deadlines and concession schedules outside model context.
6. Create a commitment ledger with owners, due times and statuses, and expire overdue entries automatically.
7. Red-team the mechanism with a colluding pair and an injected bid before it handles real budget.