0
$\begingroup$

I am currently studying the consistency property of the Shapley Value. Following Hart & Mas-Colell (1989), it is known that the Shapley Value is Hart & Mas-Colell (1989) consistent for all games $[N,\nu]$. A fairly detailed proof of such a statement can be found in Maschler et al. (2013), pp. 770. We define Hart & Mas-Colell (1989) consistency as follows:

Let $\phi(N,\nu)$ be a solution function, let $[N,\nu]$ be a TU cooperative and let $T\subseteq N$. We define the Hart & Mas-Colell (1989) reduced game $[T,\nu_t^{\phi}]$ as follows: \begin{gather*} \nu_t^{\phi}(S)=\nu(S\cup T^c)-\sum_{i\in T^c}\phi^i(S\cup T^c,\nu)\qquad\forall S\subseteq T \end{gather*} Where $T^c=N\backslash T$. A solution function $\phi(N,\nu)$ is Hart & Mas-Colell (1989) consistent if for every game $[N,\nu]$ and every coalition $T\subseteq N$, one has \begin{gather*} \phi^j(T,\nu_T^{\phi})=\phi^j(N,\nu)\qquad\forall j\in T \end{gather*}

Although I thought I understood this concept, it turns out that I found a very simple example I can't correctly cope with (and it is preventing me from doing further research). Consider the game $[N,\nu]$ with $|N|=3$ and a coalition function given by \begin{gather*} \nu(N)=1,\nu(1,2)=0.75,\nu(1,3)=0.5,\nu(2,3)=0.25\text{ and }0\text{ else.} \end{gather*} Unless I'm wrong, the Shapley Value of this game is given by the following vector: \begin{gather*} Sh(N,\nu)=\left(\frac{11}{24},\frac{8}{24},\frac{5}{24}\right) \end{gather*} When I reduce $[N,\nu]$ à la Hart & Mas-Colell (1989) with respect to $Sh(N,\nu)$ for singleton coalitions, I do not get that $Sh^j(N,\nu)=Sh^j(N,\nu_T^{\phi})$ (I haven't tried with larger coalitions). In any case, there must be something I'm doing wrong (I don't know what it is, but I suspect I'm not reducing $[N,\nu]$ correctly). Therefore, could anybody please help me understand the consistency of the Shapley Value by reducing the example I gave with respect to $Sh(N,\nu)$ for singleton coalitions and show that the Hart & Mas-Colell (1989) consistency property holds in my example?

EDIT! In order to make things a little bit less obscure, let me show exactly what I did and why I am confused. Consider the game above and take the vector $Sh(N,\nu)$. Then, reduce $[N,\nu]$ with respect to $Sh_i(N,\nu)$ for the Player $i=1$, and let this game be denoted by $[N\backslash\{1\},\nu_1^{\phi}]$.

For Player $1$ and $Sh_1(N,\nu)=\frac{11}{24}$, the Hart & Mas-Colell (1989) reduced game (if I understood it properly) $[N\backslash\{1\},\nu_1^{\phi}]$ is defined as follows. The set of Players is given by $N=\{2,3\}$, and the new coalition function $\nu_1^{\phi}$ is given by: \begin{gather*} \nu_1^{\phi}(2,3)=\nu(N)-\frac{11}{24}=\frac{13}{24},\\ \nu_1^{\phi}(2)=\nu(1,2)-\frac{11}{24}=\frac{7}{24},\\ \nu_1^{\phi}(3)=\nu(1,3)-\frac{11}{24}=\frac{1}{24} \end{gather*}

When I compute the Shapley Value of $[N\backslash\{1\},\nu_1^{\phi}]$, I obtain the following vector: \begin{gather*} Sh(N\backslash\{1\},\nu_1^{\phi})=\left(\frac{19}{48},\frac{7}{48}\right) \end{gather*} Obviously, $Sh_2(N\backslash\{1\},\nu_1^{\phi})\neq Sh_2(N,\nu)$ and $Sh_3(N\backslash\{1\},\nu_1^{\phi})\neq Sh_3(N,\nu)$, which is what triggers my confusion and my question in the site. I am absolutely sure that there is something I'm not understanding, but I can't see what it is. Could anybody please enlighten me a bit?

$\endgroup$
  • 1
    $\begingroup$ Do you get for each singleton reduced game the values $11/24,8,24$ and $5/24$ respectively? These games must reproduce the associated payoffs of the Shapley value. However, for $T=\{1,2\}$ the reduced game ought give $v_{T}=[1/4,1/8,19/24]$. $\endgroup$ – Holger I. Meinhardt May 21 '18 at 13:12
  • $\begingroup$ Thank you for your comment. Unfortunately, I am not sure I understand your question. Could you please re-phrase it? Also, you can see my edit, which may be helpful to understand where I'm stuck at. $\endgroup$ – Héctor May 21 '18 at 13:31
  • 1
    $\begingroup$ For the singleton reduced game $T=\{1\}$ you should only get the value $11/24$, which has the Shapley value $11/24$. However, for $T=\{2\}$ the reduced game is given by $1/3$ with Shapley value $1/3$, and finally for $T=\{3\}$ we have for the reduced game $5/24$ and the Shapley value gives $5/24$. It remains then to consider the reduced games for $T=\{1,2\}$,$T=\{1,3\}$, and finally $T=\{2,3\}$. The former two person reduced game has then Shapley value of $(11,8)/24$. $\endgroup$ – Holger I. Meinhardt May 21 '18 at 13:42
  • 1
    $\begingroup$ One remark, the calculation is not correct. For $T=\{1\}$, you have $T^c=\{2,3\}$. This means for $T=\{1\}$ you have the empty coalition and the grand coalition $\{1\}$ to consider. For the last you get then $v(1,2,3)-13/24=11/24=v_{T}(1)$, and for the empty coalition you have $v_{T}()=0$. $\endgroup$ – Holger I. Meinhardt May 21 '18 at 13:53
  • 1
    $\begingroup$ The point is you start with $T=\{1\}$, the complement is $\{2,3\}$, which remains fixed. For $T$ one has only to consider two coalitions $S$,i.e., the empty set and $T$ itself. The values of this game is then computed using the fixed set of outsiders $T^c$. $\endgroup$ – Holger I. Meinhardt May 21 '18 at 14:05
1
$\begingroup$

Let us only consider the case $T=\{1,2\}$, then $T^{c}=\{3\}$. The reduced game $\langle T,v^{\phi}_{\{1,2\}}\rangle $ is then computed through

$$v^{\phi}_{T}(\{1\}) = v(\{1,3\}) - \sum_{k \in T^{c}}\,\phi_{k}(\{1,3\},v) = 1/2 - 1/4 = 1/4,$$ with $\phi_{1}(\{1,3\},v)=1/4$ and $\phi_{3}(\{1,3\},v)=1/4$. Hence, $\phi(\{1,3\},v)$ is the Shapley value of the sub-game arising from the subset $\{1,3\}$ and game $v$.

Similar, we get

$$v^{\phi}_{T}(\{2\}) = v(\{2,3\}) - \sum_{k \in T^{c}}\,\phi_{k}(\{2,3\},v) = 1/4 - 1/8 = 1/8,$$ with $\phi_{2}(\{2,3\},v)=1/8$ and $\phi_{3}(\{2,3\},v)=1/8$.

Finally for the grand coalition of the reduced game $T=\{1,2\}$, we get

$$v^{\phi}_{T}(\{1,2\}) = v(\{1,2,3\}) - \sum_{k \in T^{c}}\,\phi_{k}(\{1,2,3\},v) = 1 - 5/24 = 19/24,$$ with $\phi(\{1,2,3\},v)=(11,8,5)/24$. Whereas the empty set gives zero by definition.

To conclude, the two person reduced game is given by $[0,1/4,1/8,19/24]$ which gives a Shapley value of $(11,8)/24=\phi(N,v)_{\{1,2\}}$.

$\endgroup$
  • $\begingroup$ Thank you very much. Now I see where I was making the wrong computation. Essentially, I was not reading the definition correctly. Thank you very much again. $\endgroup$ – Héctor May 22 '18 at 22:41

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.