Shapley value is efficient

Question

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!

Answer 1

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.