In den USA wird seit einigen Jahren wieder verstärkt über “Gerrymandering” diskutiert, also das Verschieben von Wahlkreisgrenzen, um (unter den Bedingungen des amerikanischen Mehrheitswahlrechts) die voraussichtlichen Ergebnisse einer Partei zu optimieren. Nachdem Barack Obama 2017 das Thema auf seine Agenda setzte, haben sich auch zahlreiche Mathematiker in den USA mit dieser Frage befaßt.
Meist geht es dabei natürlich um die realen Wahlkreise und um die praktischen Konsequenzen ihres Zuschnitts. Aber auch für die theoretische Mathematik lassen sich aus dem Stoff Themen gewinnen. Zum Beispiel: kann man (bei vorab korrekt geschätztem Stimmverhalten) zumindest theoretisch eine maximal ungerechte Verteilung der Wahlkreise finden, die also einer Partei 100% der Wahlmänner bzw. der Sitze in Kongreß und Repräsentantenhaus sichert.
Die Notices of the AMS hatten dazu im Oktober 2017 einen Artikel Gerrymandering, sandwiches and topology von Pablo Soberón.
Mathematischer Hintergrund ist das Ham-Sandwich-Theorem. Das beantwortet eigentlich die Frage, wie man mit einem Schnitt ein Schinken-Sandwich so zerschneiden kann, daß beide Brothälften und der Schinken jeweils in Teile gleichen Volumens zerlegt werden?
Das positive Antwort liefert ein 1938 von Stefan Banach bewiesenes Theorem, demzufolge man zu drei Teilmengen des Raumes (von endlichem Volumen) eine Ebene findet, die alle drei jeweils in Stücke gleichen Volumens teilt. (Der Satz gilt auch, wenn die drei Mengen jeweils aus mehreren Stücken bestehen. Man kann also zum Beispiel mehrere Schichten Schinken, Käse, Brot haben und dann eine Ebene finden, die Schinken, Käse, Brot jeweils gerecht aufteilt – wobei also nicht jede einzelne Käse-Scheibe halbiert wird, sondern nur der Käse insgesamt; entsprechend für den Schinken und das Brot insgesamt.)
Beim Gerrymandering geht es um die einfachere 2-dimensionale Variante: kann man zwei Teilmengen (endlichen Flächeninhalts) in der Ebene durch eine Gerade so zerschneiden, dass beide Mengen in Teile gleichen Flächeninhalts zerlegt werden.
Wahltechnisch gesehen ist es scheinbar eine besonders gerechte Lösung, die Mengen gleichmäßig zerlegen zu wollen. In Wirklichkeit ist es aber gerade umgekehrt: die Partei mit 51% gewinnt jetzt beide Wahlkreise statt nur einem.
(Eigentlich geht es beim Gerrymandering natürlich nicht um den Flächeninhalt von Teilmengen, sondern um die Anzahl der Wähler, mathematisch eine Anzahl von Punkten in der Ebene. Mathematisch ist das aber fast dasselbe Problem, der Beweis unten läßt sich leicht anpassen.)
Der Beweis dieses Satzes ist ein besonders schönes Beispiel für einen Beweis mittels topologischer Argumente. (Ich gebe unten den 2-dimensionalen Beweis, der 3-dimensionale ginge ähnlich.)
Beweis:
Zunächst bemerken wir, daß es zu jeder Richtung eine senkrecht auf dieser Richtung stehende Gerade gibt, die die erste Menge genau halbiert, wenn auch nicht unbedingt die zweite. Man starte einfach mit einer senkrechten Gerade und verschiebe sie solange bis die erste Menge genau halbiert wird.)
‘Richtungen’ entsprechen Punkten auf dem Einheitskreis S1. (Wenn man eine Halbgerade vom Nullpunkt in eine bestimmte Richtung zeichnet, schneidet sie den Einheitskreis in einem bestimmten Punkt.)
Dies benutzen wir nun, um eine stetige Funktion f:S1 —>R zu konstruieren: zu einem Punkt x auf dem Einheitskreis bzw. der zugehörigen ‘Richtung’ betrachten wir die zu dieser Richtung senkrechte Gerade, die die erste Menge halbiert und definieren f(x):=Flächeninhalt der zweiten Menge in der Halbebene von x.
Damit ist dann f(-x)= Flächeninhalt der zweiten Menge in der Halbebene von -x. Offenbar haben x und -x dieselbe senkrechte Gerade, liegen bzgl. dieser Gerade aber in unterschiedlichen Halbebenen. Damit ist f(x)=f(-x) genau dann, wenn auch die zweite Menge von der zu x senkrechten, die erste Menge halbierenden Geraden genau halbiert wird. Mit anderen Worten: eine Richtung mit f(x)=f(-x) wäre die Lösung unseres Problems.
Nach dem Borsuk-Ulam-Theorem (Teil 12) gibt es aber ein x auf dem Einheitskreis mit f(x)=f(-x). Damit hat man also die gesuchte Gerade. (Und man kann aus diesem Beweis auch einen Algorithmus machen, der die Gerade tatsächlich findet.
Mit diesem Verfahren zerlegt man also das Land in zwei Wahlkreise, die beide von derselben Partei gewonnen werden. Die beiden Wahlkreise zerlegt man wieder auf dieselbe Weise und bekommt dann vier, im nächsten Schritt acht, usw., Wahlkreise, die alle von derselben Partei gewonnen werden und die alle gleich groß sind.
Etwas schwieriger ist es für Zahlen, die keine Zweierpotenzen sind, eine Aufteilung in diese Zahl von Wahlkreisen zu finden, die alle gleich groß sind und wo beide Parteien jeweils dieselben Prozentzahlen erreichen. Dieses Problem wurde in den Arbeiten S. Bespamyatnikh, D. Kirkpatrick, and J. Snoeyink, Generalizing Ham Sandwich Cuts to Equitable Subdivisions, Discrete Comput. Geom. 24 (2000), no. 4, 605–622 und T. Sakai, Balanced Convex Partitions of Measures in R2, Graphs Combin. 18 (2002), no. 1, 169–192 gelöst.
Kommentare (10)