The Feasible Region · Topic 13 of 33 · reading step 21 of 33 · Many goals and players

Cooperative games and the Shapley value

If a team earns money together, who earned how much of it?

  1. 01
  2. 02
  3. 16
  4. 03
  5. 17
  6. 04
  7. 05
  8. 19
  9. 21
  10. 10
  11. 06
  12. 18
  13. 07
  14. 08
  15. 20
  16. 22
  17. 09
  18. 23
  19. 11
  20. 12
  21. 13
  22. 14
  23. 15
  24. 25
  25. 26
  26. 27
  27. 28
  28. 29
  29. 30
  30. 31
  31. 32
  32. 33
  33. 24
About this section: Many goals and players

Topic 23 keeps one decision-maker but gives them several objectives that genuinely conflict, so “optimal” stops being a point and becomes a curve. Game theory (topics 11 to 15) drops the other assumption: when another party is also choosing in response to you, your best plan depends on theirs and there is no single answer to compute, only an equilibrium to find. It underwrites markets that clear through auctions, security proofs written as games between an adversary and a defender, and populations that settle into stable mixes of strategy.

See it

1 🧤L 2 🧤R 3 🧤R v(1) = 0 v(2) = 0 v(3) = 0 v(1,2) = $1 v(1,3) = $1 v(2,3) = 0 v(1, 2, 3) = $1: only one pair is ever sellable
The "glove game." Player 1 holds the scarce half of every deal. A pair sells for $1; a lone glove sells for nothing; the grand coalition is worth exactly $1, no more, because a third glove of the same hand adds nothing. The Shapley value below computes exactly how that dollar should split, and it is not an even three-way share.

The intuition

Topics 11 and 12 asked what stable, non-cooperative play looks like. Cooperative game theory asks a different question: given that a group creates value together, how should the value be split fairly among them? Cost-sharing a shared warehouse, splitting a startup's equity, dividing a prize a whole team won: all the same question with a different noun.

The Shapley value (Shapley, 1953) answers it by asking, for each player, "across every possible order in which people could have joined this coalition, how much did adding me change the total value, on average?" A player who is essential wherever they arrive gets a large share. A player who never changes the outcome (a spare wheel) gets exactly zero, however friendly the room is.

What makes it worth naming after one person is that it is not merely a reasonable split. Shapley proved it is the unique split satisfying four properties nearly everyone agrees a fair split should have: stated precisely below. Reasonable-sounding fairness rules turn out to pin down one specific formula.

The mathematics

For a coalitional game with value function v (v(S) = the worth of any subset S of the n players, v(∅) = 0), player i's Shapley value averages their marginal contribution over every possible arrival order:

φᵢ = (1/n!) · Σ over all orderings π [ v(Pᵢ(π) ∪ {i}) − v(Pᵢ(π)) ]

where Pi(π) is the set of players arriving before i in ordering π. Uniqueness (Shapley, 1953): φ is the only allocation rule satisfying efficiency (the whole value v(N) gets fully distributed), symmetry (two players who contribute identically get identical shares), the dummy/null player property (a player who adds zero value in every coalition gets zero), and additivity (the value of two combined games is the sum of the two separate allocations).

Worked exactly on the glove game (6 orderings of 3 players, player 1's marginal contribution in each):

order 1,2,3: v(1)−v(∅)=0 order 2,1,3: v(1,2)−v(2)=1 order 1,3,2: v(1)−v(∅)=0 order 2,3,1: v(1,2,3)−v(2,3)=1 order 3,1,2: v(1,3)−v(3)=1 order 3,2,1: v(1,2,3)−v(2,3)=1 φ₁ = (0+0+1+1+1+1)/6 = 4/6 = 2/3

By symmetry, players 2 and 3 must split the remainder equally: φ₂ = φ₃ = (1 − 2/3)/2 = 1/6 each. Check: 2/3 + 1/6 + 1/6 = 1, exactly v(1,2,3). Player 1, the scarce resource, takes four times either partner's share: computed from the coalition structure alone, not asserted.

Where it actually runs

Explaining machine-learning predictions SHAP (SHapley Additive exPlanations) (one of the standard tools for explaining what a machine-learning model actually did) is the Shapley value applied to a model's input features as if they were players in a coalition, and the model's prediction as the value they jointly produced. "How much did this feature move the prediction?" is answered the same way "how much did this player earn?" is answered above: average its marginal effect over every possible order features could be revealed in. Lundberg & Lee, "A Unified Approach to Interpreting Model Predictions," NeurIPS (2017). One of the most cited papers in applied machine learning, precisely because it gave an ad hoc practice a 1953 game-theoretic proof of uniqueness.

And older: airport landing fees Cost-sharing a runway sized for the largest aircraft that uses it, fairly, among airlines flying very different aircraft, is a textbook cooperative-game application dating to the 1970s: the same marginal-contribution logic, applied to cost instead of profit.