/************************************
Algorithm to determine voting power.
Suppose there are N (unequal) voters.
Each voter i gets to cast an integer number V[i] of votes,
where 0<=V[i] and sum_{i=1}^N V[i] = Vtot.
(That is, to vote "yes" you add V[i] to the sum-vote,
to vote "no" you add 0 to the sum-vote, and then if the sum-vote
exceeds some threshhold T, e.g. T=V/2, then that
vote is won by the "yes" camp.)
Then the "voting power" of voter i is the 
probability (assuming all voters choose their votes
by flipping probability-p coins independently)
that i's vote will win the election.
(We assume ties are broken by a probability ptiebreak coin toss.)

The runtime of this algorithm is O(Vtot*N).
Compile with 
  gcc -O6 votpow.c 
******Warren D. Smith Nov 2000****************/
#include <stdio.h>
#include <math.h>
#include <assert.h>
#define uint unsigned int

void findvotpow(
/**input*/  uint V[],  uint N, double T,  double p,           double ptiebreak,
/**          #votes    #voters  thresh   voter coin prob      tiebreak coin prob */
/*output*/  double prob[],      double votpow[])
/**            of total vote    of voter  */
{
   int i1,i2,i,j,k;
   uint Vtot, Vmax;
   double q, qtiebreak, s;

   Vtot=0; Vmax=0;
   for(i=0; i<N; i++){
      votpow[i]=0.0;
      Vtot += V[i]; 
      if(Vmax<V[i]) Vmax=V[i];
   }

   for(i=1; i<=Vtot; i++){
      prob[i] = 0.0;
   }
   prob[0] = 1.0;

   assert(0.0<=p);
   assert(p<=1.0);
   q = 1.0-p;
   for(i=0; i<N; i++){
      if(V[i]>0){
         for(j=Vtot-V[i]; j>=0; j--){
            k = j+V[i];
	    prob[k] += prob[j] * p;
            prob[j] *= q;
         }      
      }      
   }
   /* prob[j], j=0..Vtot, now contains the probability
    * that the election result (sum of votes) will be j. */
   
   assert(0.0<=ptiebreak);
   assert(ptiebreak<=1.0);
   qtiebreak = 1.0-ptiebreak;
   i1 = ceil(T);
   i2 = floor(T)+Vmax;
   if(i2>Vtot) i2=Vtot;
   for(i=i1; i<=i2; i++){
      s = prob[i];
      if(i==T) s *= ptiebreak;
      for(j=0; j<N; j++){
	if(V[j]>0){
	  if(i-V[j] <= T){
	    if(i-V[j] == T) s *= qtiebreak;
	    votpow[j] += s;
	  }
	}
      }
   }
   /* votpow[j], j=0..N-1, now contains the probability
    * that voter j's vote will win the election, i.e.
    * this is j's "voting power." */
   return;
}

/* sample driver */
main(){
  int i; 
  double sumprob;
  double votpow[51];
  double prob[539];
  uint Electoral1996[] = { 
/*Alabama*/ 9,
/*Alaska*/ 3,
/*Arizona*/ 8,
/*Arkansas*/ 6,
/*California*/ 54,
/*Colorado*/ 8,
/*Connecticut*/ 8,
/*Delaware*/ 3,
/*DistrictofColumbia*/ 3,
/*Florida*/ 25,
/*Georgia*/ 13,
/*Hawaii*/ 4,
/*Idaho*/ 4,
/*Illinois*/ 22,
/*Indiana*/ 12,
/*Iowa*/ 7,
/*Kansas*/ 6,
/*Kentucky*/ 8,
/*Louisiana*/ 9,
/*Maine*/ 4,
/*Maryland*/ 10,
/*Massachusetts*/ 12,
/*Michigan*/ 18,
/*Minnesota*/ 10, 
/*Mississippi*/ 7,
/*Missouri*/ 11,
/*Montana*/ 3,
/*Nebraska*/ 5,
/*Nevada*/ 4,
/*NewHampshire*/ 4,
/*NewJersey*/ 15,
/*NewMexico*/ 5,
/*NewYork*/ 33,
/*NorthCarolina*/ 14,
/*NorthDakota*/ 3,
/*Ohio*/ 21,
/*Oklahoma*/ 8,
/*Oregon*/ 7,
/*Pennsylvania*/ 23,
/*RhodeIsland*/ 4,
/*SouthCarolina*/ 8,
/*SouthDakota*/ 3,
/*Tennessee*/ 11,
/*Texas*/ 32,
/*Utah*/ 5,
/*Vermont*/ 3,
/*Virginia*/ 13,
/*Washington*/ 11,
/*WestVirginia*/ 5,
/*Wisconsin*/ 11,
/*Wyoming*/ 3
/*Total 538*/
	  };

char StateName[51][19] = {
"Alabama" ,
"Alaska" ,
"Arizona" ,
"Arkansas" ,
"California" ,
"Colorado" ,
"Connecticut" ,
"Delaware" ,
"DistrictofColumbia" ,
"Florida" ,
"Georgia" ,
"Hawaii" ,
"Idaho" ,
"Illinois" ,
"Indiana" ,
"Iowa" ,
"Kansas" ,
"Kentucky" ,
"Louisiana" ,
"Maine" ,
"Maryland" ,
"Massachusetts" ,
"Michigan" ,
"Minnesota" , 
"Mississippi" ,
"Missouri" ,
"Montana" ,
"Nebraska" ,
"Nevada" ,
"NewHampshire" ,
"NewJersey" ,
"NewMexico" ,
"NewYork" ,
"NorthCarolina" ,
"NorthDakota" ,
"Ohio" ,
"Oklahoma" ,
"Oregon" ,
"Pennsylvania" ,
"RhodeIsland" ,
"SouthCarolina" ,
"SouthDakota" ,
"Tennessee" ,
"Texas" ,
"Utah" ,
"Vermont" ,
"Virginia" ,
"Washington" ,
"WestVirginia" ,
"Wisconsin" ,
"Wyoming" };

  printf("Test driver - the 50 US states & DC:\n");
  findvotpow(Electoral1996, 51, 270.0, 0.5, 0.5, prob,votpow);
  
  sumprob = 0.0;
  printf("probabilities\n");
  for(i=0; i<538; i++){
    printf("%2d %.6f\n", i, prob[i]);
    sumprob += prob[i];
  }
  printf("sumprob=%f\n",sumprob);
  
  printf("voting powers\n");
  printf("State, Electoral, Votpow, ratio(E/V)\n");
  printf("====================================\n");
  for(i=0; i<51; i++){
    printf("%20s %2d %.6f %3.6f\n", StateName[i],
	   Electoral1996[i], votpow[i], Electoral1996[i]/votpow[i]);
  }

}/*end of file*/