Hauptseminar Multiagentensysteme:
Spieltheorie und Implementierungstheorie

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

Felix Brandt
Felix Fischer
Paul Harrenstein

Mittwoch, 14-16 Uhr
Oettingenstr. 67, Oe 0.41

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 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. Seit einiger Zeit herrscht eine rege Interaktion zwischen Spieltheorie und Informatik. Zum einen werden Konzepte aus der Spieltheorie zur formalen Analyse verteilter Systeme 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. Ein weiterer Schwerpunkt liegt auf dem Entwurf von Mechanismen und Protokollen zur verteilten Entscheidungsfindung. Letzteres bezeichnet man häufig auch als "inverse Spieltheorie", da hier "Spiele" mit wünschenswerten Eigenschaften konstruiert werden (z.B. Auktionen oder Wahlverfahren).

• Normal-form games
  Utility theory, prisoner's dilemma, solution concepts, (iterated) dominance, security level, rationalizability
• Nash equilibria
  Pure equilibria, mixed equilibria, zero-sum games, refinements of Nash equilibria (strong, coalition-proof, trembling-hand-perfect, etc.), correlated equilibria
• Extensive-form games
  Subgame perfect equilibria, centipede example, imperfect and incomplete information
• Cooperative game theory
  The core, Shapley value, stability
• Social choice theory
  Voting rules, Condorcet paradox, Arrow's impossibility
• Implementation theory I
  Revelation principle, Gibbard-Satterthwaite impossibility, Nash implementation
• Implementation theory II: Mechanism Design
  Quasilinear Preferences, VCG mechanism, Bayes Nash implementation
• Auction theory
  English, Dutch, Vickrey, revenue equivalence, combinatorial auctions

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)

Spezielle Literatur zu den einzelnen Themen wird vom jeweiligen Betreuer zur Verfügung gestellt.

Online:

• Robert Aumann: Game Theory, in J. Eatwell, M. Milgate, and P. Newman: The New Palgrave, A Dictionary of Economics, Vol. 2 (Macmillan, 1987)
• Tuomas Sandholm: Distributed Rational Decision Making, in Gerhard Weiss: Multiagent Systems (MIT Press, 1999)
• Matthew Jackson: A Crash Course in Implementation Theory (Caltech Working Paper, 1999)
• David Parkes: Classic Mechanism Design (Chapter 2 of Parkes' PhD thesis, 2001)
• Rajdeep Dash, Nicholas Jennings, and David Parkes: Computational Mechanism Design: A Call to Arms (IEEE Intelligent Systems 18(6), 2003)
• Wikiludia

• Martin Osborne and Ariel Rubinstein: A Course in Game Theory (MIT Press, 1994)
• Martin Osborne: An Introduction to Game Theory (Oxford University Press, 2004)
• Roger Myerson: Game Theory - Analysis of Conflict (Harvard University Press, 1991)
• Drew Fudenberg and Jean Tirole: Game Theory (MIT Press, 1991)
• Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green: Microeconomic Theory (Oxford University Press, 1995)

Bei weitergehenden Fragen wenden Sie sich bitte an Felix Fischer.