/*
	C Program to Sequentially Search for Voter Nash Equilibria

		by Jeffrey S. Rosenthal, http://probability.ca/jeff/

	This program investigates an algorithm of repeated candidate
	action tweaks in an attempt to converge to equilibrium
	behaviour, in Model 4* of voting behaviour as discussed and
	analysed in the paper "Many-Candidate Nash Equilibria for
	Elections Involving Random Selection", available at:
	    http://probability.ca/jeff/ftpdir/runoff.pdf

	This file is "runoff.c".

	Adjust the parameters n, alpha, NUMREPS, AV below as desired.

	Then e.g. compile with "cc runoff.c", and run as "a.out".

	The resulting output is designed to be read into the free
	statistical software R, to produce graphical barplots.
*/


#include <stdio.h>
#include <sys/time.h>
#include <math.h>

#define NUMREPS 1000
#define BURNIN (NUMREPS/2)
#define NUMAV 100

int n=5;
double alpha=2.9;

int verbose=0;
int maxmark = 10;
double inc, drand48();

/* v=Unif[0,1] */
/* Notation: position x[i] = mark[i] / maxmark = mark[i] * inc */
/* Also, locmark[i] = -999 if OUT, or -r if eliminated on r'th round. */

int main()
{
    double *avrpayoffvec(), curpayoff[99], newpayoff[99], *tmppayoff;
    int curmark[99], newmark[99], randmark();
    void seedrand();
    int i, rep, mover;
    int outcount=0, numcounted=0, markcount[99];
    int numc = imin(n, ifloor(alpha)+1);
    seedrand();

    inc = 1.0/maxmark;

    /* Zero the counts. */
    outcount=0;
    numcounted=0;
    for (i=0; i<=maxmark; i++)
      markcount[i] = 0;

    /* Random action initialisation. */
    for (i=0; i<n; i++)
      curmark[i] = randmark();
    tmppayoff = avrpayoffvec(curmark);
    for (i=0; i<n; i++)
      curpayoff[i] = tmppayoff[i];
    if (verbose >= 2) {
      printf("initial mark values:  ");
      for (i=0; i<n; i++)
        printf("%d,  ", curmark[i]);
      printf("\n");
      printf("initial average payoff values:  ");
      for (i=0; i<n; i++)
        printf("%.2f,  ", curpayoff[i]);
      printf("\n");
    }

    /* Repeatedly try tweaking one action. */
    for (rep=0; rep<NUMREPS; rep++) {
      mover = randint(0,n-1);
      if (verbose >= 2)
        printf("mover is %d\n", mover);
      for (i=0; i<n; i++)
        newmark[i] = curmark[i];
      newmark[mover] = randmark();

      /* Compute the payoffs from the new action. */
      tmppayoff = avrpayoffvec(newmark);
      for (i=0; i<n; i++)
        newpayoff[i] = tmppayoff[i];
      if (verbose >= 2) {
        printf("new mark values:  ");
        for (i=0; i<n; i++)
          printf("%d,  ", newmark[i]);
        printf("\n");
        printf("current payoff values:  ");
        for (i=0; i<n; i++)
          printf("%.2f,  ", curpayoff[i]);
        printf("\n");
        printf("new payoff values:  ");
        for (i=0; i<n; i++)
          printf("%.2f,  ", newpayoff[i]);
        printf("\n");
        printf("curpayoff[%d] = %.2f,  newpayoff[%d] = %.2f\n",
      	          mover, curpayoff[mover], mover, newpayoff[mover]);
      }

      /* See if the new action improves the mover's payoff. */
      if (newpayoff[mover] > curpayoff[mover]) {
        if (verbose >= 1)
	  printf("Candidate %d from %d to %d increasing from %.3f to %.3f.\n",
	  			mover, curmark[mover], newmark[mover],
	  			curpayoff[mover], newpayoff[mover]);
        curmark[mover] = newmark[mover];
        for (i=0; i<n; i++)
	  curpayoff[i] = newpayoff[i];
      }

      /* Update the counts. */
      if (rep > BURNIN) {
	numcounted++;
        for (i=0; i<n; i++) {
	  if (curmark[i] == -999)
	    outcount++;
	  else
	    markcount[curmark[i]]++;
	}
      }

      if (verbose >= 1) {
        printf("mark values %d:  ", rep+1);
        for (i=0; i<n; i++)
          printf("%d,  ", curmark[i]);
        printf("\n");
      }

    }

    if (verbose >= 2) {
      printf("final mark values:  ");
      for (i=0; i<n; i++)
        printf("%d,  ", curmark[i]);
      printf("\n");
      printf("final average payoff values:  ");
      for (i=0; i<n; i++)
        printf("%.2f,  ", curpayoff[i]);
      printf("\n");
    }

    /* Output average mark counts. */
    printf("\nn=%d, alpha=%.3f, NUMREPS=%d, NUMAV=%d\n\n",
    					n, alpha, NUMREPS, NUMAV);

    printf("# Theoretical values for actions OUT, 0/%d, 1/%d, ..., %d/%d:\n",
    		maxmark, maxmark, maxmark, maxmark);
    printf("th = c(%d.000, ", n-numc);
    for (i=0; i<maxmark/2; i++)
      printf("0.000, ");
    printf("%d.000, ", numc);
    for (i=maxmark/2+1; i<maxmark; i++)
      printf("0.000, ");
    printf("0.000");
    printf(")\n\n");

    printf("# Average counts for actions OUT, 0/%d, 1/%d, ..., %d/%d:\n",
    		maxmark, maxmark, maxmark, maxmark);
    printf("av = c(%.3f, ", 1.0*outcount/numcounted);
    for (i=0; i<=maxmark; i++) {
      printf("%.3f", 1.0*markcount[i]/numcounted);
      if (i<maxmark)
        printf(", ");
    }
    printf(")\n\n");

    /* Output R plotting commands. */
    printf("mat = rbind(th,av)\n");
    printf("pdf(file=\"runoff-%d-%dp%d.pdf\")\n", n, ifloor(alpha),
			    ifloor( (alpha-ifloor(alpha))*10 ) );
    printf("barplot(mat, beside=TRUE, col=c(\"blue\", \"red\"),\n");
    printf("\tmain=\"Average counts: n=%d, alpha=%.1f, reps=%d, av=%d\",\n",
    			n, alpha, NUMREPS, NUMAV);
    printf("\tnames.arg=c(\"OUT\",\"0.0\",");
    for (i=1; i<maxmark; i++)
      printf("\"%.1f\",", i*inc);
    printf("\"1.0\"))\n");
    printf("dev.off()\n\n");

}

double * avrpayoffvec(int *markarg) {
  int anum, i;
  double psum[99], *tmpvec;
  double *payoffvec();
  static double theavrpayoff[99];

  for (i=0; i<n; i++)
    psum[i] = 0.0;

  for (anum=0; anum<NUMAV; anum++) {
    tmpvec = payoffvec(markarg);
    for (i=0; i<n; i++)
      psum[i] = psum[i] + tmpvec[i];
  }

  for (i=0; i<n; i++)
    theavrpayoff[i] = psum[i] / NUMAV;

  return theavrpayoff;

}

double * payoffvec(int *markarg) {

    double v[99], maxv, minv;
    int winner, numlosers, loser[99], theloser, locmark[99];
    int totcontest = n;
    int i,j;
    int numwin, stepnum;
    double winfrac;
    double leftend();
    double rightend();
    int markmult[99];
    double x[99];
    static double thepayoff[99];

    for (i=0; i<n; i++)
      locmark[i] = markarg[i];

    /* Loop through the steps, repeatedly eliminating one candidate. */
    stepnum = 0;
    while (totcontest >= 2) {
      stepnum++;

      /* Reset the counters. */
      minv = 2.0;
      maxv = -1.0;
      winner = -1;
      numlosers = 0;
      for (j=0; j<=maxmark; j++)
        markmult[j] = 0;
      totcontest = 0;

      /* Compute positions x[i], and markmult multiplicities. */
      for (i=0; i<n; i++)
        x[i] = markarg[i] * inc;
      for (i=0; i<n; i++) {
	if (locmark[i] >= 0) {
          markmult[locmark[i]]++;
	  totcontest++;
        }
      }

      for (i=0; i<n; i++) {
        if (locmark[i] >= 0) {

	  /* Compute vote share of player i. */
          v[i] = ( rightend(x,i) - leftend(x,i) ) / markmult[locmark[i]];

	  /* Check for winners and losers. */
	  if (v[i] >= maxv) {
	    maxv = v[i];
	    winner = i;
          }
	  if (v[i] == minv) {
	    loser[numlosers] = i;
	    numlosers++;
	  } else if (v[i] < minv) {
	    minv = v[i];
	    loser[0] = i;
	    numlosers=1;
          }
	  if (verbose >= 3)
	    printf("i=%d, left=%f, right=%f, v=%f, winner=%d\n",
			i,leftend(x,i),rightend(x,i),v[i],winner);

        }
      }
      if (verbose >= 2) {
        printf("current local mark values:  ");
        for (i=0; i<n; i++)
          printf("%d,  ", locmark[i]);
        printf("\n");
        printf("totcontest=%d, numlosers=%d, locmark[3]=%d\n",
				totcontest, numlosers, locmark[3]);
      }
      if (verbose >= 2) {
	printf("  loser list:  ");
	for (j=0; j<numlosers; j++)
	  printf("%d, ", loser[j]);
        printf("\n");
      }

      /* Eliminate one of the losers. */
      if ( (totcontest >= 2) && (numlosers >= 1) ) {
        theloser = randint(0,numlosers-1);
        if (verbose >= 2)
          printf("The chosen loser is: loser[%d]=%d\n",
					theloser, loser[theloser]);
        locmark[ loser[theloser] ] = -stepnum;
      }

    }
    if (verbose >= 2)
      printf("winner = %d\n", winner);
    if (verbose >= 2) {
      for (i=0; i<n; i++)
        printf("locmark[%d]= %d, ", i, locmark[i]);
      printf("\n");
    }

    for (i=0; i<n; i++) {
      if (locmark[i] == -999)
        thepayoff[i] = 0.0;
      else if (locmark[i] < 0)
        thepayoff[i] = -1.0;
      else
        thepayoff[i] = alpha;
    }
    if (verbose >= 2) {
      for (i=0; i<n; i++)
        printf("thepayoff[%d]= %.2f, ", i, thepayoff[i]);
      printf("\n");
    }

    return(thepayoff);

}

double leftend(double xx[3], int ii)
{
  int jj;
  double newbound;
  double sofar = 0;
  for (jj=0; jj<n; jj++) {
    if ( (jj != ii) && (xx[jj]<xx[ii]) ) {
      newbound = (xx[jj]+xx[ii])/2;
      if (newbound>sofar)
        sofar = newbound;
    }
  }
  return sofar;
}

double rightend(double xx[3], int ii)
{
  int jj;
  double newbound;
  double sofar = +1;
  for (jj=0; jj<n; jj++) {
    if ( (jj != ii) && (xx[jj]>xx[ii]) ) {
      newbound = (xx[jj]+xx[ii])/2;
      if (newbound<sofar)
        sofar = newbound;
    }
  }
  return sofar;
}

/* SEEDRAND: SEED RANDOM NUMBER GENERATOR. */
void seedrand()
{
    void srand48();
    int i, seed;
    struct timeval tmptv;
    gettimeofday (&tmptv, (struct timezone *)NULL);
    seed = (int) tmptv.tv_usec;
    srand48(seed);
    (void)drand48();  /* Spin it once. */
}

/* IFLOOR */
int ifloor(double x)  /* returns floor(x) as an integer */
{
    return((int)floor(x));
}

/* IMIN */
int imin(int aa, int bb)
{
    if (aa<bb)
      return(aa);
    return(bb);
}

/* RANDINT */
int randint(int aa, int bb)  /* return rand int between aa and bb inclusive */
{
    return( ifloor( aa + drand48()*(bb+1-aa) ) );
}

/* RANDMARK */
int randmark()
{
  int therandmark;
  therandmark = randint(0,maxmark);
  if (drand48() < 0.5)
    therandmark = -999;
  return(therandmark);
}