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?

  • $\begingroup$ You probably mean $v(s\cup\{i\})−v(s)$? $\endgroup$ – joriki Feb 21 '12 at 6:04
  • $\begingroup$ And unless you're using ordinal notation, "$N$ players" should be "$|N|$ players" to match the later formulas? $\endgroup$ – joriki Feb 21 '12 at 6:11
  • $\begingroup$ Also you've introduced both lowercase and uppercase $s$, but apparently they're supposed to refer to the same set. $\endgroup$ – joriki Feb 21 '12 at 7:38
  • $\begingroup$ Thanks joriki, have edited since. $\endgroup$ – Bravo Feb 21 '12 at 9:23
  • 1
    $\begingroup$ 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. $\endgroup$ – 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:


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

  • $\begingroup$ Thanks @joriki, that is very clear. $\endgroup$ – Bravo Feb 21 '12 at 9:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.