Shapley Value

Published by Mario Oettler on

The Shapley value is a solution concept in cooperative game theory. With the value, one can determine what pay-off a participant in a coalition should receive. It tries to take the individual contribution of each participant into account.

Let’s consider the following case. There are three participants who work on a project.

First, we need to find out all possible coalitions with their value.

CoalitionValue of the coalition
v({A})12
v({B})6
v({C})9
v({A, B})24
v({A, C})27
v({B, C})15
v({A, B, C})36
v({o})0

Algorithm

  1. First, we make a list of all orders of participants.
  2. For every order, we determine the value of the coalition consisting of the participants that come before participant i. This value is V-i.
  3. For every order, we determine the value of the coalition consisting of the participants, including i. This value is Vi+.
  4. Calculate marginal contribution Mi = W+I – W-i
  5. Calculate average over all Mi.

Contribution of player B

Orderv({participant before B})v({participants including B})Marginal contribution participant B
A, B, Cv({A}) = 12v({A, B}) = 2424-12 = 12
A, C, Bv({A, C}) = 27v({A, C, B}) = 3636-27 = 9
B, A, Cv({o}) = 0v({B}) = 66-0 = 6
B, C, Av({o}) = 0v({B}) = 66-0 = 6
C, A, Bv({A, C}) = 27v({A, C, B}) = 3636-27= 9
C, B, Av({C}) = 15v({C, B}) = 1515-9 = 6

Shapley Value player B: SB = (12+9+6+6+9+6)/6 = 8

We do the same for players A and C.

SA = 17

SC = 11

Categories: