VI · Multi-AgentExperimental·

Coalition Formation

also known as Ad-Hoc Team Formation, Cooperative Subgroup

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.

Context

A multi-agent system holds many agents with overlapping capabilities. Some tasks are super-additive — three agents working as a coalition deliver more than they would individually. Other tasks are sub-additive. Without a coalition-formation step, agents act in isolation and the super-additive value is left on the floor.

Problem

Static team rosters do not match the problem. Some problems need three specialists, others need eight generalists, others need only the agent who already holds context. Either there is a fixed multi-agent topology that wastes capacity on small problems and underprovisions for large ones, or there is no coordination and the agents work alone. Worse, when a coalition does form ad hoc, the credit/payoff allocation is implicit and political: contributors who did the heaviest lifting do not get the credit, and over time agents stop volunteering.

Forces

  • Coalition value depends on the problem and on which agents join.
  • Joining is a cost — at least the coordination overhead — that the joining agent must expect to recover.
  • Credit / payoff sharing must be principled or contributors disengage.
  • Coalition dissolution must be clean — agents return to the pool.

Example

A document-analysis platform holds 15 specialist agents. A new task arrives: 'review this 60-page contract'. The coordinator forms a coalition of the legal-clause specialist, the entity-extractor, and the redline-comparator (skipping the design-review agent). Payoff (compute budget, reputation credit) is split per Shapley value on a small holdout eval. After the task the three return to the pool.

Diagram

Solution

Therefore:

Define a value function v(S) for any subset S of agents on a given task. A coalition-formation protocol enumerates candidate coalitions, scores them, and chooses the one with the best value/cost ratio. A payoff-allocation rule (Shapley value, equal split, proportional to contribution, weighted by reputation) determines how the coalition's reward is split. Coalitions are temporary: once the task is done, the coalition dissolves and agents return to the pool. For LLM agents this can be lighter — a coordinator picks a few agents per task based on heuristics rather than full optimisation.

What this pattern forbids. Multi-agent teams must not be static when task shape varies; coalitions form per-task with an explicit value function and a declared payoff-allocation rule.

The smaller patterns that complete this one —

  • usesWorld Model as Tool·— Let a planning agent invoke a generative world model as a tool to roll out hypothetical futures before committing to an action, treating the world model as a callable simulator rather than a training target.

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

  • complementsContract Net Protocol★★— 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.
  • alternative-toSupervisor★★— Place a coordinating agent above a set of specialised agents and route work to them.
  • 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.
  • 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.
  • composes-withJoint Commitment Team·— A team of agents adopts a shared goal plus the meta-commitment that each member will notify the others as soon as it believes the goal is achieved, impossible, or no longer relevant.

Neighbourhood

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

Used in recipes

References

Provenance