Cooperative Games and Coalitions

"We agreed to pool our payloads and split the proceeds. The argument was never about whether to cooperate; it was about who deserved what, and whether anyone could storm off and do better alone."

A Coalition Mid-Negotiation

In Section 28.3 we studied agents that choose actions independently and cannot make their promises binding; the Nash equilibrium told us where such non-cooperative play settles. Many multi-agent systems are not like that. A team of delivery robots can agree, in advance and enforceably, to pool their capacity and share the revenue. A set of data owners can commit to train a model together and split the credit. A group of compute providers can form a consortium and divide the bill. In all of these the agents can form a coalition, a subset that acts as one, and the binding contract changes the question we must answer. We no longer ask which single-agent action is a best response; we ask which coalitions form and how the value they jointly create is divided. That is the subject of cooperative, or coalitional, game theory.

1. The Characteristic Function: What Each Coalition Can Secure Beginner

A cooperative game with transferable utility is specified compactly. Let $N = \{1, 2, \dots, n\}$ be the set of agents. A coalition is any subset $S \subseteq N$, and the whole set $N$ is the grand coalition. The game is given by a single object, the characteristic function $v$, which assigns to every coalition $S$ a number $v(S)$, the total value that the members of $S$ can guarantee themselves by cooperating, regardless of what the agents outside $S$ do. By convention the empty coalition is worth nothing, $v(\emptyset) = 0$. Everything else, who should team up and who deserves what, is read off from this one function.

Cooperation is worthwhile precisely when teams are worth more than the sum of their parts, a property called superadditivity: for disjoint coalitions $S$ and $T$, $v(S \cup T) \ge v(S) + v(T)$. When this holds, merging never hurts, so the grand coalition $N$ creates the most total value and the interesting question is purely distributive: how do we split $v(N)$? The difficulty is that the agents are still self-interested. They will cooperate only if their slice of the joint value is at least as large as anything they could secure on their own or in a breakaway subgroup. A division that ignores this invites defection, and a coalition that is one defection away from collapse is not a coalition at all.

To make this concrete we will carry one running example: three delivery robots, $A$, $B$, and $C$. Working alone, $A$ completes 10 deliveries an hour, while $B$ and $C$ manage only 4 each. Paired up they specialize and do far better, and the full trio does best of all. Figure 28.4.1 shows the lattice of all eight coalitions with the value each can secure, the raw material from which both stability and fairness are computed.

2. The Core: Divisions Nobody Can Improve On by Leaving Intermediate

Suppose the grand coalition forms and produces $v(N)$. A payoff vector $x = (x_1, \dots, x_n)$ proposes to give agent $i$ the amount $x_i$. For this to be a credible division of exactly what was created, it must be efficient, meaning it hands out the whole pie and no more:

Efficiency alone is not enough. A coalition $S$ that is offered $\sum_{i \in S} x_i$ in total but could secure $v(S)$ for itself by walking out will walk out whenever $v(S)$ is larger. A division survives only if every coalition is offered at least what it could get alone. That condition, applied to all $2^n$ coalitions at once, defines the core: the set of efficient payoff vectors satisfying

An allocation in the core is stable in a strong sense. No subset of agents, however clever, can point to a way of doing strictly better by seceding, so the grand coalition holds together with no further enforcement. This is exactly the property a system designer wants when the goal is to get self-interested machines to cooperate at all, a thread we picked up in Section 27.7 on the stability of cooperation in distributed AI: a value-sharing rule that lands outside the core is an invitation for the most valuable agents to defect.

The catch is that the core can be empty. Some games have no division that simultaneously satisfies every coalition; whatever you propose, some subgroup is always tempted to break away, and the grand coalition is inherently unstable. The classic example is three agents who each create value only in a pair, where any two can always profitably abandon the third. Emptiness is not a defect of the analysis; it is the analysis correctly reporting that no stable grand coalition exists, which is itself crucial information when designing a system that depends on agents staying together.

3. The Shapley Value: Fairness as Average Marginal Contribution Intermediate

The core asks for stability and may deliver many answers or none. A different question is fairness: of all the ways to split $v(N)$, is there a single division that is demonstrably even-handed? Lloyd Shapley answered this in 1953 by writing down a few axioms any fair division ought to satisfy and proving that exactly one rule meets them all. The axioms are mild and hard to argue with. Efficiency: the whole value is distributed. Symmetry: two agents who contribute identically to every coalition receive equal pay. Null player: an agent that adds nothing to any coalition is paid nothing. Additivity: the value of two independent games run together is the sum of the separate values. The unique rule satisfying all four is the Shapley value.

Its definition is an average of marginal contributions. Imagine the agents joining the coalition one at a time in some order. When agent $i$ joins a partially formed coalition $S$, it adds value $v(S \cup \{i\}) - v(S)$, its marginal contribution in that order. The Shapley value $\phi_i$ pays agent $i$ the average of this marginal contribution over all $n!$ possible orderings:

where $\Pi$ is the set of all orderings of the agents and $P_i^\pi$ is the set of agents that precede $i$ in ordering $\pi$. Equivalently, grouping orderings that produce the same predecessor set $S$ gives the familiar weighted-subset form,

By construction the shares sum to $v(N)$, so the Shapley value is always efficient. It rewards an agent for what it genuinely adds, averaged so that no agent is privileged by being asked to join first or last. Figure 28.4.2 traces all six orderings of our three robots and shows agent $A$'s marginal contribution in each, the numbers that average to its Shapley value.

4. Computing Both, and Seeing Where They Disagree Intermediate

The two concepts answer different questions, and a small program makes the distinction tangible. The code below builds our three-robot game as a characteristic function, computes the Shapley value by averaging marginal contributions over every ordering exactly as the formula prescribes, then tests two candidate divisions for core membership: the Shapley value itself, and a naive equal split that hands each robot a third of the total. Core membership is checked by verifying that every one of the $2^n$ coalitions is offered at least the value it could secure alone.

from itertools import permutations, combinations

# Three robots cooperating on a delivery task. The characteristic function v(S)
# gives the value (deliveries completed per hour) that coalition S can secure on
# its own. A carries packages, B drives fast, C navigates; pairs and the trio do
# strictly better than the sum of singletons (the gains from cooperation).
agents = ["A", "B", "C"]
v = {
    frozenset(): 0,
    frozenset(["A"]): 10,
    frozenset(["B"]): 4,
    frozenset(["C"]): 4,
    frozenset(["A", "B"]): 32,
    frozenset(["A", "C"]): 26,
    frozenset(["B", "C"]): 14,
    frozenset(["A", "B", "C"]): 42,
}
grand = frozenset(agents)

# ---- Shapley value: average marginal contribution over all join orderings ----
def shapley(agents, v):
    n = len(agents)
    phi = {a: 0.0 for a in agents}
    orderings = list(permutations(agents))
    for order in orderings:
        joined = set()
        for a in order:
            before = frozenset(joined)
            after = frozenset(joined | {a})
            phi[a] += v[after] - v[before]   # a's marginal contribution here
            joined.add(a)
    for a in agents:
        phi[a] /= len(orderings)
    return phi

phi = shapley(agents, v)
print("Shapley value (fair share of the %d total):" % v[grand])
for a in agents:
    print("  agent %s : %6.2f" % (a, phi[a]))
print("  sum      : %6.2f   (must equal v(grand)=%d)" % (sum(phi.values()), v[grand]))

# ---- Core membership: no coalition can do better by breaking away ----
def in_core(x, agents, v):
    # efficiency: the whole value is shared
    if abs(sum(x[a] for a in agents) - v[frozenset(agents)]) > 1e-9:
        return False, "not efficient"
    # coalition rationality: every subset gets at least what it could secure alone
    for r in range(1, len(agents) + 1):
        for S in combinations(agents, r):
            payoff = sum(x[a] for a in S)
            if payoff + 1e-9 < v[frozenset(S)]:
                return False, "coalition %s could secure %d but only gets %.1f" % (
                    "".join(S), v[frozenset(S)], payoff)
    return True, "stable: no coalition can improve by leaving"

ok, reason = in_core(phi, agents, v)
print("\nIs the Shapley allocation in the core? %s" % ("YES" if ok else "NO"))
print("  reason: %s" % reason)

# A tempting but UNSTABLE equal split, for contrast.
equal = {a: v[grand] / 3 for a in agents}
ok2, reason2 = in_core(equal, agents, v)
print("\nIs the equal split (%.0f each) in the core? %s" % (v[grand] / 3, "YES" if ok2 else "NO"))
print("  reason: %s" % reason2)

Shapley value (fair share of the 42 total):
  agent A :  21.00
  agent B :  12.00
  agent C :   9.00
  sum      :  42.00   (must equal v(grand)=42)

Is the Shapley allocation in the core? YES
  reason: stable: no coalition can improve by leaving

Is the equal split (14 each) in the core? NO
  reason: coalition AB could secure 32 but only gets 28.0

The lesson in those few lines is the whole point of the section. An intuitively fair rule (split evenly) can be unstable, dissolving the coalition it was meant to hold together, while a rule grounded in marginal contribution can be both fair and stable at once. When the Shapley value happens to lie in the core, as it does here, a system designer gets the best of both worlds: a division agents accept as just and one no subgroup wants to escape. The Shapley value does not always land in the core, and the core is sometimes empty, but when they coincide the value-sharing question has a clean answer.

5. Coalition Formation as a Distributed Problem Advanced

So far we assumed the grand coalition forms and asked only how to divide its value. In many multi-agent systems the prior question is live: which teams should form in the first place? When ten robots face a set of tasks, the best outcome may not be one giant team but a partition of the agents into several disjoint coalitions, each tackling a task it is suited to. Choosing that partition to maximize total value is the coalition structure generation problem, and agents must often solve it themselves through distributed negotiation, with no central planner dictating the teams. This is the multi-robot, multi-task setting taken up directly in Section 29.7 on coalition formation, and it drives the team assembly of the drone-swarm case study in Chapter 39.

The difficulty is combinatorial and severe. The number of coalitions is already $2^n$, and the number of ways to partition $n$ agents into coalitions, the Bell number, grows even faster: 5 agents admit 52 partitions, 15 agents admit over a billion. Evaluating every coalition structure to find the optimum is hopeless beyond a handful of agents, and computing the characteristic function itself may be expensive when each $v(S)$ requires solving a planning or scheduling subproblem. Real systems therefore lean on approximation: anytime algorithms that return progressively better structures and can be stopped when the budget runs out, greedy merge-and-split heuristics where agents locally agree to join or break apart, and compact representations of the characteristic function that avoid listing all $2^n$ values explicitly. The Shapley value inherits the same blow-up, since the exact formula sums over $n!$ orderings; for games beyond a dozen agents it is estimated by Monte Carlo sampling of random orderings rather than enumerated, the same trick we will rely on for its machine-learning incarnation.

import shap                      # pip install shap

# model: any trained predictor; X: the feature rows to explain
explainer = shap.Explainer(model, X_background)   # treats each feature as a "player"
shap_values = explainer(X)                         # Shapley value of every feature, per row

shap.plots.bar(shap_values)      # average marginal contribution of each feature

6. Where Cooperative Games Sit in the Larger Story Beginner

This section answered the cooperative half of game theory: given that agents can form binding teams, which teams are stable and how should the joint value be divided. The characteristic function compressed the game to the value of every subset; the core identified divisions no coalition would flee; the Shapley value singled out the unique fair division and, when it falls in the core, gave a split that is fair and stable together. These tools turn "should these agents cooperate?" into a question with computable, defensible answers, which is precisely what a designer of self-interested distributed agents needs.

What we have not yet asked is which outcomes are good for the group as a whole, independent of how the value is split. A division can be perfectly stable yet leave total welfare on the table, and comparing whole outcomes rather than individual shares requires a different yardstick. Section 28.5 takes up social welfare and Pareto optimality, the criteria for judging an outcome's collective quality, and connects them back to the equilibria and coalitions we have now built.