/*******************
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*