Methodology · Coordinationprovenverified

Coalition Formation

also known as computational coalition formation, coalition structure generation methodology

Applies to: multi-agent-system

Tags: coalition-formationshapleycorenucleoluscooperative-game-theory

Group agents into teams that create the most value together, then split the reward fairly. First write down how much value each possible team can produce. Then find the grouping that maximises total value. Then divide each team's reward using a payoff rule that matches what you need: fairness, stability, or keeping the most upset member as happy as possible. Common rules are a fair-share split (the Shapley value), a no-defection split (the core), and a minimise-the-worst-complaint split (the nucleolus). This is more than ad-hoc team building. It gives compact ways to record team values, an account of which payoff rules you can actually compute, and the fairness-versus-stability trade-offs each rule makes.

Methodology process overview

flowchart TD agents[Agent population + capabilities] --> rep[Choose compact representation of v(S)] rep --> gen[Generate coalition structure: maximise sum v(S)] gen --> sc{Pick solution concept} sc -- fairness --> sh[Shapley value: average marginal contribution] sc -- stability --> core{Core non-empty?} sc -- always-exists --> nuc[Nucleolus: minimise max dissatisfaction] core -- yes --> coreok[Core payoff] core -- no --> eps[Fall back to least-core / epsilon-core / nucleolus] sh --> div[Compute payoff division] coreok --> div eps --> div nuc --> div div --> verify[Verify stability + fairness properties] verify --> out[Coalition structure + payoff + certificate] out -.value landscape shifts.-> agents

Intent. Group agents into teams that maximise joint value and split the reward using a payoff rule whose fairness or stability property matches the deployment.

When to apply. Use this when several agents could pool resources or skills to produce more together than apart, and the hard question is who joins which team and who gets what share. Examples are joint planning, resource pooling, federated computation, and multi-agent task delivery. Don't apply it when agents are interchangeable and any grouping is fine; simple partitioning is enough. One exception: even interchangeable agents may benefit from this when coordinating inside a team is itself costly.

Example scenario

An edge-computing startup runs a federated inference network. Independent operators contribute GPU nodes and split the revenue from serving inference jobs. The hard question is which operators form which serving pools, and how a pool's revenue is divided. Big operators bring raw capacity. Smaller operators may bring rare hardware, such as Hopper cards, or good locations with low latency to a major customer. Applying the methodology, the platform team treated each subset of operators as a team. Its value was the expected revenue if those operators served jointly. With 14 operators, listing all 2^14 team values was feasible to compute once a week from logs. But they used a more compact representation that recorded just the synergies, such as a 'Hopper card plus EU-West location' bonus. To find the grouping, they ran an anytime branch-and-bound capped at 30 seconds and kept the best grouping found in that budget. For splitting the reward they chose the fair-share rule (Shapley value), because operators cared more about being seen as fairly paid than about strict stability, and the platform's reputation depended on it. They computed the fair shares by Monte Carlo sampling over orderings. What they learned: re-forming the teams every Monday caught a slow drift. One operator who had been pivotal lost a key customer's traffic and stopped adding much value. The new fair-share split reflected that within a week and avoided a quarter-long dispute. They documented two known violations honestly. The fair-share split was sometimes not defection-proof, meaning a subgroup could in principle do better by breaking off. They accepted that trade-off because fairness optics outweighed strict stability. The hero-agent failure mode showed up once, when a single operator was contributing 60% of the value. They used that signal to recruit backup capacity.

Inputs

Agent population — The agents that may form teams, with their individual skills and the cost of working together.
Characteristic function — A record of how much value each possible team can produce. When there are many agents, store it compactly instead of listing every team, such as by recording only the synergies between agents.
Solution concept — The chosen rule for splitting a team's reward. Options include a fair-share split (Shapley value), a no-defection split (core), and a split that keeps the most upset member as happy as possible (nucleolus).

Outputs

Coalition structure — A grouping of all the agents into teams that comes as close as possible to maximising total value.
Payoff division — How each team's value is split among its members under the chosen rule.
Stability or fairness certificate — Evidence that the split meets its rule's promise, such as no team wanting to defect or the fair-share conditions holding. Or a clear note where it does not.

Steps (6)

Choose how to record team values
Listing the value of every possible team takes 2^n entries and is infeasible past a small number of agents. Use a compact form that records just the structure, such as the synergies between agents or a weighted graph, so the size stays manageable.
Find the best grouping
Find the grouping of agents that maximises total value. This is hard in general. Use exact search for a few agents, anytime branch-and-bound for medium groups, and bounded heuristics for large ones.
Pick a payoff-splitting rule
Fair-share split (Shapley value): each agent gets its average added value. It is fair but not always defection-proof. No-defection split (core): no subgroup can break off and do better. It is stable but may not exist. Minimise-the-worst-complaint split (nucleolus): it always exists but can be expensive to compute.
Compute the split
Apply the chosen rule and note its computational cost. For the no-defection split, first check that it exists. If it does not, fall back to a relaxed version, or switch to the minimise-the-worst-complaint split.
Verify stability and fairness
Stability check: for any agent, could some subgroup give it a strictly better payoff? Fairness check: does the split treat equal contributors equally and give zero-contributors nothing? If you tolerate a violation, write it down. A silent violation destroys trust in the mechanism.
Re-plan when agents or values shift
Team values do not stay fixed. New agents arrive, skills change, and prices move. Schedule regular re-forming instead of treating the first grouping as permanent.

Framework-specific instructions

Pick a framework and generate a framework-targeted rewrite of this methodology's steps.

Choose framework

AI-generated for Agent Development Kit (ADK) (Google) — verify against official docs.

Principles

Record team values compactly. Listing all 2^n team values is rarely feasible.
Choosing a payoff rule is a fairness-versus-stability trade-off. Pick on purpose and document the trade.
Finding the best grouping is hard in general. Bound it with an anytime algorithm.
Teams are not permanent. Re-form them when the value landscape shifts.

Known failure modes (3)

Related patterns (3)

Related methodologies (1)

Auction-Based Task Allocation★★
6 steps
Choose and set up an auction that rewards honest bidding, so self-interested agents reveal their true values and the tasks go where they are worth the most.

Sources (2)

Provenance

Added to catalog: 2026-05-24
Last updated: 2026-05-27
Verification status: verified

Methodology process overview

Steps (6)

Choose how to record team values

Find the best grouping

Pick a payoff-splitting rule

Compute the split

Verify stability and fairness

Re-plan when agents or values shift