Editing Shapley value (section)

== 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 \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 {{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 <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 [[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>.

=== In terms of synergy ===
[[File:Shapley Value Venn Diagram.jpg|thumb|Venn Diagram displaying synergies for Shapley values]]

[[File:Shapley Value Synergy Division Venn Diagram.jpg|thumb|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#Other forms|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">{{Cite journal|last=Grabisch|first=Michel|date=October 1997|title=Alternative Representations of Discrete Fuzzy Measures for Decision Making|journal=International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems|language=en-US|volume=5|issue=5|pages=587–607|doi=10.1142/S0218488597000440|issn=0218-4885}}</ref><ref name="Grabisch Representations 2">{{cite journal |last1=Grabisch |first1=Michel |title=k-order additive discrete fuzzy measures and their representation |journal=Fuzzy Sets and Systems |date=1 December 1997 |volume=92 |issue=2 |pages=167–189 |doi=10.1016/S0165-0114(97)00168-1|issn=0165-0114}}</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.