Die New Yorker von Politico wählen einen neuen Bürgermeister, nachdem chaotische, historische Vorwahlen begonnen haben:
NEW YORK – Die Umfragen sind bei der ersten Ranglistenwahl in New York City geschlossen, und obwohl die Würfel gefallen sind, wissen die Wähler möglicherweise wochenlang nicht, wie es ausgeht.
[...] Eine weitere Ausweitung der Stimmzettelzahl ist das Aufkommen der Ranglistenwahl, die es den New Yorkern ermöglicht, bis zu fünf Kandidaten für jede Position auszuwählen. Das System greift, wenn kein Kandidat im ersten Durchgang 50 Prozent der Stimmen erhält. Der Vorstand plant, die vorläufigen Ergebnisse der Ranglistenwahlen am 29. Juni bekannt zu geben.
Demnach : _
Mehr als ein Dutzend Demokraten und zwei Republikaner werden um die Nachfolge des scheidenden Bürgermeisters Bill de Blasio (D) kämpfen. Es wird erwartet, dass die Entscheidung für die Ranglistenwahl Wochen dauern wird.
Die Anzahl unterschiedlicher, aber gültiger Möglichkeiten, wie eine Person wählen kann, ist also groß. Ich denke, dass es die Summe von 0-, 1-, 2-, 3-, 4- und 5-aus-14-Möglichkeiten ist, aber ich bin mir nicht einmal sicher (siehe unten).
Ich bin gespannt, wie New York City die Auszählung der Stimmen nach Rangfolge physisch und rechnerisch umsetzen wird.
Frage: Algorithmisch geht das über mehrere Durchgänge einer Sortierfunktion über alle Ranglisten-Stimmen in einer Tabelle im Speicher oder auf einer Festplatte, aber wie setzt man das bei den verschiedenen physischen Formen der Stimmabgabe bei der Bürgermeisterwahl in New York um? ?
Werden sie auf eine vollständig elektronische Implementierung des Algorithmus, eine vollständig physische oder eine hybride Methode zurückgreifen?
In Python unter der Annahme (zum Beispiel) genau 14 verfügbare Kandidaten (in Mathematik ist es die Anzahl der Permutationen ohne Wiederholungen )
from itertools import permutations
possible = []
for k in [0, 1, 2, 3, 4, 5]:
uniques = list(permutations('abcdefghijklmn', k))
possible.append(uniques)
print(k, len(uniques))
all_possible = sum(possible, [])
print('total: ', len(all_possible))
k uniques
0 1
1 14
2 182
3 2184
4 24024
5 240240
total: 266645
Ich denke, das Zählen kann von Hand durchgeführt werden (ggf. mit mehreren "Durchgängen"). Zum Beispiel in Kanada laut CBC.ca (über Ranglistenwahl in Kanada):
„Sie sind wirklich einfach. Sie sind so einfach wie eins, zwei, drei. Sie ordnen Ihre Entscheidungen der Reihe nach – also, wen möchte ich Bürgermeister werden, wer ist meine erste Wahl, wer ist meine zweite Wahl und wer ist meine dritte Wahl.
In der ersten Runde addieren wir einfach die ersten Wahlmöglichkeiten, und wenn jemand die Mehrheit hat, ist es vorbei. Sie gewinnen. Aber wenn niemand eine Mehrheit hat – sagen wir, die Person mit den meisten Stimmen hat nur 30 Prozent – dann sollten sie natürlich nicht unbedingt Bürgermeister sein.
Sie eliminieren also den Kandidaten mit den wenigsten Stimmen und übertragen diese Stimmzettel bei jedem Wahlgang einfach auf die zweite Wahl, bis jemand die Mehrheit hat.
Das Auszählen von Hand scheint nicht so schwierig zu sein, Sie müssten nicht alle möglichen Stimmkombinationen im Auszählungsprozess berücksichtigen.
Wie das Zitat sagt, beginnen Sie damit, die Stimmzettel nach erster Wahl zu teilen. Wenn Sie 14 Kandidaten haben, dann haben Sie 14 Stapel Stimmzettel. Wenn es basierend auf der ersten Wahl keinen Gewinner gibt, eliminieren Sie den Kandidaten mit den wenigsten Stimmen (erste Wahl) und beginnen, sich die zweite Wahl auf den Stimmzetteln dieses Stapels anzusehen. Dann sind nur noch 13 Kandidaten im Rennen. Dieser Vorgang wird fortgesetzt, bis Sie einen Gewinner haben.
So beschreibt NPR auch den Auszählungsprozess für die New Yorker Bürgermeisterwahl:
Wenn jemand 50 % plus eins erhält, nachdem alle Erststimmen gezählt wurden, ist die Wahl beendet und dieser Kandidat gewinnt.
Aber wenn niemand 50 % plus eins bekommt, geht es in Runde 2 weiter.
Die Person mit der niedrigsten Anzahl an Stimmen auf dem ersten Platz wird eliminiert, und die zweite Wahl der Wähler dieses Kandidaten wird als Stimmen für andere Kandidaten neu verteilt.
Diese Neuverteilung der Stimmen wird fortgesetzt, bis jemand 50 % plus eins erreicht.
Bei der Wahl in New York hingegen werden die Stimmen maschinell ausgezählt. Wie CBS News am 25. Mai 2021 berichtete :
Die New Yorker können damit rechnen, schneller herauszufinden, wer die bevorstehende demokratische Bürgermeisterwahl der Stadt gewonnen hat, als wenn das New York State Board of Elections am Dienstag nicht gehandelt hätte, um eine Software für die tabellarische Auflistung der Wahlergebnisse zu genehmigen. Die Entscheidung bedeutet, dass die Stadt nun eine langwierige Handauszählung der im Rennen im nächsten Monat abgegebenen Stimmzettel vermeiden wird.
Trotzdem werden Ergebnisse aus demselben CBS News-Artikel wahrscheinlich nicht sofort verfügbar sein :
Trotz der Softwarezulassung wird es noch Tage, wenn nicht Wochen dauern, bis die New Yorker wissen, wer die Vorwahlen am 22. Juni gewonnen hat. Es wird erwartet, dass inoffizielle Ergebnisse der First-Choice-Stimmen am Vorwahlabend veröffentlicht werden, um die First-Choice-Stimmen zu zeigen, aber der Wahlausschuss der Stadt sagt, dass die Beamten erst in der folgenden Woche mit der Berechnung der Ergebnisse beginnen können.
Die spezifische Implementierung wurde bereits ausführlich in Zach Liptons Antwort behandelt .
New York City hat bei Sonderwahlen Anfang dieses Jahres einige Stimmzettel per Hand tabelliert , bei denen die Anzahl der Stimmzettel und Kandidaten vergleichsweise gering und das Auszählen von Hand praktikabler war.
Für die Bürgermeisterwahlen hat die staatliche Wahlbehörde jedoch eine Software für den Auszählungsprozess zertifiziert: The RCV Universal Tabulator , ein Open-Source-Paket, das von einer gemeinnützigen Gruppe namens The Rated Choice Resource Center entwickelt wurde.
Die Software ist Open Source und kann auf GitHub eingesehen werden . Ich stelle mir vor, dass die physischen Stimmzettel mit typischen zertifizierten Abstimmungstabellengeräten gescannt werden, um die Eingabe für die RCV-Software zu erzeugen. Wenn Sie Java lesen können, sieht die Kerntabellenschleife ziemlich einfach aus (die Software unterstützt mehrere Gewinner, obwohl dies bei dieser Wahl eindeutig nicht verwendet wird):
// At each iteration, we'll either a) identify one or more
// winners and transfer their votes to the remaining candidates (if we still need to find more
// winners), or b) eliminate one or more candidates and gradually transfer votes to the
// remaining candidates.
Sie werden schließlich auch den vollständigen Stimmensatz veröffentlichen, der es jedem ermöglicht, seine eigene Version des Algorithmus auszuführen, wenn er dies wünscht.
Ich glaube, Sie missverstehen, wie die Ranglistenwahl funktioniert. Wenn wie bisher kein Kandidat 50 % der Stimmen erreicht, scheidet der letztplatzierte Kandidat aus. Ihre Stimmzettel werden nun alle den Kandidaten zweiter Wahl ihrer Wähler zugeteilt. Die einzigen Stimmen, die neu ausgezählt werden müssen, sind also die des letztplatzierten Kandidaten.
Wir gehen dann zurück zum Anfang und tun so, als hätten diese neu kategorisierten Stimmen den Kandidaten der zweiten Wahl als Kandidaten der ersten Wahl, den Kandidaten der dritten Wahl als Kandidaten der zweiten Wahl usw. und sehen erneut nach, ob jemand 50 % überschritten hat. Wenn nicht, wiederholen wir den Vorgang mit dem neuen Letztplatzierten. Beachten Sie, dass es möglich ist, dass die Schwelle für 50 % im Laufe des Prozesses sinkt, wenn jemand keinen zweiten, dritten usw. Kandidaten auswählt.
Der Prozess wird hier beschrieben: https://vote.nyc/page/ranked-choice-voting
Ich möchte auch hinzufügen, dass (a) sie den Prozess erst nächste Woche beginnen werden und (2) einige der Neuzuweisungen in der ersten Runde sehr schnell gehen werden, da es sehr kleine Zahlen für die kleinsten Kandidaten gibt.
14!/9!
, aber für bis zu 5 von 14 bewerteten Entscheidungen ist es tatsächlich SUM(14!/(14-n)!) for n=1 to 5
das, was ich in Excel berechnen könnte, aber trotzdem, ... Punkt ist, dass es dafür keine Rolle spielt.Ich bin gespannt, wie New York City die Zählung der Stimmen nach Rangfolge physisch und rechnerisch umsetzen wird.
Physisch erhielten die Wähler einen tabellarischen Stimmzettel (siehe diese Seite der Regierung von NYC ), in dem die Zeilen Kandidaten und die Spalten die bevorzugte Reihenfolge darstellen, und die Stimmzettel werden gescannt, um Aufzeichnungen unterschiedlicher Länge zu erhalten (der Wähler kann 1 bis 5 Auswahlmöglichkeiten ausdrücken), die die gewählten Kandidaten enthalten Reihenfolge der Präferenz.
Rechnerisch hat NYC eine ausfallsicherere Version dieses (relativ) einfachen Python-Skripts
from random import seed, shuffle
from timeit import default_timer as dt
seed(20210622)
n_candidates, n_choices, n_ballots = 14, 5, 10**6
# ##### generate the ballots
start_generation = dt()
candidates = list(range(n_candidates))+[0] # introducing a bias for candidate 0
ballots = [candidates[:n_choices] for _ in range(n_ballots)
if not shuffle(candidates)]
print("\nGeneration of %d ballots required %.2f s"%(
n_ballots, dt()-start_generation))
# ##### process the ballots
start_count = dt()
while True:
counts = {candidate:0 for candidate in candidates}
# count 1st choices
for ballot in ballots: counts[ballot[0]] += 1
# sort candidates according to 1st choices
ranks = sorted(list(counts.items()), key=lambda t:t[1])
# max no. of 1st choices
max_1st = ranks[-1][1]
# if there is a winner, stop counting
if max_1st > len(ballots)//2: break
# who is the loser?
loser = ranks[0][0]
# remove loser from ballots and from list of candidates
for ballot in ballots:
if loser in ballot: ballot.remove(loser)
candidates.remove(loser)
# remove any empty ballot from list of ballots
# (copying not empty ballots is WAY FASTER than deleting void ballots)
ballots = [ballot for ballot in ballots if ballot]
# we have a winner
print(*reversed(ranks), sep='\n')
print("Counting %d ballots required %.2f s"%(
n_ballots, dt()-start_count))
Als ich es auf meinem alten Low-End-Notebook ausführte, erhielt ich die folgende Ausgabe
Generation of 1000000 ballots required 9.29 s
(0, 490711)
(12, 245897)
Counting 1000000 ballots required 6.08 s
Schon in dieser Simulation zeigt sich, dass das eigentliche Problem darin besteht, die Daten in einem für die Zählung geeigneten Format aufzubereiten, dann geht es um Sekunden…
Als Fußnote dachte ich zunächst, ich müsste das Skript mithilfe von Vektormathematikbibliotheken optimieren, aber es stellte sich heraus, dass dies nicht erforderlich ist.
+n!
stattdessen, aber ich frage mich, ob die Erkennung und Behandlung fehlender Rankings (z. B. nur 2., 3. und 5.) oder Wiederholungen (z. B. 1.: "X", 2.: "Y", 3.). : "X") ist ein wichtiger Teil des Prozesses? Ich habe nicht speziell danach gefragt, aber da Sie einen Beispielalgorithmus gepostet haben, sollte er irgendwie jedes der kritischen Elemente darstellen.s/- 3 - 7 2/3 7 2 - -/
." Gleiches gilt für Wiederholungen, aber hier sagt die von mir verlinkte Seite, dass Wiederholungen einfach ignoriert werden, so sollte es sein s/3 3 3 12 1/3 12 1 - -/
. Schließlich werden bei der Verarbeitung unterschiedliche Datensatzlängen behandelt, sodass ich sagen kann, dass Datensätze mit unterschiedlicher Länge auch im ersten Durchgang behandelt werden können.
Italienische Philosophen 4 Monica
äh
Alpha Draconis
Italienische Philosophen 4 Monica
äh
äh
Gidds
Chris H
äh
Phoog
äh
Robert Bristol-Johnson