Skip to content

Latest commit

 

History

History
325 lines (229 loc) · 9.39 KB

shapley-value.rst

File metadata and controls

325 lines (229 loc) · 9.39 KB
Raw

Shapley Value

Motivating example: Sharing a taxi fare

For the :ref:`taxi trip game <motivating-example-characteristic-function-game>` with characteristic function:

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}

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 :ref:`taxi fare <motivating-example-characteristic-function-game>` 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 :ref:`taxi fare <motivating-example-characteristic-function-game>` 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:
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}

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 :ref:`taxi fare <motivating-example-characteristic-function-game>` 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 :ref:`taxi fare <motivating-example-characteristic-function-game>` 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:
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}

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 :ref:`taxi fare <motivating-example-characteristic-function-game>` 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 :ref:`taxi fare <motivating-example-characteristic-function-game>`.

Answer

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

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

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

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

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

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

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

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

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

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

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

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

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.