# Shapley Value Formula

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?

-
You probably mean $v(s\cup\{i\})−v(s)$? – joriki Feb 21 '12 at 6:04
And unless you're using ordinal notation, "$N$ players" should be "$|N|$ players" to match the later formulas? – joriki Feb 21 '12 at 6:11
Also you've introduced both lowercase and uppercase $s$, but apparently they're supposed to refer to the same set. – joriki Feb 21 '12 at 7:38
Thanks joriki, have edited since. – Bravo Feb 21 '12 at 9:23
You let one of the errors stand ($N$ instead of $|N|$) and introduced a new one (missing parentheses in the sum). Please take a bit more care in posting. – joriki Feb 21 '12 at 9:46

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)\;.$$