1
$\begingroup$

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?

  • 1
    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.2012-02-21

1 Answers 1

3

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

  • 0
    Thanks @joriki, that is very clear.2012-02-21