Shapley value

Template:Short description In cooperative game theory, the Shapley value is a method (solution concept) for fairly distributing the total gains or costs among a group of players who have collaborated. For example, in a team project where each member contributed differently, the Shapley value provides a way to determine how much credit or blame each member deserves. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Memorial Prize in Economic Sciences for it in 2012.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref><ref>Template:Cite book</ref>

The Shapley value determines each player's contribution by considering how much the overall outcome changes when they join each possible combination of other players, and then averaging those changes. In essence, it calculates each player's average marginal contribution across all possible coalitions.<ref>Template:Cite book</ref><ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref> It is the only solution that satisfies four fundamental properties: efficiency, symmetry, additivity, and the dummy player (or null player) property,<ref name=":2" /> which are widely accepted as defining a fair distribution.

This method is used in many fields, from dividing profits in business partnerships to understanding feature importance in machine learning.

File:Lloyd Shapley 2 2012.jpg

Lloyd Shapley in 2012

Formal definition

Formally, a coalitional game is defined as: There is a set N (of n players) and a function <math> v </math> that maps subsets of players to the real numbers: <math> v \colon 2^N \to \mathbb{R} </math>, with <math> v ( \emptyset ) = 0 </math>, where <math>\emptyset</math> denotes the empty set. The function <math> v </math> is called a characteristic function.

The function <math>v</math> has the following meaning: if <math>S</math> is a coalition of players, then <math>v(S)</math>, called the worth of coalition <math>S</math> describes the total expected sum of payoffs the members of <math>S</math> can obtain by cooperation.

The Shapley value is one way to distribute the total gains to the players, assuming that they all collaborate. It is a "fair" distribution in the sense that it is the only distribution with certain desirable properties listed below. According to the Shapley value,<ref>For a proof of unique existence, see Template:Cite book</ref> the amount that player <math>i</math> is given in a coalitional game <math>(v, N) </math> is

<math>\varphi_i(v)=\sum_{S \subseteq N \setminus

\{i\}} \frac{|S|!\; (n-|S|-1)!}{n!}(v(S\cup\{i\})-v(S)) </math>

<math> \quad \quad \quad = \frac{1}{n} \sum_{S \subseteq N \setminus

\{i\}} {n - 1 \choose |S|}^{-1} (v(S\cup\{i\})-v(S)) </math>

where <math>n</math> is the total number of players and the sum extends over all subsets <math>S</math> of <math>N</math> not containing player <math>i</math>, including the empty set. Also note that <math>{n \choose k}</math> is the binomial coefficient. The formula can be interpreted as follows: imagine the coalition being formed one actor at a time, with each actor demanding their contribution <math>v(S\cup \{ i \} ) - v(S)</math> as a fair compensation, and then for each actor take the average of this contribution over the possible different permutations in which the coalition can be formed.

An alternative equivalent formula for the Shapley value is:

<math>\varphi_i(v)= \frac{1}{n!}\sum_R\left [ v(P_i^R \cup \left \{ i \right \}) - v(P_i^R) \right ]</math>

where the sum ranges over all <math>n!</math> orders <math>R</math> of the players and <math>P_i^R</math> is the set of players in <math>N</math> which precede <math>i</math> in the order <math>R</math>.

In terms of synergy

File:Shapley Value Venn Diagram.jpg

Venn Diagram displaying synergies for Shapley values

File:Shapley Value Synergy Division Venn Diagram.jpg

Venn Diagram of the division of synergies that sum to the Shapley Value

From the characteristic function <math>v</math> one can compute the synergy that each group of players provides. The synergy is the unique function <math> w \colon 2^N \to \mathbb{R} </math>, such that

<math>v(S) = \sum_{R \subseteq S } w(R) </math>

for any subset <math>S \subseteq N </math> of players. In other words, the 'total value' of the coalition <math>S</math> comes from summing up the synergies of each possible subset of <math>S</math>.

Given a characteristic function <math>v</math>, the synergy function <math>w</math> is calculated via

<math>w(S) = \sum_{R \subseteq S } (-1)^{|S| - |R|} v(R) </math>

using the Inclusion exclusion principle. In other words, the synergy of coalition <math>S</math> is the value <math>v(S)</math> , which is not already accounted for by its subsets.

The Shapley values are given in terms of the synergy function by<ref name="Grabisch Representations">Template:Cite journal</ref><ref name="Grabisch Representations 2">Template:Cite journal</ref>

<math>\varphi_i(v) = \sum_{i \in S \subseteq N } \frac{w(S)}{|S|} </math>

where the sum is over all subsets <math>S</math> of <math>N</math> that include player <math>i</math>.

This can be interpreted as

<math>\varphi_i(v) = \sum_{\text{coalitions including i}} \frac{\text{synergy of the coalition}}{\text{number of members in the coalition}} </math>

In other words, the synergy of each coalition is divided equally between all members.

This can be interpreted visually with a Venn Diagram. In the first example diagram above, each region has been labeled with the synergy bonus of the corresponding coalition. The total value produced by a coalition is the sum of synergy bonuses of the composing subcoalitions - in the example, the coalition of the players labeled "You" and "Emma" would produce a profit of <math> 30+20+40=90 </math> dollars, as compared to their individual profits of <math> 30 </math> and <math> 20 </math> dollars respectively. The synergies are then split equally among each member of the subcoalition that contributes that synergy - as displayed in the second diagram.

Examples

Business example

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

<math>N = \{o, w_1,\ldots,w_m\}.</math>

The value function for this coalitional game is

<math>

v(S) = \begin{cases}

 (|S|-1)p  & \text{if }o \in S\;,\\
 0 & \text{otherwise}\;.\\

\end{cases} </math> Computing the Shapley value for this coalition game leads to a value of Template:Sfrac for the owner and Template:Sfrac for each one of the m workers.

This can be understood from the perspective of synergy. The synergy function <math>w</math> is

<math>

w(S) = \begin{cases}

 p,  & \text{if } S = \{ o, w_i \} \\
 0, & \text{otherwise}\\

\end{cases} </math>

so the only coalitions that generate synergy are one-to-one between the owner and any individual worker.

Using the above formula for the Shapley value in terms of <math>w</math> we compute

<math>\varphi_{w_i} = \frac{w(\{o, w_i \})}{2} = \frac{p }{2} </math>

and

<math>\varphi_o = \sum_{i=1}^m \frac{w(\{o, w_i \})}{2} = \frac{m p }{2} </math>

The result can also be understood from the perspective of averaging over all orders. A given worker joins the coalition after the owner (and therefore contributes p) in half of the orders and thus makes an average contribution of <math>\frac p2</math> upon joining. When the owner joins, on average half the workers have already joined, so the owner's average contribution upon joining is <math>\frac{mp}2</math>.

Glove game

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

<math>N = \{1, 2, 3\},</math>

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

<math>

v(S) = \begin{cases}

 1  & \text{if }S \in \left\{ \{1,3\},\{2,3\},\{1,2,3\} \right\};\\
 0 & \text{otherwise}.\\

\end{cases} </math>

The formula for calculating the Shapley value is

<math>\varphi_i(v)= \frac{1}{|N|!}\sum_R\left [ v(P_i^R \cup \left \{ i \right \}) - v(P_i^R) \right ],</math>

where Template:Mvar is an ordering of the players and <math>P_i^R</math> is the set of players in Template:Mvar which precede Template:Mvar in the order Template:Mvar.

The following table displays the marginal contributions of Player 1.

<math>

\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,3,2\}) - v(\{3,2\}) = 1 - 1 = 0 \end{array} </math>

Observe

<math>\varphi_1(v)= \!\left(\frac{1}{6}\right)(1)=\frac{1}{6}.</math>

By a symmetry argument it can be shown that

<math>\varphi_2(v)=\varphi_1(v)=\frac{1}{6}.</math>

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

<math>\varphi_3(v) = \frac{4}{6} = \frac{2}{3}.</math>

Properties

The Shapley value has many desirable properties. Notably, it is the only payment rule satisfying the four properties of Efficiency, Symmetry, Linearity and Null player (or dummy player).<ref name=":2">Template:Cite book</ref> See<ref name=":1" />Template:Rp for more characterizations of the Shapley value.

Efficiency

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:

<math>\sum_{i\in N}\varphi_i(v) = v(N)</math>

Proof: <math>\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)</math>

since <math>\sum_{i\in N} v(P_i^R \cup \left \{ i \right \}) - v(P_i^R)</math> is a telescoping sum and there are <math>|N|!</math> different orderings <math>R</math>.

Symmetry

If <math>i</math> and <math>j</math> are two actors who are equivalent in the sense that

<math>v(S\cup\{i\}) = v(S\cup\{j\})</math>

for every subset <math>S</math> of <math>N</math> which contains neither <math>i</math> nor <math>j</math>, then <math>\varphi_i(v) = \varphi_j(v)</math>.

This property is also called equal treatment of equals.

Linearity

If two coalition games described by gain functions <math>v</math> and <math>w</math> are combined, then the distributed gains should correspond to the gains derived from <math>v</math> and the gains derived from <math>w</math>:

<math>\varphi_i(v+w) = \varphi_i(v) + \varphi_i(w)</math>

for every <math>i</math> in <math>N</math>. Also, for any real number <math>a</math>,

<math>\varphi_i(a v) = a \varphi_i(v)</math>

for every <math>i</math> in <math>N</math>.

Null player

The Shapley value <math>\varphi_i(v)</math> of a null player <math>i</math> in a game <math>v</math> is zero. A player <math>i</math> is null in <math>v</math> if <math>v(S\cup \{i\}) = v(S)</math> for all coalitions <math>S</math> that do not contain <math>i</math>.

Stand-alone test

If <math>v</math> is a subadditive set function, i.e., <math>v(S\sqcup T) \leq v(S) + v(T)</math>, then for each agent <math>i</math>: <math>\varphi_i(v) \leq v(\{i\})</math>.

Similarly, if <math>v</math> is a superadditive set function, i.e., <math>v(S\sqcup T) \geq v(S) + v(T)</math>, then for each agent <math>i</math>: <math>\varphi_i(v) \geq v(\{i\})</math>.

So, if the cooperation has positive synergy, all agents (weakly) gain, and if it has negative synergy, all agents (weakly) lose.<ref name=":1">Template:Cite Moulin 2004</ref>Template:Rp

Anonymity

If <math>i</math> and <math>j</math> are two agents, and <math>w</math> is a gain function that is identical to <math>v</math> except that the roles of <math>i</math> and <math>j</math> have been exchanged, then <math>\varphi_i(v) = \varphi_j(w)</math>. This means that the labeling of the agents doesn't play a role in the assignment of their gains.

Marginalism

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

Aumann–Shapley value

In their 1974 book, Lloyd Shapley and Robert Aumann extended the concept of the Shapley value to infinite games (defined with respect to a non-atomic measure), creating the diagonal formula.<ref name=":0">Template:Cite book</ref> This was later extended by Jean-François Mertens and Abraham Neyman.

As seen above, the value of an n-person game associates with each player the expectation of their contribution to the worth of the coalition of players before them in a random ordering of all the players. When there are many players and each individual plays only a minor role, the set of all players preceding a given one is heuristically thought of as a good sample of all players. The value of a given infinitesimal player Template:Mvar is then defined as "their" contribution to the worth of a "perfect" sample of all the players.

Symbolically, if Template:Mvar is the coalitional worth function that associates each coalition Template:Mvar with its value, and each coalition Template:Mvar is a measurable subset of the measurable set Template:Mvar of all players, that we assume to be <math>I=[0,1]</math> without loss of generality, the value <math>(Sv)(ds)</math> of an infinitesimal player Template:Mvar in the game is

<math>

(Sv)(ds) = \int_0^1 (\, v(tI + ds)- v(tI)\,)\,dt. </math>

Here Template:Mvar is a perfect sample of the all-player set Template:Mvar containing a proportion Template:Mvar of all the players, and <math>tI+ ds</math> is the coalition obtained after Template:Mvar joins Template:Mvar. This is the heuristic form of the diagonal formula.<ref name=":0" />

Assuming some regularity of the worth function, for example, assuming Template:Mvar can be represented as differentiable function of a non-atomic measure on Template:Mvar, Template:Mvar, <math>v(c)=f(\mu(c))</math> with density function <math>\varphi</math>, with <math>\mu(c)=\int 1_c(u)\varphi(u)\,du,</math> where <math> 1_c(\bullet)</math> is the characteristic function of Template:Mvar. Under such conditions

<math>\mu(tI)=t\mu(I)

</math>,

as can be shown by approximating the density by a step function and keeping the proportion Template:Mvar for each level of the density function, and

<math>

v(tI + ds)=f(t\mu(I))+f'(t\mu(I))\mu(ds) .</math>

The diagonal formula has then the form developed by Aumann and Shapley (1974)

<math>

(Sv)(ds) = \int_0^1 f'_{t\mu(I)}(\mu(ds)) \, dt </math>

Above Template:Mvar can be vector valued (as long as the function is defined and differentiable on the range of Template:Mvar, the above formula makes sense).

In the argument above if the measure contains atoms <math>\mu(tI)=t\mu(I)</math> is no longer true—this is why the diagonal formula mostly applies to non-atomic games.

Two approaches were deployed to extend this diagonal formula when the function Template:Mvar is no longer differentiable. Mertens goes back to the original formula and takes the derivative after the integral thereby benefiting from the smoothing effect. Neyman took a different approach. Going back to an elementary application of Mertens's approach from Mertens (1980):<ref>Template:Cite journal</ref>

<math>

(Sv)(ds) = \lim_{\varepsilon \to 0, \varepsilon>0} \frac{1}{\varepsilon}\int_0^{1-\varepsilon} (f(t+\varepsilon \mu(ds))-f(t)) \, dt </math>

This works for example for majority games—while the original diagonal formula cannot be used directly. How Mertens further extends this by identifying symmetries that the Shapley value should be invariant upon, and averaging over such symmetries to create further smoothing effect commuting averages with the derivative operation as above.<ref>Template:Cite journal</ref> A survey for non atomic value is found in Neyman (2002)<ref>Neyman, A., 2002. Value of Games with infinitely many Players, "Handbook of Game Theory with Economic Applications," Handbook of Game Theory with Economic Applications, Elsevier, edition 1, volume 3, number 3, 00. R.J. Aumann & S. Hart (ed.).[1]</ref>

Generalization to coalitions

The Shapley value only assigns values to the individual agents. It has been generalized<ref>Template:Cite journal</ref> to apply to a group of agents C as,

<math>

\varphi_C(v) = \sum_{T \subseteq N \setminus C} \frac{(n - |T| - |C|)! \; |T|!}{(n - |C| + 1)!} \sum_{S \subseteq C} (-1)^{|C| - |S|} v( S \cup T ) \; . </math>

In terms of the synergy function <math>w</math> above, this reads<ref name="Grabisch Representations"/><ref name="Grabisch Representations 2"/>

<math>

\varphi_C(v) = \sum_{C \subseteq T \subseteq N} \frac{w(T)}{|T| - |C| + 1} </math>

where the sum goes over all subsets <math>T</math> of <math>N</math> that contain <math>C</math>.

This formula suggests the interpretation that the Shapley value of a coalition is to be thought of as the standard Shapley value of a single player, if the coalition <math>C</math> is treated like a single player.

Value of a player to another player

The Shapley value <math>\varphi_i(v)</math> was decomposed by Hausken and Matthias<ref>Template:Cite journal</ref> into a matrix of values

<math>

\varphi_{ij}(v) = \sum_{S \subseteq N} \frac{(|S| - 1)! \; (n - |S|)!}{n!} (v(S) - v(S \setminus \{i\}) - v(S \setminus \{j\}) + v(S \setminus \{i, j\})) \sum_{t=|S|}^n \frac{1}{t} </math>

Each value <math>\varphi_{ij}(v) </math> represents the value of player <math>i</math> to player <math>j</math>. This matrix satisfies

<math>

\varphi_i(v) = \sum_{j \in N} \varphi_{ij}(v) </math>

i.e. the value of player <math>i</math> to the whole game is the sum of their value to all individual players.

In terms of the synergy <math>w</math> defined above, this reads

<math>

\varphi_{ij}(v) = \sum_{\{i, j\} \subseteq S \subseteq N} \frac{w(S)}{|S|^2} </math>

where the sum goes over all subsets <math>S</math> of <math>N</math> that contain <math>i</math> and <math>j</math>.

This can be interpreted as sum over all subsets that contain players <math>i</math> and <math>j</math>, where for each subset <math>S</math> you

• take the synergy <math>w(S)</math> of that subset
• divide it by the number of players in the subset <math>|S|</math>. Interpret that as the surplus value player <math>i</math> gains from this coalition
• further divide this by <math>|S|</math> to get the part of player <math>i</math>'s value that's attributed to player <math>j</math>

In other words, the synergy value of each coalition is evenly divided among all <math>|S|^2</math> pairs <math>(i, j)</math> of players in that coalition, where <math>i</math> generates surplus for <math>j</math>.

Shapley value regression

Shapley value regression is a statistical method used to measure the contribution of individual predictors in a regression model. In this context, the "players" are the individual predictors or variables in the model, and the "gain" is the total explained variance or predictive power of the model. This method ensures a fair distribution of the total gain among the predictors, attributing each predictor a value representing its contribution to the model's performance. Lipovetsky (2006) discussed the use of Shapley value in regression analysis, providing a comprehensive overview of its theoretical underpinnings and practical applications.<ref>Template:Cite journal</ref>

Shapley value contributions are recognized for their balance of stability and discriminating power, which make them suitable for accurately measuring the importance of service attributes in market research.<ref>Template:Cite journal</ref> Several studies have applied Shapley value regression to key drivers analysis in marketing research. Pokryshevskaya and Antipov (2012) utilized this method to analyze online customers' repeat purchase intentions, demonstrating its effectiveness in understanding consumer behavior.<ref>Template:Cite journal</ref> Similarly, Antipov and Pokryshevskaya (2014) applied Shapley value regression to explain differences in recommendation rates for hotels in South Cyprus, highlighting its utility in the hospitality industry.<ref>Template:Cite journal</ref> Further validation of the benefits of Shapley value in key-driver analysis is provided by Vriens, Vidden, and Bosch (2021), who underscored its advantages in applied marketing analytics.<ref>Template:Cite journal</ref>

In machine learning

The Shapley value provides a principled way to explain the predictions of nonlinear models common in the field of machine learning. By interpreting a model trained on a set of features as a value function on a coalition of players, Shapley values provide a natural way to compute which features contribute to a prediction <ref name="Lundberg Lee pp. 4765–4774">Template:Cite journal</ref> or contribute to the uncertainty of a prediction.<ref name= "Watson et al">Template:Cite journal</ref> This unifies several other methods including Locally Interpretable Model-Agnostic Explanations (LIME),<ref name="Ribeiro Singh Guestrin p. ">Template:Cite conference</ref> DeepLIFT,<ref name="Shrikumar Greenside Kundaje 2017 pp. 3145–3153">Template:Cite journal</ref> and Layer-Wise Relevance Propagation.<ref name="Bach Binder Montavon Klauschen p=e0130140">Template:Cite journal</ref><ref>Template:Cite journal</ref>

Distributional values are an extension of the Shapley value and related value operators designed to preserve the probabilistic output of predictive models in machine learning, including neural network classifiers and large language models.<ref>Template:Cite journal</ref>

The statistical understanding of Shapley values remains an ongoing research question. A smooth version, called Shapley curves,<ref>Template:Cite journal</ref> achieves the minimax rate and is shown to be asymptotically Gaussian in a nonparametric setting. Confidence intervals for finite samples can be obtained via the wild bootstrap.

See also

• Airport problem
• Banzhaf power index
• Shapley–Shubik power index

Further reading

• Template:Cite book

External links

• Template:Springer
• Shapley Value Calculator
• Calculating a Taxi Fare using the Shapley Value