Shapley value
From Free net encyclopedia
In game theory, a Shapley value, named in honor 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 fairly distribute the gains among the actors. Or phrased differently: how important is each actor to the overall operation, and what payoff can they reasonably expect?
Contents |
Formal definition
To formalize this situation, we use the notion of a coalitional game: we start out with a set N (of players) and a (worth function) function v : 2N → R with the properties
- <math>v(\varnothing) = 0</math>
- <math>v(S\cup T) \ge v(S) + v(T) </math>
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 (of the coalitional game v) 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
- <math>\phi_i(v)=\sum_{i\not\in S\subseteq N} \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 justified if one imagines 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 averaging over the possible different permutations in which the coalition can be formed.
Example
Consider a simplified description of a business. We have an owner o, who does not work but provides the crucial capital, meaning that without him no gains can be obtained. Then we have workers w1,...,wk, each of whom contributes an amount p to the total profit. So N = {o, w1,...,wk} and v(S) = 0 if o is not a member of S and v(S) = mp if S contains the owner and m workers. Computing the Shapley value for this coalition game leads to a value of kp/2 for the owner and p/2 for each worker.
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 they would have gotten had they not collaborated at all.
2. The total gain is distributed:
- <math>\sum_{i\in N}\phi_i(v) = v(N)</math>
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 labeling of the actors doesn't play a role in the assignment of their gains.
4. If i and j are two actors which are equivalent in the sense that
- <math>v(S\cup\{i\}) = v(S\cup\{j\})</math>
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:
- <math>\phi_i(v+w) = \phi_i(v) + \phi_i(w)</math>
for every i in N.
In fact, the Shapley value is the only function that has the properties 2, 3 and 5.
See also
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.