Everyone's a winner, baby, that's no lie.
Hot Chocolate, Every 1's a Winner (1978)

Kombinatorische Spieltheorie

Als vernunftbegabte Wesen möchten wir unser Handeln vorausschauend planen soweit dies möglich ist, zumindest bei wichtigen Fragen, die uns am Herzen liegen. Die Spieltheorie untersucht strategische Interaktionen mit mathematischen Methoden und bietet hierzu einen reichhaltigen Werkzeugkasten. Einige der sehr erfolgreichen kombinatorischen Lösungsmethoden wollen wir an praktischen Beispielen vorstellen und erproben und schließlich als Satz beweisen.

TryScience an der Universität Stuttgart.

Jede:r kennt das Fach „Mathematik“ aus der Schule. Doch wie abstrakt, vielseitig und faszinierend Mathematik wirklich sein kann, bleibt vielen Schüler:innen verborgen. Der Fachbereich Mathematik bietet für TryScience auch dieses Jahr wieder eine unterhaltsame und lehrreiche Infoveranstaltung an. Wir stellen ein mathematisches Thema vor, mit dem interessierte Schüler:innen „die Uni ausprobieren“ können.

Unser Thema diesmal heißt: kombinatorische Spieltheorie

Was soll die Spieltheorie?

Wir alle haben als Kinder gespielt, viele spielen auch als Erwachsene mit Begeisterung. Sobald zwei oder mehr Spieler interagieren, entsteht eine besondere Situation: Das Ergebnis jedes einzelnen hängt nicht nur von seinen eigenen Aktionen ab, sondern auch von den Aktionen der anderen Spieler. Insbesondere stellt sich die Frage, wie ein Spieler sein Ergebnis verbessern kann, gar optimieren.

Erstaunlicherweise lassen sich die meisten Konfliktsituationen als ein Spiel beschreiben. Dies wird in vielen Bereichen angewendet, von Ökonomik bis Informatik, von Biologie bis Soziologie. Oft ist es jedoch keineswegs offensichtlich, wie wir die Konflikte analysieren oder gar lösen können. Wie verzwickt selbst einfache Beispiele sein können, zeigt das Gefangendilemma (engl. Prisoner's dilemma).

Die Spieltheorie beschreibt und untersucht solche Situationen, in denen mehrere Teilnehmer miteinander interagieren. Ein typisches Ziel der Spieltheorie ist es, rationale Entscheidungen in (sozialen) Konfliktsituationen zu finden oder zu erklären. Umgekehrt wird auch das reale Verhalten beobachtet, und sehr häufig ist unser Verhalten gar nicht so rational.

Mal verlierst du,
mal gewinnen die anderen.
Otto Rehhagel (1938–)

Was ist kombinatorische Spieltheorie?

Speziell in der kombinatorischen Spieltheorie betrachten wir Spiele, in denen zwei Spieler abwechselnd ziehen. Dabei soll kein Zufall vorkommen und alle Information für beide Spiele offen liegen. Dazu gehören etwa Schach und Go, nicht jedoch Poker oder Handball. Kombinatorische Spiele lösen wir mit der genial-einfachen Methode der Rückwärtsinduktion: Spielen müssen wir in der Zeit vorwärts, aber lösen können wir das Spiel besser rückwärts!

Spiele wie Schach und Go sind rechnerisch extrem komplex, das ist gerade ihr Reiz. Andere Spiele wie Tic-Tac-Toe sind allzu einfach und damit langweilig. Viele interessante Spiele liegen im Mittelfeld, weder zu schwer noch zu leicht. Hier können wir mit einer mathematischen Analyse unsere Strategie optimieren. Der krönende Höhepunkt dieser Veranstaltung ist der Satz von Sprague-Grundy: Damit können Sie Spiele effizient lösen. Gewinnen mit Mathematik!

Verstehen kann man das Leben nur rückwärts;
leben muss man es aber vorwärts.
Søren Kierkegaard (1813–1855)

Ablauf der Veranstaltung

Wir beginnen mit einer Vorstellung der Mathematik-Studiengänge. Danach präsentieren wir das Thema kombinatorische Spieltheorie in Form einer Vorlesung und zugehöriger Übung, wie im richtigen Studium (nur langsamer).

Kurzfassung der Folien zur Projektion
Druckversion im Format 2x2 oder 1x1

Die historischen Originalartikel sind online frei zugänglich und noch immer schön zu lesen: