O Valor de Shapley

Game Theory Professor Giacomo Bonanno

COOPERATIVE GAMES: the SHAPLEY VALUE

The description of a cooperative game is still in terms of a characteristic function

which specifies for every group of players the total payoff that the members of S can obtain by

signing an agreement among themselves; this payoff is available for distribution among the

members of the group.

DEFINITION. A coalitional game with transferable payoff (or characteristic function

game) is a pair N,  where N = {1, ..., n} is the set of players and for every subset S of I

(called a coalition) (S)   is the total payoff that is available for division among the members

of S (called the worth of S). We assume that the larger the coalition the higher the payoff (this

property is called superadditivity):

for all disjoint S, T  N, v(S  T)  v(S) + v(T)

As before, an agreement is a list (x1, x2, …, xn) where xi is the proposed payoff to

individual i. Shapley proposed some conditions (or axioms) that a solutions should satisfy and

proved that there is a unique solution that meets those conditions. The solution, known as the

Shapley value, has a nice interpretation in terms of expected marginal contribution. It is

calculated by considering all the possible orders of arrival of the players into a room and giving

each player his marginal contribution. The following examples illustrate this.

Page 2 of 3

EXAMPLE 1. Suppose that there are two players and v({1}) = 10, v({2}) =12 and

v({1,2}) = 23. There are two possible orders of arrival: (1) first 1 then 2, and (2) first 2 then 1.

If 1 comes first and then 2, 1’s contribution is v({1}) = 10; when 2 arrives the surplus

increases from 10 to v({1,2}) = 23 and therefore 2’s marginal contribution is v({1,2})  v({1}) =

23  10 = 13.

If 2 comes first and then 1, 2’s contribution is v({2}) = 12; when 1 arrives the surplus

increases from 12 to v({1,2}) = 23 and therefore 1’s marginal contribution is v({1,2})  v({2}) =

23  12 = 11.

Thus we have the following table:

Probability Order of arrival 1’s marginal contribution 2’s marginal contribution

1

2 first 1 then 2 10 13

1

2 first 2 then 1 11 12

Thus 1’s expected marginal contribution is: 1

2 10 + 1

2 11 = 10.5 and 2’s expected

marginal contribution is 1

2 13 + 1

2 12 = 12.5. This is the Shapley value: x1 = 10.5 and x2 = 12.5.

EXAMPLE 2. Suppose that there are three players now and v({1}) = 100, v({2}) =125,

v({3}) = 50, v({1,2}) = 270, v({1,3}) = 375, v({2,3}) = 350 and v({1,2,3}) = 500. Then we

have the following table:

Page 3 of 3

v({1}) = 100, v({2}) =125, v({3}) = 50, v({1,2}) = 270, v({1,3}) = 375, v({2,3}) = 350 and v({1,2,3}) = 500

Probability Order of arrival 1’s marginal contribution 2’s marginal contribution 3’s marginal contribution

1

6

first 1 then 2 then 3:

123

v({1}) = 100 v({1,2})  v({1}) = 270  100

= 170

v({1,2,3})  v({1,2}) =

500  270 = 230

1

6

first 1 then 3 then 2:

132

v({1}) = 100 v({1,2,3})  v({1,3}) =

500  375 = 125

v({1,3})  v({1}) = 375  100

=

...