Shapley value

From Wikipedia, the free encyclopedia

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?

Contents

[edit] 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) \; \to \Re , that goes from subsets of players to reals and is called a worth function, with the properties

  1. v(\varnothing) = 0
  2. v(S\cup 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{|S|!\; (n-|S|-1)!}{n!}(v(S\cup\{i\})-v(S))

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.

[edit] 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.

[edit] Glove game

The glove game is a coalitional game where the player's have left and right hand gloves and the goal is to form pairs.

N = \{1, 2, 3\}\,\!

where players 1 and 2 have left hand gloves and player 3 has a right hand glove

The value function for this coaltional game is

V(S) = \begin{cases} 1, & \mbox{if }s = \{1,3\},\{2,3\},\{1,2,3\} \\ 0, & \mbox{otherwise}\\ \end{cases}

Where the formula for calculating the Shapley Value is:

\phi_i(v)= \frac{1}{|N|!}\sum_R\left [ V(P_i^R + i) - V(P_i^R) \right ]\,\!

Where R\,\! is an ordering of the players and P_i^R\,\! is the set of players in N\,\! which precede i\,\! in the order R\,\!

The following table displays the Margin of Contribution of Player 1

Order R\,\! MC_1
{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(2,3,1) - V(2,3) = 1 - 1 = 0\,\!
{3,1,2}\,\! V(3,1) - V(3) = 1 - 0 =1\,\!
{3,2,1}\,\! V(3,2,1) - V(3,2) = 1 - 1 = 0\,\!
\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}.\,

[edit] 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_{i\in 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(S\cup\{i\}) = v(S\cup\{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:

φi(v + w) = φi(v) + φi(w)

for every i in N.

6. Null player: a null player should receive zero. A player i is null if v(S\cup \{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.

[edit] See also

[edit] 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.
v • d • e
Topics in game theory
Definitions
Equilibrium concepts
Strategies
Classes of games
Games
Theorems