aus: OR News, Nr. 52, November 2014, Seite 19-21

Optimierte Einteilung der Wahlkreise für die Deutsche Bundestagswahl

SEBASTIAN GODERBAUER, AACHEN

Bei der grundsätzlich alle vier Jahre stattfindendenDeutschen Bundestagswahl sind Wahlkreise vonerheblicher Bedeutung. In jedem Wahlkreisentscheiden die Wähler mit ihren Erststimmen überdie konkrete Besetzung eines Sitzes im Parlamentder Bundesrepublik Deutschland, sodass jeder Teildes Wahlgebietes parlamentarisch vertreten wird.Auf diese Weise werden über die Wahlkreise in derTheorie die Hälfte der Bundestagsmandatevergeben. In der Realität beträgt der Anteil der überdie Wahlkreise gewählten Abgeordneten meistetwas weniger als die Hälfte. Grund dafür sindwahlrechtsbedingte, zusätzliche Überhang- undAusgleichsmandate, deren Anzahl auch von demZweitstimmenergebnis der Wahl abhängt. DieEinteilung der 299 Bundestagswahlkreise (vgl.Abb. 1) unterliegt gesetzlich verankertenGrundsätzen und Regeln (§ 3 Abs. 1Bundeswahlgesetz (BWG)). Auf Interpretation undAuslegung dieser Gesetze aufbauend kann dasProblem der Wahlkreiseinteilung alsOptimierungsproblem definiert werden. Für dessenLösung wurde eine optimierungsbasierte Heuristikentwickelt und erfolgreich auf neustenBevölkerungs- und Geodaten angewendet.

Abb. 1: Für die Bundestagswahl ist Deutschland in299 Wahlkreise einzuteilen.

Um dem Grundsatz der Wahlgleichheit zugenügen, sind die Bevölkerungsunterschiedezwischen den Wahlkreisen möglichst gering zuhalten. Dazu ist eine Toleranzgrenze von ±15%sowie eine absolute Höchstgrenze von ±25% derzulässigen Abweichung zwischenBevölkerungszahl eines Wahlkreises und derdurchschnittlichen Bevölkerungszahl derWahlkreise definiert (§ 3 Abs. 1 Nr. 3 BWG).Darüber hinaus soll jeder Wahlkreis einzusammenhängendes Gebiet bilden (§ 3 Abs. 1 Nr.4 BWG) und dessen Einteilung soll sich nachMöglichkeit an bestehenden Verwaltungsgrenzenorientieren (§ 3 Abs. 1 Nr. 5 BWG). Strikteinzuhalten sind hingegen dieBundesländergrenzen (§ 3 Abs. 1 Nr. 1 BWG), diesfolgt aus dem verfassungsrechtlich verankertenBundesstaatsprinzip (Art. 20 Abs. 1 Grundgesetz).Das gesetzlich vorgeschriebene Sainte-Laguë-Verfahren [12, 14] verteilt die Wahlkreisanzahl vonDeutschland auf die Bundesländer (§ 3 Abs. 1 Nr. 2BWG bzw. § 6 Abs. 2 Satz 2 bis 7 BWG). Um demVerdacht einer z.B. politisch motiviertenEinflussnahme durch Wahlkreisgeometrie (engl.Gerrymandering, vgl. [9, 16, 17])entgegenzuwirken, sollen visuell kompakteWahlkreise eingeteilt werden. Mit dem BegriffWahlkreisgeometrie wird das Vorgehen bezeichnet,welches durch gezieltes Festlegen derWahlkreisgrenzen einen Vorteil oder Nachteil füreine gewisse politische Partei oder auchgesellschaftliche Teilmenge anstrebt. Bei einerAnwendung können skurrile Wahlkreiseformenentstehen. Dieser Grundsatz zur visuellen Gestaltder Wahlkreise ist zwar nicht explizit imWahlgesetz genannt, jedoch entspricht eineÄhnlichkeit zu der geometrischen Form einesKreises oder regulärem Polygons derweitverbreiteten Vorstellung eines Wahlkreises.

Aufgrund von u.a. Bevölkerungsentwicklungen istdie Wahlkreiseinteilung regelmäßig anzupassen.Zur letzten Bundestagswahl im September 2013wurden durch den Gesetzgeber die Grenzen von 32Wahlkreisen gegenüber der bisherigen Einteilungmodifiziert [6]. Bei den 2013 verwendetenWahlkreisen überstieg dieBevölkerungsabweichung von mehr als jedemfünften Wahlkreis die gesetzliche Toleranzgrenzevon 15% [3]. Zahlreiche dieser Wahlkreiseschöpften sogar die 25%-Grenze aus [3].Bevölkerungsabweichungen von über 15% habenlaut Gesetz jedoch klar die Ausnahme zu sein [5].Darüber hinaus kritisiert die europäischeOrganisation OSZE in einem Report über ihreWahlbeobachtung die hohenBevölkerungsabweichungswerte bei denWahlkreisen für die Deutschen Bundestagswahl[10, 11]. Die Wahlkreiseinteilung zur nächsten,planmäßig 2017 stattfindenden Bundestagswahlwird erstmalig auf Grundlage der Ergebnisse desZensus 2011 berechnet werden [5]. Zuvor wurdenfortgeschriebene Daten beruhend auf derVolkszählung von 1987 verwendet. Da die Datenmehr oder weniger stark voneinander abweichen,werden zahlreiche Änderungen in derWahlkreiseinteilung vorzunehmen sein. Durch dieneue Datengrundlage wird Hessenhöchstwahrscheinlich einen Wahlkreis verlieren,den Bayern hinzu bekommt. Aufgrund dessen wirddie Wahlkreiseinteilung in diesen beidenBundesländern wahrscheinlich vergleichsweisegroße Anpassungen erfahren.

Neben der Problemstellung an sich bilden diegenannten und aktuellen Punkte zusätzlicheMotivation, das Problem der Wahlkreiseinteilungaus Sicht der mathematischen Optimierung zubearbeiten. In der Masterarbeit ist das Problem derWahlkreiseinteilung als multikriteriellesGraphpartitionsproblem definiert. Um das Problemzu lösen ist eine optimierungsbasierte, mehrstufigeHeuristik entwickelt worden.

Ausgangspunkt der mathematischen Definition desProblems der Wahlkreiseinteilung ist einsogenannter Bevölkerungsgraph. In einem solchenGraphen G=(V, E) repräsentiert ein Knoten i V∈ein Gebiet, z.B. eine Gemeinde, und ist gewichtetmit der dort wohnenden deutschen Bevölkerung pi.Zwei Bevölkerungsknoten i, j V∈ sind über eineungerichtete Kante (i,j) E∈ adjazent, wenn die

zugehörigen Gebiete benachbart sind. Im Zugeeiner Aufbereitung und Verknüpfung von Geodaten[2] und Bevölkerungsdaten des Zensus 2011 [15]können die Bevölkerungsgraphen für Deutschlandberechnet werden. Abbildung 2 enthält einenBevölkerungsgraphen von Nordrhein-Westfalen.

Abb. 2: Der Bevölkerungsgraph auf Gemeinde-ebene von Nordrhein-Westfalen ist mit 396 Knoten

und 1 084 Kanten einer der kleineren. Insgesamtgibt es 11 339 deutsche Gemeinden.

Das Problem der Wahlkreiseinteilung ist als einmultikriterielles Optimierungsproblem definiert,bei dem ein knotengewichteter Bevölkerungsgraphin eine gegebene Anzahl an zusammenhängendenund gewichtsbeschränkten Teilgraphen zupartitionieren ist. Die zu findenden Teilgraphenentsprechen dabei intuitiv den einzuteilendenWahlkreisen. Aus komplexitätstheoretischer Sichtist das Problem der Wahlkreiseinteilung NP-schwer[1]. Auf Wegen und speziellen Bäumen alsBevölkerungsgraph können zulässigeWahlkreiseinteilungen in polynomieller oder sogarin linearer Zeit gefunden werden [4, 8]. DiesesProblem wird auf Bäumen NP-schwer, wenn dieSumme der Bevölkerungsunterschiede minimiertwird [7]. Aus Modellierungssicht ähnelt dasProblem der Wahlkreiseinteilung einemKnotenfärbungsproblem: Unter der Auswahl von299 verschiedenen Farben ist jederBevölkerungsknoten unter gewissenNebenbedingungen und Optimierungszielen mitgenau einer Farbe zu färben.

In der Masterarbeit wird eine optimierungsbasierteHeuristik vorgestellt, die anhand der deutschen,aufeinander aufbauenden Verwaltungsebenen dasProblem der Wahlkreiseinteilung geeignet inkleinere Teilprobleme aufteilt. Zum einen kann sodas Ziel, Übereinstimmungen von bekanntenVerwaltungs- und Wahlkreisgrenzen zu fördern,adäquat umgesetzt werden. Zum anderen entstehenhandhabbare Graphgrößen innerhalb derTeilprobleme. Die erste Aufteilung in Teilproblemeist von dem Gesetzgeber gegeben: Das Problemder Wahlkreiseinteilung ist für jedes Bundeslandeinzeln zu lösen. Die Vereinigung allerBundesländerwahlkreise ergibt dann eineWahlkreiseinteilung für Deutschland. Für einBundesland wird der Bevölkerungsgraph auf derEbene der Kreise und kreisfreien Städte betrachtet.Auf diesem Graphen wird ein Set PartitioningProblem gelöst und so die Wahlkreisanzahl desBundeslandes auf Teilmengen der Kreisebeneaufgeteilt. Berechnet wird eine Partition desBevölkerungsgraphen in zusammenhängendeTeilgraphen, denen jeweils eine Wahlkreisanzahlzugewiesen ist, sodass in der Summe die denausgewählten Teilmengen der Kreise undkreisfreien Städte zugesprochene Anzahl derWahlkreise gleich der Wahlkreisanzahl desBundeslandes ist (vgl. Abb. 3a). Es werden dabeidie durch diese Wahlkreiszuweisung entstehenden

(durchschnittlichen) Bevölkerungsunterschiedeminimiert und möglichst Teilgraphen ausgewählt,die eine kompakte Wahlkreiseinteilungermöglichen. Partitionsmengen, denen genau einWahlkreis zugewiesen wird, bilden gelösteTeilprobleme. Verbleibende Partitionsmengenbilden offene Teilprobleme und deren Wahlkreisewerden auf dem Bevölkerungsgraph derGemeindeebene eingeteilt. Hierbei könnenpassende Lösungsalgorithmen aus der Literatur(vgl. [13]) oder, wie in der Masterarbeit, eineeinfache Heuristik angewendet werden (vgl. Abb.3b).

Die mithilfe des genannten Algorithmuseingeteilten Wahlkreise sind aufgrund derverwendeten, aktuellen Daten sowie dem Einhaltender gesetzlichen Vorgaben und Zielsetzungengrundsätzlich für die Bundestagswahl verwendbar.Die Ergebnisse zeigen, dass die berechnetenWahlkreise die im Wahlgesetz genanntenGrundsätze zumeist in einem größeren Umfangverkörpern als die gegenwärtig geltendeWahlkreiseinteilung für die DeutscheBundestagswahl.

a) b)

Abb. 3: (a) Lösung des Set Partitioning Problems und (b) Einteilung von vier Wahlkreisenauf Gemeindeebene in den Kreisen Borken, Coesfeld und Steinfurt

Literatur

[1] Altman, M. (1997). Is Automation the Answer:The Computational Complexity of AutomatedRedistricting. Rutgers Computer and LawTechnology Journal, 23(1), 81-142.

[2] Bundesamt für Kartographie und Geodäsie(2011). Shapefiles der VerwaltungsgrenzenDeutschlands (VG250_1Jan2011_UTM32).

[3] Bundeswahlleiter (2013). Strukturdaten für dieWahlkreise zum 18. Deutschen Bundestag.

[4] De Simone, C., Lucertini, M., Pallottino, S.,Simeone, B. (1990). Fair dissections of spiders,worms and caterpillars. Networks, 20, 323-344.

[5] Deutscher Bundestag (2011). Bericht derWahlkreiskommission für die 17. Wahlperiode desDeutschen Bundestagesgemäß § 3Bundeswahlgesetz. Bundestag-Drucksache17/4642.

[6] Gisart, B. (2013). Grundlagen und Daten derWahl zum 18. Deutschen Bundestag am 22.September 2013. Wirtschaft und Statistik,Statistisches Bundesamt, 528-550.

[7] Ito, T., Zhou, X., Nishizeki, T. (2006).Partitioning a graph of bounded tree-width toconnected subgraphs of almost uniform size.Journal of Discrete Algorithms, 4(1), 142-154.

[8] Lucertini, M., Perl, Y., Simeone, B. (1993).Most uniform path partitioning and its use inimage processing. Discrete Applied Mathematics,42(2-3), 227-256.

[9] Mehrotra, A., Jonson, E.L., Nemhauser, G.L.(1998). An Optimization Based Heuristic forPolitical Districting. Management Science 44,1100-1114.

[10] OSZE/ODIHR-Wahlbewertungsmission(2009). Bundestagswahlen am 27. September 2009.

[11] OSZE/ODIHR-Wahlexpertenteam (2013).Bundestagswahlen am 22. September 2013.

[12] Pukelsheim, F. (1998). Divisor oder Quote?Zur Mathematik von Mandatszuteilungen beiVerhältniswahlen. Report 392, Institut fürMathematik, Universität Augsburg.

[13] Ricca, F., Scozzari, A., Simeone, B. (2011).Political Districting: From classical models torecent approaches. 4OR, 9(3), 223-254.

[14] Sainte-Laguë, A. (1910). La représentationproportionnelle et la méthode des moindres carrés.Annales scientifiques de l'École NormaleSupérieure 27, 529-542.

[15] Statistisches Bundesamt (2013). Zensus 2011– Fakten zur Bevölkerung in Deutschland,Tabellenmaterial mit Ergebnissen des Zensus2011: Kernmerkmale Bevölkerung.

[16] Vickrey, W.S. (1961). On the Prevention ofGerrymandering. Political Science Quarterly, 76,105-110.

[17] Young, H.P. (1988). Measuring theCompactness of Legislative Districts. LegislativeStudies Quarterly, 13(1), 105-115.

Goderbauer, Sebastian, M.Sc., RWTH Aachen University, Lehrstuhl für Operations Research,Kackertstraße 7, 52072 Aachen und Lehrstuhl II für Mathematik, Pontdriesch 14-16, 52062 Aachen, E-Mail: sebastian.goderbauer@rwth-aachen.de