Lindo Systems

! 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; 120;
ENDDATA

! 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; 
     );