The Shapley Value

Fair allocation as average marginal contribution over join orders.

The idea

The Shapley value is the standard fair division of a cooperative game's total worth: it pays each player their average marginal contribution over all orders in which the players could join.

A cooperative game gives each coalition $S$ of players a worth $v(S)$, the total payoff that group can secure together; the grand coalition of all $n$ players produces $v(N)$, which is what there is to divide. Player $i s marginal contribution to a coalition $S$ that does not contain them is

$v(S \cup \{i\}) - v(S),$

the extra worth they bring by joining. This number depends on who is already present — a player can be worth a great deal to one group and nothing to another — so no single marginal contribution measures player $i s contribution to the game.

The Shapley value averages over every possibility. Suppose the players arrive one at a time in some order, and credit each arrival with what they add to those already present. Player $i s Shapley value $\phi_{i}$ is that credit averaged over all $n!$ orders:

$\phi_{i} = \frac{1}{n!}\sum_{\text{orders}} \big[v(S \cup \{i\}) - v(S)\big],$

where $S$ is the set of players ahead of $i$ in the order being counted. For three players $a$, $b$, $c$ there are $3! = 6$ arrival orders, and $a s credit in each is measured against the set already present when $a$ arrives. Within any one order the credits telescope from $v(\varnothing) = 0$ up to $v(N)$, so the values sum to $v(N)$: the whole worth is distributed, none of it invented or lost.

Ways to work on it

• Walkthrough. Marginal contributions, averaging over orderings, and efficiency.
• Practice. Compute a player's Shapley value in a two-player game.
• Hardest. Full three-player Shapley value by averaging over all orderings.

Not sure where to start? Take the ten-question placement test.