View source for Shapley value

The '''Shapley value''' is a solution concept in cooperative [[game theory]]. It was named in honor of [[Lloyd Shapley]], who introduced it in 1953.<ref name=":0">{{cite book|title=Contributions to the Theory of Games|last=Shapley|first=Lloyd S.|publisher=Princeton University Press|year=1953|isbn=9781400881970|editor-last=Kuhn|editor-first=H. W.|series=Annals of Mathematical Studies|volume=28|location=|pages=307–317|chapter=A Value for n-person Games|doi=10.1515/9781400881970-018|editor2-first=A. W.|editor2-last=Tucker|chapterurl=}}</ref><ref>{{cite book|title=The Shapley Value: Essays in Honor of Lloyd S. Shapley|last=|first=|publisher=Cambridge University Press|year=1988|isbn=0-521-36177-X|editor-last=Roth|editor-first=Alvin E.|location=Cambridge|pages=|doi=10.1017/CBO9780511528446}}</ref> To each [[cooperative game]] it assigns a unique distribution (among the players) of a total surplus generated by the coalition of all players. The Shapley value is characterized by a collection of desirable properties. Hart (1989) provides a survey of the subject.<ref>{{cite book|title=The New Palgrave: Game Theory|last=Hart|first=Sergiu|publisher=Norton|year=1989|isbn=978-0-333-49537-7|editor-last=Eatwell|editor-first=J.|location=|pages=210–216|chapter=Shapley Value|doi=10.1007/978-1-349-20181-5_25|editor2-first=M.|editor2-last=Milgate|editor3-first=P.|editor3-last=Newman}}</ref><ref>{{cite web |title=A Bibliography of Cooperative Games: Value Theory |first=Sergiu |last=Hart |date=May 12, 2016 |url=http://www.ma.huji.ac.il/~hart/value.html }}</ref>

The setup is as follows: a coalition of players cooperates, and obtains a certain overall gain from that cooperation. Since some players may contribute more to the coalition than others or may possess different  bargaining power (for example threatening to destroy the whole surplus), what final distribution of generated surplus among the players should arise in any particular game? Or phrased differently: how important is each player to the overall cooperation, and what payoff can he or she reasonably expect? The Shapley value provides one possible answer to this question.

For cost-sharing games with concave cost functions, the optimal cost-sharing rule that optimizes the [[price of anarchy]], followed by the [[price of stability]], is precisely the Shapley value cost-sharing rule.<ref>{{Cite journal|last=Phillips|first=Matthew|last2=Marden|first2=Jason R.|date=July 2018|title=Design Tradeoffs in Concave Cost-Sharing Games|journal=IEEE Transactions on Automatic Control|language=en-US|volume=63|issue=7|pages=2242–2247|doi=10.1109/tac.2017.2765299|issn=0018-9286}}</ref>

== Formal definition ==

Formally, a '''coalitional game''' is defined as:
There is a set ''N'' (of ''n'' players) and a [[function (mathematics)|function]] <math> v </math> that maps subsets of players to the real numbers:  <math> v \; : \; 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 ''S'' is a coalition of players, then ''v''(''S''), called the worth of coalition ''S'', 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 {{cite book |first=Tatsuro |last=Ichiishi |title=Game Theory for Economic Analysis |location=New York |publisher=Academic Press |year=1983 |isbn=0-12-370180-5 |pages=118–120 |url=https://books.google.com/books?id=zFm7AAAAIAAJ&pg=PA118 }}</ref> the amount that player ''i'' gets 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>

where ''N'' is the total number of players and the sum extends over all subsets ''S'' of ''N'' not containing player ''i''. The formula can be interpreted as follows: imagine the coalition being formed one actor at a time, with each actor demanding their contribution ''v''(''S''∪{''i''}) − ''v''(''S'') as a fair compensation, and then for each actor take the average of this contribution over the possible different [[permutation]]s 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>. Finally, it can also be expressed as

: <math>\varphi_i(v) = \frac{1}{N} \sum_{S \subseteq N \setminus \{i\}} \binom{N-1}{|S|}^{-1} (v(S \cup \{i\}) - v(S))</math>

which can be interpreted as

: <math>\varphi_i(v) = \frac{1}{\text{number of players}} \sum_{\text{coalitions excluding }i} \frac{\text{marginal contribution of }i\text{ to coalition}}{\text{number of coalitions excluding } i \text{ of this size}}</math>

== Examples ==
=== Business example ===
Consider a simplified description of a business. An owner, ''o'', provides crucial capital in the sense that without him no gains can be obtained. There are ''k'' workers ''w''<sub>1</sub>,...,''w''<sub>''k''</sub>, each of whom contributes an amount ''p'' to the total profit. Let

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

The value function for this coalitional game is
:<math>
v(S) = 
\begin{cases}
  mp,  & \text{if }o \in S\\
  0, & \text{otherwise}\\
\end{cases}
</math>
where ''m'' is the cardinality of <math>S \setminus \{o\}</math>. Computing the Shapley value for this coalition game leads to a value of {{sfrac|''kp''|2}} for the owner and {{sfrac|''p''|2}} for each worker.

=== 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 {{mvar|R}} is an ordering of the players and <math>P_i^R</math> is the set of players in {{mvar|N}} which precede {{mvar|i}} in the order {{mvar|R}}.

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,2,3\}) - v(\{2,3\}) = 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.

=== 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} \left [ v(P_i^R \cup \left \{ i \right \}) - v(P_i^R) \right ]
= \frac{1}{|N|!} \sum_R v(N) = \frac{1}{|N|!}
(N!)\cdot v(N) = v(N)</math>

:since there are ''N''! different orderings&nbsp;''R''.

=== 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&nbsp;<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&nbsp;<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>.

Given a player set <math>N</math>, 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.

=== Stand-alone test ===
If ''v'' is a [[Subadditive set function|subadditive set function]], i.e., <math>v(S\sqcup T) \leq v(S) + v(T)</math>, then for each agent ''i'': <math>\varphi_i(v) \leq v(\{i\})</math>.

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

So, if the cooperation has positive externalities, all agents (weakly) gain, and if it has negative externalities, all agents (weakly) lose.<ref name=":1">{{Cite Moulin 2004}}</ref>{{Rp|147-156}}

=== Anonymity ===
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 <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 i as the arguments.

== Characterization ==
The Shapley value not only has desirable properties, it is also the ''only'' payment rule satisfying some subset of these properties. For example, it is the only payment rule satisfying the four properties of Efficiency, Symmetry, Linearity and Null player.<ref name=":0" /> See <ref name=":1" />{{Rp|147-156}} for more characterizations.

== 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 [[atom (measure theory)|non-atomic]] [[measure (mathematics)|measure]]), creating the diagonal formula.<ref>{{cite book |first=Robert J. |last=Aumann |first2=Lloyd S. |last2=Shapley |title=Values of Non-Atomic Games |publisher=Princeton Univ. Press |location=Princeton |year=1974 |isbn=0-691-08103-4 }}</ref> This was later extended by [[Jean-François Mertens]] and [[Abraham Neyman]].

As seen above, the value of an n-person game associates to each player the expectation of his contribution to the worth or the coalition or players before him 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 as a good sample of the players so that the value of a given infinitesimal player {{mvar|ds}} around  as "his" contribution to the worth of a "perfect" sample of the population of all players.

Symbolically, if {{mvar|v}} is the coalitional worth function associating to each coalition {{mvar|c}} measured subset of a measurable set {{mvar|I}} that can be thought as <math>I=[0,1]</math> without loss of generality.

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

where <math>(Sv)(ds)</math>denotes  the Shapley value of the infinitesimal player {{mvar|ds}} in the game, {{mvar|tI}} is a perfect sample of the all-player set {{mvar|I}} containing a proportion {{mvar|t}} of all the players, and <math>tI+ ds</math> is the coalition obtained after {{mvar|ds}} joins {{mvar|tI}}. This is the heuristic form of the [[Polygon|diagonal formula]].

Assuming some regularity of the worth function, for example assuming {{mvar|v}}  can be represented as differentiable function of a non-atomic measure on  {{mvar|I}}, {{mvar|&mu;}}, <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> ( <math> 1_c()</math> the characteristic function of {{mvar|c}}). 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 {{mvar|t}} 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 {{mvar|&mu;}} can be vector valued (as long as the function is defined and differentiable on the range of {{mvar|&mu;}}, 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 {{mvar|f}} 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>{{cite journal |last=Mertens |first=Jean-François |year=1980 |title=Values and Derivatives |journal=Mathematics of Operations Research |volume=5 |issue=4 |pages=523–552 |jstor=3689325 |doi=10.1287/moor.5.4.523}}</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>{{cite journal |last=Mertens |first=Jean-François |year=1988 |title=The Shapley Value in the Non Differentiable Case |journal=International Journal of Game Theory |volume=17 |issue=1 |pages=1–65 |doi=10.1007/BF01240834 }}</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.).[http://ratio.huji.ac.il/dp/neyman/values.pdf]</ref>

== Generalization to coalitions ==
The Shapley value only assigns values to the individual agents.  It has been generalized<ref>{{cite journal|last= Owen|first= Guillermo|year=1972|title=Multilinear Extensions of Games|journal= Management Science|volume=18|issue=5|pages=64–79|doi=10.1287/mnsc.18.5.64|hdl= 10338.dmlcz/135728}}</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>

== See also ==
* [[Airport problem]]
* [[Banzhaf power index]]
* [[Shapley–Shubik power index]]

== References ==
{{Reflist|30em}}

== Further reading ==
* {{cite book |first=James W. |last=Friedman |title=Game Theory with Applications to Economics |location=New York |publisher=Oxford University Press |year=1986 |isbn=0-19-503660-3 |pages=209–215 |url=https://books.google.com/books?id=20i7AAAAIAAJ&pg=PA209 }}

== External links ==
* {{springer|title=Shapley value|id=p/s084780}}

{{game theory}}

[[Category:Game theory]]
[[Category:Cooperative games]]
[[Category:Fair division]]
[[Category:Lloyd Shapley]]