Shapley value

The Shapley value (named after Lloyd Shapley ) is a punktwertiges solution concept from cooperative game theory. It specifies which payment can expect the player in response to a coalition function ( positive interpretation ), or receive should ( normative interpretation).

Example

Given three players, which are referred to with the suffixes a, b ​​and c, that is, N = {a, b, c}, and obtain the following values ​​:

It is, for example v ( { b} ) = 6 that the "coalition" consisting only of players b alone can reach the value 6; v ( {a, b} ) = 24 means that a coalition of players a can together create the value 24 with b; since v ( {a, b, c} ) = 36 can together produce the value 36 to all players.

The Shapley value is used to divide the value v ( {a, b, c} ) = 36 The following procedure is possible to determine the Shapley value of a player i: One lists all the sequences in which the players can be arranged. For each order you determine the value of the coalition, which consists of those players that are listed before i looked at players. One lists the value that this coalition has in common with the player i, and forms the difference, ie the so-called marginal contribution of player i in the considered order. Finally, take the average of these marginal contributions and receives the Shapley value of player i The following table gives these considerations for players b again:

The average of the marginal contributions of player b yields the Shapley value

Analogously, one will definitely get the Shapley values ​​of the players a and c

General definition

Given a cooperative game with transferierbarem benefit, that is given is

• A finite set of players and
• A coalition function that assigns to each subset of a real number, and in particular the empty coalition is the value:

Where N denotes the power set of, ie the set of all subsets. A subset of the players called coalition. The expression is called the value of the coalition.

The Shapley value now assigns each player a payoff for the game. For this purpose, there are different formulas that lead to the same result.

Sequence definition

First, the marginal contribution of a player for a given order of the players is defined. Let be a sequence of player crowd with the interpretation that player is listed at position. For a player who is listed before players, applies. The predecessor of in are thus in the amount

Be added in the order in succession to form a coalition, the players, the player must do the following marginal contribution in at:

The Shapley value of a player is calculated as the average of the marginal contributions over all possible sequences:

The set of all possible sequences of players called. Note: The above example is calculated according to this definition. For example, is and

Subset definition

The marginal contribution of a player to a given coalition

The Shapley value of a player is calculated as the weighted average of the marginal contributions to all possible coalitions:

Starting from the sequence definition of the Shapley value, this formula can now be understood as follows: For each there is

Sequences, such that, for there are ways that players from before the players organize and opportunities that players behind the player to arrange (see also multinomial ). example: Consider again the above example and take the case. It is then just for the two sequences and. It is therefore necessary. Instead of going over all sequences, one can thus establish the following table:

The average of the marginal contributions results for games b the Shapley value

Definition via Harsanyi dividends

Another calculation option will also allow a better insight into the structure of a coalition function.

Harsanyi dividends

The following argument is often attributed to John Harsanyi. Consider a coalition and its value. What proportion of really arises from the combination of all the members, and not just by combining the subgroups contained in? That is, what part of it is not already due to the achievement of any sub-grouping? To answer, the procedure is recursive. First, the actual performance of an empty coalition is nothing. The actual additional services arise recursively as the value of a coalition minus the services that are already provided by coalitions included:

These expressions are called Harsanyi dividends. example Consider again the example above and notice that is actually performed by player. The actual performance of players alone is so. Similarly, the genuine achievements of the other individual coalitions can be determined,

For the coalition now already rendered by the coalitions included services must be deducted:

Analog applies:

There remains the actual performance of the combination of having to determine, so that power, that has not occurred already by or alone, or by the pairwise combinations or. For this purpose, we calculate:

Shapley value as divided Harsanyi dividends

The Harsanyi dividend of a coalition if and only delivered when all the players are available. It is therefore plausible to divide this power among all players in the coalition equally. This gives another formula for the Shapley value:

Example Consider again the above example and note that players in the coalitions

Is included. Therefore, he gets

Characterization

The Shapley value is the only payoff function which satisfies the following four axioms:

• Pareto efficiency: The value of the grand coalition is distributed to the players.
• Symmetry: players with the same marginal contributions receive the same.
• Zero Player: A player with a marginal contribution to any coalition receives zero zero.
• Additivity: If the game can be decomposed into two independent games, then the payoff of each player in the composite game is the sum of the payoffs in the split games.