Shapley value

Shapley proposed a solution concept that would associate a payoff with each of n agents in a coalition function game, where n could be any positive integer. Shapley first adopts a series of three axiomata (CGT, p. 71) that are regarded as necessary characteristics of a solution. In ordinary language, these are that (1) nothing depends on the identity of a player, as distinct from the role (dealer, maker of the opening lead play, etc.) that she plays in the game, (2) the payoffs add up to the total payoff of the grand coalition in the game, and (3) if the same players play two different games, the values in the merged game are the sum of the values in the two games. He then shows (1997, pp. 71-4) that these conditions are uniquely satisfied by an algebraic, permutational formula,

Ф;О0 = agn(s)(v(S) - v(S - {i}))

(8.1)

S# N i [S

where фг(г) is the value assigned to player i in the game characterized by v, and gn(s) is

gn (s)

n

(s - 1)! (n - 1)!

n!

(8.2)

where s is the number of players in coalition S, n the total number of players in the game, and ! denotes the factorial of the number. Thus, in ordinary terms, the value will be the weighted sum of the individual’s contributions to the value of a coalition, for all coalitions in which he might participate. The weights do not lend themselves to a simple ordinary language explanation in themselves. However, Shapley also offers (CGT, pp. 78-9) what he describes as a bargaining process that would generate the value. He writes

The players . . . agree to play the game v in the grand coalition, formed in the following way: 1. Starting with a single player, the coalition adds one player at a time until every player is admitted. 2. The order in which the players are to join is determined by chance, with all arrangements equally probable. 3. Each player, on his admission, demands and is promised the amount his adherence contributes to the value of the coalition . . .. The expectations under this scheme are easily worked out. (emphasis added)

This is as equation (8.1) above, where gn(s) is the probability that the corresponding payment will be the one offered. It may be that Shapley was following the example of Nash (1953) in this bargaining interpretation. The Shapley value has a number of desirable properties:

  • (1) It is Pareto-optimal.
  • (2) It is covariant under strategic equivalence.
  • (3) While it is not necessarily anonymous, the Shapley value has a property of symmetry: if the players are permuted, without any other change in the game, their Shapley values are unchanged. (Note that this is not true for the “toy” solution concept of section 1 above. The difference arises from the fact that the “toy” assumes a particular ordering of the agents, while the Shapley value averages over all such orders.)
  • (4) It has an equal treatment property: suppose that two agents make the same contribution to all coalitions; then they are assigned the same Shapley value.
  • (5) It is additive (this is the assumption in the introductory paragraph of this section).
  • (6) It has a null player property: if an agent adds nothing to any coalition then his Shapley value is zero.7

The additivity property is crucial and is a defining property of the Shapley value. It may also be the least compelling to intuition (McCain, 2013, pp. 12-13).

 
Source
< Prev   CONTENTS   Source   Next >