Shapley value
Encyclopedia
In game theory
, the Shapley value, named in honour of Lloyd Shapley
, who introduced it in 1953, is a solution concept in cooperative game theory. To each cooperative game
it assigns a unique distribution (among the players) of a total surplus generated by the coalition of all players. Shapley value is characterized by a collection of desirable properties or axioms described below.
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 we expect to arise in any particular game? Or phrased differently: how important is each player to the overall cooperation, and what payoff can she reasonably expect? Shapley value provides one possible answer to this question.
we start out with a set N (of n players) and a function
, that goes from subsets of players to reals and is called a characteristic function. We always let 
, where 
denotes the empty set.
Function v has following meaning: if S is a coalition of players which agree to cooperate, then v(S), called the worth of coalition S, describes the total expected gain from this cooperation, independent of what the players outside of S do.
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. According to Shapley value the amount that player i gets given 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. 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 averaging over the possible different permutation
s in which the coalition can be formed.
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
is an ordering of the players and 
is the set of players in 
which precede 
in the order 
The following table displays the marginal contributions of Player 1
By a symmetry argument it can be shown that
Due to the efficiency axiom we know that the sum of all the Shapley values is equal to 1, which means that
1. Individual fairness: φ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. Efficiency: The total gain is distributed:
3. 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 φi(v) = φj(v).
4. 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:
for every i in N.
5. Zero Player (Null player): A null player should receive zero. A player
is null if 
for all 
not containing 
.
In fact, given a player set N, and payout (reward) function v(S), the vector of Shapley values is the only vector, defined on the class of all superadditive games that satisfies all four properties 2, 3, 4 and 5 from above.
2. Marginalism: the Shapley value can be defined as a function which uses only the marginal contributions of player i as the arguments.
extended the concept of the Shapley value to infinite games (defined with respect to a non-atomic
measure
).
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
, the Shapley value, named in honour of Lloyd Shapley
Lloyd Shapley
Lloyd Stowell Shapley is a distinguished American mathematician and economist. He is a Professor Emeritus at University of California, Los Angeles, affiliated with departments of Mathematics and Economics...
, who introduced it in 1953, is a solution concept in cooperative game theory. To each cooperative game
Cooperative game
In game theory, a cooperative game is a game where groups of players may enforce cooperative behaviour, hence the game is a competition between coalitions of players, rather than between individual players...
it assigns a unique distribution (among the players) of a total surplus generated by the coalition of all players. Shapley value is characterized by a collection of desirable properties or axioms described below.
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 we expect to arise in any particular game? Or phrased differently: how important is each player to the overall cooperation, and what payoff can she reasonably expect? Shapley value provides one possible answer to this question.
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
Function (mathematics)
In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...
, that goes from subsets of players to reals and is called a characteristic function. We always let , where denotes the empty set.Function v has following meaning: if S is a coalition of players which agree to cooperate, then v(S), called the worth of coalition S, describes the total expected gain from this cooperation, independent of what the players outside of S do.
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. According to Shapley value the amount that player i gets given a coalitional game
iswhere 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 averaging over the possible different permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s 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 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 mp/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
is an ordering of the players and is the set of players in which precede in the order The following table displays the marginal contributions of Player 1
Order  | MC_1 |
|---|---|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
By a symmetry argument it can be shown that
Due to the efficiency axiom we know that the sum of all the Shapley values is equal to 1, which means that
Properties
The Shapley value has the following desirable properties:1. Individual fairness: φ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. Efficiency: The total gain is distributed:
3. 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 φi(v) = φj(v).
4. 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:
for every i in N.
5. Zero Player (Null player): A null player should receive zero. A player
is null if for all not containing .In fact, given a player set N, and payout (reward) function v(S), the vector of Shapley values is the only vector, defined on the class of all superadditive games that satisfies all four properties 2, 3, 4 and 5 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, Shapley and Robert AumannRobert Aumann
Robert John Aumann is an Israeli-American mathematician and a member of the United States National Academy of Sciences. He is a professor at the Center for the Study of Rationality in the Hebrew University of Jerusalem in Israel...
extended the concept of the Shapley value to infinite games (defined with respect to a non-atomic
Atom (measure theory)
In mathematics, more precisely in measure theory, an atom is a measurable set which has positive measure and contains no set of smaller but positive measure...
measure
Measure (mathematics)
In mathematical analysis, a measure on a set is a systematic way to assign to each suitable subset a number, intuitively interpreted as the size of the subset. In this sense, a measure is a generalization of the concepts of length, area, and volume...
).
External links
- http://www.ma.huji.ac.il/~hart/value.html – A Bibliography of Cooperative Games: Value Theory by Sergiu Hart