Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Kelly's Favorite
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.HashMap;
public class KellysFavorite implements Player {
private ArrayList<Double> cache = new ArrayList<Double>();
public KellysFavorite(int elections) {
cache.add(0.0);
double v = 0.0;
for(int i=1; i<1000; i++) {
v += Math.log(i);
cache.add(v);
}
}
@Override
public String getName() {
return "Kelly's Favorite";
}
private double factln(int n) {
return cache.get(n);
}
private double binll(int x, int n, double p)
{
double ll = 0.0;
ll += ((double)x)*Math.log(p);
ll += ((double)(n - x))*Math.log(1.0 - p);
ll += factln(n) - factln(x) - factln(n-x);
return ll;
}
public double logAdd(double logX, double logY) {
// 1. make X the max
if (logY > logX) {
double temp = logX;
logX = logY;
logY = temp;
}
// 2. now X is bigger
if (logX == Double.NEGATIVE_INFINITY) {
return logX;
}
// 3. how far "down" (think decibels) is logY from logX?
// if it's really small (20 orders of magnitude smaller), then ignore
double negDiff = logY - logX;
if (negDiff < -20) {
return logX;
}
// 4. otherwise use some nice algebra to stay in the log domain
// (except for negDiff)
return logX + java.lang.Math.log(1.0 + java.lang.Math.exp(negDiff));
}
@Override
public int getVote(int[] voteCounts,
int votersRemaining,
int[] payoffs,
int[] totalPayoffs) {
int totalviable = 0;
boolean[] viable = { false, false, false };
int topVote = Arrays.stream(voteCounts).max().getAsInt();
for (int index = 0; index < 3; index++) {
if (voteCounts[index] + votersRemaining + 1 >= topVote) {
viable[index] = true;
totalviable += 1;
}
}
// if only one candidate remains viable, vote for them
if(totalviable == 1) {
for(int index = 0; index < 3; index++)
if(viable[index])
return index;
} else {
double votelikelihoods[] = { 0.0, 0.0, 0.0 };
double totalweight = 0.0;
for(int index=0; index<3; index++) {
if(!viable[index])
votelikelihoods[index] -= 10.0;
else if(voteCounts[index] < topVote)
votelikelihoods[index] -= 0.1;
totalweight += Math.exp(votelikelihoods[index]);
}
double probs[] = new double[3];
for(int index=0; index<3; index++) {
probs[index] = Math.exp(votelikelihoods[index]) / totalweight;
}
double[] utilities = {0,0,0};
for(int mychoice=0; mychoice<3; mychoice++) {
boolean seen[] = { false, false, false };
double likelihoods[] = { Double.NEGATIVE_INFINITY,
Double.NEGATIVE_INFINITY,
Double.NEGATIVE_INFINITY };
int[] localVoteCounts = { voteCounts[0] + (mychoice==0?1:0),
voteCounts[1] + (mychoice==1?1:0),
voteCounts[2] + (mychoice==2?1:0) };
for(int iVotes=0; iVotes<=votersRemaining; iVotes++)
for(int jVotes=0; jVotes<=(votersRemaining-iVotes); jVotes++) {
int kVotes = votersRemaining - iVotes - jVotes;
int a = localVoteCounts[0] + iVotes;
int b = localVoteCounts[1] + jVotes;
int c = localVoteCounts[2] + kVotes;
int wincount = Math.max(a, Math.max(b, c));
int winners = 0;
if(a>=wincount) { winners += 1; }
if(b>=wincount) { winners += 1; }
if(c>=wincount) { winners += 1; }
double likelihood =
binll(iVotes, votersRemaining, probs[0])
+ binll(jVotes, votersRemaining-iVotes, probs[1] / (probs[1] + probs[2]));
likelihood += Math.log(1.0/winners);
if(a>=wincount) {
if(seen[0])
likelihoods[0] = logAdd(likelihoods[0],
likelihood);
else
likelihoods[0] = likelihood;
seen[0] = true;
}
if(b>=wincount) {
if(seen[1])
likelihoods[1] = logAdd(likelihoods[1],
likelihood);
else
likelihoods[1] = likelihood;
seen[1] = true;
}
if(c>=wincount) {
if(seen[2])
likelihoods[2] = logAdd(likelihoods[2],
likelihood);
else
likelihoods[2] = likelihood;
seen[2] = true;
}
}
for(int index=0; index<3; index++)
utilities[mychoice] += Math.exp(likelihoods[index]) * Math.log((double)payoffs[index]);
}
double maxutility = Math.max(utilities[0], Math.max(utilities[1], utilities[2]));
int choice = 0;
for(int index=0; index<3; index++)
if(utilities[index]>=maxutility)
choice = index;
return choice;
}
throw new InternalError();
}
@Override
public void receiveResults(int[] voteCounts, double result) {
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.