Missing Link: Von Thesen, Algorithmen und der Logik - mit Algorithmen ins Gefängnis und wieder raus
1950 notierte der kanadische Mathematiker Albert Tucker ein logisches Paradox, das als Gefangenendilemma in die Geschichte einging. Es zählt zu den bekanntesten Problemen der Spiel- und Entscheidungstheorie und ist noch immer für Überraschungen gut.
Alice und Bob, das Traumpaar vom Datenland, sind des Chiffrierens und Dechiffrierens müde. Sie möchten etwas erleben, und da empfiehlt sich der Einbruch in eine Bank. Am nächsten Morgen hat Datenland einen komplett entleerten Geldautomaten, und im Apartment von Alice und Bob liegen viele Scheine herum. Die schlechte Nachricht ist, dass wenig später die Polizei eintrifft und die beiden verhaftet.
Nachweisen kann man ihnen nichts, aber es startet der ortsübliche Strafprozess. Alice und Bob werden dabei getrennt verhört. Gesteht Alice den Einbruch, kommt sie frei, und Bob wandert fünf Monate ins Gefängnis, sofern er nichts sagt. Das Gleiche gilt für Bob: Freiheit beim Geständnis, fünf Monate für die schweigsame Komplizin. Wenn beide gestehen, müssen sie drei Monate hinter Gittern. Sollten beide ein Geständnis verweigern, gibt es für jeden einen Monat wegen Steuerhinterziehung.
Logik, Algorithmen und die Realität
Was wäre nun die vernünftigste Handlungsweise? Damit befasst sich das Gefangendilemma, das vermutlich bekannteste Problem der mathematischen Spieltheorie. Die Ursprünge des Dilemmas verlieren sich im Dunkel der Geschichte. Zum ersten Mal und mit Geld- statt Gefängnisstrafen notierte es der Kanadier Albert Tucker, der 1950 ein Rechenbeispiel für einen wissenschaftlichen Vortrag suchte. Danach hat es sich in aller Welt herumgesprochen.
Versuchen wir, jene Frage zu beantworten. Alice weiß: Falls Bob schweigt und sie gesteht, wäre sie frei. Falls er reden würde, wäre sie mit einem Geständnis ebenfalls besser dran. Sie und Bob erhielten zwar eine Strafe von drei Monaten, doch würde sie nichts sagen, müsste sie fünf Monate in den Knast. Bob denkt analog in Bezug auf Alice. Ergo geben beide alles zu und werden für ein Vierteljahr eingebuchtet. Gemeinsames Schweigen hätte schon nach einem Monat die Entlassung gebracht. Die Logik scheint aber unerbittlich.
Ein willig ertragenes Dilemma
Dieser Widerspruch zwischen Rationalität und Realität ist der Kern unseres Problems. Die Logiker haben das Dilemma seit 1950 willig ertragen, und es wurde zu einem Klassiker der Entscheidungstheorie, der Wirtschaftswissenschaft und der Sozialpsychologie. Die Forschung widmete sich in der Folgezeit vor allem einer Weiterentwicklung, dem iterierten Gefangenendilemma. Hier wird der Algorithmus für die Strafen mehrfach wiederholt, und ein Mitspieler kann auf Aktionen des Partners in späteren Runden reagieren.
Die Logik des Dilemmas wurde seit Tuckers Notiz nie angezweifelt. Der Algorithmus lässt sich aber durchaus anders analysieren. Betrachten wir die Situation nach der Verhaftung. Alice und Bob müssen sich separat und jeder für sich entscheiden. Sie können entweder gestehen oder den Mund halten, kurz, vier Kombinationen sind möglich: Geständnis-Geständnis, Geständnis-Schweigen, Schweigen-Geständnis, Schweigen-Schweigen. Die gesetzlichen Folgen zeigt die Auszahlungsmatrix.
In jedem Paar der Matrix steht links die Strafe für Alice und rechts die für Bob. Eines wird klar: ein Geständnis von Alice bringt Bob drei oder fünf Monate Knast ein. Das wäre die obere Zeile der Matrix. Im Falle ihres Schweigens, siehe die untere Zeile, kann sich Bob über die Freilassung freuen oder sitzt bloß einen Monat. Die analogen Effekte für Alice haben das Geständnis von Bob – das zeigt die linke Spalte und sein Nicht-Geständnis, siehe die Spalte rechts.
Wenn Du geschwiegen hättest ...
Nichts zu sagen verkürzt also die Strafe des Partners und der Partnerin. Alice profitiert vom Schweigen Bobs und Bob beim Schweigen von Alice. Die optimale Kombination – dass beide profitieren – stellte sich ein, wenn weder Bob noch Alice ein Wörtchen äußern. Die rechte untere Ecke der Matrix nennt die Strafe: einen Monat für jeden. Dass zweiseitiges Schweigen die beste Lösung ist, hatten wir eigentlich schon immer geahnt ... und das nicht nur, weil noch jeder Rechtsanwalt seit Krimi-Urgedenken seinen Klienten solches anempfiehlt.
Diese Analyse kann man in eine Regel kleiden: Entscheide so, dass es der anderen Partei nützt, und vergiss deine eigenen Haftzeiten, die Zahlen links in den Paaren. Das heißt nicht, dass Alice und Bob die großen Altruisten spielen und gute Taten tun sollen. Es zeigt nur, wie der Algorithmus funktioniert und wie man handeln muss, damit die erträglichsten Strafen herauskommen. Da Alice und Bob perfekte Logiker sind, begreifen sie es sofort und geben in den Verhören nichts preis.
Könnte aber Alice nicht in letzter Minute Bob reinlegen und ein Geständnis ablegen? Natürlich in der Hoffnung, so die Freiheit zu erlangen. Wenn wir solch eine Aktion zulassen, müssen wir Bob das gleiche Vorgehen erlauben, und ebenso wenig dürfen wir ausschließen, dass beide den Einbruch beichten. Dann droht Alice und Bob aber ein Vierteljahr im Gefängnis. Ein Abweichen von der optimalen Lösung ist immer möglich, doch kann es auch die Strafe verlängern. Wir sollten also der Logik folgen.
Chicken oder King
Der Ansatz, nicht die eigenen erlittenen Übel, sondern die des Partners zu zählen, lässt sich auf ein anderes berühmtes Problem übertragen, das Chicken- oder Feiglingsspiel. Zwei Autos rasen aufeinander zu; wer durchfährt, ist der King, und wer ausweicht, das Hühnchen. Beiderseitiges Ausweichen wäre gerade noch okay. Die Regel, dem Gegner zu helfen, führt zur optimalen Strategie, die wir einmal als Übungsaufgabe stellen möchten. Die Zahlen der Auszahlungsmatrix bezeichnen dabei den Seelenzustand der beiden Fahrer: 0 = King, 1 = Okay, 3 = Chicken, 5 = Crash.
Vor 500 Jahren schrieb Martin Luther in Wittenberg seine 95 Thesen nieder. Wir begnügen uns mit einer: Die Theoretiker haben mit den Algorithmen nur verschieden gespielt, es kommt aber drauf an, sie zu durchschauen. Unseren Lesern wünschen wir noch einen schönen Reformationstag. (jk)
