Shapley value

The Shapley value (named after Lloyd Shapley ) is a point-worthy solution concept from cooperative game theory . It indicates which payout the players can expect (positive interpretation) or should receive (normative interpretation) depending on a coalition function.

example

Given are three players who are identified by the abbreviations and , i.e. H. , and which can achieve the following values: ${\displaystyle a,b}$ ${\displaystyle c}$ ${\displaystyle N=\left\{a,b,c\right\}}$

${\displaystyle v(\{a\})=12}$	${\displaystyle v(\{a,b\})=24}$	${\displaystyle v(\emptyset )=0}$
${\displaystyle v(\{b\})=6}$	${\displaystyle v(\{a,c\})=27}$
${\displaystyle v(\{c\})=9}$	${\displaystyle v(\{b,c\})=15}$	${\displaystyle v(\{a,b,c\})=36}$

This means, for example , that the “coalition” consisting of players alone can achieve the value ; means that a coalition of players can work together to create value ; because of this, all players can create value together . ${\displaystyle v(\left\{b\right\})=6}$ ${\displaystyle b}$ ${\displaystyle 6}$ ${\displaystyle v(\left\{a,b\right\})=24}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 24}$ ${\displaystyle v(\left\{a,b,c\right\})=36}$ ${\displaystyle 36}$

The Shapley value is used to divide the value . The following procedure can be used to determine the Shapley score of a player : Note all the orders in which the players can be arranged. For each order you determine the value of the coalition, which consists of those players who are listed in front of the player in question. The value that this coalition has together with the player is noted and the difference is formed, i.e. the so-called marginal contribution of the player in the order under consideration. Finally, you take the average of these marginal contributions and get the player's Shapley score . The following table reflects these considerations for gamers : ${\displaystyle v(\left\{a,b,c\right\})=36}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle b}$

sequence	${\displaystyle v(\{}$Player before b ${\displaystyle \})}$	${\displaystyle v(\{}$Player in front of b plus b ${\displaystyle \})}$	marginal contribution from player b
${\displaystyle a,b,c}$	${\displaystyle v(\{a\})=12}$	${\displaystyle v(\{a,b\})=24}$	${\displaystyle 12}$
${\displaystyle a,c,b}$	${\displaystyle v(\{a,c\})=27}$	${\displaystyle v(\{a,b,c\})=36}$	${\displaystyle 9}$
${\displaystyle b,a,c}$	${\displaystyle v(\emptyset )=0}$	${\displaystyle v(\{b\})=6}$	${\displaystyle 6}$
${\displaystyle b,c,a}$	${\displaystyle v(\emptyset )=0}$	${\displaystyle v(\{b\})=6}$	${\displaystyle 6}$
${\displaystyle c,a,b}$	${\displaystyle v(\{a,c\})=27}$	${\displaystyle v(\{a,b,c\})=36}$	${\displaystyle 9}$
${\displaystyle c,b,a}$	${\displaystyle v(\{c\})=9}$	${\displaystyle v(\{b,c\})=15}$	${\displaystyle 6}$

The average of the marginal contributions gives the Shapley value for players ${\displaystyle b}$

${\displaystyle \mathrm {Sh} _{b}(\{a,b,c\},v)=(12+9+6+6+9+6)/6=8.}$

The Shapley values ​​of the players and and are obtained in the same way ${\displaystyle a}$ ${\displaystyle c}$

${\displaystyle \mathrm {Sh} _{a}(\{a,b,c\},v)=17}$      and       ${\displaystyle \mathrm {Sh} _{c}(\{a,b,c\},v)=11.}$

general definition

Given is a cooperative game with transferable benefits, that is, given

• a finite set of players with elements and ${\displaystyle N}$ ${\displaystyle n:=|N|}$
• a coalition function that assigns a real number to each subset of and, in particular, gives the empty coalition the value : ${\displaystyle v}$ ${\displaystyle N}$ ${\displaystyle 0}$

${\displaystyle {\begin{array}{rcccl}v&:&{\mathcal {P}}(N)&\longrightarrow &\mathbb {R} \\&:&v(\emptyset )&\mapsto &0\\\end{array}}}$

where denotes the power set of , i.e. the set of all subsets. A subset of the players is called a coalition. The expression is called the value of the coalition . ${\displaystyle {\mathcal {P}}(N)}$ ${\displaystyle N}$ ${\displaystyle S\subseteq N}$ ${\displaystyle v(S)}$ ${\displaystyle S}$

The Shapley value now assigns a payout for the game to each player . There are different formulas that lead to the same result. ${\displaystyle N}$ ${\displaystyle v}$

Order definition

First, the marginal contribution of a player for a given order of players is defined. Be an order of the player set with the interpretation that player is listed at position in . For a player listed before Player in , applies . So the predecessors of in are in the crowd ${\displaystyle i\in N}$ ${\displaystyle \sigma }$ ${\displaystyle i}$ ${\displaystyle \sigma (i)}$ ${\displaystyle \sigma }$ ${\displaystyle j\in N}$ ${\displaystyle i}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma (j)<\sigma (i)}$ ${\displaystyle i}$ ${\displaystyle \sigma }$

${\displaystyle P_{i}^{\sigma }=\{j\in N\colon \sigma (j)<\sigma (i)\}}$.

If the players are added one after the other to a coalition according to the order, the player makes the following marginal contribution : ${\displaystyle \sigma }$ ${\displaystyle i}$ ${\displaystyle \sigma }$

${\displaystyle v(P_{i}^{\sigma }\cup \{i\})-v(P_{i}^{\sigma })}$.

A player's Shapley score is calculated as the average of the marginal contributions over all possible orders: ${\displaystyle i}$ ${\displaystyle n!}$

${\displaystyle \mathrm {Sh} _{i}(N,v)={\frac {1}{n!}}\cdot \sum _{\sigma \in {\mathcal {R}}}[v(P_{i}^{\sigma }\cup \{i\})-v(P_{i}^{\sigma })]}$

where denotes the set of all possible orders of the players. ${\displaystyle {\mathcal {R}}}$

Note: The above example is calculated according to this definition. For is z. B. and ${\displaystyle \sigma =(c,a,b)}$ ${\displaystyle P_{b}^{\sigma }=\{a,c\}}$ ${\displaystyle v(P_{b}^{\sigma }\cup \{b\})-v(P_{b}^{\sigma })=36-27=9.}$

Subset definition

The marginal contribution of a player at any given coalition is ${\displaystyle i\in N}$ ${\displaystyle S\subseteq N}$

${\displaystyle v(S\cup \{i\})-v(S).}$

A player's Shapley score is calculated as the weighted mean of the marginal contributions to all possible coalitions: ${\displaystyle i}$

${\displaystyle \mathrm {Sh} _{i}(N,v)=\sum _{S\subseteq N\setminus \{i\}}{\frac {(n-1-|S|)!\cdot |S|!}{n!}}(v(S\cup \{i\})-v(S))}$

Based on the sequence definition of the Shapley value, this formula can now be understood as follows: For each there is ${\displaystyle S\subseteq N\setminus \{i\}}$

${\displaystyle (n-1-|S|)!\cdot |S|!}$

Orders, so that applies, because there are possibilities to arrange the players from in front of the player and possibilities to arrange the players from behind the player (see also multinomial coefficients ). ${\displaystyle P_{i}^{\sigma }=S}$ ${\displaystyle |S|!}$ ${\displaystyle S}$ ${\displaystyle i}$ ${\displaystyle (n-|S|-1)!}$ ${\displaystyle N\setminus \{S\cup \{i\}\}}$ ${\displaystyle i}$

example

Look again at the above example and take the case . It is then exactly for the two sequences and . So it applies . Instead of going through all the sequences, you could also set up the following table: ${\displaystyle S=\{a,c\}}$ ${\displaystyle P_{b}^{\sigma }=S}$ ${\displaystyle (a,c,b)}$ ${\displaystyle (c,a,b)}$ ${\displaystyle (n-1-|S|)!\cdot |S|!=(3-2-1)!\cdot 2!=2}$

coalition	frequency	marginal contribution
${\displaystyle S\subseteq N\setminus \{i\}}$	${\displaystyle (n-1-|S|)!\cdot |S|!}$	${\displaystyle v(S\cup \{i\})-v(S)}$
${\displaystyle \emptyset }$	${\displaystyle 2}$	${\displaystyle 6}$
${\displaystyle \{a\}}$	${\displaystyle 1}$	${\displaystyle 12}$
${\displaystyle \{c\}}$	${\displaystyle 1}$	${\displaystyle 6}$
${\displaystyle \{a,c\}}$	${\displaystyle 2}$	${\displaystyle 9}$

The average of the marginal contributions gives the Shapley value for games in the crowd ${\displaystyle b}$ ${\displaystyle N=\{a,b,c\}}$

${\displaystyle \mathrm {Sh} _{b}(N,v)=(2\cdot 6+1\cdot 12+1\cdot 6+2\cdot 9)/6=8.}$

Definition via Harsanyi dividends

Another calculation option also provides a better insight into the structure of a coalition function.

Harsanyi dividends

The following argument is often attributed to John Harsanyi . Look at a coalition and its worth . What proportion of is actually created by the combination of all members , and not by the combination of the subgroups contained in? That is, what part of is not already due to the achievement of some subgroup? The answer is recursive. First of all, the real performance of an empty coalition is nothing . The other actual services result recursively as the value of a coalition minus the services that are already provided by the coalitions contained: ${\displaystyle S}$ ${\displaystyle v(S)}$ ${\displaystyle v(S)}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle v(S)}$ ${\displaystyle \lambda _{\emptyset }^{v}=0}$

${\displaystyle \lambda _{\emptyset }^{v}:=0,}$

${\displaystyle \lambda _{S}^{v}:=v(S)-\sum _{T\subsetneq S}\lambda _{T}^{v}.}$

These expressions are known as the Harsanyi dividends. Note: Instead of just write or just write . ${\displaystyle \lambda _{\{a,b,\ldots ,c\}}^{v}}$ ${\displaystyle \lambda _{a,b,\ldots ,c}}$ ${\displaystyle \lambda _{ab\ldots c}}$

example

Look again at the above example and see that it is actually being performed by the player . So the actual performance from the player alone is . The genuine achievements of the other individual coalitions can be determined in the same way, ${\displaystyle v(\{a\})=12}$ ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle \lambda _{a}=v(\{a\})=12}$

${\displaystyle \lambda _{b}=6}$

${\displaystyle \lambda _{c}=9}$.

For the coalition , the services already provided by the included coalitions must now be deducted: ${\displaystyle \{a,b\}}$

${\displaystyle \lambda _{a,b}=v(\{a,b\})-\lambda _{a}-\lambda _{b}=24-12-6=6}$.

The following apply analogously:

${\displaystyle \lambda _{a,c}=v(\{a,c\})-\lambda _{a}-\lambda _{c}=27-12-9=6}$

${\displaystyle \lambda _{b,c}=v(\{b,c\})-\lambda _{b}-\lambda _{c}=15-9-6=0}$

${\displaystyle \lambda _{a,b,c}=v(\{a,b,c\})-\lambda _{a}-\lambda _{b}-\lambda _{c}-\lambda _{a,b}-\lambda _{a,c}-\lambda _{b,c}=36-12-9-6-6-6-0=-3.}$

Shapley value as shared Harsanyi dividends

A coalition's Harsanyi dividend is paid when all the players are present. So it is plausible to split this performance equally among all the players in the coalition. This gives another formula for the Shapley value:

${\displaystyle \mathrm {Sh} _{i}(N,v)=\sum _{S\subseteq N:~i\in S}{\frac {\lambda _{S}}{|S|}}.}$

example

Look again at the example above with the number of players and notice that there are players in the coalitions ${\displaystyle N=\{a,b,c\}}$ ${\displaystyle b}$

${\displaystyle \{b\},~\{a,b\},~\{b,c\}\qquad {\text{und}}\qquad \{a,b,c\}}$

is included. Hence he gets

${\displaystyle \mathrm {Sh} _{b}(N,v)={\frac {\lambda _{b}}{|\{b\}|}}+{\frac {\lambda _{a,b}}{|\{a,b\}|}}+{\frac {\lambda _{b,c}}{|\{b,c\}|}}+{\frac {\lambda _{a,b,c}}{|\{a,b,c\}|}}={\frac {6}{1}}+{\frac {6}{2}}+{\frac {0}{2}}+{\frac {-3}{3}}=8}$

characterization

The Shapley value is the only payoff function that satisfies the following four axioms:

• Pareto efficiency: the value of the grand coalition is shared among the players.
• Symmetry: Players with the same marginal contribution get the same.
• Zero Player: A player with a marginal zero contribution to any coalition receives zero.
• Additivity: If the game can be broken down into two independent games, then each player's payout in the composite game is the sum of the payouts in the split games.

literature

• Lloyd S. Shapley: A Value for n-person Games . In: HW Kuhn and AW Tucker (Eds.): Contributions to the Theory of Games, volume II. (Annals of Mathematics Studies v. 28), Princeton University Press, Princeton 1953, ISBN 0-691-07935-8 , pp. 307-317.
• Harald Wiese: Cooperative game theory . Oldenbourg, Munich 2005, ISBN 3-486-57745-X .