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?

$\endgroup$
5
  • $\begingroup$ You probably mean $v(s\cup\{i\})−v(s)$? $\endgroup$
    – joriki
    Feb 21, 2012 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, 2012 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, 2012 at 7:38
  • $\begingroup$ Thanks joriki, have edited since. $\endgroup$
    – Bravo
    Feb 21, 2012 at 9:23
  • 2
    $\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, 2012 at 9:46

1 Answer 1

5
$\begingroup$

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

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .