Shapley Value Formula

Question

I understand Shapley value in game theory is a means to capture the average marginal contribution of a player. Obviously the way to do it would be to consider all possible coalitions of $|N|$ players excluding a particular player, say $i$.

So the Shapley value can be $\phi_i(N)=\sum_{s \subseteq N \setminus i} k\ \left(v(s \cup \{ i \})-v(s)\right)$. The value of $k$, the factor used for averaging is found to be $\frac{|s|!(|N|-|s|-1)!}{|N|!}$. I can see that the value of $k$ is such that the solution concept is allocatively efficient (and satisfies a few other axioms, besides), but is there any direct intuitive way to understand the formula?

Answer 1

It's easier to see how the factor $k$ arises starting from another definition of the Shapley value (which the Wikipedia article mentions but only gives a formula for in the example), namely as the average of the marginal contributions over all orders in which the players could join the complete coalition:

$$\phi_i(N)=\frac1{|N|!}\sum_R\left(v(P^R_i\cup\{i\})-v(P^R_i)\right)\;,$$

where $R$ runs over all possible orders of the players and $P^R_i$ is the set of players that precede $i$ in $R$. The denominator $|N|!$ is the number of different permutations of $|N|$ players. Since the summand depends only on $P_i^R$ and not on the order in which the players join the coalition before $i$ or the order in which they join the coalition after $i$, we can sum over $S=P_i^R$ instead. Then we have to count how often each of these sets arises, and this is the product of the number of permutations of the players in $S$, which is $|S|!$, with the number of permutations of the players in $N\setminus(S\cup\{i\})$, which is $(|N|-|S|-1)!$, yielding

$$\phi_i(N)=\frac1{|N|!}\sum_{S\subseteq N\setminus\{i\}}|S|!(|N|-|S|-1)!\left(v(S\cup\{i\})-v(S)\right)\;.$$