The Shapley value is a solution concept in cooperative game theory. It was named in honour of Lloyd Shapley, who introduced it in 1953. To each cooperative game it assigns a unique distribution (among the players) of a total surplus generated by the coalition of all players. The Shapley value is characterized by a collection of desirable properties. Hart (1989) provides a survey of the subject.
Contents
The setup is as follows: a coalition of players cooperates, and obtains a certain overall gain from that cooperation. Since some players may contribute more to the coalition than others or may possess different bargaining power (for example threatening to destroy the whole surplus), what final distribution of generated surplus among the players should arise in any particular game? Or phrased differently: how important is each player to the overall cooperation, and what payoff can he or she reasonably expect? The Shapley value provides one possible answer to this question.
Formal definition
Formally, a coalitional game is defined as: There is a set N (of n players) and a function
The function
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, the amount that player i gets given in a coalitional game
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 interpreted as follows: imagine 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 for each actor take the average of this contribution over the possible different permutations in which the coalition can be formed.
An alternative equivalent formula for the Shapley value is:
where the sum ranges over all
which can be interpreted as
Example
Consider a simplified description of a business. An owner, o, provides crucial capital in the sense that without him no gains can be obtained. There are k 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.
Glove game
The glove game is a coalitional game where the players have left and right hand gloves and the goal is to form pairs.
where players 1 and 2 have right hand gloves and player 3 has a left hand glove
The value function for this coalitional game is
Where the formula for calculating the Shapley value is:
Where
The following table displays the marginal contributions of Player 1
By a symmetry argument it can be shown that
Due to the efficiency axiom the sum of all the Shapley values is equal to 1, which means that
Properties
The Shapley value has the following desirable properties:
1. Efficiency: The total gain is distributed:
2. Symmetry: If i and j are two actors who are equivalent in the sense that
for every subset S of N which contains neither i nor j, then
3. Linearity: If two coalition games described by gain functions v and w are combined, then the distributed gains should correspond to the gains derived from v and the gains derived from w:
for every i in N. Also, for any real number a,
for every i in N.
4. Zero player (null player): The Shapley value
Given a player set N, the Shapley value is the only map from the set of all games to payoff vectors that satisfies all four properties 1, 2, 3, and 4 from above.
Addendum definitions
1. Anonymous: 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. Such a function is said to be anonymous.
2. Marginalism: the Shapley value can be defined as a function which uses only the marginal contributions of player i as the arguments.
Aumann–Shapley value
In their 1974 book, Lloyd Shapley and Robert Aumann extended the concept of the Shapley value to infinite games (defined with respect to a non-atomic measure), creating the diagonal formula. This was later extended by Jean-François Mertens and Abraham Neyman.
As seen above, the value of an n-person game associates to each player the expectation of his contribution to the worth or the coalition or players before him in a random ordering of all the players. When there are many players and each individual plays only a minor role, the set of all players preceding a given one is heuristically thought as a good sample of the players so that the value of a given infinitesimal player
Symbolically, if
where
Assuming some regularity of the worth function, for example assuming
as can be shown by approximating the density by a step function and keeping the proportion
The diagonal formula has then the form developed by Aumann and Shapley (1974)
Above
In the argument above if the measure contains atoms
Two approaches were deployed to extend this diagonal formula when the function
This works for example for majority games—while the original diagonal formula cannot be used directly. How Mertens further extends this by identifying symmetries that the Shapley value should be invariant upon, and averaging over such symmetries to create further smoothing effect commuting averages with the derivative operation as above. A survey for non atomic value is found in Neyman (2002)