Computing the Shapley Value for this two-player game

112 Views Asked by At

It is well known that the Shapley Value for any player $i\in N$ in any game $v:2^N\to\mathbb{R}$ is defined by the following formula: \begin{gather} S_i(\nu)=\sum_{S\subseteq N\backslash\{i\}}\frac{|S|!\times[|N|-|S|-1]!}{|N|!}\times[\nu(S\cup\{i\})-\nu(S)] \end{gather}

Consider the following two-player game: $\nu(\{i,j\})=1,\nu(\{i\})=0,\nu(\{j\})=-1$. It is straightforward to see that the $S_i(\nu)=1$ and $S_j(\nu)=0$. However, applying the formula above for player $i$ yields: \begin{align} S_i(\nu)&=\frac{1!\times0!}{2!}\times[1-(-1)]\\ &=\frac{1}{2}\times2\\ &=1 \end{align}

And for player $j$, applying the formula yields: \begin{align} S_j(\nu)&=\frac{1!\times0!}{2!}\times[1-0]\\ &=\frac{1}{2}\times1\\ &=\frac{1}{2} \end{align}

It is obvious to me that I'm not understanding the formula above and I am thus not applying it correctly. Can anybody please spot and explain my mistake?

Thank you all!

1

There are 1 best solutions below

0
On BEST ANSWER

It took me more time than expected, but I finally figured it out myself. Instead of deleting the question, I post here the answer because it may help others in the future.

The error in my reasoning is the omission of the emptyset. It is generally assumed that $\nu(\{\emptyset\})=0$. Therefore, the correct way to apply the formula above is as follows. For player $i$, \begin{align} \mathcal{S}_i(\nu)&=\frac{1!\times0!}{2!}\times[1-(-1)]+\frac{1!\times0!}{2!}\times[0-0]\\ &=\frac{1}{2}\times2+\frac{1}{2}\times0\\ &=1 \end{align}

Applying the formula for player $j$, \begin{align} \mathcal{S}_j(\nu)&=\frac{1!\times0!}{2!}\times[1-0]+\frac{1!\times0!}{2!}\times[0-1]\\ &=\frac{1}{2}\times1+\frac{1}{2}\times(-1)\\ &=0 \end{align}

Hence, $\mathcal{S}_i(\nu)=1$ and $\mathcal{S}_j(\nu)=0$. And we're done!