Uno de los sistemas de votación más comunes para las elecciones de un solo ganador es el método de votación plural. En pocas palabras, el candidato con más votos gana. Sin embargo, la votación en pluralidad es matemáticamente poco sólida y puede crear situaciones en las que los votantes se vean obligados a votar por el "menor de dos males" en lugar del candidato que realmente prefieren.
En este juego, escribirás un programa que aprovecha el sistema de votación plural. Votará por uno de los tres candidatos en una elección. Cada candidato está asociado con un cierto beneficio para usted y su objetivo es maximizar su beneficio esperado.
Los pagos se distribuyen aleatoriamente "uniformemente", cambian con cada elección y suman 100. El candidato A podría tener un pago 40, el candidato B podría tener un pago 27 y el candidato C podría tener un pago 33. Cada jugador tiene un conjunto diferente de pagos.
Cuando sea tu turno de votar, tendrás información incompleta. A continuación se enumera la información que tendrá disponible para usted. Dado que no sabe cuáles son los pagos individuales de otros jugadores, será su desafío predecir cómo votarían dados los resultados de la encuesta actual.
- Los resultados parciales de las elecciones hasta el momento
- El número de participantes (excluyéndose) que aún no han votado
- Sus pagos personales para cada uno de los candidatos.
- Los pagos totales del grupo para cada uno de los candidatos.
Después de que cada jugador haya tenido la oportunidad de votar, el candidato con más votos gana de acuerdo con la votación por pluralidad. Luego, cada jugador recibe el número de puntos que corresponde a su recompensa de ese candidato. Si hay un empate en los votos, entonces el número de puntos asignados será el promedio de los candidatos empatados.
Estructura de torneo
Cuando se instancia por primera vez, se le informará al participante el número de elecciones celebradas en el torneo. Intentaré organizar un número extremadamente grande de elecciones. Luego, cada elección se llevará a cabo una por una.
Después de barajar a los participantes, cada uno tiene un turno para votar. Se les proporciona la información limitada mencionada anteriormente y devuelven un número que indica su voto. Una vez que finaliza cada elección, cada bot recibe los resultados finales de la encuesta y su puntaje aumenta con respecto a esa elección.
El participante victorioso será el que obtenga el puntaje total más alto después de que se hayan celebrado un gran número de elecciones. El controlador también calcula un puntaje "normalizado" para cada concursante al comparar su puntaje con la distribución de puntaje prevista para un bot que vota al azar.
Detalles de envío
Las presentaciones tomarán la forma de clases Java 8. Cada participante debe implementar la siguiente interfaz:
public interface Player
{
public String getName();
public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs);
public void receiveResults(int[] voteCounts, double result);
}
- Su constructor debe tomar un solo
int
parámetro, que representará el número de elecciones que se celebrarán. - El
getName()
método devuelve el nombre que se utilizará en la tabla de clasificación. Esto le permite tener nombres bien formateados, simplemente no se vuelva loco. - Los
getVote(...)
devuelve el método0
,1
o2
para indicar qué candidato recibirá el voto. - El
receiveResults(...)
método es principalmente para permitir la existencia de estrategias más complejas que utilizan datos históricos. - Se le permite crear prácticamente cualquier otro método / variable de instancia que desee registrar y procesar la información que se le proporciona.
Ciclo de torneo ampliado
- Los participantes se instancian cada uno con
new entrantName(int numElections)
. - Para cada elección:
- El controlador determina aleatoriamente los pagos para cada jugador para esta elección. El código para esto se da a continuación. Luego, baraja a los jugadores y les hace comenzar a votar.
- El método del participante
public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
se invoca, y el participante regresa a su voto de0
,1
o2
por el candidato de su elección. - A los participantes cuyo
getVote(...)
método no devuelva un voto válido se les asignará un voto al azar. - Después de que todos hayan votado, el controlador determina los resultados de la elección por el método de la pluralidad.
- Los participantes son informados de los recuentos de votos finales y de sus pagos llamando a su método
public void receiveResults(int[] voteCounts, double result)
.
- Después de que se hayan celebrado todas las elecciones, el ganador es el que tiene el puntaje más alto.
La distribución aleatoria de los pagos
La distribución exacta tendrá un efecto significativo en el juego. Elegí una distribución con una gran desviación estándar (aproximadamente 23.9235) y que es capaz de crear pagos muy altos y muy bajos. He comprobado que cada uno de los tres pagos tiene una distribución 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;
}
Más reglas
Aquí hay algunas reglas más generalizadas.
- Su programa no debe ejecutar / modificar / instanciar ninguna parte del controlador u otros participantes o sus recuerdos.
- Como su programa permanece "en vivo" durante todo el torneo, no cree ningún archivo.
- No interactúes, ayudes ni apuntes a ningún otro programa entrante.
- Usted puede enviar múltiples participantes, siempre y cuando sean razonablemente diferente, y siempre y cuando siga las reglas anteriores.
- No he especificado un límite de tiempo exacto, pero agradecería mucho los tiempos de ejecución que son significativamente menos de un segundo por llamada. Quiero poder organizar tantas elecciones como sea posible.
El controlador
El controlador se puede encontrar aquí . El programa principal es Tournament.java
. También hay dos bots simples, que competirán, titulados RandomBot
y PersonalFavoriteBot
. Publicaré estos dos bots en una respuesta.
Tabla de clasificación
Parece que ExpectantBot es el líder actual, seguido por Monte Carlo y luego 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.
Aquí hay algunos torneos más antiguos, pero ninguno de los bots ha cambiado en funcionalidad desde estas ejecuciones.
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.
También corrí un segundo torneo de 10m, confirmando la ventaja de 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.
fuente
Array
conteo de todos los votos. ¿Estoy en lo correcto?Respuestas:
NoThirdPartyBot
Este bot intenta adivinar qué candidato será el tercero y vota al candidato que más le gusta de los dos favoritos.
CircunferenciaBot
Este bot vota por su favorito que no ha sido eliminado matemáticamente.
fuente
ExpectanteBot
Este bot calcula el valor esperado de cada opción de votación, suponiendo que todos los votantes votarán al azar.
fuente
HipBot
HipBot no se preocupa por los pagos. El dinero es solo un sedante que distrae del verdadero arte.
HipBot quiere votar por alguien real , no solo por un chelín corporativo. También quiere usar su camisa de campaña después de su (supuestamente) humillante derrota, por lo que se siente superior cada vez que el ganador hace algo mal.
Por lo tanto, HipBot vota por la persona con los votos más bajos o, si hay un empate, quien tenga el mejor pago. Comer solo orgánico no es gratis.
HipBot tampoco ha sido probado, así que avíseme si está sucediendo algo.
EDITAR: agregado en comentarios más competitivos y decisivos.
fuente
PersonalFavoriteBot
Este bot simplemente vota por el candidato con la recompensa personal más alta, ignorando todo lo demás. Uno de los puntos principales de este desafío es demostrar cómo esta no es la estrategia óptima.
RandomBot
Este bot vota al azar. Independientemente del número de elecciones llevadas a cabo (siempre que sea razonablemente alto, como más de 100), el puntaje normalizado de este concursante fluctúa entre -2 y 2.
fuente
Seguidor
El seguidor quiere encajar. Piensa que la mejor manera de lograrlo es votando de la misma manera que todos los demás, o al menos con la pluralidad hasta ahora. Romperá los lazos hacia su propia preferencia, para mostrar un poco de independencia. Pero no demasiado.
Nota: No he probado esto, así que avíseme si hay algún error.
fuente
Monte Carlo
Esto simula una gran cantidad de elecciones aleatorias. Luego elige la opción que maximiza sus propios beneficios.
fuente
StatBot
StatBot se basa en ExpectantBot; sin embargo, en lugar de suponer que cada voto es igualmente probable, recopila estadísticas sobre cómo votan las personas y las usa para estimar la probabilidad.
fuente
Mejor candidato viable
Versión bastante revisada de mi presentación original. Este todavía elimina a los candidatos que no pueden ganar dados los votos restantes que se emitirán, pero luego utiliza una estrategia que trata de optimizar el pago relativo en lugar del absoluto. La primera prueba es tomar la relación de mi pago personal con el pago general de cada candidato, buscando el mejor valor allí. Luego busco otras proporciones que estén muy cerca de las mejores y si hay una que tenga una rentabilidad general más baja que la mejor, elijo esa. Con suerte, esto tenderá a deprimir el pago de los otros jugadores mientras mantiene el mío razonablemente alto.
Este bot funciona casi tan bien como el original en mis propias pruebas, pero no del todo. Tendremos que ver cómo funciona en el campo completo.
fuente
CircumspectBot
?Optimista
El optimista es muy optimista y asume que la mitad de los votantes restantes votarán por el candidato que le da el mejor resultado.
fuente
ABotDoNotForget
Su objetivo es simple: determinar las tendencias generales usando los pagos totales y contando el número de veces que ganaron los más bajos / medios / más altos. Luego votará por el que es más probable que gane.
Editar:
Algún cambio hecho en el algoritmo de decisión, ahora tiene en cuenta su mejor recompensa. Ahora debería poder votar mejor cuando la distribución actual lo estaba haciendo votar por su propio Bajo cuando otros votaron por sus pagos superiores.fuente
Priam
Priam odia la recursión. Estima la probabilidad de cada bot restante en función de los pagos totales y luego calcula la mejor manera de maximizar su pago.
Mucho más rápido que Odiseo ya que no hay recursividad (se ejecuta en el tiempo O (n ^ 2)) y puede hacer un millón de elecciones en unos 15 segundos.
fuente
NoClueBot
NoClue en realidad no conoce muy bien Java o matemáticas, por lo que no tiene idea de si esta relación de ponderación lo ayudará a ganar. Pero lo está intentando.
SomeClueBot
SomeClueBot ha sido dado de baja.
en realidad usa la lógica! solía usar la lógica, que resultó ser ineficiente, por lo que en cambio se dio cuenta de la recompensa total, no de la suya. usa la lógica de nuevo! Pero no le va bien con todos estos seguidores y optimistas, ¡e incluso con personas a las que no les importa! :)A veces segundo segundo mejor
Básicamente PersonalFavouriteBot, mejorado (en teoría).
fuente
El extremista
Siempre vote por el candidato con el menor pago
fuente
SmashAttemptByEquality
El objetivo es igualar a todos los candidatos, ¡entonces SMASH! todos los otros bots en la última ronda.
Este es un algoritmo destructivo que trata de molestar a todos los demás, para reclamar la victoria.
¡Tenga en cuenta que esto no se ha probado !
fuente
Bot Básico
Basic Bot solo vota por los candidatos que no se eliminan y tiene la mayor recompensa máxima de esos candidatos.
fuente
El favorito de Kelly
Comencé con CircumspectBot, pero no queda mucho. Hace una especie de suposición aburrida sobre la distribución de probabilidad de los votos restantes, y luego toma la decisión que maximiza su propia utilidad de registro (Criterio de Kelly). No es el más rápido, sino dentro del parque de pelota de algunos de los otros. Además, es bastante competitivo con el campo (tal como estaba cuando comencé a trabajar en esto y descargué los otros bots).
También disponible en https://gist.github.com/jkominek/dae0b3158dcd253e09e5 en caso de que sea más simple.
fuente
Comunismo
CommunismBot piensa que todos deberíamos llevarnos bien y elegir al candidato que sea mejor para todos.
Hatebot
Hatebot siempre elige al mejor candidato. A menos que sean una fiesta sucia y apestosa 1. Esos tipos son horribles.
StrategicBot
StrategicBot vota por el mejor candidato siempre que estén dentro de una desviación estándar del próximo mejor candidato, dada la cantidad de votantes restantes.
fuente
ExpectorBot
Intenta predecir cómo votarán todos los demás Bots calculando el pago promedio para los demás. Votos predeterminados para el mejor pago, pero votará por el segundo mejor, si tiene más votos esperados que el mejor, un pago mejor que el promedio para mí y el peor pago tiene la posibilidad de ganar esto.
fuente
LockBot
Solo un filósofo solitario, buscando su "e" ...
fuente
Ganar-perder
¡Si ganas, yo pierdo! Así de simple Entonces este bot vota por el que le gusta y a los demás no les gusta.
fuente