Shapley value

Consider a simplified description of a business. An owner, o, provides crucial capital in the sense that without her no gains can be obtained. There are k workers w₁,...,w_k, each of whom contributes an amount p to the total profit. Let

${\displaystyle N=\{o,w_{1},\ldots ,w_{k}\}.}$

The value function for this coalitional game is

${\displaystyle v(S)={\begin{cases}mp,&{\text{if }}o\in S\\0,&{\text{otherwise}}\\\end{cases}}}$

where m is the cardinality of ${\displaystyle S\setminus \{o\}}$. Computing the Shapley value for this coalition game leads to a value of kp/2 for the owner and p/2 for each worker.

The glove game is a coalitional game where the players have left- and right-hand gloves and the goal is to form pairs. Let

${\displaystyle N=\{1,2,3\},}$

where players 1 and 2 have right-hand gloves and player 3 has a left-hand glove.

The value function for this coalitional game is

${\displaystyle v(S)={\begin{cases}1&{\text{if }}S\in \left\{\{1,3\},\{2,3\},\{1,2,3\}\right\};\\0&{\text{otherwise}}.\\\end{cases}}}$

The formula for calculating the Shapley value is

${\displaystyle \varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\left[v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})\right],}$

where R is an ordering of the players and ${\displaystyle P_{i}^{R}}$ is the set of players in N which precede i in the order R.

The following table displays the marginal contributions of Player 1.

${\displaystyle {\begin{array}{|c|r|}{\text{Order }}R\,\!&MC_{1}\\\hline {1,2,3}&v(\{1\})-v(\varnothing )=0-0=0\\{1,3,2}&v(\{1\})-v(\varnothing )=0-0=0\\{2,1,3}&v(\{1,2\})-v(\{2\})=0-0=0\\{2,3,1}&v(\{1,2,3\})-v(\{2,3\})=1-1=0\\{3,1,2}&v(\{1,3\})-v(\{3\})=1-0=1\\{3,2,1}&v(\{1,2,3\})-v(\{2,3\})=1-1=0\end{array}}}$

Observe

${\displaystyle \varphi _{1}(v)=\!\left({\frac {1}{6}}\right)(1)={\frac {1}{6}}.}$

By a symmetry argument it can be shown that

${\displaystyle \varphi _{2}(v)=\varphi _{1}(v)={\frac {1}{6}}.}$

Due to the efficiency axiom, the sum of all the Shapley values is equal to 1, which means that

${\displaystyle \varphi _{3}(v)={\frac {4}{6}}={\frac {2}{3}}.}$

The sum of the Shapley values of all agents equals the value of the grand coalition, so that all the gain is distributed among the agents:

${\displaystyle \sum _{i\in N}\varphi _{i}(v)=v(N)}$

Proof: ${\displaystyle \sum _{i\in N}\varphi _{i}(v)={\frac {1}{|N|!}}\sum _{R}\sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})={\frac {1}{|N|!}}\sum _{R}v(N)={\frac {1}{|N|!}}|N|!\cdot v(N)=v(N)}$

since ${\displaystyle \sum _{i\in N}v(P_{i}^{R}\cup \left\{i\right\})-v(P_{i}^{R})}$ is a telescoping sum and there are |N|! different orderings R.

If ${\displaystyle i}$ and ${\displaystyle j}$ are two actors who are equivalent in the sense that

${\displaystyle v(S\cup \{i\})=v(S\cup \{j\})}$

for every subset ${\displaystyle S}$ of ${\displaystyle N}$ which contains neither ${\displaystyle i}$ nor ${\displaystyle j}$, then ${\displaystyle \varphi _{i}(v)=\varphi _{j}(v)}$.

This property is also called equal treatment of equals.

If two coalition games described by gain functions ${\displaystyle v}$ and ${\displaystyle w}$ are combined, then the distributed gains should correspond to the gains derived from ${\displaystyle v}$ and the gains derived from ${\displaystyle w}$:

${\displaystyle \varphi _{i}(v+w)=\varphi _{i}(v)+\varphi _{i}(w)}$

for every ${\displaystyle i}$ in ${\displaystyle N}$. Also, for any real number ${\displaystyle a}$,

${\displaystyle \varphi _{i}(av)=a\varphi _{i}(v)}$

for every ${\displaystyle i}$ in ${\displaystyle N}$.

The Shapley value ${\displaystyle \varphi _{i}(v)}$ of a null player ${\displaystyle i}$ in a game ${\displaystyle v}$ is zero. A player ${\displaystyle i}$ is null in ${\displaystyle v}$ if ${\displaystyle v(S\cup \{i\})=v(S)}$ for all coalitions ${\displaystyle S}$ that do not contain ${\displaystyle i}$.

Given a player set ${\displaystyle N}$, the Shapley value is the only map from the set of all games to payoff vectors that satisfies all four properties: Efficiency, Symmetry, Linearity, Null player.

If v is a subadditive set function, i.e., ${\displaystyle v(S\sqcup T)\leq v(S)+v(T)}$, then for each agent i: ${\displaystyle \varphi _{i}(v)\leq v(\{i\})}$.

Similarly, if v is a superadditive set function, i.e., ${\displaystyle v(S\sqcup T)\geq v(S)+v(T)}$, then for each agent i: ${\displaystyle \varphi _{i}(v)\geq v(\{i\})}$.

So, if the cooperation has positive externalities, all agents (weakly) gain, and if it has negative externalities, all agents (weakly) lose.[7]^:147–156

If i and j are two agents, and w is a gain function that is identical to v except that the roles of i and j have been exchanged, then ${\displaystyle \varphi _{i}(v)=\varphi _{j}(w)}$. This means that the labeling of the agents doesn't play a role in the assignment of their gains.

The Shapley value can be defined as a function which uses only the marginal contributions of player i as the arguments.