ADM III Vorlesung: Algorithmische Spieltheorie, SS 2010

LV-Nr.: 3236 L 235

Zeit und Raum:

Art der Veranstaltung:

Inhalt:

Viele Prozesse im Alltag lassen sich als eine Art Spiel zwischen mehreren interagierenden Spielern interpretieren, wobei jeder einzelne Spieler strategisch handelt, um sein eigenes Ziel zu erreichen. Bei hohem Verkehrsaufkommen werden wir zum Beispiel eine Route so auszuwählen, dass wir möglichst schnell unser Ziel erreichen; bei einer Ebay-Auktion versuchen wir, andere Interessenten durch die Abgabe eines möglichst guten Gebots zu überbieten, etc.

Die Spieltheorie, ein interdisziplinäres Gebiet der Mathematik und Wirtschaftswissenschaften, hat sich diese Sichtweise zur Grundlage gemacht und bietet eine Vielzahl von Konzepten und Methoden, um derartige Prozesse analysieren zu können. Sie findet ihre Anwendung unter anderem in Bereichen der Wirtschaft, Ingenieurwissenschaften, Politik, Biologie, Informatik und Mathematik.

Ziel der Vorlesung ist es, einen Überblick über aktuelle Resultate im Bereich der Algorithmischen Spieltheorie zu vermitteln. Schwerpunkte der Vorlesung bilden die folgenden Themen: Berechenbarkeit von Gleichgewichten, Algorithmisches Mechanismen Design, Kombinatorische Lastspiele, Ineffizienz von Equilibria.

Voraussetzungen:

Die Vorlesung richtet sich an Studierende der Mathematik/Informatik im Hauptstudium. Grundkenntnisse aus der Kombinatorischen Optimierung (ADM I + II) sind hilfreich.

Übungen:

References & Links

  1. Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (Eds.), Algorithmic Game Theory, Cambridge University Press, 2007.
    Remark: The book can be accessd online here (username=agt1user, password=camb2agt). Errata.
  2. Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory, MIT Press, 2001.
  3. Martin J. Osborne, An Introduction to Game Theory, Oxford University Press, 2004.
  4. Tim Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press, 2005.
  5. Online resources to game theory: [Game Theory .net]
  6. The Braess paradoxon in press:
  7. M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
  8. Online resources to complexity theory: [Compendium of NP optimization problems]

Kontakt: