Shapley value

In game theory, a Shapley value, named in honour of Lloyd Shapley, who introduced it in 1953, describes one approach to the fair allocation of gains obtained by cooperation among several actors.

The setup is as follows: a coalition of actors cooperates, and obtains a certain overall gain from that cooperation. Since some actors may contribute more to the coalition than others, the question arises how to distribute fairly the gains among the actors. Or phrased differently: how important is each actor to the overall operation, and what payoff can they reasonably expect?

Formal definition

To formalize this situation, we use the notion of a coalitional game:we start out with a set "N" (of "n" players) and a function $v\; ;\; :\; ;\; mathcal\{P\}(N)\; ;\; o\; Re$, that goes from subsets of players to reals and is called a worth function, with the properties

# $v(varnothing)\; =\; 0$
# $v(Scup\; T)\; ge\; v(S)\; +\; v(T)$, whenever "S" and "T" are disjoint subsets of "N".

The interpretation of the function "v" is as follows: if "S" is a coalition of players which agree to cooperate, then "v"("S") describes the total expected gain from this cooperation, independent of what the actors outside of "S" do. The super additivity condition (second property) expresses the fact that collaboration can only help but never hurt.

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 to be listed below. The amount that actor "i" gets if the gain function "v" is being used is

:$phi\_i(v)=sum\_\{S\; subseteq\; N\; setminus\{i\; frac$

:$phi\_1(v)=(1)(frac\{1\}\{6\})=frac\{1\}\{6\},!$

By a symmetry argument it can be shown that:$phi\_2(v)=phi\_1(v)=frac\{1\}\{6\},!$

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

:$phi\_3(v)\; =\; frac\{4\}\{6\}\; =\; frac\{2\}\{3\}.,$

Properties

The Shapley value has the following desirable properties:

1. φ_"i"("v") ≥ "v"({"i"}) for every "i" in "N", i.e. every actor gets at least as much as he or she would have got had they not collaborated at all.

2. The total gain is distributed::$sum\_\{iin\; N\}phi\_i(v)\; =\; v(N)$

3. If "i" and "j" are two actors, and "w" is the gain function that acts just like "v" except that the roles of "i" and "j" have been exchanged, then φ_"i"("v") = φ_"j"("w"). In essence, this means that the labelling of the actors doesn't play a role in the assignment of their gains. Such a function is said to be "anonymous".

4. If "i" and "j" are two actors who are equivalent in the sense that :$v(Scup\{i\})\; =\; v(Scup\{j\})$for every subset "S" of "N" which contains neither "i" nor "j", then φ_"i"("v") = φ_"j"("v").

5. Additivity: if we combine two coalition games described by gain functions "v" and "w", then the distributed gains should correspond to the gains derived from "v" and the gains derived from "w"::$phi\_i(v+w)\; =\; phi\_i(v)\; +\; phi\_i(w)$for every "i" in "N".

6. Null player: a null player should receive zero. A player $i$ is "null" if $v(Scup\; \{i\})\; =\; v(S)$ for all $S$ not containing $i$.

In fact, given a player set "N", the Shapley value is the only function, defined on the class of all superadditive games which have "N" as player set, that satisfies properties 2, 3, 5 and 6.

ee also

* Airport problem
* Banzhaf power index
* Shapley-Shubik power index

References

* Lloyd S. Shapley. "A Value for n-person Games". In "Contributions to the Theory of Games", volume II, by H.W. Kuhn and A.W. Tucker, editors. "Annals of Mathematical Studies" v. 28, pp. 307-317. Princeton University Press, 1953.
* Alvin E. Roth (editor). "The Shapley value, essays in honor of Lloyd S. Shapley". Cambridge University Press, Cambridge, 1988.
* Sergiu Hart, "Shapley Value", The New Palgrave: Game Theory, J. Eatwell, M. Milgate and P. Newman (Editors), Norton, pp.210-216, 1989.

External links

[http://www.ma.huji.ac.il/~hart/value.html] - "A Bibliography of Cooperative Games: Value Theory" by Sergiu Hart