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$
8
  • 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$ May 21, 2018 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$
    – EoDmnFOr3q
    May 21, 2018 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$ May 21, 2018 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$ May 21, 2018 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$ May 21, 2018 at 14:05

1 Answer 1

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$
1
  • $\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$
    – EoDmnFOr3q
    May 22, 2018 at 22:41

You must log in to answer this question.

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