Shapley Value

Motivating example: Sharing a taxi fare

For the taxi trip game with characteristic function:

\[\begin{split}v(C)=\begin{cases} 0,&\text{if }C=\emptyset\\ 6,&\text{if }C=\{1\}\\ 12,&\text{if }C=\{2\}\\ 42,&\text{if }C=\{3\}\\ 12,&\text{if }C=\{1,2\}\\ 42,&\text{if }C=\{1,3\}\\ 42,&\text{if }C=\{2,3\}\\ 42,&\text{if }C=\Omega=\{1,2,3\}\\ \end{cases}\end{split}\]

How much should each individual contribute?

Payoff vector

This corresponds to a payoff vector \(\lambda\in\mathbb{R}_{\geq 0}^{N}\) that divides the value of the grand coalition \(\Omega\) between the various players. Thus \(\lambda\) must satisfy:

\[\sum_{i=1}^N\lambda_i=v(\Omega)\]

Thus one potential solution to our taxi example would be \(\lambda=(14,14,14)\). Obviously this is not ideal for player 1 and/or 2: they actually pay more than they would have paid without sharing the taxi!

Another potential solution would be \(\lambda=(6,6,30)\), however at this point sharing the taxi is of no benefit to player 1. Similarly \((0,12,30)\) would have no incentive for player 2.

To find a “fair” distribution of the grand coalition we must define what is meant by “fair”. We require four desirable properties:

Definition of efficiency

For \(G=(N,v)\) a payoff vector \(\lambda\) is efficient if:

\[\sum_{i=1}^N\lambda_i=v(\Omega)\]

Question

For the taxi fare which of the following payoff vectors are efficient?

  • \(\lambda=(42, 0, 0)\).

  • \(\lambda=(12, 12, 18)\).

  • \(\lambda=(14, 14, 14)\).

  • \(\lambda=(1, 14, 28)\).

Answer

For all of these cases we need \(v(\Omega)=v(\{1, 2, 3\})=42\).

  • \(\lambda=(42, 0, 0)\) is efficient as \(42 + 0 + 0=42\).

  • \(\lambda=(12, 12, 18)\) is efficient as \(12 + 12 + 18 = 42\).

  • \(\lambda=(14, 14, 14)\) is efficient as \(14 + 14 + 14 = 42\).

  • \(\lambda=(1, 14, 28)\) is not efficient as \(1 + 14 + 28 = 43\).

Definition of null player

For \(G(N,v)\) a payoff vector possesses the null player property if \(v(C\cup \{i\})=v(C)\) for all \(C\in 2^{\Omega}\) then:

\[x_i=0\]

Question

1. For the taxi fare which of the following payoff vectors possess the null player property?

  • \(\lambda=(42, 0, 0)\).

  • \(\lambda=(12, 12, 18)\).

  • \(\lambda=(14, 14, 14)\).

  • \(\lambda=(1, 14, 28)\).

  1. For game \(G(3, v_3)\) with \(v_3\) defined as:

\[\begin{split}v_3(C)=\begin{cases} 0,&\text{if }C=\emptyset\\ 0,&\text{if }C=\{1\}\\ 12,&\text{if }C=\{2\}\\ 42,&\text{if }C=\{3\}\\ 12,&\text{if }C=\{1,2\}\\ 42,&\text{if }C=\{1,3\}\\ 42,&\text{if }C=\{2,3\}\\ 42,&\text{if }C=\Omega=\{1,2,3\}\\ \end{cases}\end{split}\]

which of the following payoff vectors possess the null player property?

  • \(\lambda=(42, 0, 0)\).

  • \(\lambda=(12, 12, 18)\).

  • \(\lambda=(14, 14, 14)\).

  • \(\lambda=(0, 15, 28)\).

Answer

  1. For the taxi fare there is no player \(i\) such that \(v(C\cup \{i\})=v(C)\) for all \(C\in 2^{\Omega}\). Indeed, \(v(\{1\}\cup \{2\})\ne v(\{1\})\) and \(v(\{1\}\cup\{3\})\ne v(\{1\})\) and \(v(\emptyset \cup \{1\}) \ne v(\emptyset)\). Thus, all the payoff vector have the null property.

  2. For \(v_3\) we have that \(v(C \cup \{1\})=V(C)\) for all

    \(C\in 2^{\Omega}\). Thus the only payoff vector that has the null player property is \(\lambda=(0, 15, 28)\).

Definition of symmetry

For \(G(N,v)\) a payoff vector possesses the symmetry property if \(v(C\cup i)=v(C\cup j)\) for all \(C\in 2^{\Omega}\setminus\{i,j\}\) then:

\[x_i=x_j\]

Question

1. For the taxi fare which of the following payoff vectors possess the symmetry property?

  • \(\lambda=(42, 0, 0)\).

  • \(\lambda=(12, 12, 18)\).

  • \(\lambda=(14, 14, 14)\).

  • \(\lambda=(1, 14, 28)\).

  1. For game \(G(3, v_4)\) with \(v_4\) defined as:

\[\begin{split}v_4(C)=\begin{cases} 0,&\text{if }C=\emptyset\\ 2,&\text{if }C=\{1\}\\ 2,&\text{if }C=\{2\}\\ 2,&\text{if }C=\{3\}\\ 12,&\text{if }C=\{1,2\}\\ 12,&\text{if }C=\{1,3\}\\ 42,&\text{if }C=\{2,3\}\\ 42,&\text{if }C=\Omega=\{1,2,3\}\\ \end{cases}\end{split}\]

which of the following payoff vectors possess the null player property?

  • \(\lambda=(42, 0, 0)\).

  • \(\lambda=(12, 12, 18)\).

  • \(\lambda=(14, 14, 14)\).

  • \(\lambda=(0, 15, 28)\).

Answer

  1. For the taxi fare there is no pair of players \(i\) and \(j\) such that \(v(C\cup i)=v(C\cup j)\) for all \(C\in 2^{\Omega}\setminus\{i,j\}\). Indeed, \(v(\{1\}\cup \{2\})\ne v(\{1\}\cup\{3\})\) and \(v(\{2\}\cup\{3\})\ne v(\{2\}\cup\{1\})\). Thus, all the payoff vector have the symmetry property.

  2. For \(v_4\) we have that \(v(\emptyset \cup \{2\})=v(\emptyset \cup\{3\})\), \(v(\{1\}\cup \{2\})=v(\{1\}\emptyset \cup\{3\})\) so players 2 and 3 contribute the same to all subsets. However \(v(\{2\}\cup \{3\})\ne v(\{2\}\emptyset \cup\{1\})\) and \(v(\{2\}\cup \{1\})\ne v(\{2\}\emptyset \cup\{3\})\) thus player 1 does not contribute the same as either player 2 or player 3 to all subsets. Thus the payoff vectors that have the symmetry property are \(\lambda=(42, 0, 0)\) and \(\lambda=(14, 14, 14)\).

Definition of additivity

For \(G_1=(N,v_1)\) and \(G_2=(N,v_2)\) and \(G^+=(N,v^+)\) where \(v^+(C)=v_1(C)+v_2(C)\) for any \(C\in 2^{\Omega}\). A payoff vector possesses the additivity property if:

\[x_i^{(G^+)}=x_i^{(G_1)}+x_i^{(G_2)}\]

We will not prove in this course but in fact there is a single payoff vector that satisfies these four properties. To define it we need two last definitions.

Definition of predecessors

If we consider any permutation \(\pi\) of \([N]\) then we denote by \(S_\pi(i)\) the set of predecessors of \(i\) in \(\pi\):

\[S_\pi(i)=\{j\in[N]\;|\;\pi(j)<\pi(i)\}\]

For example for \(\pi=(1,3,4,2)\) we have \(S_\pi(4)=\{1,3\}\).

Definition of marginal contribution

If we consider any permutation \(\pi\) of \([N]\) then the marginal contribution of player \(i\) with respect to \(\pi\) is given by:

\[\Delta_\pi^G(i)=v(S_{\pi}(i)\cup i)-v(S_{\pi}(i))\]

Definition of the Shapley value

Given \(G=(N,v)\) the Shapley value of player \(i\) is denoted by \(\phi_i(G)\) and given by:

\[\phi_i(G)=\frac{1}{N!}\sum_{\pi\in\Pi_n}\Delta_\pi^G(i)\]

Question

Obtain the Shapley value for the taxi fare.

Answer

For \(\pi=(1,2,3)\):

\[\begin{split}\begin{aligned} \Delta_{\pi}^G(1)&=6\\ \Delta_{\pi}^G(2)&=6\\ \Delta_{\pi}^G(3)&=30\\ \end{aligned}\end{split}\]

For \(\pi=(1,3,2)\):

\[\begin{split}\begin{aligned} \Delta_{\pi}^G(1)&=6\\ \Delta_{\pi}^G(2)&=0\\ \Delta_{\pi}^G(3)&=36\\ \end{aligned}\end{split}\]

For \(\pi=(2,1,3)\):

\[\begin{split}\begin{aligned} \Delta_{\pi}^G(1)&=0\\ \Delta_{\pi}^G(2)&=12\\ \Delta_{\pi}^G(3)&=30\\ \end{aligned}\end{split}\]

For \(\pi=(2,3,1)\):

\[\begin{split}\begin{aligned} \Delta_{\pi}^G(1)&=0\\ \Delta_{\pi}^G(2)&=12\\ \Delta_{\pi}^G(3)&=30\\ \end{aligned}\end{split}\]

For \(\pi=(3,1,2)\):

\[\begin{split}\begin{aligned} \Delta_{\pi}^G(1)&=0\\ \Delta_{\pi}^G(2)&=0\\ \Delta_{\pi}^G(3)&=42\\ \end{aligned}\end{split}\]

For \(\pi=(3,2,1)\):

\[\begin{split}\begin{aligned} \Delta_{\pi}^G(1)&=0\\ \Delta_{\pi}^G(2)&=12\\ \Delta_{\pi}^G(3)&=42\\ \end{aligned}\end{split}\]

Using this we obtain:

\[\phi(G)=(2,5,35)\]

Thus the fair way of sharing the taxi fare is for player 1 to pay 2, player 2 to pay 5 and player 3 to pay 35.

[Maschler2013] is recommended for further reading.