The Shapley value is a solution concept in cooperative game theory. It was named in honor of Lloyd Shapley, who introduced it in 1951 and won the Nobel Memorial Prize in Economic Sciences for it in 2012. 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.
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.
For cost-sharing games with concave cost functions, the optimal cost-sharing rule that optimizes the price of anarchy, followed by the price of stability, is precisely the Shapley value cost-sharing rule. (A symmetrical statement is similarly valid for utility-sharing games with convex utility functions.) In mechanism design, this means that the Shapley value solution concept is optimal for these sets of games.
Formal definition
Formally, a coalitional game is defined as: There is a set N (of n players) and a function that maps subsets of players to the real numbers: , with , where denotes the empty set. The function is called a characteristic function.
The function has the following meaning: if S is a coalition of players, then (S), called the worth of coalition S, describes the total expected sum of payoffs the members of can obtain by cooperation.
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 is given in a coalitional game is
where n is the total number of players and the sum extends over all subsets S of N not containing player i. Also note that is the multinomial coefficient. The formula can be interpreted as follows: imagine the coalition being formed one actor at a time, with each actor demanding their contribution (S∪{ i}) − (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 orders of the players and is the set of players in which precede in the order . Finally, it can also be expressed as
which can be interpreted as
In terms of synergy
From the characteristic function one can compute the synergy that each group of players provides. The synergy is the unique function , such that
for any subset of players. In other words, the 'total value' of the coalition comes from summing up the synergies of each possible subset of .
Given a characteristic function , the synergy function is calculated via
using the Inclusion exclusion principle. In other words, the synergy of coalition is the value , which is not already accounted for by its subsets.
The Shapley values are given in terms of the synergy function by
where the sum is over all subsets of that include player .
This can be interpreted as
In other words, the synergy of each coalition is divided equally between all members.
Examples
Business example
Consider a simplified description of a business. An owner, o, provides crucial capital in the sense that, without him/her, no gains can be obtained. There are m workers w1,...,wm, each of whom contributes an amount p to the total profit. Let
The value function for this coalitional game is
where m is the cardinality of . Computing the Shapley value for this coalition game leads to a value of for the owner and for each one of the m workers.
This can be understood from the perspective of synergy. The synergy function is
so the only coalitions that generate synergy are one-to-one between the owner and any individual worker.
Using the above formula for the Shapley value in terms of we compute
and
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. Let