/******************* Voting system testing program votetest.c version 2 - incorporates Bucklin system and optional voter ignorance version 3 - incorporates Meek voting system(s?) and Carey's IFPP3 system (c) Warren D. Smith NEC Research Institute NJ USA October 2000 on LINUX systems, compile with gcc votetest.c -lm -lc -O9 -o votetest on other operating systems, or other C compilers than gcc, may require some fiddling to get it to compile. ****************************************************** Compares various voting systems experimentally via monte-carlo... Here is how... 1. generate (for V voters, c candidates) random in [0,1] utilities for each voter-candidate pair. (Other utility probability distributions also could be considered. See below.) 2. since we know the true voter utilities we know the true best candidate and his utility (summed over all voters). 3. run various voting schemes to elect the candidates various ways. 4. compute the "regret" for that voting system, which is the utility difference between the true-best candidate and whoever is elected. Presumably the best voting system is the one with minimal expected regret. With 100,000 simulated elections with [0,1] uniform utilities, the regret values should be accurate (90% conf error bds) to better than 1%, bootstrapping experiments show. -------- Following written critique by Prof. Steven J. Brams (NYU dept. of Politics) recvd March 2001, I now have modified this program to allow "ignorant voters." Brams was worried that range voting might not work well with ignorant voters and claimed (!?!) that half the electorate does not even know who the vice-president is. So, in the simulation, each voter has a true utility for each election winner, just as before, and these true utility values are used to assess the Bayesian regrets just as before. BUT now, each voter does not KNOW his own candidate-election utilities, instead what he knows is, those utilities, POLLUTED by the addition of IGNORANCE, i.e., added noise. Specifically we add a Gaussian random deviate with mean 0 and std. deviation Q. (If Q=0 this reduces to the old version of the program.) We may now re-run all the simulations with some Q>0, and see what happens. -------- All this is easy to do if have "honest" voters. "Honest approval" voting is somewhat hard to define since there are c-1 approval votes consistent with any c-candidate ordering. Which one do we pick? I will, somewhat arbitrarily, assume the honest voters approve of above-average candidates, in ApHa. Another kind of honest approval voter chooses his threshhold to maximize his expected utility assuming all other voters are completely random uniform, namely he maximizes the sum of utility differences between his top and bottom 2 groups. This is ApHu. Theorem (confirmed computationally): This actually is the same as ApHa!! To do the same experiment with "rational" voters is tougher. We will construct various strategies which seem to approximate rationality. PlS (strategic plurality) is: you vote for the best of the 2 frontrunners. BuS (strategic bullet) is: you vote against the worst of the 2 frontrunners. RaS (strategic range) is, you use as your threshhold, a utility midway between the 2 frontrunners and you give +1 to candidates above threshhold, -1 to candidates below. This seems to be the strategy which maximizes expected utility in 3-candidate elections, based on the reasoning that the 2 frontrunners have probability enormously close to 1 of being elected so you have to give them +1 and -1 to maximize your expected impact; then in the enormously unlikely event the 3rd candidate can contend, it is best to then act as though it were a 3-way tie in the polls so equally likely for you to break a tie between 3rd candidate and 1st, as between 3rd and 2nd, and given that you've already committed to +1 and -1 for the 2 frontrunners, the best choice of +1 and -1 for the 3rd candidate is the one maximizing the expected utility difference, i.e. use the avg of U1 and U2 as your threshhold. For elections with c>=4 candidates, though, I think the RaS strategy should be modified. Namely: consider the candidates in decreasing order of their election chances based on the pre-election polls. Vote +1,-1 or -1,+1 for the first 2 candidates. For candidates i=3,4,5,... select +1 or -1 as your vote, whichever maximizes sum sum (Uj - Uk) j=cands with +1 k=cands with -1 j<=i k<=i This is the same thing as: pick your vote[i] to be sign[ sum (Ui - Uk) - sum (Uj - Ui) ] k=cands with -1 j=cands with +1 k #include #include #include #include #define uint unsigned #define uchar unsigned char #define uint64 unsigned long long #define bool uint #define FALSE (1==0) #define TRUE (!(FALSE)) #define MaxVoters 200 #define MaxCandids 10 #define MaxSystems 50 int NumExperiments = 2000; #define VERBOSE 0 #define CHEESYCHECK 0 #define HONESTYSTATS 1 #define CONDHARESTATS 0 #define VERBOSECAREY 1 #define RANDOM_UTILITIES 0 #define NORMAL_UTILITIES 5 #define MaxIssues 10 double sqrt(double x); double log(double x); /*base e*/ /*voting systems:*/ #define RaH 0 #define BoH 1 #define LRH 2 #define CoombsH 3 #define STVH 4 #define Hcope 5 #define Hdaba 6 #define BlackH 7 #define Hbuck 8 #define PlRunH 9 #define PlH 10 #define BuH 11 #define RPM 12 #define RandomDict 13 #define RandomWin 14 #define WorstWin 15 #define ApHa 16 /*#define ApHu 11*/ #define RaS 17 #define RaS2 18 #define PlS 19 #define BoS 20 #define BuS 21 #define LRS 22 #define STVS 23 #define BoS2 24 #define CoombsS 25 #define BoS3 26 #define DaS 27 #define CopeS 28 #define BlackS 29 #define HIFPP3 30 #define SIFPP3 31 #define HMeek123 32 #define SMeek123 33 #define Htide 34 #define Stide 35 uint64 RaS2MisOrder[MaxCandids]; uint64 RaS2RaSDiffer[MaxCandids]; uint64 FunnyStatCt[MaxCandids]; int path[MaxCandids][MaxCandids]; double fabs (double x); /**** UNIX man page description of drand48: ...sequence of 48-bit integer values, X[i], according to the linear congruential formula X[n+1] = (a X[n] + c)mod m n>0. 48 The parameter m=2 ; hence 48-bit integer arithmetic is performed. Unless lcong48 has been invoked, the multiplier value a and the addend value c are given by a = 5DEECE66D_16 c = B_16 Therefore Period=2^48, but low-period least signif bits. *********************************************************/ double drand48(void); void srand48(long int seedval); /********************************************* long int random(void); void srandom(unsigned int seed); char *initstate(unsigned int seed, char *state, int n); UNIX man page falsely claims random() nonlinear. Actually, examining the source code shows it is a linear subtractive lagged fibonacci generator, has very large period if you go for max-size 256. ***********************************************/ char randstate[256]; int RandSeed = 3456781; int Voters = 10; double IGNORANCEQ = 1.0; double CandIgnorance[MaxCandids]; /* candidate-dependent ignorance values */ double utils[MaxVoters][MaxCandids]; /* utils[i][j] true utility of cand j for voter i */ double igutl[MaxVoters][MaxCandids]; /* utils[][] but with ignorance added */ double voterstance[MaxVoters][MaxIssues]; double candstance[MaxCandids][MaxIssues]; uint hrank[MaxVoters][MaxCandids]; uint drank[MaxVoters][MaxCandids]; double hplurregret; double hplurRUNregret; double hbulletregret; double hbordaregret; double htidemanregret; double stidemanregret; double hIFPP3regret; double sIFPP3regret; double hMeek123regret; double sMeek123regret; double hblackregret; double hrangeregret; double hSTVregret; double hLRregret; double hAPPAregret; double hAPPUregret; double hRdictregret; double hrandregret; double hworstregret; double hRPMregret; double hBucklinregret; double hCOPEregret; double hDABAregret; double srangeregret; double splurregret; double sblackregret; double sbordaregret; double sbulletregret; double srangeregret2; double sLRregret; double sSTVregret; double sBoS2regret; double sBoS3regret; double hCoombsregret; double sCoombsregret; double sDABAregret; double sCOPEregret; double regrets[MaxCandids][MaxSystems]; uint sclrw[MaxCandids], shstvw[MaxCandids]; /* used for collecting stats on strategic condorcet least rev, * strategic hare stv winners */ /************************************* I.D.Hill, B.A.Wichmann, D.R.Woodall: Algorithm 123, single transferable vote by Meek's method, Computer Journal 30,3 (1987) 277-281 available online at http://www.bcs.org.uk/election/meek/meekm.htm Sometimes very high precision floating point #s are required, s later demonstrated by Wichmann. For instance, with 69 candidates and <1000 votes, one can produce an example requiring 127 decimal places! But in practice high precision is usually not a problem. I am using double precision and ignoring the issue. Brian L. Meek died in 1997. His voting method was adopted by the Electoral Reform Society, the Royal Statistical Society, and the London Mathematical Society. This implementation has not been tested for NUMSEATS>1. This may or may not be the same as: Brian L. Meek: A transferable voting system including intensity of preference, Math\'ematiques et Sciences Humaines 13, 50 (Summer 1975) 23-29. This Meek paper was reprinted in the ERS publication ``Voting Matters,'' Issue 6, May 1996. *************************************/ #define NUMSEATS 1 /* more than 1 if want more-than-1-winner elections */ int MeekAlg123( rankings, randperm, C ) uint rankings[MaxVoters][MaxCandids]; uint randperm[MaxCandids]; /* used for tie-breaking */ uint C; /* number of candidates */ /* rankings[3][5] is the 4th voter's 6th ranked candidate (note * counts start from 0). It is left unaltered by this routine. */ { #define EXCLUDED 0 #define HOPEFUL 1 #define ELECTED 2 #define MaxMeekIters 333 int i,j,h; uint leastliked,iterct,numelected,numexcluded; bool Converged,ElectedSomebody; double minvots,adjustfactor,totalvotes,quota,excess,w1,w2; double CandWeight[MaxCandids]; double CandV[MaxCandids]; uchar CandStatus[MaxCandids]; assert(1<=NUMSEATS); assert(NUMSEATS<=C); /* initial set up: */ for(i=0; iB>C is processed as follows: * A receives from that voter v[A] += w[A] * B receives from that voter v[B] += (1-w[A])*w[B] * C receives from that voter v[C] += (1-w[A])*(1-w[B])*w[C] * the remaining votes go to excess += (1-w[A])*(1-w[B])*(1-w[C]) * Then we let totalvotes = v[0]+v[1]+...+v[C-1]; ****************************************************/ excess = 0.0; for(i=0; i1.0000001 || adjustfactor<0.9999999){ Converged=FALSE; } CandWeight[j] *= adjustfactor; if(CandWeight[j]>1.0) CandWeight[j]=1.0; } } }while( iterct= quota ){ CandStatus[j] = ELECTED; /* CandWeight[j] = quota/CandV[j]; ???*/ ElectedSomebody = TRUE; numelected++; } } leastliked=C; if( ElectedSomebody==FALSE ){ minvots = HUGE; for(j=C-1; j>=0; j--){ h = randperm[j]; if( CandV[h] < minvots ){ minvots = CandV[h]; leastliked = h; } } assert(leastliked= C){ for(i=0; i=0; i--){ if(numelected<=NUMSEATS) break; h = randperm[i]; if( CandStatus[h] == ELECTED ){ numelected--; CandStatus[h] == EXCLUDED; } } for(i=0; i>32)); } double myrand(){ /* combines 2 UNIX randgens, and my 2 randgens above, * since don't trust any of them */ double x,z; z = drand48(); assert(0.<=z); assert(z<=1.); x = random() / (1. + RAND_MAX); assert(0.<=x); assert(x<=1.); z -= x; if(z<0.0) z += 1.0; assert(0.<=z); assert(z<=1.); x = (Coveyou()^((uint)ParkMiller())) * (1/4294967295.7); assert(0.<=x); assert(x<=1.); z -= x; if(z<0.0) z += 1.0; assert(0.<=z); assert(z<=1.); return z; } /* uses myrand() to find a unit-variance normal deviate * Polar method Knuth SNA 3.4.1C */ double mynormalrand(){ double v1,s; static double v2; static int normct=0; if(normct){ normct=0; return(v2); } normct=1; do{ v1 = myrand(); v2 = myrand(); v1 = 2.*v1-1.; v2 = 2.*v2-1.; s = v1*v1+v2*v2; }while( s >= 1.0 ); s = sqrt(-2.*log(s)/s); v1 *= s; v2 *= s; return(v1); } /************************************* G.A.Craig Carey's "IFPP" method Carey email: research@ijs.co.nz ("Improved First Past the Post") for conducting 3-candidate elections, with the 3 candidates named A,B,C. You can cast exactly one of 9 possible types of votes: The 9 kinds Name of variable that of allowed votes counts that kind of vote ---------------- ------------------------- A a0 A>B ab A>C ac B b0 B>C bc B>A ba C c0 C>A ca C>B cb (It seems that Carey intends "A" to mean "A>B and A>C" and "B>C" to mean "B>C>A"; the candidates un-named in your preference ordering are regarded as worse, in your view, than the named ones.) Let a = a0+ab+ac; b = b0+ba+bc; c = c0+ca+cb; The below C code by WDS is based on Carey's RELOG code. IFPP is only available for 1,2, and 3 candidate elections, with either 1 or 2 winners allowed in the 3-candidate case. ****************************************** IFPP3(a,ab,ac, b,bc,ba, c,ca,cb) int a,ab,ac, b,bc,ba, c,ca,cb; { bool Wa,Wb,Wc, La,Lb,Lc; Wa = (b+c<2*a) && ((b+cb2*a) && ((b+cb>a+ca) || (2*b>a+c)) && ((c+bc>a+ba) || (2*c>a+b)); Lb = (c+a>2*b) && ((c+ac>b+ab) || (2*c>b+a)) && ((a+ca>b+cb) || (2*a>b+c)); Lc = (a+b>2*c) && ((a+ba>c+bc) || (2*a>c+b)) && ((b+ab>c+ac) || (2*b>c+a)); * Lc=TRUE means A and B are both winners if 2-winner election; one could * then set Wa = Lc || Lb; Wb = Lc || La; Wc = Lb || La; * if desired. ** return stuff; } *********************************** If all voters express full preference orderings (i.e. only 6 of the 9 kinds of votes are now allowed) then IFPP simplifies to the following: *******************************************/ uint SimpleIFPP3(ab,ac, bc,ba, ca,cb) uint ab,ac, bc,ba, ca,cb; { uint a,b,c; uint Wa,Wb,Wc; /* actually bool */ /*,La,Lb,Lc;*/ a=ab+ac; b=bc+ba; c=ca+cb; Wa = (b+c<2*a) && ((b+cb2*a) && ((b+cb>a+ca) || (2*b>a+c)) && ((c+bc>a+ba) || (2*c>a+b)); Lb = (c+a>2*b) && ((c+ac>b+ab) || (2*c>b+a)) && ((a+ca>b+cb) || (2*a>b+c)); Lc = (a+b>2*c) && ((a+ba>c+bc) || (2*a>c+b)) && ((b+ab>c+ac) || (2*b>c+a)); * Lc=TRUE means A and B are both winners if 2-winner election; one could * then set Wa = Lc || Lb; Wb = Lc || La; Wc = Lb || La; * if desired. **************/ if(Wa) return(0); if(Wb) return(1); if(!Wc){ /*no winner! *this pathology apparently cannot happen if prime # of voters */ #if VERBOSECAREY printf("ab=%d ac=%d bc=%d ba=%d ca=%d cb=%d\n", ab,ac, bc,ba, ca,cb); #endif /* not sure below is what Carey really wanted: */ return( (uint)(myrand()*3.0) ); } assert(Wc); return(2); } uint MySimpleIFPP3(ab,ac, bc,ba, ca,cb) double ab,ac, bc,ba, ca,cb; { uint a,b,c; uint Wa,Wb,Wc; /* actually bool */ /*,La,Lb,Lc;*/ a=ab+ac; b=bc+ba; c=ca+cb; Wa = (b+c<2*a) && ((b+cb 0){ /* ISSUE_BASED_UTILS; kind=#issues */ assert(kind<=MaxIssues); for(i=0; i sumutils[i]) worstutil = sumutils[i]; /* honest ranks hrank[0]=best, hrank[1]=2ndbest ... hrank[C-1]=worst: */ for(i=0; i= igutl[i][hrank[i][j]] ); } } /* dishonest ranks drank[0]=best, drank[1]=2ndbest etc: just like honest ranks except * best frontrunner is top ranked and worst is bottom ranked. */ for(j=0; j= 0 ); assert( argmax == hrank[i][0] ); hplurvotes[argmax] ++; } best = -99; winner = -1; for(i=0; i= 0); hplurregret = bestutil - sumutils[winner]; /* honest IFPP3 (use honest plurality if c!=3): */ if(C!=3){ hIFPP3regret = bestutil - sumutils[winner]; } /* honest plurality with runoff: */ if(2*hplurvotes[winner] < Voters){ /*only do runoff if no >=50% winner*/ best = -99; secbest = -99; for(i=0; i= 0); assert(secwinr >= 0); /* now do runoff between winner, secwinr: */ c1=c2=0; for(i=0; i= igutl[i][secwinr] ) c1++; else c2++; } if(c2>c1) winner = secwinr; } hplurRUNregret = bestutil - sumutils[winner]; /* honest IFPP3 (if c==3) */ if(C==3){ double ab,ac,bc,ba,ca,cb; ab=ac=cb=ca=bc=ba=0.0; for(i=0; i igutl[i][j]){ minutil = igutl[i][j]; argmin = j; } } assert( argmin >= 0 ); assert( fabs( igutl[i][argmin] - igutl[i][ hrank[i][C-1] ] ) < 0.000001 ); hbullets[argmin] ++; } best = Voters*99; winner = -1; for(i=0; i hbullets[randperm[i]]){ best = hbullets[randperm[i]]; winner = randperm[i]; } assert(winner >= 0); hbulletregret = bestutil - sumutils[winner]; /* honest range (i.e. scaled utility voting): */ for(i=0; i0.0); reciputildiff = 1.0/utildiff; for(j=0; j=0; i--) if(elimcand[randperm[i]]==0){ if(best > hplurvotes[randperm[i]]){ best = hplurvotes[randperm[i]]; loser = randperm[i]; } } assert(loser>=0); assert(loser=0); assert(winner<=C); hSTVregret = bestutil - sumutils[winner]; /* strategic Hare STV - vote one of the 2 frontrunners last place, other top, rest honest. */ for(i=0; i=0; i--) if(elimcand[randperm[i]]==0){ if(best > hplurvotes[randperm[i]]){ best = hplurvotes[randperm[i]]; loser = randperm[i]; } } assert(loser>=0); assert(loser=0); assert(winner<=C); sSTVregret = bestutil - sumutils[winner]; shstvwinner = winner; shstvw[shstvwinner]++; /* honest Coombs STV (eliminate candid with most worst-place votes): */ for(i=0; i=0; j--){ if(best=0); assert(elimcand[loser]==0); elimcand[loser]=1; /*eliminate loser*/ for(i=0; i= 0); } assert( elimcand[hrank[i][elimind[i]]] == 0 ); } } winner = -1; for(i=0; i=0); assert(winner<=C); hCoombsregret = bestutil - sumutils[winner]; /* Strategic Coombs STV (eliminate candid with most worst-place votes): */ for(i=0; i=0; j--){ if(best=0); assert(elimcand[loser]==0); elimcand[loser]=1; /*eliminate loser*/ for(i=0; i= 0); } assert( elimcand[drank[i][elimind[i]]] == 0 ); } } winner = -1; for(i=0; i=0); assert(winner<=C); sCoombsregret = bestutil - sumutils[winner]; /* strategic IFPP3 (if c==3) */ if(C==3){ double ab,ac,bc,ba,ca,cb; ab=ac=cb=ca=bc=ba=0.0; for(i=0; i igutl[i][k]) ? 1 : -1); }}} for(i=0; i summargin[randperm[i]]){ best = summargin[randperm[i]]; winner = randperm[i]; } hLRregret = bestutil - sumutils[winner]; Hcondwinner = winner; for( k=0; k 0) sumvictories[j] += 2; if(pairels[j][k] == 0) sumvictories[j] ++; }} best = -1; for(i=0; iB comparison with the largest margin and "lock it in". * Then you pick the next largest one available * ("available" means: not already used and not creating a cycle), * and continue on. This creates an ordering of the candidates. The * topmost in the ordering wins. It is a bit tricky to spot * the cycles as we go... * (This code based on email from Blake Cretney bcretney@postmark.net): ******************************************/ /*path[][] is used as a changeable copy of pairels.*/ for(i=0;imaxp){ maxp=path[oi][oj]; i=oi; j=oj; } if(path[oj][oi]>maxp){ maxp=path[oj][oi]; i=oj; j=oi; } } } if(maxp==INT_MIN) break; /********* print the pair and its margin: printf("(%d %d) %d\n",i,j,maxp); ***********************/ /*lock in the pair and clobber future no-good pairs:*/ for(oi=0;oi=C){ winner=i; break; } } assert(winner >= 0); htidemanregret = bestutil - sumutils[winner]; /* Remarks: * B.Cretney: The Ranked Pair algorithm above takes O(C^4) time. * An O(C^3) time algorithm is possible, but it is more complex. * WD.Smith: An O(C^4) algorithm is perfectly acceptable if C<20, * but anyway... for people interested in the true asymptotic * complexity for large C... I suspect an O(C^{2.001}) algorithm is * possible, or more precisely O(C^2 * logterms). This would be * best possible (except for the logterms). * It would work as follows. Regard the already-locked-in ranked pairs * as a DAG (directed acyclic graph; the "acyclic" means there * are no logical inconsistencies in the ranking). We maintain * a spanning forest which sort of "over-represents" the "skeleton" * of this DAG. (By "skeleton" I mean the key comparisons from which * all the others merely are consequences by transitivity. By *"over-represented" I mean: For a DAG C<--B2<--A-->B1-->C, * the node C is represented twice in the spanning tree shown.) * We now go thru the candidate edges in increasing cost order. 8 (Can use a "heap," also called "priority queue," data structure * to allow doing that in O(logC) time per candidate edge.) * Now at any moment we want to find a new lowest-cost directed-edge * to adjoin to the DAG, which does not cause a directed cycle. * With the aid of fast "lowest common ancestor" data structures * associated with each tree in our forest (and associated * algorithm tricks), we may quickly determine for any candidate * directed-edge whether it would cause a cycle in the DAG. * (Namely: If the candidate edge joins two forest trees, it cannot * cause a cycle. If it joins nodes from a single tree, then * it causes a cycle if and only if the lowest common ancestor of the * two nodes is, in fact, one of the nodes themselves, and * the edge is directed toward it.) If it would, we mark that edge * as "dead and never to be looked at again ever", i.e. we delete * it from the "heap". If it would not cyclize, we adjoin it * to the DAG and update all our tree and LCA data structures * and lock it in. The total number of such data structure * updates is O(C). * * The above sketch is still a sketch with missing details and * it could easily be there is a big problem with it. I.e. it * is not to be regarded as a proof such a runtime complexity * is achievable, but it is pointing the way to try to * devise such a proof. -WDS. *****************************************************/ /* honest Borda: */ for(i=0; i= 0) winner = Hcondwinner; else winner = Hbordwinner; hblackregret = bestutil - sumutils[winner]; /* honest Dabagh: */ for(i=0; i igutl[i][k]+extra[k]) ? 1 : -1); }}} for(i=0; i summargin[randperm[i]]){ best = summargin[randperm[i]]; winner = randperm[i]; } sLRregret = bestutil - sumutils[winner]; sclrwinner = winner; sclrw[sclrwinner]++; #if CONDHARESTATS if( sclrwinner>1 || shstvwinner>1 || sclrwinner != shstvwinner ){ printf("sclrwinner=%d != shstvwinner=%d >1\n", sclrwinner, shstvwinner); } #endif Scondwinner = winner; for( k=0; k 0) sumvictories[j] += 2; if(pairels[j][k] == 0) sumvictories[j] ++; }} best = -99; for(i=0; iB comparison with the largest margin and "lock it in". * Then you pick the next largest one available * ("available" means: not already used and not creating a cycle), * and continue on. This creates an ordering of the candiates. The * topmost in the ordering wins. It is a bit tricky to spot * the cycles as we go... * (This code based on email from Blake Cretney bcretney@postmark.net): ******************************************/ /*path[][] is used as a changeable copy of pairels.*/ for(i=0;imaxp){ maxp=path[oi][oj]; i=oi; j=oj; } if(path[oj][oi]>maxp){ maxp=path[oj][oi]; i=oj; j=oi; } } } if(maxp==INT_MIN) break; /********* print the pair and its margin: printf("(%d %d) %d\n",i,j,maxp); ***********************/ /*lock in the pair and clobber future no-good pairs:*/ for(oi=0;oi=C){ winner=i; break; } } assert(winner >= 0); stidemanregret = bestutil - sumutils[winner]; /* random dictator; */ dictator = myrand() * Voters; assert(dictator < Voters); bestD = -99.; for(i=0; i=c1) winner=winner2; else winner=winner1; hRPMregret = bestutil - sumutils[winner]; /* worst winner (pessimal): */ hworstregret = bestutil - worstutil; /* honest approval: uses avg as threshhold for approval */ for(i=0; i avg ) happrov[j]++; } } best = -99; for(i=0; i bestudiff){ bestudiff = udiff; thw = th; } } for(j=0; j Voters || rnd==C-1){ hBucklinregret = bestutil - sumutils[winner]; break; } } /***********************now for strategic voting********************/ /*PlS (strategic plurality) vote for the best of the 2 frontrunners.*/ for(i=0; i sbullets[randperm[i]]){ best = sbullets[randperm[i]]; winner=randperm[i]; } sbulletregret = bestutil - sumutils[winner]; /*RaS (strategic range): use as your threshhold, a utility midway * between the 2 frontrunners and you give +1 to candidates above * threshhold, -1 to candidates below: ****/ for(i=0; i umsum) myvotes[j]++; umsum += myutil; } for(j=0; jigutl[i][j]) topmin = igutl[i][j]; if(myvotes[j]==0 && botmaxuthresh) ){ /******************** printf("RaS2 and RaS differ %f\n", fabs(igutl[i][j]-uthresh) ); for(k=0; k umsum){ sbordavotes[j] += maxBvote; maxBvote--; }else{ sbordavotes[j] += minBvote; minBvote++; } umsum += myutil; } assert(maxBvote==minBvote-1); } best = -Voters*C*99; for(i=0; i umsum || j==C-1){ sdabaghvotes[j] += 1; break; } umsum += myutil; } } best = -99; for(i=0; i= 0) winner = Scondwinner; else winner = Sbordwinner; sblackregret = bestutil - sumutils[winner]; /* Strategic Meek123: */ winner = MeekAlg123( drank, randperm, C ); sMeek123regret = bestutil - sumutils[winner]; } CheeseTest() { int i,j,k,best,winner; double uthresh,umsum,myutil,topmin,botmax,bestutil=100.; int C=4; int srangevotes[MaxCandids]; int myvotes[MaxCandids]; double foou[] = {0.,9.,100.,11.}; /*RaS (strategic range): use as your threshhold, a utility midway * between the 2 frontrunners and you give +1 to candidates above * threshhold, -1 to candidates below: ****/ for(i=0; i umsum) myvotes[j]++; umsum += myutil; } for(j=0; jfoou[j]) topmin = foou[j]; if(myvotes[j]==0 && botmaxuthresh) ){ printf("RaS2 and RaS differ %f\n", fabs(foou[j]-uthresh) ); for(k=0; k9.0){ fprintf(stderr, "Making IGNORANCEQ=9 since you specified >9, moron.\n"); fprintf(stderr, "0 means no voter ignorance; 1 is a fairly high ignorance setting.\n"); IGNORANCEQ=9.0; } printf("Seeding with %u\n", RandSeed); srand48(RandSeed); initstate(RandSeed, randstate, 256); CoveyouX ^= (((uint64)RandSeed)<<2); ParkMillerX ^= RandSeed; ParkMillerX |= 1; ParkMillerX &= 2147483647; if(NumExperiments<1){ fprintf(stderr, "At least 1 experiment needed, you said %d\n", NumExperiments); exit(1); } if(Voters>MaxVoters){ fprintf(stderr, "No more than %d voters allowed, you used %d\n", MaxVoters,Voters); exit(1); } if(Voters<1){ fprintf(stderr, "Need >=1 voter, fool: used %d\n", Voters); exit(1); } printf("drand48 %lf %lf %lf %lf %lf\n", drand48(),drand48(),drand48(),drand48(),drand48()); printf("drand48 %f %f %f %f %f\n", drand48(),drand48(),drand48(),drand48(),drand48()); printf("random %8x %8x %8x %8x %8x\n", random(),random(),random(),random(),random()); printf("random %8x %8x %8x %8x %8x\n", random(),random(),random(),random(),random()); printf("random %8x %8x %8x %8x %8x\n", random(),random(),random(),random(),random()); printf("random %8x %8x %8x %8x %8x\n", random(),random(),random(),random(),random()); printf("RAND_MAX %8x\n", RAND_MAX); printf("Coveyou %8x %8x %8x %8x %8x\n", Coveyou(),Coveyou(),Coveyou(),Coveyou(),Coveyou()); printf("Coveyou %8x %8x %8x %8x %8x\n", Coveyou(),Coveyou(),Coveyou(),Coveyou(),Coveyou()); printf("Coveyou %8x %8x %8x %8x %8x\n", Coveyou(),Coveyou(),Coveyou(),Coveyou(),Coveyou()); printf("Coveyou %8x %8x %8x %8x %8x\n", Coveyou(),Coveyou(),Coveyou(),Coveyou(),Coveyou()); printf("Coveyou %8x %8x %8x %8x %8x\n", Coveyou(),Coveyou(),Coveyou(),Coveyou(),Coveyou()); printf("Coveyou %8x %8x %8x %8x %8x\n", Coveyou(),Coveyou(),Coveyou(),Coveyou(),Coveyou()); printf("ParkMiller %8x %8x %8x %8x %8x\n", ParkMiller(),ParkMiller(),ParkMiller(),ParkMiller(),ParkMiller()); printf("ParkMiller %8x %8x %8x %8x %8x\n", ParkMiller(),ParkMiller(),ParkMiller(),ParkMiller(),ParkMiller()); printf("myrand %f %f %f %f %f\n", myrand(),myrand(),myrand(),myrand(),myrand()); printf("myrand %f %f %f %f %f\n", myrand(),myrand(),myrand(),myrand(),myrand()); printf("myrand %f %f %f %f %f\n", myrand(),myrand(),myrand(),myrand(),myrand()); printf("myrand %f %f %f %f %f\n", myrand(),myrand(),myrand(),myrand(),myrand()); if(CHEESYCHECK){ printf("CheeseTest:\n"); CheeseTest(); printf("end CheeseTest.\n"); } printf("\nsystems\n"); printf( "-------\n"); for(i= -1; i 1 ) printf("s). "); else printf("). "); } printf("IgnoranceQ=%.2f. ", IGNORANCEQ); if(cand_ignorance){ printf("Canddt-Dependent. "); }else{ printf("(Identical.) "); } printf("%d voters.\n", Voters); if(kind_of_utils!=NORMAL_UTILITIES ){ printf("Each candidate utility (for each voter)\n"); printf("normalized to lie somewhere in [0,1].\n"); } printf("Each regret datapoint averages %u expts.\n", NumExperiments); for(i=0; i