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