# Shapley value is efficient

The question seems trivial: I must show that the Shapley value distributes the full value of the grand coalition among the players. In other words, if the Shapley value of player $$i$$ is defined to be $$\phi_i(v)=\sum_{S\subseteq N-i} \frac{|S|!(|N|-|S|-1)!}{|N|!}(v(S\cup\{i\})-v(S))$$ then I should conclude that $$\sum_{i=1}^n \phi_i (v) = v(N).$$ The naive approach suggests extending the double sum $$\sum_{i=1}^n\sum_{S\subseteq N-i} \frac{|S|!(|N|-|S|-1)!}{|N|!}(v(S\cup\{i\})-v(S))$$ but this looks formidibale and desperate, since we have no assumption on the size of $$N$$ or $$S$$. Any help will be appreciated!

• Would induction on $\vert N \vert$ work? Commented Apr 23, 2018 at 5:52
• I've been trying that for days but so far no luck :( Commented Apr 23, 2018 at 6:25

For each coalition, add up the coefficients with which its value appears in the double sum.

$v(N)$ appears exactly once per player, namely for $S=N-i$, and the coefficient in each case is $\frac1n$, so the sum of the coefficients is $1$ as required.

All other coalition values appear with positive and negative signs. The value of coalition $C$ with $|C|=k$ players appears $k$ times with positive sign, once for each player in $C$, with coefficient

$$\frac{(k-1)!(n-k)!}{n!}$$

in each case, for a total of $\binom nk^{-1}$. It also appears $n-k$ times with negative sign, once for each player not in $C$, with coefficient

$$\frac{k!(n-k-1)!}{n!}$$

in each case, again for a total of $\binom nk^{-1}$. So the positive and negative contributions for all coalitions except for the grand coalition cancel.