// Analyze expected cost per agent for mixed Nash equilibrium.
// Roughgarden, p.178

#include <stdio.h>

int main() {
  int binChoice[4];
  int i,sum=0;
  int ballCount[6];

  // Generate each mapping for 4 agents to 6 edges
  for (binChoice[0]=0; binChoice[0]<6; binChoice[0]++)
    for (binChoice[1]=0; binChoice[1]<6; binChoice[1]++)
      for (binChoice[2]=0; binChoice[2]<6; binChoice[2]++)
        for (binChoice[3]=0; binChoice[3]<6; binChoice[3]++) {
          // Clear the edges
          for (i=0;i<6;i++)
            ballCount[i]=0;
          // Count agents for each edge
          for (i=0;i<4;i++)
            ballCount[binChoice[i]]++;
          // Accumulate c(x)=x costs
          for (i=0;i<6;i++)
            sum+=ballCount[i]*ballCount[i];
          }
  // 4 agents * number of choices for choosing bin simultaneously
  printf("Expected cost %10.6f\n",((double) sum)/(4*6*6*6*6));
  }