4
$\begingroup$

It is my belief that the more common representation of the Shapley value is given by $$ \phi_i(v)=\sum_{S\subseteq N-i} \frac{|S|!(|N|-|S|-1)!}{|N|!}(v(S\cup\{i\})-v(S)) $$ where $v \in \mathbb{R}^{L(N)}$ is a coalitional game on the finite player set $N$, and $i\in N$. (Note $L(N)=\{S|S\subseteq N \text{ and } S\ne\emptyset\}$.)

There is yet another representation of the Shapley value, claimed to be equivalent to the previous, given by $$ \phi_i(v)=\sum_{S\subseteq N-i} \frac{|S|!(|N|-|S|-1)!}{|N|!}(v(N\backslash S)-v(S)).$$ (See R. B. Myerson, Game Theory, 1991, p.441, and also an online note here on p. 10.)

Frankly, I do not see how these two formulae are equal. A naive yet natural sufficient condition for these to be equivalent is for $v(S\cup\{i\})=v(N\backslash S)$, which is not generally true. May anyone enlighten me? Thank you!

$\endgroup$
1
$\begingroup$

The piece with $v(S \cup \lbrace i \rbrace)$ in the first formula, is equal to the same thing with $v(N \backslash T)$ where $T$ is the complement of $S$ in $N - \lbrace i \rbrace$. The sum can be indexed by $T$ instead of $S$, and will give the same result, because the weight of $S$ and $T$ (the expression with factorials) is the same by the equation ${{N-1} \choose |S|} = {{N-1} \choose {N - 1 - |S|}}$.

The second term, with "$ - v(S)))$", is the same in both formulas.

$\endgroup$
  • $\begingroup$ That is, the sums can be split into two parts. The second parts are identical, and the first parts are equal if you index one sum by S, the other by T, and make the correspondence S <---> T. $\endgroup$ – zyx Aug 12 '13 at 15:46

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.