TU Berlin

FG Kombinatorische Optimierung und GraphenalgorithmenAlgorithmische Spieltheorie

COGA 5-Wheel

Inhalt des Dokuments

zur Navigation

Algorithmische Spieltheorie (ADM III)

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: Kombinatorische Spiele, Gleichgewichtstheorie, Algorithmisches Mechanismen Design, Kombinatorische Auslastungsspiele, Kooperative Spiele.

Kontakt:

Die Vorlesung wird von Britta Peis gehalten.

Sprechstunde: Donnerstags, 14-15 Uhr

Zeitplan:

Wochentag
Uhrzeit
Raum
Vorlesung
Mittwoch
10:15-11:45
MA 212
Vorlesung
Donnerstag
12:15-13:45
MA 212

Art der Veranstaltung:

Die Vorlesung (4 SWS) kann als ADM III angerechnet werden.

Folien

Sortiert nach Datum:

  1. Vorlesung 10. April: Folien (Einleitung: Was sind strategische und kooperative Spiele)
  2. Vorlesung 11. April: Folien (Satz von Nikaido-Isoda)
  3. Vorlesung 17. April: Folien (Trennende Hyperebenen, Nullsummenspiele)
  4. Vorlesung 18. April: nur Tafel
  5. Vorlesung 24. April : Folien (Wardrop-Modell)
  6. Vorlesung 26. April: nur Tafel (Diskrete Netzwerkfluesse)
  7. Vorlesung 08. Mai: Folien (Congestion Games: Vortrag von Max Klimm)
  8. Vorlesung 15.Mai: Folien (Fixpunkte bei diskreten Mengen)
  9. Vorlesung 16. Mai: nur Tafel
  10. Vorlesung 17. Mai: Folien (Splittable Routing: Vortrag von Phillipp von Falkenhausen)
  11. Vorlesung 23. Mai: Nur Tafel (Supermodulare Spiele)
  12. Vorlesung 24. Mai: Nur Tafel (Endliche Strategiemengen)
  13. Vorlesung 29.Mai: Folien (Einfuehrung kooperativer Spiele)
  14. Vorlesung 30. Mai: Folien (Core)
  15. Vorlesung 06. Juni: Folien (Marginale Vektoren und Greedy)
  16. Vorlesung 07. Juni: Nur Tafel (Das Kern-Konzept)

Hausaufgaben

1. Uebung (Besprechung am Donnerstag, 18. April)

2. Uebung (Besprechung am Donenrstag, 16. Mai)

3. Uebung (Besprechung am Donnerstag, 13. Juni)

Literatur

  • 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.
  • Martin J. Osborne and Ariel Rubinstein, A Course in Game Theory, MIT Press, 2001.
  • Martin J. Osborne, An Introduction to Game Theory, Oxford University Press, 2004.
  • Tim Roughgarden, Selfish Routing and the Price of Anarchy, MIT Press, 2005.
  • Online resources to game theory: [Game Theory .net]
  • M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, 1979.
  • Online resources to complexity theory: [Compendium of NP optimization problems]

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe