Um dos sistemas de votação mais comuns para eleições de vencedor único é o método de votação por pluralidade. Simplificando, o candidato com mais votos vence. A votação da pluralidade, no entanto, é matematicamente doentia e é suscetível de criar situações nas quais os eleitores são levados a votar no "menor dos dois males", em oposição ao candidato que eles realmente preferem.
Neste jogo, você escreverá um programa que tira proveito do sistema de votação da pluralidade. Ele votará em um dos três candidatos em uma eleição. Cada candidato está associado a uma certa recompensa para si mesmo, e seu objetivo é maximizar a recompensa esperada.
As recompensas são "uniformemente" distribuídas aleatoriamente, mudam a cada eleição e aumentam para 100. O candidato A pode ter a recompensa 40, o candidato B pode ter a recompensa 27 e o candidato C pode ter a recompensa 33. Cada jogador tem um conjunto diferente de recompensas.
Quando for a sua vez de votar, você terá informações incompletas. Abaixo estão listadas as informações que você terá disponível para você. Como você não sabe quais são os pagamentos individuais de outros jogadores, será seu desafio prever como eles votariam, dados os resultados da pesquisa atual.
- Os resultados parciais das eleições até agora
- O número de participantes (excluindo você) que ainda não votaram
- Seus pagamentos pessoais para cada um dos candidatos
- O total de pagamentos do grupo para cada um dos candidatos
Após a chance de cada jogador votar, o candidato com mais votos vence de acordo com a votação na pluralidade. Cada jogador recebe o número de pontos que corresponde à sua recompensa daquele candidato. Se houver empate nos votos, o número de pontos atribuídos será a média dos candidatos empatados.
Estrutura do torneio
Quando instanciado pela primeira vez, o participante será informado do número de eleições realizadas no torneio. Vou tentar executar um número extremamente grande de eleições. Então, cada eleição será realizada uma a uma.
Depois que os participantes são embaralhados, cada um recebe uma chance de votar. Eles recebem as informações limitadas listadas acima e retornam um número que significa seu voto. Depois que cada eleição termina, cada bot recebe os resultados finais da pesquisa e sua pontuação aumenta a partir dessa eleição.
O participante vitorioso será aquele com a pontuação total mais alta após a realização de um grande número de eleições. O controlador também calcula uma pontuação "normalizada" para cada competidor comparando sua pontuação com a distribuição de pontuação prevista para um bot de votação aleatória.
Detalhes da submissão
As submissões terão a forma de classes Java 8. Cada participante deve implementar a seguinte 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);
}
- Seu construtor deve usar um único
int
como parâmetro, o que representará o número de eleições que serão realizadas. - O
getName()
método retorna o nome a ser usado na tabela de classificação. Isso permite que você tenha nomes bem formatados, apenas não enlouqueça. - Os
getVote(...)
método retorna0
,1
ou2
para indicar qual candidato receberá o voto. - O
receiveResults(...)
método é principalmente para permitir a existência de estratégias mais complexas que usam dados históricos. - Você tem permissão para criar praticamente quaisquer outros métodos / variáveis de instância que deseja registrar e processar as informações fornecidas a você.
Ciclo de Torneio, Expandido
- Os participantes são instanciados
new entrantName(int numElections)
. - Para cada eleição:
- O controlador determina aleatoriamente os pagamentos de cada jogador para esta eleição. O código para isso é dado abaixo. Em seguida, embaralha os jogadores e faz com que eles comecem a votar.
- O método do participante
public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
é invocado, e o participante retorna seu voto de0
,1
ou2
para o candidato de sua escolha. - Os participantes cujo
getVote(...)
método não retornar uma votação válida receberão uma votação aleatória. - Depois que todos votam, o controlador determina os resultados da eleição pelo método da pluralidade.
- Os participantes são informados da contagem final dos votos e do seu retorno, chamando seu método
public void receiveResults(int[] voteCounts, double result)
.
- Após todas as eleições, o vencedor é aquele com a maior pontuação.
A distribuição aleatória de payoffs
A distribuição exata terá um efeito significativo na jogabilidade. Eu escolhi uma distribuição com um grande desvio padrão (cerca de 23,9235) e que é capaz de criar retornos muito altos e muito baixos. Eu verifiquei que cada um dos três payoffs tem uma distribuição idêntica.
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;
}
Mais regras
Aqui estão algumas regras mais generalizadas.
- Seu programa não deve executar / modificar / instanciar nenhuma parte do controlador ou outros participantes ou suas memórias.
- Como seu programa permanece "ativo" durante todo o torneio, não crie nenhum arquivo.
- Não interaja, ajude ou direcione outros programas participantes.
- Você pode enviar vários participantes, desde que sejam razoavelmente diferentes e desde que siga as regras acima.
- Não especifiquei um limite de tempo exato, mas agradeceria muito os tempos de execução significativamente inferiores a um segundo por chamada. Eu quero poder executar tantas eleições quanto possível.
O controlador
O controlador pode ser encontrado aqui . O programa principal é Tournament.java
. Existem também dois bots simples, que estarão competindo, intitulados RandomBot
e PersonalFavoriteBot
. Vou postar esses dois bots em uma resposta.
Entre os melhores
Parece que o ExpectantBot é o líder atual, seguido por Monte Carlo e depois pelo 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.
Aqui estão alguns torneios antigos, mas nenhum dos bots mudou de funcionalidade desde essas rodadas.
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.
Também realizei um segundo torneio de 10m, confirmando a liderança do ExpectantBot.
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.
fonte
Array
contendo uma contagem de todos os votos. Estou correcto?Respostas:
NoThirdPartyBot
Esse bot tenta adivinhar qual candidato será o terceiro e vota no candidato que ele mais gosta dos dois primeiros colocados.
CircumspectBot
Este bot vota no seu favorito que não foi matematicamente eliminado.
fonte
ExpectantBot
Este bot calcula o valor esperado de cada opção de votação, assumindo que todos os eleitores depois votarão aleatoriamente.
fonte
HipBot
O HipBot não se importa com pagamentos. O dinheiro é apenas um sedativo que distrai a verdadeira arte.
O HipBot quer votar em alguém de verdade , não apenas em algum conhecimento corporativo. Ele também quer vestir a camisa da campanha após a derrota (presumivelmente) humilhante, para se sentir superior sempre que o vencedor fizer algo errado.
Portanto, o HipBot vota na pessoa com os votos mais baixos ou, se houver empate, quem tiver o melhor pagamento. Comer apenas orgânico não é gratuito.
O HipBot também não foi testado, então deixe-me saber se há algo acontecendo.
EDIT: adicionado em comentários competitivos, expressivos.
fonte
PersonalFavoriteBot
Esse bot simplesmente vota no candidato com a maior recompensa pessoal, ignorando todo o resto. Um dos principais pontos desse desafio é demonstrar como essa não é a estratégia ideal.
RandomBot
Este bot vota aleatoriamente. Independentemente do número de eleições realizadas (contanto que seja razoavelmente alto, como mais de 100), a pontuação normalizada deste competidor varia entre -2 e 2.
fonte
Seguidor
O seguidor quer se encaixar. Ele acha que a melhor maneira de conseguir isso é votando da mesma maneira que todos os outros, ou pelo menos com a pluralidade até agora. Quebrará laços com sua própria preferência, para mostrar um pouco de independência. Mas não muito.
Nota: Eu não testei isso, então, deixe-me saber se há algum erro.
fonte
Monte Carlo
Isso simula uma grande quantidade de eleições aleatórias. Em seguida, escolhe a opção que maximiza seus próprios lucros.
fonte
StatBot
StatBot é baseado em ExpectantBot; no entanto, em vez de assumir que cada voto é igualmente provável, ele coleta estatísticas sobre como as pessoas votam e o usa para estimar a probabilidade.
fonte
Melhor candidato viável
Versão bastante revisada da minha submissão original. Este ainda elimina todos os candidatos que não podem vencer, dado os votos restantes a serem dados, mas usa uma estratégia que tenta otimizar o retorno relativo, em vez do absoluto. O primeiro teste é levar a proporção do meu pagamento pessoal para o pagamento geral de cada candidato, procurando o melhor valor lá. Em seguida, procuro outras proporções muito próximas das melhores e, se houver uma que tenha uma recompensa geral menor do que a melhor, eu escolho essa. Esperançosamente, isso tenderá a diminuir o pagamento dos outros jogadores, mantendo o meu razoavelmente alto.
Esse bot funciona quase tão bem quanto o original nos meus próprios testes, mas não exatamente. Nós teremos que ver como isso acontece em todo o campo.
fonte
CircumspectBot
?Otimista
O Optimist é muito otimista e assume que metade dos eleitores restantes votará no candidato que lhe der o melhor retorno.
fonte
ABotDoNotForget
Seu objetivo é simples: determinar as tendências gerais usando o total de pagamentos e contar o número de vezes que as baixas / médias / altas venceram. Ele votará então no que tem mais chances de ganhar.
Editar:
Algumas mudanças feitas no algoritmo de decisão agora levam em consideração seu melhor retorno. Agora ele deveria poder votar melhor quando a distribuição atual o estava fazendo votar em seu próprio Lower quando outros votavam em seus pagamentos mais altos.fonte
Priam
Priam odeia recursão. Ele estima a probabilidade de cada bot restante com base no total de pagamentos e depois calcula a melhor maneira de maximizar seu pagamento.
Muito mais rápido que Odisseu, pois não há recursão (corre no tempo O (n ^ 2)) e pode fazer um milhão de eleições em cerca de 15 segundos.
fonte
NoClueBot
NoClue, na verdade, não conhece Java ou matemática muito bem, então ele não tem idéia se essa proporção de ponderação o ajudará a vencer. Mas ele está tentando.
SomeClueBot
SomeClueBot foi encerrado.
realmente usa lógica! costumava usar a lógica, que se mostrava ineficiente, então, em vez disso, tornou-se consciente do pagamento total, não do seu. usa a lógica novamente! Mas ele não se dá bem com todos esses seguidores e otimistas, e mesmo com pessoas que não se importam! :)Às vezesSegundoBestBot
Basicamente PersonalFavouriteBot, melhorado (em teoria).
fonte
O extremista
Sempre vote no candidato com o menor retorno
fonte
SmashAttemptByEquality
O objetivo é igualar todos os candidatos, depois SMASH! todos os outros bots na última rodada.
Este é um algoritmo destrutivo que tenta resolver todos os outros, para reivindicar a vitória.
Observe que isso não foi testado !
fonte
Bot básico
O Basic Bot apenas vota nos candidatos que não são eliminados e tem o maior retorno máximo desses candidatos.
fonte
O favorito de Kelly
Comecei com o CircumspectBot, mas não resta muito. Faz uma espécie de palpite chato sobre a distribuição de probabilidade dos votos restantes e, em seguida, faz a escolha que maximiza seu próprio utilitário de log (Critério Kelly). Não é o mais rápido, mas dentro do parque de bola de alguns dos outros. Além disso, é bastante competitivo com o campo (como estava quando comecei a trabalhar nisso e baixei os outros bots).
Também disponível em https://gist.github.com/jkominek/dae0b3158dcd253e09e5 , caso seja mais simples.
fonte
CommunismBot
O CommunismBot acha que todos devemos nos dar bem e escolher o candidato que é melhor para todos.
Hatebot
O Hatebot sempre escolhe o melhor candidato. A menos que eles sejam uma festa suja e fedorenta. Esses caras são horríveis.
StrategicBot
O StrategicBot vota no melhor candidato desde que esteja dentro de um desvio padrão do próximo melhor candidato, considerando o número de eleitores restantes.
fonte
ExpectorBot
Tenta prever como todos os outros robôs votarão calculando o pagamento médio dos outros. Votos padrão para o melhor pagamento, mas votarão no segundo melhor, se houver mais votos esperados do que os melhores, um pagamento acima da média para mim e o pior pagamento tiver chance de ganhar essa coisa.
fonte
LockBot
Apenas um filósofo solitário, procurando seu "e" ...
fonte
Ganhar perder
Se você ganhar, eu perco! Que simples. Então esse bot vota no que ele gosta e todo mundo não gosta.
fonte