Coalition Formation
Agents form temporary subgroups around super-additive tasks — explicit rules determine who joins, how the coalition works, and how payoff is split when the task is done.
Intent & Description
🎯 Intent
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. Without a coalition-formation step, agents act in isolation and the super-additive value is left on the table.
💡 Solution
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 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, they dissolve 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 optimization.
Real-world Use Case
- Agents have heterogeneous capabilities and tasks vary wildly in required shape.
- Some tasks are demonstrably super-additive in agent contribution.
- Reputation or payoff allocation matters for sustained agent engagement.
Source
📌 TL;DR
Score candidate agent subsets, assemble the coalition that maximizes value, run the task, split the payoff, dissolve — repeat per task rather than maintaining a fixed team.
Advantages
- Team shape matches the problem shape — no forcing a task into a fixed crew.
- Super-additive tasks unlock value that solo or fixed-team operation misses.
- Explicit payoff rule keeps contributors engaged and accountable.
Disadvantages
- Enumerating coalitions is exponential in agent count without heuristic pruning.
- Payoff allocation rules each have failure modes — no rule is universally fair.
- Coalition-formation overhead can exceed the task value for small or simple problems.