Cooperative Games

Why this concept exists (motivation first)

In many real systems, value is produced by groups, not isolated individuals:

• •A set of companies shares infrastructure and reduces costs.
• •A team of sensors triangulates a target better than any single sensor.
• •Multiple ML models ensemble to improve accuracy.
• •Countries form trade blocs.

In these settings, the core strategic issue is not “Which action do I pick in a payoff matrix?” but:

1. 1)Which coalitions can form?
2. 2)What value can each coalition create?
3. 3)How should we divide the total value of cooperation among individuals?

Cooperative game theory abstracts away the internal bargaining process and focuses on the outcome space of cooperation.

Players and coalitions

Let N = {1,2,…,n} be the set of players. A coalition is any subset S ⊂ N. Think of S as a group that can coordinate and act as a unit.

Two immediate observations:

• •There are 2ⁿ coalitions (including ∅ and N). This combinatorial explosion is why computation becomes hard at difficulty 5.
• •We often care most about the grand coalition N, because it typically produces the most total value—but only if the split is acceptable.

Transferable Utility (TU) and the characteristic function

In a transferable utility (TU) cooperative game, coalitions can generate a single real-valued “pie” that can be freely redistributed among coalition members. The game is defined by a characteristic function:

• •v: 2ᴺ → ℝ
• •v(S) = total value coalition S can guarantee for itself

Common conventions:

• •v(∅) = 0
• •Sometimes monotonicity is assumed: if S ⊂ T then v(S) ≤ v(T), but this is not required.

Intuition: v(S) is the best total payoff S can secure by coordinating internally (and possibly acting against outsiders).

The allocation problem

An allocation (also called an imputation in some contexts) is a vector x = (x₁,…,xₙ) that assigns each player i a payoff xᵢ.

Two baseline requirements often appear:

1. 1)Efficiency (budget balance):

∑ᵢ xᵢ = v(N)

2. 2)Individual rationality (participation):

xᵢ ≥ v({i}) for all i

Efficiency says we split the entire grand-coalition value. Individual rationality says nobody should get less than they can guarantee alone.

But these are not enough. There are usually many efficient allocations, and many individually rational ones. We need a principle for fairness and/or stability.

Marginal contribution as the atomic unit

A central primitive is the marginal contribution of player i to a coalition S (not containing i):

• •Δᵢ(S) = v(S ∪ {i}) − v(S)

This measures the incremental value created when i joins S.

Why this matters: any reasonable allocation rule must “pay attention” to contributions across different contexts. A player might be crucial when paired with certain others, and irrelevant elsewhere. Cooperative game theory gives a systematic way to aggregate these context-dependent contributions into a single number φᵢ.

What cooperative games are not

It’s easy to confuse cooperative games with “players cooperate in a matrix game.” Cooperative games (in this TU characteristic-function form) do not specify:

• •A timeline of moves
• •Strategies
• •Detailed bargaining

They specify coalition values and then analyze allocation rules and stability concepts (like the core, which we’ll connect to later).

Why fairness is tricky

If v(N) is large, you might think forming N is automatic. But if a subgroup S believes it can do better on its own, it can threaten to break away.

That creates two intertwined design goals:

• •Stability: no coalition wants to deviate.
• •Fairness: allocation reflects contributions in a principled way.

These are not always compatible. Some games have no stable split that satisfies all coalitions (empty core), but still have a well-defined fair split (e.g., Shapley value).

Superadditivity and synergy

A common (not mandatory) assumption is superadditivity:

• •For disjoint S,T ⊂ N: v(S ∪ T) ≥ v(S) + v(T)

This expresses synergy: merging coalitions doesn’t destroy value.

If superadditivity holds broadly, the grand coalition is socially attractive. But even then, the division is contentious.

The idea of “value created by a player” depends on context

In cooperative games, contributions are not fixed numbers like “player i is worth 5.” Instead:

• •Player i might add a lot to a small coalition but little to a large one.
• •Two players might be substitutes (either one is enough), or complements (both needed).

This is why marginal contribution Δᵢ(S) depends on S.

A quick contrast of allocation philosophies

Here are some common allocation ideas and why Shapley stands out.

Shapley’s key move is to treat “who joins first” as a source of symmetry and average across it.

The permutation viewpoint (intuition)

Imagine players enter a room one by one in a random order. When player i enters, they join the set of players already present S, and the coalition value increases from v(S) to v(S ∪ {i}).

The increment:

• •v(S ∪ {i}) − v(S)

is credited to i for that arrival order.

Fairness idea: since no arrival order is privileged, we average i’s credited increments over all n! possible orders.

This is exactly the Shapley value.

The subset-weight viewpoint (how the same idea becomes a formula)

For a fixed player i, each subset S ⊂ N \ {i} can appear as “the set of players who arrived before i” in many permutations.

If |S| = k, then:

• •S’s members can be ordered in k! ways before i
• •the remaining (n − k − 1) players can be ordered after i in (n − k − 1)! ways
• •total permutations: n!

So the probability that “exactly S arrives before i” under a uniform random permutation is:

• •k! (n − k − 1)! / n!

This produces a closed form:

φᵢ(v) = ∑_{S ⊂ N\{i}} [ |S|! (n − |S| − 1)! / n! ] · ( v(S ∪ {i}) − v(S) )

This is the same averaging idea, just regrouped by subset rather than enumerating permutations.

What makes an allocation rule convincing?

Shapley value is often taught via axioms because axioms clarify what kind of fairness you are buying. The standard axioms are:

1. 1)Efficiency: ∑ᵢ φᵢ = v(N)
2. 2)Symmetry: if players i and j contribute identically to every coalition, they get the same payoff
3. 3)Dummy (null player): if v(S ∪ {i}) = v(S) for all S, then φᵢ = 0
4. 4)Additivity: for two games v and w, φᵢ(v + w) = φᵢ(v) + φᵢ(w)

A remarkable theorem (Shapley, 1953): There is a unique allocation rule satisfying these axioms. That unique rule is φ.

At difficulty 5, it’s worth pausing on additivity: it says if total value is the sum of two independent “sources” of value, then the allocated payoff should sum as well. This linearity becomes powerful for decomposition and computation, and it’s one reason Shapley shows up in ML feature attribution.

A short derivation sketch: why the subset weights look like factorials

Let n = |N|. Fix i. Consider a subset S not containing i.

Number of permutations π where S is exactly the set before i:

• •Arrange S before i: |S|!
• •Arrange remaining N \ (S ∪ {i}) after i: (n − |S| − 1)!

So count = |S|! (n − |S| − 1)!

Uniform over n! permutations ⇒ weight:

w(S) = |S|! (n − |S| − 1)! / n!

Then:

φᵢ = ∑_{S ⊂ N\{i}} w(S) · (v(S ∪ {i}) − v(S))

This shows exactly how combinatorics encodes the “random order” fairness principle.

Why the axioms matter (before the math)

Many allocation rules sound plausible until you test them against edge cases:

• •What if two players are indistinguishable in every coalition? (symmetry)
• •What if someone adds no value anywhere but still demands a share? (dummy)
• •What if value comes from two independent projects and you’re splitting both at once? (additivity)

The Shapley axioms are designed to remove these ambiguities.

The Shapley value definition (two equivalent forms)

Let N be the player set, n = |N|.

Permutation form

Let Π be the set of all permutations of N. For a permutation π, define Preᵢ(π) as the set of players appearing before i.

Then:

φᵢ(v) = (1 / n!) · ∑_{π ∈ Π} [ v(Preᵢ(π) ∪ {i}) − v(Preᵢ(π)) ]

Subset form

φᵢ(v) = ∑_{S ⊂ N\{i}} \frac{|S|! (n − |S| − 1)!}{n!} ( v(S ∪ {i}) − v(S) )

Efficiency proof (showing the work)

A key sanity check: do the φᵢ sum to v(N)? Yes.

Using the permutation form, sum over i:

∑_{i ∈ N} φᵢ

= ∑_{i ∈ N} (1/n!) ∑_{π ∈ Π} [ v(Preᵢ(π) ∪ {i}) − v(Preᵢ(π)) ]

Swap sums:

= (1/n!) ∑_{π ∈ Π} ∑_{i ∈ N} [ v(Preᵢ(π) ∪ {i}) − v(Preᵢ(π)) ]

Now fix a permutation π = (i₁,i₂,…,iₙ). The inner sum telescopes:

Let S₀ = ∅

S₁ = {i₁}

S₂ = {i₁,i₂}

…

Sₙ = N

Then the increments are:

v(S₁) − v(S₀)

• •v(S₂) − v(S₁)
• •…
• •v(Sₙ) − v(S_{n−1})

Telescoping gives:

= v(Sₙ) − v(S₀) = v(N) − v(∅) = v(N)

So for each π, the inner sum equals v(N). Therefore:

∑_{i ∈ N} φᵢ

= (1/n!) ∑_{π ∈ Π} v(N)

= (1/n!) · (n!) · v(N)

= v(N)

That’s efficiency.

Symmetry and dummy (intuitions)

• •Symmetry: If i and j have identical marginal contributions for all S, then averaging over orders cannot distinguish them, so φᵢ = φⱼ.
• •Dummy: If i never changes v(S), then every marginal term is 0, so φᵢ = 0.

Additivity (why it’s a big deal)

Suppose v describes profit from “Project A” and w from “Project B”, and the combined situation is (v + w)(S) = v(S) + w(S).

Then for any coalition S:

(v + w)(S ∪ {i}) − (v + w)(S)

= [v(S ∪ {i}) + w(S ∪ {i})] − [v(S) + w(S)]

= [v(S ∪ {i}) − v(S)] + [w(S ∪ {i}) − w(S)]

Averaging preserves sums, so φᵢ(v + w) = φᵢ(v) + φᵢ(w).

This linearity means you can often decompose a complex value function into simpler components (when structure is available), compute Shapley on each, and sum.

Computational reality: exact Shapley is expensive

The subset formula includes all S ⊂ N\{i}: that’s 2^{n−1} subsets per player, and n players.

• •Naïve exact cost: Θ(n 2ⁿ)

For n = 30, 2ⁿ is already ~1 billion.

So in large systems, people use approximations:

• •Monte Carlo permutations: sample K random orders, average marginal contributions.
• •Structure exploitation: if v has special form (e.g., weighted voting), compute φ via dynamic programming.

A useful Monte Carlo estimator:

φᵢ ≈ (1/K) ∑_{k=1}^K [ v(Preᵢ(πₖ) ∪ {i}) − v(Preᵢ(πₖ)) ]

By the law of large numbers, this converges to φᵢ as K grows.

Weighted voting games (an important class)

A weighted voting game is often written as:

• •players have weights wᵢ ≥ 0
• •quota q
• •coalition S is “winning” if ∑_{i∈S} wᵢ ≥ q

Characteristic function typically:

v(S) = 1 if S is winning, else 0

Shapley value here becomes the Shapley–Shubik power index: the probability a player is pivotal (their addition turns a losing coalition into a winning one) under a random order.

This bridges cooperative games to political science and reliability theory.

Relation to stability: the core (preview)

The core is the set of allocations x such that:

• •∑ᵢ xᵢ = v(N)
• •For all coalitions S: ∑_{i∈S} xᵢ ≥ v(S)

This says no coalition S can do better by leaving, because the members of S already receive at least v(S) in total.

Shapley value is not guaranteed to lie in the core. When it does, you get an allocation that is both fair (axiomatic) and stable (coalition-proof).

At difficulty 5, it’s helpful to keep the conceptual separation:

• •Shapley: fairness by averaging contributions.
• •Core: stability by blocking deviations.

They answer different “why should I accept this split?” questions.

Why cooperative-game allocations show up everywhere

Any time you can measure the value of a group, you can ask how to assign credit or cost:

• •Cost sharing: how to split a shared network bill.
• •Joint ventures: how to divide profit from collaboration.
• •Political power: how much influence a voting member has.
• •ML explainability: how to attribute a prediction to features.

The same mathematics appears under different names.

Cost sharing example (intuition)

Suppose several departments share a cloud contract. Coalition value might represent savings compared to buying alone. Then Shapley assigns each department an expected marginal savings contribution, producing a principled discount allocation.

A key modeling step is deciding what v(S) means:

• •v(S) could be negative cost (so higher is better), or
• •v(S) could be “savings” relative to baseline.

The Shapley math works as long as v is consistent; interpretation changes with sign.

Power in committees: pivotality

In a weighted voting game with v(S) ∈ {0,1}, φᵢ is the probability that i is pivotal in a random order.

This can diverge sharply from weight share. A player with moderate weight can have outsized power if they frequently “complete” winning coalitions.

ML connection: Shapley as feature attribution

In many ML explanation methods (e.g., SHAP), features are treated like “players,” and v(S) is the model’s expected prediction when only features in S are “present.” Then:

• •φᵢ ≈ contribution of feature i to the prediction

The axioms (efficiency, symmetry, dummy, additivity) become desiderata for explanations:

• •Efficiency: contributions sum to the difference between prediction and baseline.
• •Dummy: irrelevant features get 0.

This is not a coincidence: SHAP is explicitly built from Shapley values.

Choosing between fairness and stability (when they conflict)

In some applications, you might prioritize:

• •Fairness: choose Shapley even if some coalition could object.
• •Stability: choose a core allocation (if core is nonempty), even if it deviates from Shapley.

A practical perspective:

Modeling warnings (what can break the interpretation)

• •TU assumes the coalition’s value is a transferable scalar. Some settings have nontransferable utility (NTU), requiring different tools.
• •v(S) must reflect what S can do on its own. If it instead reflects something like “market value with outsiders cooperating,” the stability interpretation changes.
• •In ML, the definition of “feature missing” is subtle; different baselines change v(S), changing φ.

Where this node fits in the tech tree

Cooperative games sit at a crossroads:

• •From basic game theory, you bring rational agents and incentives.
• •From probability/expected value, you bring averaging over random orders.
• •Next, you can branch into stability concepts (core), solution refinements (nucleolus), computational methods, or ML explanation frameworks.

A useful mental model: Shapley is expected marginal contribution under a symmetry assumption (random order). If you remember that, you can re-derive the formulas whenever needed.