Bei manchen Wahlen werden die Wähler in Gruppen eingeteilt. In jeder Gruppe wird ein Sieger bestimmt, und wer die Mehrheit der Gruppen gewinnt, gewinnt die gesamte Wahl.
Stell dir vor, Alex und Kim kandidieren sich als Schulsprecher. Jede Klasse gibt ihre Stimme ab, und wer in den meisten Klassen gewinnt, wird gewählt.
Gerrymandering bedeutet, dass die Gruppeneinteilung so verändert wird, dass sie zum Vorteil eines bestimmten Kandidaten dient. Zum Beispiel: Wenn Umfragen zeigen, dass Alex besser abschneidet, wenn nach Schuljahr statt nach Klasse gruppiert wird, dann bringt diese Neueinteilung Alex einen Vorteil. Wenn also der Schuldirektor die Gruppen so anpasst, dass Alex bevorzugt wird, handelt es sich um Gerrymandering.
Neun Wähler entscheiden zwischen Kandidat A und B. Die Stimmen lauten:
Wer gewinnt die Wahl? Wie könnte Kandidat B durch Gerrymandering gewinnen, wenn man die Wähler in 3er-Gruppen aufteilt?
A erhält 5 von 9 Stimmen, also gewinnt A bei einer einfachen Auszählung. Wenn man die Wähler nach Zeile (oder Spalte) gruppiert, gewinnt A weiterhin in 2 von 3 Gruppen. Aber Kandidat B kann durch Gerrymandering gewinnen, indem die Gruppeneinteilung wie folgt gewählt wird:
In diesem Fall gewinnt Kandidat B in 2 von 3 Gruppen und gewinnt somit die Wahl.
Angenommen, die Kandidaten A und B treten bei einer Wahl gegeneinander an, und es gibt 81 Wähler, die in Gruppen von je 9 Personen aufgeteilt sind. Kandidat A kennt alle Präferenzen im Voraus und darf die Gruppen frei einteilen. Wenn A über sehr präzise Umfragen verfügt (sodass A im Voraus weiß, wer für wen stimmen wird) und A Gerrymandering betreiben kann, wie viele Stimmen benötigt A mindestens, um die Wahl zu gewinnen?
Um eine Gruppe zu gewinnen, benötigt Kandidat A 5 von 9 Stimmen und A muss mindestens 5 von 9 Gruppen gewinnen. Um also mit möglichst wenigen Stimmen die Wahl zu gewinnen, muss A genau 5 Gruppen gewinnen , mit jeweils genau 5 Stimmen in jeder dieser Gruppen (und keine befürwortenden Stimmen in den übrigen Gruppen hat). Das ergibt insgesamt 25 Wählerstimmen, die notwendig und ausreichend sind, damit A die Wahl durch Gerrymandering gewinnt.
Angenommen, die Kandidaten A und B treten bei einer Wahl gegeneinander an, und es gibt 100 Wähler, die in Gruppen zu je 10 Personen aufgeteilt sind. Kandidat A kennt alle Präferenzen im Voraus und darf die Gruppen frei einteilen. Wenn A über sehr präzise Umfragen verfügt (sodass A im Voraus weiß, wer für wen stimmen wird) und A Gerrymandering betreiben kann, wie viele Stimmen benötigt A mindestens, um die Wahl zu gewinnen?
Wir zeigen, dass 35 Stimmen ausreichen, damit A die Wahl gewinnt. Beachte, dass Kandidat A 6 Stimmen benötigt, um eine Gruppe zu gewinnen, und 5 Stimmen, um ein Unentschieden in einer Gruppe zu erzielen.
Angenommen, Kandidat A gewinnt in $w$ Gruppen und erreicht ein Unentschieden in $t$ Gruppen. Dann erzielt Kandidat B ebenfalls ein Unentschieden in diesen $t$ Gruppen und gewinnt in den verbleibenden $10 - w - t$ Gruppen die Wahl.
Dann gewinnt A die Wahl, wenn:
$$2w + t > 10$$
Wenn $t = 0$ ist, dann muss $w \geq 6$ gelten, und A würde 36 Stimmen benötigen (um in 6 Gruppen zu gewinnen).
Wenn $t$ gerade und strikt positiv ist, kann man $t$ um 1 verringern, ohne dass die Bedingung $2w + t > 10$ verletzt wird, daher kann dieser Fall ausgeschlossen werden.
Wenn $t = 1$ ist, dann muss $w \geq 5$ sein, und A würde 35 Stimmen benötigen (um in 5 Gruppen zu gewinnen und in 1 Gruppe ein Unentschieden zu erreichen).
Wenn $t$ ungerade und größer als 1 ist, kann man $t$ um 2 verringern und gleichzeitig $w$ um 1 erhöhen, wodurch man 4 Stimmen spart, auch dieser Fall kann daher ausgeschlossen werden.
