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

Kombinatorische Spieltheorie und optimales Verhalten

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 äußerst erfolgreichen kombinatorischen Lösungsmethoden wollen wir an praktischen Beispielen vorstellen und erproben und schließlich als Satz beweisen.

TryScience an der Universität Stuttgart – Workshop für Schüler:innen der Oberstufe

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

Was ist und was soll die Spieltheorie?

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

Erstaunlicherweise lassen sich die meisten Konfliktsituationen als ein Spiel beschreiben. Dies wird in vielen Bereichen angewendet, von Biologie bis Soziologie, von Ökonomik bis Informatik, jüngst sogar in der Künstlichen Intelligenz. 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 am besten 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 schnell langweilig – nach ihrer Lösung. 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 für TryScience

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).

„In unserem Workshop gewinnt ihr einen realistischen Einblick, was Mathematik bedeuten kann. In einer speziell für TryScience konzipierten Vorlesung werdet ihr echte Mathematik erleben, exemplarisch vorgeführt an einer spannenden Theorie, verständlich doch tiefgehend. Anschließend könnt ihr das Erlernte in Übungen anwenden und vertiefen, genau wie im richtigen Studium. Ergänzend gibt es Informationen zum Mathematikstudium und genügend Gelegenheit, eure Fragen zu stellen.“