Skip to content
Tutorials Center
My learning

Topics

Lesson 31 of 37 ยท Applications

Cooperative Games and the Shapley Value

Split the gains of cooperation fairly: coalitions, characteristic functions, the core and the Shapley value, with Python code and a cost-sharing example.

Most of this course has treated games as non-cooperative: players choose actions on their own, and any agreement has to be self-enforcing. In cooperative (coalitional) game theory, the focus moves to what groups of players can achieve if they work together, and how to divide the surplus. Typical questions: how should three airlines share the cost of a runway? How much credit does each feature deserve in a machine-learning model? How should a company's profit be split among partners?

Coalitional games

A transferable-utility (TU) coalitional game is a set of players N and a characteristic function v. For every coalition S (a subset of N), v(S) is the total value the members of S can secure by themselves. We assume v(empty set) = 0. A solution assigns each player a share x_i with the total equal to v(N), the value of the grand coalition.

Example: three players. Alone each makes nothing. Any pair makes 60. All three make 100. So v({1}) = v({2}) = v({3}) = 0, v({i, j}) = 60, v({1, 2, 3}) = 100.

Cooperative games

Coalitions Any subset of players
Characteristic function v(S): what S can earn alone
Allocation Split v(N) among players
Fairness and stability Shapley value and the core
1 / 2

The core

An allocation is in the core if no coalition can do better by leaving: for every S, the sum of x_i for i in S is at least v(S). It captures stability. In the example, an even split (33.3, 33.3, 33.3) gives each pair 66.7, which beats the 60 they could get alone, so it is in the core.

The core can be empty. If every pair can earn 80 and the grand coalition earns only 100, then the three pair requirements sum to 240 but the total shares add to 100, which is impossible.

Python Is an allocation in the core? Is the core empty?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Shapley value

Lloyd Shapley proposed a unique allocation that satisfies four fairness axioms:

  • Efficiency: the shares add up to v(N).
  • Symmetry: players who contribute equally get equal shares.
  • Dummy: a player who adds nothing to any coalition gets nothing.
  • Additivity: the shares of two games added together equal the shares of the sum game.

It has a vivid description. Imagine the players arriving one at a time in a random order. When player i arrives, they add their marginal contribution v(S plus i) - v(S) to the players already present, S. The Shapley value of i is their marginal contribution averaged over all n! orders:

phi_i = average over orderings of (v(S_i plus i) - v(S_i))

Python Shapley value by averaging over all orders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the symmetric game each player gets 33.33. In the second game the shares sum to 100, with A (who starts the value) getting the most. The brute-force approach needs n! orders, which is only feasible for about 10 players. For larger games use Monte Carlo sampling of random orders.

A faster formula and a Monte Carlo version

The Shapley value can also be written as a weighted sum over coalitions: for each S not containing i, the weight is |S|! (n - |S| - 1)! / n!. The sampled version estimates the same average by drawing random permutations.

Python Sampling the Shapley value

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

By symmetry, all six get v(N) / 6 = 18. The sampled version is close, and it scales to large games.

Uses of the Shapley value

  • Cost sharing: airport landing fees (the classic "airport game"), shared infrastructure, joint projects.
  • Voting power: the Shapley-Shubik index is the Shapley value of a game where a coalition has value 1 if it can pass a vote.
  • Machine learning: SHAP explains a model's prediction by treating each feature as a player and the model's output as the coalition value.
  • Attribution: splitting credit for a conversion among advertising channels.

The Shapley value need not lie in the core, so it is "fair" but not always "stable" in the coalition sense. For convex games (where larger coalitions get larger marginal contributions) it does belong to the core.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the characteristic function v(S) give?

    It describes what each group of players could achieve, which is the basis for deciding allocations.
  2. 2. When is an allocation in the core?

    Core allocations are stable: every coalition gets at least what it could earn alone.
  3. 3. How is the Shapley value computed?

    That is its defining description, and it satisfies the efficiency, symmetry, dummy and additivity axioms.
  4. 4. Which is a known use of the Shapley value in machine learning?

    SHAP treats features as players and the model output as the coalition value.

Summary

  • Cooperative games describe what coalitions can achieve (characteristic function) and how to share the total.
  • The core collects stable allocations; it can be empty.
  • The Shapley value averages marginal contributions over all orders and is the unique allocation satisfying four axioms.
  • Exact computation needs n! orders or 2^n coalitions; sampling scales it.
  • Applications include cost sharing, voting power and model explanations.

Next: Stable Matching and the Gale-Shapley Algorithm