/* code for decision function and related functions from dsvsim4.c
*
* declared strategy voting simulation program
* by Lorrie Faith Cranor (lorracks@cs.wustl.edu)
*/
#define square(x) ((x)*(x))
struct ballot_list {
int *ballot; /* array of utility values */
int *indx; /* indexes for ballot sorted in ascending order */
int *tindx; /* location of utility ties */
struct ballot_list *next;
};
void decide_vote(ptr, tally, last_tally, altvote, N, B, S, pfunc)
struct ballot_list *ptr; /* pointer to one voter's ballot */
int *tally; /* current election tally (will be incremented) */
int *last_tally; /* tally in BBB, tally from last round in Batch */
int *altvote; /* number of voters who have voted insincerely so far */
int N; /* number of candidates */
int B; /* number of voters */
double S; /* uncertaintly */
int pfunc; /* probability function to use */
{
int i, j, k, t, found;
int *E_indx, *E_tindx, *t_indx, *t_tindx;
double *E; /* array of expected gains */
double lb, ub; /* lower bound, upper bound */
double param1, param2, param3, param4; /* params to prob. calc. function */
double M, x, P, U;
double (*func)(); /* probability calculation function */
/* setup */
E = (double *)malloc (sizeof (double) * (N+1));
E_indx = (int *)malloc (sizeof (int) * (N+1));
E_tindx = (int *)malloc (sizeof (int) * (N+1));
t_indx = (int *)malloc (sizeof (int) * (N+1));
t_tindx = (int *)malloc (sizeof (int) * (N+1));
iindexx(N, last_tally, t_indx); /* index last_tallies */
ifindties(N, last_tally, t_indx, t_tindx); /* find ties in last_tallies
* also randomizes tied
* elements in array */
if (pfunc == 1) func = euDistanc;
else if (pfunc == 2) func = gaussian3;
else if (pfunc == 4) func = gaussian1;
else {
fprintf (stderr, "Invalid pfunc\n");
free (E); free (E_indx); free (E_tindx); free (t_indx); free(t_tindx);
exit (0);
}
found = 0;
/* if 1st choice is in 1st or 2nd place vote for it and don't
* worry about probabiliy calculations
*/
for (t = ptr->tindx[N]+1; t>0; t--) { /* loop over 1st choice ties */
for (i = t_tindx[N]+1; i>0; i--) { /* loop over 1st place ties */
if (ptr->indx[N-t+1]==t_indx[N-i+1]) { /* 1st choice in 1st place? */
tally[t_indx[N-i+1]]++;
found = 1; t = 0; i = 0;
}
}
}
if (found) {
free (E); free (E_indx); free (E_tindx); free (t_indx); free (t_tindx);
return;
}
/* calculate expected gain */
E[1] = 0; /* we're never going to vote for last choice, so doesn't matter */
for (i=N; i>1; i--) {
E[i] = 0;
for (j=N; j>0; j--) {
if (i==j) continue;
if (pfunc == 2 || pfunc == 1) {
lb = 1.0/3.0;
ub = 0.5;
param1 = (double)last_tally[ptr->indx[i]]/(double)B;
param2 = (double)last_tally[ptr->indx[j]]/(double)B;
for (k=1; k<=N; k++)
if(i!=k && j!=k)
param3 = (double)last_tally[ptr->indx[k]]/(double)B;
param4 = S;
E[i] += (double)((ptr->ballot[ptr->indx[i]]-ptr->ballot[ptr->indx[j]])
* qsimp (func, lb, ub, param1, param2, param3, param4));
}
else if (pfunc == 4) {
U = (double)(ptr->ballot[ptr->indx[i]] - ptr->ballot[ptr->indx[j]]);
if (U != 0) { /* doesn't matter what P is, if E term = 0 */
M = (double)last_tally[t_indx[N]]/(double)B;
x = (double)min(last_tally[ptr->indx[i]],last_tally[ptr->indx[j]])/
(double)B;
if (M == x) ub = M;
else ub = (square(M) - square(x))/(2 * (M - x)); /* intercept */
P = (S/2.0)*erf((ub-M)/(S*sqrt(2)))+S*.5;
if (P == 0.0)
P = (S/fabs(ub-M))*(1/sqrt(2*M_PI)) * exp(-square(ub-M)/(S*S*2));
E[i] += U * P;
}
}
} /* end j loop */
} /* end i loop */
indexx(N, E, E_indx); /* index expected gain */
findties(N, E, E_indx, E_tindx); /* look for ties in expected gain index */
tally[ptr->indx[E_indx[N]]]++; /* increment tally */
/* did we vote for someone other than first choice */
found = 0;
for (i = 0; i<= ptr->tindx[N]; i++)
if (ptr->indx[E_indx[N]] == ptr->indx[N-i]) found = 1;
if (!found) {
*altvote = *altvote + 1;
}
free (E); free (E_indx); free (E_tindx); free (t_indx); free (t_tindx);
}
/* return smaller of a and b */
int min (a,b)
int a, b;
{
if (a < b) return (a);
else return (b);
}
/* creates an index that identifies ties in an indexed list sorted
* in ascending order
*
* The Nth element of the indx array is the index of the first ranked
* data element. If the N-1 element is tied with the Nth element,
* the Nth element of the tindx array will contain a non-zero number
* corresponding to the number of elements that tie with the Nth
* element
*
* this function also swaps the indecies for the tied elements with
* random probability
*/
int findties(n,data,indx,tindx)
int n;
double data[];
int indx[], tindx[];
{
int i,t,r,temp,first;
first = 0;
for (i=1; i<=n; i++) tindx[i] = 0;
for (i=n; i>1; i--) {
for (t=i-1; t>0; t--) {
if (data[indx[i]] != data[indx[t]]) t=0;
else {
tindx[i]++;
if (i == n && tindx[i] > first) first = tindx[i];
r = (int)random()%2;
if (r == 1) {
temp=indx[i];
indx[i]=indx[t];
indx[t]=temp;
}
}
}
i = i - tindx[i];
}
return (first+1); /* first-place tie size */
}
/* for integers, same as above but data is an int */
int ifindties(n,data,indx,tindx)
int n, data[], indx[], tindx[];
{
/* ... */
}
/***** probability calculation functions and auxilaries *****************/
/* simple distance (note we only implemented this for 3 candidates */
double euDistanc (q, x, y, z,S)
double q, x, y, z,S;
{
return (1 - (sqrt(square(q - x) + square(q - y) + square(1 - 2.0 * q - z))));
}
/* Hoffman's method (note we only implemented this for 3 candidates */
double gaussian3 (q, x, y, z, S)
double q, x, y, z, S;
{
double D;
D = sqrt(square(q - x) + square(q - y) + square(1 - 2.0 * q - z));
return (exp (-.5 * square(D)/square(S)));
}
/* 2-D gaussian method */
double gaussian1 (q, x, S, blank1, blank2)
double q, x, S, blank1, blank2;
{
double pi = 3.14159;
return (exp (-.5 * square(q-x)/square(S))/ sqrt(2 * pi));
}
/***** functions from Numerical Recipes in C ****************************/
/* note floats have been replaced by doubles throughout */
/************************************************************************/
/* from Numerical Recipes in C: The Art of Scientific Computing
* by William H. Press, Brian P. Flannery, Saul A. Teukolsky,
* and William T. Vetterling. Cambridge University Press, 1988.
*
* The bodies of these functions have been removed and replaced with
* blank comments. Please refer to the above-mentioned text for the
* complete functions.
*/
/* Indexes an array arrin[1..n], i.e. outputs the array indx[1..n] such
* that arrin[indx[j]] is in ascending order for j=1,2,...,N. The input
* quantities n and arrin are not changed.
*/
void indexx(n,arrin,indx)
int n,indx[];
double arrin[];
{
/* ... */
}
/* same as indexx, but we made arrin an array of ints */
void iindexx(n,arrin,indx)
int n,indx[];
int arrin[]; /* changed from double */
{
/* ... */
}
/* Returns the integral of the function func from a to b. The parameters
* EPS can be set to the desired fractional accuracy and JMAX so that
* 2^JMAX-1 is the maximum allowed number of steps. Integration is performed
* by Simpson's rule
*
* modified slightly so that function can take 4 parameters
*/
#define EPS 1.0e-5 /* changed from 1.0e-6 */
#define JMAX 20
double qsimp(func,a,b,x,y,z,S)
double a,b,x,y,z,S;
double (*func)();
{
/* ... */
}
#undef EPS
#undef JMAX
/* This routine computes the nth stage of refinement of an extended
* trapezoidal rule. func is input as a pointer to the function to be
* integrated between limits a and b, also input. When called with n=1,
* the routine returns the crudest estimate of int(a->b)f(x)dx.
* Subsequent calls with n=2,3,... (in tht sequential order) will
* improve the accuracy by adding 2^n-2 additional interior points
*
* modified slighly so func can take 4 parameters
*/
#define FUNC(x) ((*func)(x,g,h,i,S))
double trapzd(func,a,b,n,g,h,i,S)
double a,b,g,h,i,S;
double (*func)(); /* ANSI: double (*func)(double); */
int n;
{
/* ... */
}