Informatik Wer hat an der Wahl gedreht?

Ein fiktiver Zeitungsartikel: „Bonn, 21. Juni 1991. Berlin wird der künftige Parlaments- und Regierungssitz. Das hat der Bundestag gestern entschieden. Wie sich aus den namentlichen Abstimmungslisten ergibt, hätte ebenso gut Bonn gewinnen können. War die Wahl manipuliert? Und war das Schicksal Bonns auf Gedeih und Verderb dem Ältestenrat ausgeliefert, der die Reihenfolge der abzustimmenden Anträge festlegte?“

Der Mauerfall 1989 war ein großer Moment. Unmittelbar danach begann die Debatte über den Sitz von Parlament und Regierung. Schließlich wurde der Streit mit einer Abstimmung im Bundestag beendet. Dabei standen drei Alternativen zur Wahl: Parlament in Berlin und Regierung in Bonn (die sogenannte Konsenslösung), beides in Berlin, oder beides in Bonn. Für die Abstimmung wurde ein sequentielles Verfahren verwendet, bei dem über die Alternativen in einer festgelegten Reihenfolge nacheinander abgestimmt wird. Die erste Alternative, die mehr Ja- als Nein-Stimmen erhält, ist der Gewinner. Der Ältestenrat entschied, zuerst über die Konsenslösung abzustimmen; hätten mehr Abgeordnete dafür als dagegen gestimmt, dann wäre sie angenommen worden, und es hätte keine weitere Abstimmung mehr gegeben. Anderenfalls sollte eine Entscheidung zwischen Berlin und Bonn fallen. Das historische Ergebnis war, dass die Konsenslösung die Mehrheit deutlich verfehlte. Weniger als ein Drittel (147 gegenüber 489) der Abgeordneten stimmte mit Ja. Anschließend wurde Berlin mit knapper Mehrheit (338 Stimmen gegenüber 320 für Bonn) zum Gewinner gekürt.

Geschickt ausgewählt

Die Entscheidung war gefallen, sorgt aber immer noch für Diskussionen. Eine natürliche Frage ist zum Beispiel, ob Bonn hätte gewinnen können, wenn die Abstimmungsreihenfolge anders gewesen wäre. Um diese Frage beantworten zu können, muss man wissen, wie die Abgeordneten in diesem Fall abgestimmt hätten. Dies hatte schon 1993 Wolfgang Leininger in einem Beitrag zur Zeitschrift Finanzarchiv untersucht. Er rekonstruierte für jeden der 658 Abgeordneten, was seine liebste, zweitliebste und drittliebste Alternative war. Daraus lässt sich ablesen, dass Bonn gewonnen hätte, wenn man zuerst über Berlin anstatt über die Konsenslösung abgestimmt hätte. Die Abstimmungsreihenfolge war also von entscheidender Bedeutung. Aber wie findet man eine geeignete Reihenfolge um eine Wunschalternative gewinnen zu lassen? Und kann eigentlich jede Alternative gewinnen?

Für die Hauptstadtwahl lässt sich die Antwort noch einfach finden, indem man alle möglichen Reihenfolgen für die Abstimmung durchprobiert. Bei drei Alternativen ist das leicht möglich, da es nur sechs verschiedene Reihenfolgen gibt. In Wahlen mit zehn oder mehr Alternativen existieren aber schon Millionen von möglichen Anordnungen, und einfaches Probieren dauert viel zu lange.

Muss man nun alle Reihenfolgen ausprobieren oder gibt es eine einfachere Lösung? Ich habe dazu folgendes beobachtet: Wenn überhaupt eine Reihenfolge existiert, durch die die Wunschalternative gewinnt, dann existiert auch eine Reihenfolge, in der sie als letzte steht und gewinnt. Daraus entwickelte ich die Idee, die Reihenfolge von hinten nach vorne aufzubauen. Zuletzt müsste über unsere Wunschalternative abgestimmt werden. Aber wo reiht man die anderen Alternativen ein? Bei genauem Betrachten der Struktur der Wahl erkannte ich, dass nicht alle Alternativen gleich wichtig für die Reihenfolge sind. Gefährlich sind die Konkurrenzalternativen, die jeweils von der Mehrheit der Wähler gegenüber der Wunschalternative bevorzugt werden. Sie dürfen nicht unmittelbar vor der Gewünschten eingereiht werden, da sonst ein Gewinner gefunden wird, bevor über die Wunschalternative abgestimmt werden kann. Zu diesem Zweck fügt man zunächst die ungefährlichen Alternativen unmittelbar vor der Gewünschten ein. Die Reihenfolge der gefährlichen Konkurrenzalternativen wird wie folgt festgelegt: Man wählt zunächst eine Konkurrenzalternative aus, die nicht gewinnt, wenn man sie gegen die schon einsortierten Alternativen zur Abstimmung stellt; falls es eine solche Alternative nicht gibt, dann bricht man ab und weiß, dass die Wunschalternative keinesfalls gewinnen kann. Ansonsten fügt man die ausgewählte Alternative vorn ein und wiederholt diesen Prozess, bis alle Konkurrenzalternativen einsortiert sind. Das Endergebnis (falls nicht vorzeitig abgebrochen wurde) ist eine Abstimmungsreihenfolge, die die Wunschalternative zum Gewinner macht. Durch den Ansatz, die Reihenfolge rückwärts und nicht vorwärts zu konstruieren, ist es mir gelungen, eine beweisbar korrekte Lösung zu finden und damit nach fast 40 Jahren Millers offene Frage zu beantworten.

Einigung unter Freunden

Parlamentarische Abstimmungen spielen im Alltag der meisten Menschen nur selten eine Rolle. Wahlen im weiteren Sinne tauchen aber immer dann auf, wenn eine kollektive Entscheidung getroffen oder ein Konsens gefunden werden muss. Wenn man sich zum Beispiel mit Freunden auf eine Zeit für einen gemeinsamen Kinobesuch einigen will, oder wenn die Personalabteilung einer Firma den besten unter hunderten von Bewerbern aussuchen soll, dann ist eine Wahl notwendig. Eine wichtige Rolle spielt das Wahlverfahren, das festlegt, nach welchem Schema aus den einzelnen Stimmen ein oder mehrere Gewinner ausgewählt werden. Wahlen waren schon immer wichtig, haben aber im Internetzeitalter noch einmal stark an Bedeutung gewonnen. Sie spielen eine tragende Rolle beispielsweise in Metasuchmaschinen, die aus den Ergebnissen mehrerer Suchmaschinen wie Google oder Yahoo zu einem bestimmten Suchbegriff eine kombinierte Reihenfolge der gefundenen Webseiten bilden. Weitere häufige Anwendungen sind Umfragen wie zum Beispiel nach der besten Universität Deutschlands oder Empfehlungsdienste von Büchern oder Videos im Online-Handel. Solche Empfehlungsdienste bieten, basierend auf Bewertungen durch andere Kunden, aus einer großen Menge an Produkten einen individuell passenden Vorschlag an.

Wie das Beispiel der Hauptstadtwahl gezeigt hat, sind Wahlen manipulierbar. Bei automatisierten Wahlen, in denen Computerprogramme die Stimmabgaben sammeln und die Gewinner berechnen, droht automatisierte Manipulation. Es ist also wichtig zu wissen, ob und mit welchem Zeitaufwand eine Manipulation überhaupt möglich ist. Eins der Hauptthemen meiner Forschungsarbeit ist die Bestimmung der Rechenzeit zur Auffindung einer Wahlmanipulation.

Wahlen können auf viele verschiedene Weisen manipuliert werden. Beispielsweise können Wähler strategisch, das heißt entgegen ihrer eigentlichen Überzeugung abstimmen, um ein für sie besseres Endergebnis zu erreichen. Bei der Hauptstadtabstimmung könnte das zum Beispiel bedeuten, dass Abgeordnete, die eigentlich Bonn als alleinige Hauptstadt befürworten, in der ersten Runde für die Konsenslösung stimmen, da sie ahnen, dass Bonn in der zweiten Runde gegen Berlin verlieren würde. Eine weitere Form der Manipulation ist die sogenannte konstruktive Bestechung, bei der man Wähler etwa durch ein Bestechungsgeld dazu bringt, ihre Stimmabgabe so zu ändern, dass eine Wunschalternative gewinnt, wobei man ein begrenztes Budget zur Verfügung hat.

Diese beiden und noch weitere Formen der Manipulation habe ich im Rahmen meiner Promotion untersucht. In vielen Fällen konnte ich obere und untere Schranken der benötigten Rechenzeit zur Entdeckung einer möglichen Manipulation bestimmen: Manche Wahlmanipulationen sind vom Rechenaufwand her ähnlich leicht wie die Wahlleitermanipulation bei der Hauptstadtwahl, während manche anderen nach unserem heutigen Wissen wahrscheinlich nicht schnell zu berechnen sind. Letzteres ist durchaus wünschenswert, da es bedeutet, dass das entsprechende Wahlverfahren schwer zu manipulieren ist.

Um zum Abschluss noch einmal auf die ursprüngliche Frage zurückzukommen: War die Hauptstadtwahl tatsächlich manipuliert? Das können nur die damaligen Mitglieder des Ältestenrates des Bundestages beantworten, die die Reihenfolge der Abstimmung festgelegt haben. Alles, was ich gezeigt habe, ist, dass eine Manipulation möglich war und nicht besonders schwierig gewesen wäre. Das gilt übrigens für alle Abstimmungen, die das beschriebene Verfahren verwenden, auch bei mehr als drei Alternativen.