! Compute the Shapley value for players in a coalition, using LINGO.
! Keywords: Shapley value, game theory, cooperative game,
nperson 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 10088 =$12 120100=$20
A, C, B $88 120119=$ 1 11988 =$31
B, A, C 100 92=$ 8 $92 120100=$20
B, C, A 120112=$ 8 $92 11292 =$20
C, A, B 119 70=$49 120119=$ 1 $70
C, B, A 120112=$ 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;
);
