Shapley value

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

1 Formal definition 2 Example 3 Properties 4 Literature

Formal definition

To formalize this situation, we use the notion of a coalition game: we start out with a set N (of actors) and a (gain-) function v : 2^N → 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 actors 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 additivity condition expresses the fact that collaboration can only help but never hurt.

The Shapley value is one way to distribute the total gains to the actors, 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 actors and the sum extends over all subsets S of N not containing the actor 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 w₁,...,w_k, each of whom contributes an amount p to the total profit. So N = {o, w₁,...,w_k} 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.

Literature

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.de:Shapley-Wert