Hauptseminar Spieltheorie

angeboten im SS 2006
an der Lehr- und Forschungseinheit 5 (Theoretische Informatik)
des Instituts für Informatik der Universität München

Felix Brandt
Felix Fischer
Paul Harrenstein

Donnerstag, 14-16 Uhr
Oettingenstr. 67, Oe 0.11

Spieltheorie (engl. game theory) beschäftigt sich mit der formalen Analyse von Situationen, in denen mehrere Entscheidungsträger ("Agenten") interagieren. Ein bekanntes Beispiel für eine derartige Situation ist das sogenannte Gefangenendilemma (prisoner's dilemma).

Spiele im herkömmlichen Sinn sind nur ein Spezialfall solcher Situationen. Spieltheorie findet darüber hinaus breite Anwendung bei der Analyse ökonomischer, gesellschaftlicher, politischer und biologischer Phänomene wie etwa der Konkurrenz zwischen Firmen, dem Wettstreit um Wählerstimmen, der Urteilsfindung in einem Prozess, dem Bieterverhalten in Auktionen oder dem Kampf um Nahrungsreserven. Wie andere Theorien auch bedient sich die Spieltheorie einer Menge von Modellen, um von der Wirklichkeit zu abstrahieren und bestimmte Aspekte formal präzise darzustellen und zu analysieren.

Die Theorie der rationalen Entscheidung (rational choice theory) ist ein grundlegender Bestandteil vieler spieltheoretischer Modelle. Im Zentrum dieser Theorie steht die Annahme, dass ein Agent in jeder Situation die aus seiner Sicht beste Aktion auswählt. Die Qualität einer Aktion ist dabei definiert über eine individuelle Präferenzordnung auf Gesamtergebnissen, die sich wiederum durch die Entscheidungen aller Agenten ergeben. Seit einiger Zeit gibt es eine rege Interaktion zwischen Spieltheoretikern und Informatikern. Zum einen werden Konzepte aus der Spieltheorie zur formalen Analyse von verteilten Systemen benutzt, zum anderen werden grundlegende Techniken der Informatik, z.B. aus der Komplexitätstheorie, auf spieltheoretische Probleme angewendet.

Im Rahmen dieses Seminars sollen einige zentrale Modelle der Spieltheorie vorgestellt werden -- wie normal-form games, extensive-form games und coalitional games --, sowie wichtige Konzepte zu deren Analyse -- wie z.B. Nash Gleichgewichte. Weitere Schwerpunkte liegen auf dem Entwurf von Mechanismen und Protokollen zur verteilten Entscheidungsfindung und Präferenzbündelung.

Teilnahmevorraussetzungen:

• bestandenes Vordiplom in Informatik oder Mathematik
• Interesse an (mathematisch) formaler Modellierung und Analyse interessanter und wichtiger Probleme
• gute Englischkenntnisse und Bereitschaft zur selbständigen Bearbeitung englischsprachiger Literatur

• Anwesenheit bei den Vorträgen und aktive Teilnahme an der Diskussion
• Halten eines Vortrags (ca. 45-60 Minuten)
• Abgabe einer Ausarbeitung zu diesem Vortrag (im Umfang von etwa 10 Seiten)

Übersicht:

• Martin Osborne and Ariel Rubinstein: A Course in Game Theory (MIT Press, 1994)
• Robert Aumann: Game Theory, in J. Eatwell, M. Milgate, and P. Newman: The New Palgrave, A Dictionary of Economics, Vol. 2 (Macmillan, 1987)
• Martin Osborne: An Introduction to Game Theory (Oxford University Press, 2004)
• Tuomas Sandholm: Distributed Rational Decision Making, in Gerhard Weiss: Multiagent Systems (MIT Press, 1999)
• Wikiludia

• Roger Myerson: Game Theory - Analysis of Conflict (Harvard University Press, 1991)
• Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green: Microeconomic Theory (Oxford University Press, 1995)
• Drew Fudenberg and Jean Tirole: Game Theory (MIT Press, 1991)

Bei weitergehenden Fragen wenden Sie sich bitte an Felix Fischer.