Eines der gebräuchlichsten Abstimmungssysteme für Wahlen mit einem Gewinner ist die Methode der Mehrfachabstimmung. Einfach ausgedrückt gewinnt der Kandidat mit den meisten Stimmen. Die Mehrheitsentscheidung ist jedoch mathematisch nicht stichhaltig und kann zu Situationen führen, in denen die Wähler gezwungen sind, für das "kleinere von zwei Übeln" zu stimmen, im Gegensatz zu dem Kandidaten, den sie wirklich bevorzugen.
In diesem Spiel werden Sie ein Programm schreiben, das das System der Mehrfachwahl nutzt. Es wird für einen von drei Kandidaten bei einer Wahl abgestimmt. Jeder Kandidat ist mit einer bestimmten Auszahlung für sich selbst verbunden. Ihr Ziel ist es, die erwartete Auszahlung zu maximieren.
Die Auszahlungen sind "gleichmäßig" zufällig verteilt, ändern sich mit jeder Wahl und addieren sich zu 100. Kandidat A könnte eine Auszahlung von 40 haben, Kandidat B könnte eine Auszahlung von 27 haben und Kandidat C könnte eine Auszahlung von 33 haben. Jeder Spieler hat einen anderen Satz von Auszahlungen.
Wenn Sie an der Reihe sind, haben Sie unvollständige Informationen. Nachfolgend finden Sie die Informationen, die Ihnen zur Verfügung stehen. Da Sie nicht wissen, wie hoch die individuellen Auszahlungen anderer Spieler sind, müssen Sie vorhersagen, wie sie angesichts der aktuellen Umfrageergebnisse abstimmen würden.
- Die bisherigen Teilergebnisse der Wahlen
- Die Anzahl der Teilnehmer (außer Ihnen), die noch nicht abgestimmt haben
- Ihre persönlichen Auszahlungen für jeden der Kandidaten
- Die Gesamtgruppenauszahlungen für jeden der Kandidaten
Nachdem jedem Spieler eine Abstimmungsmöglichkeit eingeräumt wurde, gewinnt der Kandidat mit den meisten Stimmen gemäß der Mehrfachabstimmung. Jeder Spieler erhält dann die Anzahl der Punkte, die seiner Auszahlung von diesem Kandidaten entsprechen. Bei Stimmengleichheit entspricht die Anzahl der zugewiesenen Punkte dem Durchschnitt der gebundenen Kandidaten.
Turnierstruktur
Bei der ersten Instanziierung wird dem Teilnehmer die Anzahl der im Turnier abgehaltenen Wahlen mitgeteilt. Ich werde versuchen, eine extrem große Anzahl von Wahlen abzuhalten. Dann wird jede Wahl einzeln durchgeführt.
Nachdem die Teilnehmer gemischt wurden, erhält jeder eine Stimmabgabe. Sie erhalten die oben aufgeführten eingeschränkten Informationen und geben eine Nummer zurück, die ihre Stimmabgabe bestätigt. Nachdem jede Wahl beendet ist, erhält jeder Bot die endgültigen Abstimmungsergebnisse und deren Punktzahl erhöht sich aus dieser Wahl.
Der siegreiche Teilnehmer wird derjenige mit der höchsten Gesamtpunktzahl sein, nachdem eine große Anzahl von Wahlen stattgefunden hat. Der Controller berechnet auch eine "normalisierte" Punktzahl für jeden Teilnehmer, indem er seine Punktzahl mit der für einen Bot mit zufälliger Abstimmung vorhergesagten Punktzahlverteilung vergleicht.
Einreichungsdetails
Die Einreichungen erfolgen in Form von Java 8-Klassen. Jeder Teilnehmer muss die folgende Schnittstelle implementieren:
public interface Player
{
public String getName();
public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs);
public void receiveResults(int[] voteCounts, double result);
}
- Ihr Konstruktor sollte eine einzelne
int
als Parameter verwenden, die die Anzahl der Wahlen angibt, die abgehalten werden. - Die
getName()
Methode gibt den Namen zurück, der in der Bestenliste verwendet werden soll. Auf diese Weise können Sie schön formatierte Namen haben, aber verrückt werden. - Die
getVote(...)
Methode zurückgibt0
,1
oder2
um anzugeben, welcher Kandidat die Stimme erhalten wird. - Die
receiveResults(...)
Methode besteht hauptsächlich darin, die Existenz komplexerer Strategien zu ermöglichen, die historische Daten verwenden. - Sie dürfen so ziemlich alle anderen Methoden / Instanzvariablen erstellen, die Sie aufzeichnen und die Ihnen gegebenen Informationen verarbeiten möchten.
Turnierzyklus, erweitert
- Die Teilnehmer werden jeweils mit instanziiert
new entrantName(int numElections)
. - Für jede Wahl:
- Der Controller bestimmt zufällig die Auszahlungen für jeden Spieler für diese Wahl. Der Code dafür ist unten angegeben. Dann mischt es die Spieler und lässt sie abstimmen.
- Die Methode der Teilnehmer
public int getVote(int [] voteCounts, int votersRemaining, int [] payoffs, int[] totalPayoffs)
aufgerufen wird , und die Teilnehmer geben ihre Stimme von0
,1
oder2
für den Kandidaten ihrer Wahl. - Teilnehmer, deren
getVote(...)
Methode keine gültige Bewertung abgibt, erhalten eine zufällige Bewertung. - Nachdem jeder gewählt hat, bestimmt der Controller die Wahlergebnisse durch das Mehrfachverfahren.
- Die Teilnehmer werden durch Aufrufen ihrer Methode über die endgültigen Stimmenzählungen und deren Auszahlung informiert
public void receiveResults(int[] voteCounts, double result)
.
- Nachdem alle Wahlen stattgefunden haben, ist der Gewinner derjenige mit der höchsten Punktzahl.
Die zufällige Verteilung der Auszahlungen
Die genaue Verteilung wird einen signifikanten Einfluss auf das Gameplay haben. Ich habe eine Verteilung mit einer großen Standardabweichung (ca. 23,9235) gewählt, die sowohl sehr hohe als auch sehr niedrige Auszahlungen ermöglicht. Ich habe überprüft, dass jede der drei Auszahlungen eine identische Verteilung hat.
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;
}
Weitere Regeln
Hier sind einige allgemeinere Regeln.
- Ihr Programm darf keine Teile des Controllers oder anderer Teilnehmer oder deren Speicher ausführen, ändern oder instanziieren.
- Da Ihr Programm während des gesamten Turniers "live" bleibt, erstellen Sie keine Dateien.
- Interagiere nicht mit anderen Programmen, hilf ihnen oder ziele darauf ab.
- Sie können mehrere Teilnehmer einreichen, sofern diese sich angemessen unterscheiden und Sie die oben genannten Regeln befolgen.
- Ich habe kein genaues Zeitlimit angegeben, würde mich aber über Laufzeiten freuen, die deutlich unter einer Sekunde pro Anruf liegen. Ich möchte so viele Wahlen wie möglich durchführen können.
Der Controller
Die Steuerung finden Sie hier . Das Hauptprogramm ist Tournament.java
. Es gibt auch zwei einfache Bots, die gegeneinander antreten, betitelt RandomBot
und PersonalFavoriteBot
. Ich werde diese beiden Bots in einer Antwort veröffentlichen.
Bestenliste
Es sieht so aus, als wäre ExpectantBot der derzeitige Marktführer, gefolgt von Monte Carlo und 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.
Hier sind einige ältere Turniere, aber keiner der Bots hat sich seit diesen Läufen in der Funktionalität geändert.
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.
Ich lief auch ein zweites 10-Meter-Turnier und bestätigte den Vorsprung von 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.
quelle
Array
eine Zählung aller Stimmen. Hab ich recht?Antworten:
NoThirdPartyBot
Dieser Bot versucht zu erraten, welcher Kandidat der dritte sein wird und wählt den Kandidaten, den er am liebsten mag, unter den beiden Spitzenreitern aus.
CircumspectBot
Dieser Bot wählt seinen Favoriten, der mathematisch nicht beseitigt wurde.
quelle
ExpectantBot
Dieser Bot berechnet den erwarteten Wert jeder Abstimmungsoption unter der Annahme, dass alle Wähler danach zufällig abstimmen.
quelle
HipBot
HipBot kümmert sich nicht um Auszahlungen. Geld ist nur ein Beruhigungsmittel, das von der wahren Kunst ablenkt.
HipBot möchte für jemanden stimmen, der echt ist , nicht nur für einen Corporate Shill. Er möchte auch ihr Wahlkampfhemd nach ihrer (vermutlich) demütigenden Niederlage tragen, damit er sich überlegen fühlt, wenn der Sieger etwas falsch macht.
Deshalb wählt HipBot die Person mit den niedrigsten Stimmen oder, wenn es ein Unentschieden gibt, die Person mit der besseren Auszahlung. Nur Bio zu essen ist nicht kostenlos.
HipBot ist ebenfalls ungetestet. Lassen Sie mich wissen, wenn etwas los ist.
BEARBEITEN: in wettbewerbsfähigeren, markigen Kommentaren hinzugefügt.
quelle
PersonalFavoriteBot
Dieser Bot wählt einfach den Kandidaten mit der höchsten persönlichen Auszahlung und ignoriert alles andere. Einer der Hauptpunkte dieser Herausforderung ist es zu zeigen, dass dies nicht die optimale Strategie ist.
RandomBot
Dieser Bot wählt nach dem Zufallsprinzip. Unabhängig von der Anzahl der durchgeführten Wahlen (sofern diese mit über 100 einigermaßen hoch ist) schwankt die normalisierte Punktzahl dieses Kandidaten zwischen -2 und 2.
quelle
Anhänger
Follower will dazu passen. Der beste Weg, dies zu erreichen, ist, wie alle anderen zu stimmen, oder zumindest mit der Mehrzahl, die es bisher gab. Es wird die Bindung zu seiner eigenen Präferenz brechen, um ein wenig Unabhängigkeit zu zeigen. Aber nicht zu viel.
Hinweis: Ich habe dies nicht getestet. Lassen Sie mich daher wissen, wenn Fehler auftreten.
quelle
Monte Carlo
Dies simuliert eine große Anzahl zufälliger Wahlen. Dann wählt es die Wahl, die seine eigenen Gewinne maximiert.
quelle
StatBot
StatBot basiert auf ExpectantBot; Anstatt jedoch anzunehmen, dass jede Stimme gleich wahrscheinlich ist, werden Statistiken darüber gesammelt, wie die Leute abstimmen, und diese werden zur Abschätzung der Wahrscheinlichkeit verwendet.
quelle
Bester überlebensfähiger Kandidat
Ziemlich stark überarbeitete Version meiner ursprünglichen Einreichung. Dieser eliminiert immer noch alle Kandidaten, die bei den verbleibenden abzugebenden Stimmen nicht gewinnen können, verwendet dann aber eine Strategie, die versucht, die relative Auszahlung zu optimieren, anstatt die absolute. Der erste Test besteht darin, das Verhältnis meiner persönlichen Auszahlung zur Gesamtauszahlung für jeden Kandidaten zu ermitteln und dort nach dem besten Wert zu suchen. Ich suche dann nach anderen Verhältnissen, die den besten sehr nahe kommen, und wenn eines eine geringere Gesamtauszahlung hat als das allerbeste, wähle ich stattdessen dieses aus. Hoffentlich wird dies dazu neigen, die Auszahlung der anderen Spieler zu drosseln, während meine einigermaßen hoch bleiben.
Dieser Bot macht in meinen eigenen Tests fast so gut wie das Original weiter, aber nicht ganz. Wir werden sehen müssen, wie es sich gegen das gesamte Feld verhält.
quelle
CircumspectBot
?Optimist
Der Optimist ist sehr optimistisch und geht davon aus, dass die Hälfte der verbleibenden Wähler für den Kandidaten stimmen wird, der die beste Auszahlung erzielt.
quelle
ABotDoNotForget
Sein Ziel ist einfach: Ermitteln der Gesamttendenzen anhand der Gesamtauszahlungen und Zählen der Anzahl der gewonnenen niedrigeren / mittleren / höheren Tendenzen. Er wird dann für denjenigen stimmen, der am wahrscheinlichsten gewinnt.
Bearbeiten:
Einige Änderungen, die im Entscheidungsalgorithmus vorgenommen wurden, berücksichtigen nun seine beste Auszahlung. Sollte jetzt in der Lage sein, besser abzustimmen, wenn die aktuelle Verteilung ihn dazu brachte, für sein eigenes Niedrigeres zu stimmen, wenn andere für ihre höheren Auszahlungen stimmen.quelle
Priamos
Priamos hasst Rekursion. Er schätzt die Wahrscheinlichkeit jedes verbleibenden Bots basierend auf den Gesamtauszahlungen und berechnet dann den besten Weg, um seine Auszahlungen zu maximieren.
Viel schneller als Odysseus, da es keine Rekursion gibt (läuft in Zeit O (n ^ 2)) und eine Million Wahlen in ungefähr 15 Sekunden durchführen kann.
quelle
NoClueBot
NoClue kennt Java oder Mathe eigentlich nicht so gut, also hat er keine Ahnung, ob dieses Gewichtungsverhältnis-Ding ihm helfen wird, zu gewinnen. Aber er versucht es.
SomeClueBot
SomeClueBot wurde stillgelegt.
verwendet tatsächlich Logik! benutzte er Logik, die sich als ineffizient herausstellte, und achtete stattdessen auf die Gesamtauszahlung, nicht auf seine eigene. verwendet wieder Logik! Aber er kommt mit all diesen Anhängern und Optimisten nicht gut zurecht, und sogar mit Leuten, die sich nicht darum kümmern! :)ManchmalSecondBestBot
Grundsätzlich PersonalFavouriteBot, theoretisch verbessert.
quelle
Der Extremist
Stimmen Sie immer für den Kandidaten mit der niedrigsten Auszahlung
quelle
SmashAttemptByEquality
Das Ziel ist es, alle Kandidaten auszugleichen, dann SMASH! Alle anderen Bots der letzten Runde.
Dies ist ein destruktiver Algorithmus, der versucht, alle anderen auszuspionieren, um den Sieg einzufordern.
Beachten Sie, dass dies ungetestet ist !
quelle
Basic Bot
Basic Bot wählt nur die Kandidaten aus, die nicht ausgeschieden sind und die größte maximale Auszahlung dieser Kandidaten haben.
quelle
Kellys Liebling
Ich habe mit CircumspectBot angefangen, aber es ist nicht mehr viel übrig. Schätzt die Wahrscheinlichkeitsverteilung der verbleibenden Stimmen auf eine Art langweilige Weise und trifft dann die Wahl, die sein eigenes Protokolldienstprogramm maximiert (Kelly Criterion). Nicht der Schnellste, aber innerhalb des Ballparks einiger der anderen. Es ist auch ziemlich wettbewerbsfähig mit dem Feld (wie es aussah, als ich anfing, daran zu arbeiten und die anderen Bots herunter zu laden).
Auch verfügbar unter https://gist.github.com/jkominek/dae0b3158dcd253e09e5, falls dies einfacher ist.
quelle
KommunismusBot
CommunismBot meint, wir sollten uns alle verstehen und den Kandidaten auswählen, der für alle das Beste ist.
Hatebot
Hatebot wählt immer den besten Kandidaten aus. Es sei denn, sie sind eine schmutzig-stinkende Party 1. Diese Jungs sind schrecklich.
StrategicBot
StrategicBot stimmt für den besten Kandidaten ab, vorausgesetzt, sie liegen innerhalb einer Standardabweichung vom nächstbesten Kandidaten, gemessen an der Anzahl der verbleibenden Wähler.
quelle
ExpectorBot
Versucht vorherzusagen, wie alle anderen Bots abstimmen, indem die durchschnittliche Auszahlung für die anderen berechnet wird. Standardstimmen für die beste Auszahlung, aber Stimmen für die zweitbeste, wenn mehr Stimmen erwartet werden als die besten, eine überdurchschnittliche Auszahlung für mich und die schlechteste Auszahlung hat eine Chance, diese Sache zu gewinnen.
quelle
LockBot
Nur ein einsamer Philosoph, der nach seinem "e" sucht ...
quelle
WinLose
Wenn du gewinnst, verliere ich! So einfach. Dieser Bot wählt also den, den er mag und den alle anderen nicht mögen.
quelle