! Compute the Shapley value for players in a coalition, using LINGO.
! Keywords: Shapley value, game theory, cooperative game,
n-person game;
! Suppose customers A, B, and C, are each to receive a delivery from a single truck that makes
one trip to serve the three. How should the cost of the trip be allocated? The Shapley
value allocates cost to a given customer based upon the average marginal cost of
adding that customer to the trip/coalition, where the average is taken over all possible
permutations of how customers/players could be added to the trip/coalition. Suppose
the cost of delivering to any combination of the three is as follows: {A}:$88,
{B}: $92, {C}: $70, {A,B}: $100, {A,C}: $119, {B,C}: $112, {A,B,C}: $120. E.g.,
making a single trip to just A and C costs $119. Making one trip that serves all three
costs $120. The six possible permutations and the marginal cost of each customer are:
Permutation A B C
A, B, C $88 100-88 =$12 120-100=$20
A, C, B $88 120-119=$ 1 119-88 =$31
B, A, C 100- 92=$ 8 $92 120-100=$20
B, C, A 120-112=$ 8 $92 112-92 =$20
C, A, B 119- 70=$49 120-119=$ 1 $70
C, B, A 120-112=$ 8 112- 70=$42 $70
Shapley value(average) $41.5 $40 $38.5 ;
SETS:
! A version hard coded for up to 4 players;
player: v1, shval;
s2(player,player)| &1 #lt# &2: v2;
s3( s2, player) | &2 #lt# &3: v3;
s4( s3, player) | &3 #lt# &4: v4;
ENDSETS DATA:
player = A B C D;
! Values of various coalitions. This is really
a 3 player game. D has no effect;
v1 = 88 92 70 0;
v2 =
! A B; 100
! A C; 119
! A D; 88
! B C; 112
! B D; 92
! C D; 70 v3 =
! A B C; 120
! A B D; 100
! A C D; 119
! B C D; 112 v4 =
! A B C D; 120ENDDATA
! Compute Shapley value for each player. For n
players, there are n factorial sequences, so
for 4 players there are 24 sequences;
@FOR( player(i):
shval(i) = (
! Sequences with player i first(there is only 1 set of 1 containing i);
v1(i)*6 +
! Sequences with player i second(there are 3 sets of 2 containing i);
(@SUM(s2(i1,i2)| i2 #eq# i: v2(i1,i) - v1(i1)) +
@SUM(s2(i1,i2)| i1 #eq# i: v2(i,i2) - v1(i2)))*2 +
! Sequences with player i third(3 sets of 3 containing i);
(@SUM(s3(i1,i2,i3)| i3 #eq# i: v3(i1,i2,i ) - v2(i1,i2)) +
@SUM(s3(i1,i2,i3)| i2 #eq# i: v3(i1, i,i3) - v2(i1,i3)) +
@SUM(s3(i1,i2,i3)| i1 #eq# i: v3(i, i2,i3) - v2(i2,i3)))*2 +
! Sequences with player i fourth(only 1 set of 4. It contains i);
(@SUM(s4(i1,i2,i3,i4)| i4 #eq# i: v4(i1,i2,i3,i ) - v3(i1,i2,i3)) +
@SUM(s4(i1,i2,i3,i4)| i3 #eq# i: v4(i1,i2,i,i4 ) - v3(i1,i2,i4)) +
@SUM(s4(i1,i2,i3,i4)| i2 #eq# i: v4(i1,i,i3,i4 ) - v3(i1,i3,i4)) +
@SUM(s4(i1,i2,i3,i4)| i1 #eq# i: v4(i,i2,i3,i4 ) - v3(i2,i3,i4)))*6)/24;
);
|