37
\$\begingroup\$

One of the most common voting systems for single-winner elections is the plurality voting method. Simply put, the candidate with the most votes wins. Plurality voting, however, is mathematically unsound and is liable to create situations in which voters are driven to vote for the "lesser of two evils" as opposed to the candidate they truly prefer.

In this game, you will write program that takes advantage of the plurality voting system. It will cast a vote for one of three candidates in an election. Each candidate is associated with a certain payoff for yourself, and your goal is to maximize your expected payoff.

The payoffs are "uniformly" randomly distributed, change with each election, and add to 100. Candidate A could have payoff 40, Candidate B could have payoff 27, and Candidate C could have payoff 33. Each player has a different set of payoffs.

When it is your turn to vote, you will have incomplete information. Listed below is the information that you will have available to you. Since you don't know what other player's individual payoffs are, it will be your challenge to predict how they would vote given the current poll results.

  • The partial results of the election so far
  • The number of entrants (excluding yourself), who haven't voted yet
  • Your personal payoffs for each of the candidates
  • The total group payoffs for each of the candidates

After each player has been given a chance to vote, the candidate with the most votes wins in accordance with plurality voting. Each player then receives the number of points that corresponds the their payoff from that candidate. If there is a tie in votes, then the number of points assigned will be the average of the tied candidates.

Tournament Structure

When first instantiated, the entrant will be told the number of elections held in the tournament. I will attempt to run an extremely large number of elections. Then, each election will be carried out one-by-one.

After the entrants are shuffled, each is given a turn to vote. They are given the limited information listed above and return a number signifying their vote. After each election is over, each bot is given the final poll results and their score increase from that election.

The victorious entrant will be the one with the highest total score after some large number of elections have been held. The controller also computes a "normalized" score for each contestant by comparing its score to the score distribution predicted for a randomly-voting bot.

Submission Details

Submissions will take the form of Java 8 classes. Each entrant must implement the following interface:

public interface Player
{
    public String getName();
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs);
    public void receiveResults(int[] voteCounts, double result);
}
  • Your constructor should take a single int as a parameter, which will represent the number of elections that will be held.
  • The getName() method returns the name to be used on the leaderboard. This allows you to have nicely-formatted names, just don't go crazy.
  • The getVote(...) method returns 0, 1, or 2 to signify which candidate will receive the vote.
  • The receiveResults(...) method is mainly to enable the existence of more complex strategies that use historical data.
  • You are allowed to create pretty much any other methods / instance variables you wish to record and process the information given to you.

Tournament Cycle, Expanded

  1. The entrants are each instantiated with new entrantName(int numElections).
  2. For each election:
    1. The controller randomly determines the payoffs for each player for this election. The code for this is given below. Then, it shuffles players and has them start voting.
    2. The entrant's method public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) is invoked, and the entrant returns their vote of 0, 1, or 2 for the candidate of their choice.
    3. Entrants whose getVote(...) method doesn't return a valid vote will be assigned a random vote.
    4. After everyone has voted, the controller determines the election results by the plurality method.
    5. The entrants are informed of the final vote counts and their payoff by calling their method public void receiveResults(int[] voteCounts, double result).
  3. After all elections have been held, the winner is the one with the highest score.

The Random Distribution of Payoffs

The exact distribution will have a significant effect on gameplay. I have chosen a distribution with a large standard deviation (about 23.9235) and which is capable of creating both very high and very low payoffs. I have checked that each of the three payoffs has an identical distribution.

public int[] createPlayerPayoffs()
{
    int cut1;
    int cut2;
    do{
        cut1 = rnd.nextInt(101);
        cut2 = rnd.nextInt(101);  
    } while (cut1 + cut2 > 100);
    int rem = 100 - cut1 - cut2;
    int[] set = new int[]{cut1,cut2,rem};
    totalPayoffs[0] += set[0];
    totalPayoffs[1] += set[1];
    totalPayoffs[2] += set[2];
    return set;
}

More Rules

Here are some more generalized rules.

  • Your program must not run/modify/instantiate any parts of the controller or other entrants or their memories.
  • Since your program stays "live" for the whole tournament, don't create any files.
  • Don't interact with, help, or target any other entrant programs.
  • You may submit multiple entrants, as long as they are reasonably different, and as long as you follow the above rules.
  • I haven't specified an exact time limit, but I would greatly appreciate runtimes that are significantly less than a second per call. I want to be able to run as many elections as feasible.

The Controller

The controller can be found here. The main program is Tournament.java. There are also two simple bots, which will be competing, titled RandomBot and PersonalFavoriteBot. I will post these two bots in an answer.

Leaderboard

It looks like ExpectantBot is the current leader, followed by Monte Carlo and then StaBot.

Leaderboard - 20000000 elections:
   767007688.17 (  937.86) - ExpectantBot                            
   766602158.17 (  934.07) - Monte Carlo 47                          
   766230646.17 (  930.60) - StatBot                                
   766054547.17 (  928.95) - ExpectorBot                             
   764671254.17 (  916.02) - CircumspectBot                          
   763618945.67 (  906.19) - LockBot                                 
   763410502.67 (  904.24) - PersonalFavoriteBot343                  
   762929675.17 (  899.75) - BasicBot                                
   761986681.67 (  890.93) - StrategicBot50                          
   760322001.17 (  875.37) - Priam                                   
   760057860.67 (  872.90) - BestViableCandidate (2842200 from ratio, with 1422897 tie-breakers of 20000000 total runs)
   759631608.17 (  868.92) - Kelly's Favorite                        
   759336650.67 (  866.16) - Optimist                                
   758564904.67 (  858.95) - SometimesSecondBestBot                  
   754421221.17 (  820.22) - ABotDoNotForget                         
   753610971.17 (  812.65) - NoThirdPartyBot                         
   753019290.17 (  807.12) - NoClueBot                               
   736394317.17 (  651.73) - HateBot670                              
   711344874.67 (  417.60) - Follower                                
   705393669.17 (  361.97) - HipBot                                  
   691422086.17 (  231.38) - CommunismBot0                           
   691382708.17 (  231.01) - SmashAttemptByEquality (on 20000000 elections)
   691301072.67 (  230.25) - RandomBot870                            
   636705213.67 ( -280.04) - ExtremistBot                            
The tournament took 34573.365419071 seconds, or 576.2227569845166 minutes.

Here are some older tournament, but none of the bots have changed in functionality since these runs.

Leaderboard - 10000000 elections:
   383350646.83 (  661.14) - ExpectantBot                            
   383263734.33 (  659.99) - LearnBot                                
   383261776.83 (  659.97) - Monte Carlo 48                          
   382984800.83 (  656.31) - ExpectorBot                             
   382530758.33 (  650.31) - CircumspectBot                          
   381950600.33 (  642.64) - PersonalFavoriteBot663                  
   381742600.33 (  639.89) - LockBot                                 
   381336552.33 (  634.52) - BasicBot                                
   381078991.83 (  631.12) - StrategicBot232                         
   380048521.83 (  617.50) - Priam                                   
   380022892.33 (  617.16) - BestViableCandidate (1418072 from ratio, with 708882 tie-breakers of 10000000 total runs)
   379788384.83 (  614.06) - Kelly's Favorite                        
   379656387.33 (  612.31) - Optimist                                
   379090198.33 (  604.83) - SometimesSecondBestBot                  
   377210328.33 (  579.98) - ABotDoNotForget                         
   376821747.83 (  574.84) - NoThirdPartyBot                         
   376496872.33 (  570.55) - NoClueBot                               
   368154977.33 (  460.28) - HateBot155                              
   355550516.33 (  293.67) - Follower                                
   352727498.83 (  256.36) - HipBot                                  
   345702626.33 (  163.50) - RandomBot561                            
   345639854.33 (  162.67) - SmashAttemptByEquality (on 10000000 elections)
   345567936.33 (  161.72) - CommunismBot404                         
   318364543.33 ( -197.86) - ExtremistBot                            
The tournament took 15170.484259763 seconds, or 252.84140432938332 minutes.

I also ran a second 10m tournament, confirming ExpectantBot's lead.

Leaderboard - 10000000 elections:
   383388921.83 (  661.65) - ExpectantBot                            
   383175701.83 (  658.83) - Monte Carlo 46                          
   383164037.33 (  658.68) - LearnBot                                
   383162018.33 (  658.65) - ExpectorBot                             
   382292706.83 (  647.16) - CircumspectBot                          
   381960530.83 (  642.77) - LockBot                                 
   381786899.33 (  640.47) - PersonalFavoriteBot644                  
   381278314.83 (  633.75) - BasicBot                                
   381030871.83 (  630.48) - StrategicBot372                         
   380220471.33 (  619.77) - BestViableCandidate (1419177 from ratio, with 711341 tie-breakers of 10000000 total runs)
   380089578.33 (  618.04) - Priam                                   
   379714345.33 (  613.08) - Kelly's Favorite                        
   379548799.83 (  610.89) - Optimist                                
   379289709.83 (  607.46) - SometimesSecondBestBot                  
   377082526.83 (  578.29) - ABotDoNotForget                         
   376886555.33 (  575.70) - NoThirdPartyBot                         
   376473476.33 (  570.24) - NoClueBot                               
   368124262.83 (  459.88) - HateBot469                              
   355642629.83 (  294.89) - Follower                                
   352691241.83 (  255.88) - HipBot                                  
   345806934.83 (  164.88) - CommunismBot152                         
   345717541.33 (  163.70) - SmashAttemptByEquality (on 10000000 elections)
   345687786.83 (  163.30) - RandomBot484                            
   318549040.83 ( -195.42) - ExtremistBot                            
The tournament took 17115.327209018 seconds, or 285.25545348363335 minutes.
\$\endgroup\$
  • \$\begingroup\$ o.O wow, mine did so poorly! \$\endgroup\$ – Ismael Miguel May 28 '15 at 10:46
  • \$\begingroup\$ According to what I've seen in the code, the 2nd parameter is the number of votes remaining. And the first one is an Array containing a count of all the votes. Am I correct? \$\endgroup\$ – Ismael Miguel May 28 '15 at 11:04
  • 1
    \$\begingroup\$ @IsmaelMiguel Yes. \$\endgroup\$ – PhiNotPi May 28 '15 at 11:08
  • 1
    \$\begingroup\$ The second. They are the partial results of the election, which are the votes made by the people ahead of you in the shuffled order. \$\endgroup\$ – PhiNotPi May 28 '15 at 11:10
  • 2
    \$\begingroup\$ You may also want to look at what happens when you give the voters a bunch of clones. At a brief glance, sometimesSecondBestBot, NoThirdPartyBot and optimist all seem to benefit from larger voting pools.(As do extremistBot and, in its own way, communismBot but that's less important) \$\endgroup\$ – Saidoro May 29 '15 at 1:19

20 Answers 20

10
\$\begingroup\$

NoThirdPartyBot

This bot tries to guess which candidate will be third, and votes the candidate he likes best of the two front runners.

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class NoThirdPartyBot implements Player {

    public NoThirdPartyBot(int e) {
    }


    @Override
    public String getName() {
        return "NoThirdPartyBot";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        List<Integer> order = order(totalPayoffs);

        if (payoffs[order.get(0)] > payoffs[order.get(1)]) {
            return order.get(0);
        } else {
            return order.get(1);
        }
    }

    static List<Integer> order(int[] array) {
        List<Integer> indexes = Arrays.asList(0, 1, 2);
        Collections.sort(indexes, (i1, i2) -> array[i2] - array[i1]);
        return indexes;
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {
    }
}

CircumspectBot

This bot votes for his favorite that hasn't been mathematically eliminated.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;


public class CircumspectBot implements Player {

    public CircumspectBot(int elections) {
    }

    @Override
    public String getName() {
        return "CircumspectBot";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        List<Integer> indexes = new ArrayList<>();
        int topVote = Arrays.stream(voteCounts).max().getAsInt();
        for (int index = 0; index < 3; index++) {
            if (voteCounts[index] + votersRemaining + 1 >= topVote) {
                indexes.add(index);
            }
        }
        Collections.sort(indexes, (i1, i2) -> payoffs[i2] - payoffs[i1]);

        return indexes.get(0);
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }

}
\$\endgroup\$
  • 4
    \$\begingroup\$ I'd wager Circumspect Bot is strictly better than Personal Favorite Bot. Nice. \$\endgroup\$ – isaacg May 28 '15 at 6:24
10
\$\begingroup\$

ExpectantBot

This bot computes the expected value of each voting option assuming that all voters afterwards will vote randomly.

import java.util.Arrays;

public class ExpectantBot implements Player {

    public ExpectantBot(int elections) {
    }

    @Override
    public String getName() {
        return "ExpectantBot";
    }

    static double choose(int x, int y) {
        if (y < 0 || y > x) return 0;
        if (y > x/2) {
            // choose(n,k) == choose(n,n-k), 
            // so this could save a little effort
            y = x - y;
        }

        double denominator = 1.0, numerator = 1.0;
        for (int i = 1; i <= y; i++) {
            denominator *= i;
            numerator *= (x + 1 - i);
        }
        return numerator / denominator;
    }

    double expectedPayout(int[] voteCounts, int[] payoffs, int votersRemaining) {
        double total = 0.0;
        for (int firstPartyVoters = 0; firstPartyVoters <= votersRemaining; firstPartyVoters++) {
            for (int secondPartyVoters = 0; secondPartyVoters <= votersRemaining - firstPartyVoters; secondPartyVoters++) {
                int thirdPartyVoters = votersRemaining - firstPartyVoters - secondPartyVoters;

                int [] newVoteCounts = voteCounts.clone();
                newVoteCounts[0] += firstPartyVoters;
                newVoteCounts[1] += secondPartyVoters;
                newVoteCounts[2] += thirdPartyVoters;
                int highest = Arrays.stream(newVoteCounts).max().getAsInt();
                int payoff = 0;
                int winCount = 0;
                for (int index = 0; index < 3; index++) {
                    if (newVoteCounts[index] == highest) {
                        payoff += payoffs[index];
                        winCount++;
                    }
                }
                double v = (double)payoff / (double) winCount;
                double value = choose(votersRemaining, firstPartyVoters)*choose(votersRemaining - firstPartyVoters, secondPartyVoters)*v*Math.pow(1/3.0, votersRemaining);
                total += value;
            }
        }
        return total;
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {

        int bestVote = 0;
        double bestScore = 0.0;
        for (int vote = 0; vote < 3; vote++) {      
            voteCounts[vote]++;
            double score = expectedPayout(voteCounts, payoffs, votersRemaining);
            if (score > bestScore) {
                bestVote = vote;
                bestScore = score;
            }
            voteCounts[vote]--;
        }
        return bestVote;

    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {   
    }

}
\$\endgroup\$
  • \$\begingroup\$ Without heavy metagaming from the other opponents, I'd be surprised if anything beats this guy. \$\endgroup\$ – DoctorHeckle Jun 1 '15 at 14:06
  • \$\begingroup\$ @DoctorHeckle, I had hopes for StatBot, but I think you are right. \$\endgroup\$ – Winston Ewert Jun 2 '15 at 3:22
9
\$\begingroup\$

HipBot

HipBot doesn't care about payouts. Money is just a sedative that distracts from true art.

HipBot wants to vote for someone real, not just some corporate shill. He also wants to wear their campaign shirt after their (presumably) humiliating defeat, so he feels superior whenever the winner does something wrong.

Therefore, HipBot votes for the person with the lowest votes or, if there's a tie, whoever's got the better payout. Eating organic-only isn't free.

public class HipBot implements Player{

    public HipBot(int rounds){ /*Rounds are a social construct*/ }

    public String getName(){ return "HipBot"; }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs){

        int coolest = 0;
        int lowest = 100000000;
        int gains = 0;

        for( int count = 0; count < voteCounts.length; count++ ){

            if( voteCounts[count] < lowest || (voteCounts[count] == lowest && payoffs[count] > gains) ){

                lowest = voteCounts[count];
                coolest = count;
                gains = payoffs[count];

            }

        }

        return coolest;

    }

    public void receiveResults(int[] voteCounts, double result){ /*The past is dead*/ }

}

HipBot is also untested, so let me know if there's anything going on.

EDIT: added in more competitive tiebreaking, pithy comments.

\$\endgroup\$
  • \$\begingroup\$ works for me, although his pity for the looser doesn't do much for his score :) \$\endgroup\$ – euanjt May 28 '15 at 18:32
  • 5
    \$\begingroup\$ He's won in his mind, and for him, that's all that matters :D \$\endgroup\$ – DoctorHeckle May 28 '15 at 18:41
8
\$\begingroup\$

PersonalFavoriteBot

This bot simply votes for the candidate with the highest personal payoff, ignoring everything else. One of the main points of this challenge is to demonstrate how this is not the optimal strategy.

import java.lang.Math;
import java.util.Random;
/**
 * This bot picks the candidate with the highest personal payoff, ignoring everyone else's actions.
 * 
 * @author PhiNotPi 
 * @version 5/27/15
 */
public class PersonalFavoriteBot implements Player
{
    Random rnd;
    String name;
    /**
     * Constructor for objects of class PersonalFavoriteBot
     */
    public PersonalFavoriteBot(int e)
    {
       rnd = new Random(); 
       name = "PersonalFavoriteBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        //return rnd.nextInt(3);
        int maxloc = 0;
        for(int i = 1; i< 3; i++)
        {
            if(payoffs[i] > payoffs[maxloc])
            {
                maxloc = i;
            }
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}

RandomBot

This bot votes randomly. Regardless of the number of elections carried out (as long as it's reasonably high, like over 100), this contestant's normalized score fluctuates between -2 and 2.

import java.lang.Math;
import java.util.Random;
/**
 * This bot votes for a random candidate.
 * 
 * @author PhiNotPi 
 * @version 5/27/15
 */
public class RandomBot implements Player
{
    Random rnd;
    String name;
    /**
     * Constructor for objects of class RandomBot
     */
    public RandomBot(int e)
    {
       rnd = new Random(); 
       name = "RandomBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        return rnd.nextInt(3);
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}
\$\endgroup\$
7
\$\begingroup\$

Follower

Follower wants to fit in. It thinks the best way to accomplish that is by voting the same way as everyone else, or at least with the plurality so far. It'll break ties towards its own preference, to show a little independence. But not too much.

public class Follower implements Player
{
    public Follower(int e) { }

    public String getName()
    {
        return "Follower";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int mostPopular = 0;
        int mostVotes = voteCounts[0];
        for (int i = 1; i < voteCounts.length; i++) {
            int votes = voteCounts[i];
            if (votes > mostVotes || (votes == mostVotes && payoffs[i] > payoffs[mostPopular])) {
                mostPopular = i;
                mostVotes = votes;
            }
        }
        return mostPopular;

    }

    public void receiveResults(int[] voteCounts, double result) { }
}

Note: I haven't tested this, so let me know if there are any errors.

\$\endgroup\$
  • \$\begingroup\$ It seems to work. \$\endgroup\$ – PhiNotPi May 27 '15 at 23:07
4
\$\begingroup\$

Monte Carlo

This simulates a large amount of random elections. It then chooses the choice that maximizes it's own profits.

import java.util.ArrayList;
import java.util.List;

public class MonteCarlo implements Player{

    private static long runs = 0;
    private static long elections = 0;

    public MonteCarlo(int e) {
        elections = e;
    }

    @Override
    public String getName() {
        return "Monte Carlo (difficulty " + (runs / elections) + ")";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs, int[] totalPayoffs) {
        elections++;
        double[] predictedPayoffs = new double[3];
        long startTime = System.nanoTime();
        while (System.nanoTime() - startTime <= 200_000){ //Let's give us 200 micro-seconds.
            runs++;
            int[] simulatedVoteCounts = voteCounts.clone();
            for (int j = 0; j < votersRemaining; j++){
                simulatedVoteCounts[((int) Math.floor(Math.random() * 3))]++;
            }
            for (int j = 0; j < 3; j++) {
                simulatedVoteCounts[j]++;
                List<Integer> winners = new ArrayList<>();
                winners.add(0);
                for (int k = 1; k < 3; k++) {
                    if (simulatedVoteCounts[k] > simulatedVoteCounts[winners.get(0)]) {
                        winners.clear();
                        winners.add(k);
                    } else if (simulatedVoteCounts[k] == simulatedVoteCounts[winners.get(0)]) {
                        winners.add(k);
                    }
                }
                for (int winner : winners) {
                    predictedPayoffs[j] += payoffs[winner] / winners.size();
                }
                simulatedVoteCounts[j]--;
            }
        }
        int best = 0;
        for (int i = 1; i < 3; i++){
            if (predictedPayoffs[i] > predictedPayoffs[best]){
                best = i;
            }
        }
        return best;
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {

    }
}
\$\endgroup\$
4
\$\begingroup\$

StatBot

StatBot is based on ExpectantBot; however, instead of assuming that each vote is equally probable it collects stats on how people vote and uses that to estimate the probability.

import java.util.Arrays;


public class StatBot implements Player {

    static private int[][][] data = new int[3][3][3];
    private int[] voteCounts;

    StatBot(int unused) {

    }

    @Override
    public String getName() {
        return "StatBot";

    }

     static double choose(int x, int y) {
            if (y < 0 || y > x) return 0;
            if (y > x/2) {
                // choose(n,k) == choose(n,n-k), 
                // so this could save a little effort
                y = x - y;
            }

            double denominator = 1.0, numerator = 1.0;
            for (int i = 1; i <= y; i++) {
                denominator *= i;
                numerator *= (x + 1 - i);
            }
            return numerator / denominator;
        }

    double expectedPayout(int[] voteCounts, int[] payoffs, int votersRemaining) {
        Integer[] indexes = {0, 1, 2};
        Arrays.sort(indexes, (i0, i1) -> voteCounts[i1] - voteCounts[i0]);
        int [] stats = data[indexes[0]][indexes[1]];
        int total_stats = Arrays.stream(stats).sum();
        double total = 0.0;
        for (int firstPartyVoters = 0; firstPartyVoters <= votersRemaining; firstPartyVoters++) {
            for (int secondPartyVoters = 0; secondPartyVoters <= votersRemaining - firstPartyVoters; secondPartyVoters++) {
                int thirdPartyVoters = votersRemaining - firstPartyVoters - secondPartyVoters;

                int [] newVoteCounts = voteCounts.clone();
                newVoteCounts[0] += firstPartyVoters;
                newVoteCounts[1] += secondPartyVoters;
                newVoteCounts[2] += thirdPartyVoters;
                int highest = 0;
                for (int h : newVoteCounts) {
                    if (h > highest) highest = h;
                }
                int payoff = 0;
                int winCount = 0;
                for (int index = 0; index < 3; index++) {
                    if (newVoteCounts[index] == highest) {
                        payoff += payoffs[index];
                        winCount++;
                    }
                }
                double v = (double)payoff / (double) winCount;
                double value = choose(votersRemaining, firstPartyVoters)*choose(votersRemaining - firstPartyVoters, secondPartyVoters)*v;
                value *= Math.pow((double)stats[0]/(double)total_stats, firstPartyVoters);
                value *= Math.pow((double)stats[1]/(double)total_stats, secondPartyVoters);
                value *= Math.pow((double)stats[2]/(double)total_stats, thirdPartyVoters);

                total += value;
            }
        }
        return total;
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {

        int bestVote = 0;
        double bestScore = 0.0;
        for (int vote = 0; vote < 3; vote++) {      
            voteCounts[vote]++;
            double score = expectedPayout(voteCounts, payoffs, votersRemaining);
            if (score > bestScore) {
                bestVote = vote;
                bestScore = score;
            }
            voteCounts[vote]--;
        }
        voteCounts[bestVote]++;
        this.voteCounts = voteCounts;

        return bestVote;

    }

    @Override
    public void receiveResults(int[] endVoteCounts, double result) {
        Integer[] indexes = {0, 1, 2};
        Arrays.sort(indexes, (i0, i1) -> voteCounts[i1] - voteCounts[i0]);
        for(int i = 0; i < 3; i++){
            data[indexes[0]][indexes[1]][i] += endVoteCounts[i] - voteCounts[i];
        }
    }
}
\$\endgroup\$
4
\$\begingroup\$

Best Viable Candidate

Pretty heavily revised version of my original submission. This one still eliminates any candidates that cannot win given the remaining votes to be cast, but then uses a strategy that tries to optimize the relative payoff rather than the absolute one. The first test is to take the ratio of my personal payoff to the overall payoff for each candidate, looking for the best value there. I then look for other ratios that are very close to the best and if there is one that has a lower overall payoff than the very best I pick that one instead. Hopefully this will tend to depress the payout of the other players while keeping mine reasonably high.

This bot does almost as well as the original on in my own testing, but not quite. We'll have to see how it does against the full field.

 /**
  * This bot picks the candidate with the highest relative payoff out of those
  * candidates who are not already mathematically eliminated.
  *
  * @author Ralph Marshall
  * @version 5/28/2015
  */

import java.util.List;
import java.util.ArrayList;


public class BestViableCandidate implements Player
{
    private static int NUM_CANDIDATES = 3;
    private int relativeCount = 0;
    private int relativeCountLowerTotal = 0;
    private int totalRuns;

    public BestViableCandidate(int r) {
        totalRuns = r;
    }

    public String getName() {
        return "BestViableCandidate (" + relativeCount + " from ratio, with " + relativeCountLowerTotal + " tie-breakers of " + totalRuns + " total runs)";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {

        int i, maxVoteSoFar = 0;

        // First we figure out the maximum possible number of votes each candidate would get
        // if every remaining bot voted for it
        int [] maxPossibleVotes = new int[NUM_CANDIDATES];
        for (i = 0; i < NUM_CANDIDATES; i++) {

            // The voters remaining does not include me, so we need to add one to it
            maxPossibleVotes[i] = voteCounts[i] + votersRemaining + 1;

            if (voteCounts[i] > maxVoteSoFar) {
                maxVoteSoFar = voteCounts[i];
            }
        }

        // Then we throw out anybody who cannot win even if they did get all remaining votes
        List<Integer> viableCandidates = new ArrayList<Integer>();
        for (i = 0; i < NUM_CANDIDATES; i++) {
            if (maxPossibleVotes[i] >= maxVoteSoFar) {
                viableCandidates.add(Integer.valueOf(i));
            }
        }

        // And of the remaining candidates we pick the one that has the personal highest payoff
        // relative to the payoff to the rest of the voters
        int maxCandidate = -1;
        double maxRelativePayoff = -1;
        int maxPayoff = -1;
        int minTotalPayoff = Integer.MAX_VALUE;

        int originalMaxCandidate = -1;
        double originalMaxPayoff = -1;

        double DELTA = 0.01;

        double tiebreakerCandidate = -1;

        for (Integer candidateIndex : viableCandidates) {
            double relativePayoff = (double) payoffs[candidateIndex] / (double) totalPayoffs[candidateIndex];
            if (maxRelativePayoff < 0 || relativePayoff - DELTA > maxRelativePayoff) {
                maxRelativePayoff = relativePayoff;
                maxCandidate = candidateIndex;

                maxPayoff = payoffs[candidateIndex];
                minTotalPayoff = totalPayoffs[candidateIndex];

            } else if (Math.abs(relativePayoff - maxRelativePayoff) < DELTA) {
                if (totalPayoffs[candidateIndex] < minTotalPayoff) {
                    tiebreakerCandidate = candidateIndex;

                    maxRelativePayoff = relativePayoff;
                    maxCandidate = candidateIndex;

                    maxPayoff = payoffs[candidateIndex];
                    minTotalPayoff = totalPayoffs[candidateIndex];

                }
            }

            if (payoffs[candidateIndex] > originalMaxPayoff) {
                originalMaxPayoff = payoffs[candidateIndex];
                originalMaxCandidate = candidateIndex;
            }
        }

        if (tiebreakerCandidate == maxCandidate) {
            relativeCountLowerTotal++;
        }

        if (originalMaxCandidate != maxCandidate) {
            /*                System.out.printf("%nSelecting candidate %d with relative payoff %f (%d/%d) instead of %d with relative payoff %f (%d/%d)%n",
                              maxCandidate, (double) payoffs[maxCandidate]/(double)totalPayoffs[maxCandidate], payoffs[maxCandidate], totalPayoffs[maxCandidate],
                              originalMaxCandidate, (double) payoffs[originalMaxCandidate]/(double)totalPayoffs[originalMaxCandidate], payoffs[originalMaxCandidate], totalPayoffs[originalMaxCandidate]);
            */
            relativeCount++;
        }

        return maxCandidate;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Isn't this the same as CircumspectBot? \$\endgroup\$ – TheNumberOne May 29 '15 at 1:06
  • \$\begingroup\$ Yes, it turns out it is; I made a comment to that effect up in the main question. When I started coding it up I didn't realize exactly how that one worked. Since CircumspectBot was written first it should clearly get the credit for the idea. \$\endgroup\$ – Ralph Marshall May 29 '15 at 2:38
  • \$\begingroup\$ I think you are missing the end of your class. \$\endgroup\$ – Winston Ewert May 30 '15 at 1:39
  • \$\begingroup\$ Thanks. I lost the last brace; there wasn't any other code after what was there. \$\endgroup\$ – Ralph Marshall May 30 '15 at 20:24
3
\$\begingroup\$

Optimist

The Optimist is very optimistic and assumes that half of the remaining voters will vote for the candidate that gives it the best payoff.

import java.lang.Integer;
import java.lang.String;
import java.util.Arrays;
import java.util.Comparator;

public class Optimist implements Player
{
    public Optimist(int _) { }
    public String getName() { return "Optimist"; }
    public int getVote(int[] curVotes, int rem, final int[] payoffs, int[] _)
    {
        Integer[] opt = new Integer[] { 0, 1, 2 };
        Arrays.sort(opt, new Comparator<Integer>() { public int compare(Integer i1, Integer i2) { return payoffs[i1] > payoffs[i2] ? -1 : payoffs[i1] == payoffs[i2] ? 0 : 1; } });
        int a = curVotes[opt[0]], b = curVotes[opt[1]], c = curVotes[opt[2]];
        double rest = (double)rem / 4;
        if (b <= a + rest && c <= a + rest)
            return opt[0];
        else if (c <= b)
            return opt[1];
        else
            return opt[0];
    }
    public void receiveResults(int[] _, double __) { }
}
\$\endgroup\$
3
\$\begingroup\$

ABotDoNotForget

His goal is simple : determining the overall tendencies using the total payoffs and counting the number of time the lower/medium/higher ones won. He will then vote for the one that is most likely to win.

import java.util.ArrayList;

public class ABotDoNotForget implements Player
{
    private int nbElec;
    private int countElec=0;
    private int[] currPayoffs=new int[3];
    private int[] lmh=new int[3];
    private int[] wins=new int[3];

    public ABotDoNotForget(int nbElec)
    {
        this.nbElec=nbElec;
    }

    public String getName() {return "ABotDoNotForget";}

    public int getVote(int[] voteCounts, 
                        int votersRemaining, 
                        int[] payoffs,
                        int[] totalPayoffs) 
    {
        countElec++;
        System.arraycopy(totalPayoffs, 0, currPayoffs, 0, totalPayoffs.length);

        if(countElec<=nbElec/20&&countElec<=20)
        {
            int best=0;
            for(int i=1;i<payoffs.length;i++)
                if(payoffs[i]>=payoffs[best])
                    best=i;
            return best;
        }

        for(int i =1;i<totalPayoffs.length;i++)
        {
            if(totalPayoffs[i]<totalPayoffs[i-1])
            {
                int tmp= totalPayoffs[i];
                totalPayoffs[i]=totalPayoffs[i-1];
                totalPayoffs[i-1]=tmp;
                if(i==2&&totalPayoffs[i-1]<totalPayoffs[i-2]){
                    tmp= totalPayoffs[i-1];
                    totalPayoffs[i-1]=totalPayoffs[i-2];
                    totalPayoffs[i-2]=tmp;
                }
            }
        }
        lmhDist(currPayoffs,totalPayoffs);
        int best=0;
        for(int i=1;i<wins.length;i++)
            if(wins[i]>=wins[best]){
                best=i;
            }
        int ownH=0;
        for(int i=1;i<payoffs.length;i++)
            if(payoffs[i]>=payoffs[ownH])
                ownH=i;
        int ownM=0;
        for(int i=1;i<payoffs.length;i++)
            if(payoffs[i]>=payoffs[ownM]&&i!=ownH)
                ownM=i;

        int persBest=(voteCounts[ownH]-voteCounts[ownM]+(votersRemaining/3)>=0
                &&voteCounts[ownH]-voteCounts[best]<(votersRemaining/3))?ownH:ownM;

        return persBest;

    }

    public void receiveResults(int[] voteCounts, double result) 
    {
        int best=0,bestV=voteCounts[best];
        for(int i=1;i<voteCounts.length;i++)
            if(voteCounts[i]>=bestV){
                best=i;
                bestV=voteCounts[i];
            }
        wins[lmh[best]]++;

    }

    private void lmhDist(int[] a,int[] s)
    {
        ArrayList<Integer> al = new ArrayList<Integer>();
        al.add(a[0]);al.add(a[1]);al.add(a[2]);
        lmh[0]=al.indexOf(s[0]);
        lmh[1]=al.indexOf(s[1]);
        lmh[2]=al.indexOf(s[2]);

    }
}

Edit :

Some change done in the decision algorythm, now takes into account his own best payoff. Should now be able to vote better when the current distribution was making him vote for his own Lower when others where voting for their Higher payoffs.

\$\endgroup\$
3
\$\begingroup\$

Priam

Priam hates recursion. He estimates the probability of each remaining bot based on the total payoffs and then calculates the best way of maximising his payoff.

public class Priam implements Player {
    private static double[] smallFactorials = {1,1,2,6,24,120,720,5040,40320,362880,3628800,39916800,479001600,6227020800.,87178291200.,1307674368000.,20922789888000.,355687428096000.,6402373705728000.,121645100408832000.,2432902008176640000.};
    @Override
    public String getName() {
        return "Priam";
    }

    @Override
    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
            int[] totalPayoffs) {
        int totalPayoff = totalPayoffs[0] + totalPayoffs[1] + totalPayoffs[2];
        double p0 = ((double)totalPayoffs[0])/totalPayoff;
        double p1= ((double) totalPayoffs[1])/totalPayoff;
        double p2 = ((double)totalPayoffs[2])/totalPayoff;
        double[] expectedPayoffs = {0,0,0};
        for(int myChoice=0;myChoice<3;myChoice++)
        {
            for(int x0 = 0; x0 <= votersRemaining; x0++)
            {
                for(int x1 = 0; x1 <= (votersRemaining-x0); x1++)
                {
                    int x2 = votersRemaining - (x1 + x0);
                    double probability =
                            Math.pow(p0, x0)
                            * Math.pow(p1, x1)
                            * Math.pow(p2, x2)
                            * Choose(votersRemaining, x0)
                            * Choose(votersRemaining-x0, x1);
                    int votes0 = voteCounts[0];
                    int votes1 = voteCounts[1];
                    int votes2 = voteCounts[2];
                    if(myChoice == 0)
                    {
                        votes0++;
                    }
                    else if(myChoice==1)
                    {
                        votes1++;
                    }
                    else
                    {
                        votes2++;
                    }

                    votes0+=x0;
                    votes1+=x1;
                    votes2+=x2;
                    if(votes0>votes1 && votes0>votes2)
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[0];
                    }
                    else if(votes1>votes2)
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[1];
                    }
                    else
                    {
                        expectedPayoffs[myChoice]+=probability*payoffs[2];
                    }
                }
            }
        }
        if(expectedPayoffs[0]>expectedPayoffs[1] && expectedPayoffs[0]>expectedPayoffs[2])
        {
            return 0;
        }
        else if(expectedPayoffs[1]>expectedPayoffs[2])
        {
            return 1;
        }
        else
        {
            return 2;
        }
    }

    private long Choose(int source, int team) {
        return Factorial(source)/(Factorial(team)*Factorial(source-team));
    }

    private long Factorial(int n) {
        if(n<=20)
        {
            return (long)smallFactorials[n];
        }
        double d=(double)n;
        double part1 = Math.sqrt(2*Math.PI*d);
        double part2 = Math.pow(d/Math.E, d);
        return (long)Math.ceil(part1 * part2);
    }

    @Override
    public void receiveResults(int[] voteCounts, double result) {


    }
    public Priam(int i)
    {

    }
}

Much much faster than Odysseus as there is no recursion (runs in time O(n^2)) and can do one million elections in about 15 seconds.

\$\endgroup\$
  • \$\begingroup\$ "I think this is the first bot to use the total payoffs parameter for its own benefit :)" Look at my bot (ABotDoNotForget), he's already using it, sorry :D \$\endgroup\$ – Katenkyo May 29 '15 at 10:43
  • \$\begingroup\$ Very similiar to my latest bot, ExpectantBot, except that you use totalPayoffs to predict probability and I assume every vote is equally probable. I'm eager to see which strategy works best. \$\endgroup\$ – Winston Ewert May 29 '15 at 13:05
  • \$\begingroup\$ @WinstonEwert I think yours does, you've won the last three tests I did. \$\endgroup\$ – euanjt May 29 '15 at 13:06
  • \$\begingroup\$ I've only just noticed the similarity- I was trying to make a version of Odysseus which didn't take 10 hours to run 100 elections, so I used for loops \$\endgroup\$ – euanjt May 29 '15 at 13:08
  • \$\begingroup\$ To be honest, I was inspired to take my approach by Odysseus. \$\endgroup\$ – Winston Ewert May 29 '15 at 13:35
2
\$\begingroup\$

NoClueBot

NoClue does not actually know Java or math very well, so he has no idea if this weighting-ratio-thingy will help him win. But he's trying.

import java.lang.Math;
import java.util.*;
/**
 * Created by Admin on 5/27/2015.
 */
public class NoClueBot implements Player {

    public NoClueBot(int e) { }

    public String getName() {
        return "NoClueBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {
        double x = 0;
        int y = 0;
        for (int i=0; i<3; i++) {
            double t = (double) voteCounts[i] * ((double) payoffs[i]/(double) totalPayoffs[i]);
            if (x<t) {
                x = t;
                y = i; 
            }
        }
        return y;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}


SomeClueBot

SomeClueBot has been decommissioned. actually uses logic! used to use logic, which turned out to be inefficient, so instead he became mindful of the total payoff, not his own. uses logic again! But he doesn't do well with all these followers and optimists, and even people who don't care! :)


SometimesSecondBestBot

Basically PersonalFavouriteBot, improved (in theory).

import java.lang.Math;
/**
 * Created by Admin on 5/27/2015.
 */
public class SometimesSecondBestBot implements Player {
    public SometimesSecondBestBot(int e) { }

    public String getName() {
        return "SometimesSecondBestBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs) {
        int m = 0;
        int n = 0;
        for(int i = 1; i< 3; i++) {
            if(payoffs[i] > payoffs[m]) { n = m; m = i; }
        }
        return (voteCounts[n]>voteCounts[m]&&totalPayoffs[n]>totalPayoffs[m])||(voteCounts[m]+votersRemaining<voteCounts[n])||voteCounts[m]+votersRemaining<voteCounts[Math.min(3-n-m, 2)] ? n : m;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ It looks like you calculate a number that is the largest of three weights and than take that value mod 3 to pick the best candidate. Is that correct and if so isn't it basically a random number? I understand that you're calling this "math is hard Barbie", so I'm not sure I have the concept. \$\endgroup\$ – Ralph Marshall May 27 '15 at 23:55
  • \$\begingroup\$ @RalphMarshall Yes, it's basically random. However, I totally did not intend to do that, wasn't paying attention, haha. Fixed it now. \$\endgroup\$ – Kade May 28 '15 at 0:00
  • \$\begingroup\$ @PhiNotPhi I think I've fixed it going out of range now. And yeah, I'm not surprised. \$\endgroup\$ – Kade May 28 '15 at 0:39
  • \$\begingroup\$ My god this is bad.. in my defense work was extremely mentally draining today. \$\endgroup\$ – Kade May 28 '15 at 0:50
2
\$\begingroup\$

The extremist

Always vote for the candidate with the lowest payoff

public class ExtremistBot implements Player
{
    public ExtremistBot(int e){}

    public void receiveResults(int[] voteCounts, double result){}

    public String getName(){
        return "ExtremistBot";
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int min = 0;
        for(int i = 1; i<payoffs.length; i++){
            if(payoffs[i] <payoffs[min]){
                min = i;
            }
        }
        return min;
    }
}
\$\endgroup\$
2
\$\begingroup\$

SmashAttemptByEquality

The goal is to equalize all the candidats, then SMASH! all the other bots on the last round.
This is a destructive algorith that tries to bug out all the others, to claim the win.

public class SmashAttemptByEquality implements Player {
    static private int elections;

    public SmashAttemptByEquality(int e) { 
        this.elections = e;
    }

    public String getName() {
        return "SmashAttemptByEquality (on " + String.valueOf(this.elections) + " elections)";
    }

    public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs, int[] totalPayoffs) {

        //if there are no votes or it is a tie
        if(voteCounts.length == 0 || (voteCounts[0] == voteCounts[1] && voteCounts[1] == voteCounts[2]))
        {
            //let the system handle the (distributed?) randomness
            return 3;
        }

        //we want to win, so, lets not mess when there are no voters left
        if( votersRemaining > 0 )
        {
            //lets bring some equality!
            if( voteCounts[0] >= voteCounts[1] )
            {
                if(voteCounts[0] > voteCounts[2])
                {
                    return 2;
                }
                else
                {
                    return 0;
                }
            }
            else if( voteCounts[1] >= voteCounts[2] )
            {
                if(voteCounts[1] > voteCounts[0])
                {
                    return 0;
                }
                else
                {
                    return 1;
                }
            }
            else
            {
                return 0;
            }
        }
        else
        {
            //just play for the winner!
            if( voteCounts[0] >= voteCounts[1] )
            {
                if(voteCounts[0] > voteCounts[2])
                {
                    return 0;
                }
                else
                {
                    return 2;
                }
            }
            else if( voteCounts[1] >= voteCounts[2] )
            {
                if(voteCounts[1] > voteCounts[0])
                {
                    return 1;
                }
                else
                {
                    return 0;
                }
            }
            else
            {
                return 0;
            }
        }
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

Notice that this is untested!

\$\endgroup\$
2
\$\begingroup\$

Basic Bot

Basic Bot just votes for the candidates that isn't eliminated and has the largest maximum payoff from those candidates.

public class BasicBot implements Player {
    public BasicBot(int e) { }
    public String getName()
    {
        return "BasicBot";
    }
    public static int getMax(int[] inputArray){ 
    int maxValue = inputArray[0]; 
    for(int i=1;i < inputArray.length;i++){ 
      if(inputArray[i] > maxValue){ 
         maxValue = inputArray[i]; 
      } 
    } 
    return maxValue; 
   }
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        // Check for Eliminated Candidates
        int eliminated0 = 0;
        int eliminated1 = 0;
        int eliminated2 = 0;
        if( ((voteCounts[0] + votersRemaining) < voteCounts[1]) || ((voteCounts[0] + votersRemaining) < voteCounts[2]))
        {
            eliminated0 = 1;
        }
        if( ((voteCounts[1] + votersRemaining) < voteCounts[0]) || ((voteCounts[1] + votersRemaining) < voteCounts[2]))
        {
            eliminated1 = 1;
        }
        if( ((voteCounts[2] + votersRemaining) < voteCounts[0]) || ((voteCounts[2] + votersRemaining) < voteCounts[1]))
        {
            eliminated2 = 1;
        }
        // Choose the Candidates that is not elimated with the largest payoff
        if ((payoffs[0] == getMax(payoffs)) && eliminated0 == 0)
            return 0
        else if ((payoffs[1] == getMax(payoffs)) && eliminated1 == 0)
            return 1
        else
            return 2

    }

    public void receiveResults(int[] voteCounts, double result)
    {
    }

}
\$\endgroup\$
2
\$\begingroup\$

Kelly's Favorite

I started with CircumspectBot, but not much is left. Makes a sort of boring guess at the probability distribution of the remaining votes, and then makes the choice that maximizes its own log-utility (Kelly Criterion). Not the speediest, but within the ball park of some of the others. Also, it's fairly competitive with the field (as it stood when I started working on this, and downloaded the other bots).

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) {

    }

}

Also available at https://gist.github.com/jkominek/dae0b3158dcd253e09e5 in case that's simpler.

\$\endgroup\$
2
\$\begingroup\$

CommunismBot

CommunismBot thinks we should all just get along and pick the candidate who is best for everyone.

public class CommunismBot implements Player
{
    Random rnd;
    String name;
    public CommunismBot(int e) {
        rnd = new Random(); 
        name = "CommunismBot" + rnd.nextInt(1000);
    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int maxloc = 0;
        for(int i = 1; i< 3; i++)
        {
            if(totalPayoffs[i] > totalPayoffs[maxloc])
            {
                maxloc = i;
            }
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

Hatebot

Hatebot always picks the best candidate. Unless they're a dirty-stinking-party 1. Those guys are awful.

import java.util.Random;


public class HateBot implements Player
{
    Random rnd;
    String name;
    public HateBot(int e) {
        rnd = new Random(); 
        name = "HateBot" + rnd.nextInt(1000); }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        if(payoffs[0]>payoffs[2])
            return 0;
        else
            return 2;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}

StrategicBot

StrategicBot votes for the best candidate provided that they're within one standard deviation of the next best candidate, given the number of voters remaining.

import java.util.Random;

public class StrategicBot implements Player
{
    Random rnd;
    String name;
    public StrategicBot(int e) {
        rnd = new Random(); 
        name = "StrategicBot" + rnd.nextInt(1000);

    }

    public String getName()
    {
        return name;
    }

    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        double margin = 9.0*votersRemaining/9;
        int maxloc = 0;
        boolean noLead=false;
        for(int i = 1; i< 3; i++)
        {
            for(int j = 1; j < 3; j++)
            {
                if(payoffs[j] + margin > payoffs[i])
                    noLead=true;
            }
            if(payoffs[i] > payoffs[maxloc] && noLead)
            {
                maxloc = i;
            }
            noLead=false;
        }
        return maxloc;
    }

    public void receiveResults(int[] voteCounts, double result) { }
}
\$\endgroup\$
2
\$\begingroup\$

ExpectorBot

Tries to predict how all other Bots will vote by calculating average Payout for the others. Default votes for best payoff, but will vote for second best, if it has more expected votes than the best, a better than average payout for me and the worst-payout has a chance of winning this thing.

import java.util.Arrays;

public class ExpectorBot implements Player
{
    class Votee
    {
        int index;
        int payoff;
        float avgPayoff;
        float expectedVotes;
    }

    public ExpectorBot( final int e )
    {

    }

    @Override
    public String getName()
    {
        return "ExpectorBot";
    }

    @Override
    public int getVote( final int[] voteCounts, final int votersRemaining, final int[] payoffs, final int[] totalPayoffs )
    {
        final int otherVoters = Arrays.stream( voteCounts ).sum() + votersRemaining;
        final Votee[] v = createVotees( voteCounts, otherVoters, votersRemaining, payoffs, totalPayoffs );

        final Votee best = v[ 0 ]; // Most Payoff
        final Votee second = v[ 1 ];
        final Votee worst = v[ 2 ];

        int voteFor = best.index;

        if( ( second.expectedVotes >= best.expectedVotes + 1 ) // Second has more votes than Best even after I vote
                && ( second.payoff >= second.avgPayoff ) // Second payoff better than average for the others
                && ( worst.expectedVotes >= best.expectedVotes + 0.5f ) ) // Worst has a chance to win
        {
            voteFor = second.index;
        }

        return voteFor;
    }

    private Votee[] createVotees( final int[] voteCounts, final int otherVoters, final int votersRemaining, final int[] payoffs, final int[] totalPayoffs )
    {
        final Votee[] v = new Votee[ 3 ];

        for( int i = 0; i < 3; ++i )
        {
            v[ i ] = new Votee();
            v[ i ].index = i;
            v[ i ].payoff = payoffs[ i ];

            // This is the average payoff for other Players from this Votee
            v[ i ].avgPayoff = (float)( totalPayoffs[ i ] - payoffs[ i ] ) / otherVoters;

            // The expected number of Votes he will get if everyone votes for biggest payoff
            v[ i ].expectedVotes = voteCounts[ i ] + ( votersRemaining * v[ i ].avgPayoff / 100.0f );
        }

        Arrays.sort( v, ( o1, o2 ) -> o2.payoff - o1.payoff );

        return v;
    }

    @Override
    public void receiveResults( final int[] voteCounts, final double result )
    {

    }
}
\$\endgroup\$
1
\$\begingroup\$

LockBot

Just a lonely philosopher, looking for his "e"...

//He thinks he's the father of democracy, but something's missing....
public class LockBot implements Player {

public LockBot(int i) {
    //One election, 10000000, what's the difference?
}

@Override
public String getName() {
    return "LockBot";
}

@Override
public int getVote(int[] voteCounts, int votersRemaining, int[] payoffs,
        int[] totalPayoffs) {

    double totalPlayers = voteCounts.length + votersRemaining;
    double totalPayoff = totalPlayers * 100;

    //adjust total payoffs to ignore my own
    for( int i = 0; i < totalPayoffs.length; i++){
        totalPayoffs[i] -= payoffs[i];
    }

    //Votes are probably proportional to payoffs
    //So lets just find the highest weight
    double[] expectedOutcome = new double[3];
    for(int i = 0; i< expectedOutcome.length; i++){
        expectedOutcome[i] = (totalPayoffs[i] / totalPayoff) * payoffs[i];
    }

    //Find the highest
    int choice = 0;
    if(expectedOutcome[1] > expectedOutcome[choice]){
        choice = 1;
    }
    if(expectedOutcome[2] > expectedOutcome[choice]){
        choice = 2;
    }




    return choice;
}

@Override
public void receiveResults(int[] voteCounts, double result) {
    // TODO Auto-generated method stub

}

}
\$\endgroup\$
0
\$\begingroup\$

WinLose

If you win, I lose! That simple. So this bot votes for the one that he likes and everyone else dislikes.

public class WinLose implements Player
{
    public WinLose(int e) { }

    public String getName()
    {
        return "WinLose";
    }
    public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
    {
        int max = 0;
        for(int i = 1; i< 3; i++)
        {
            if(10*payoffs[i]-totalPayoffs[i] > 10*payoffs[max]-totalPayoffs[max])
            {
                max = i;
            }
        }
        return max;
    }

    public void receiveResults(int[] voteCounts, double result)
    {

    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.