English English

Termine

Termin / Ort
Beginn
Dozent
Mo 10:15-11:45 /
Seminarraum 5056 (geändert)
22.10.2007
Berthold Vöcking, Simon Fischer
Übung 14-tägig
Do 10:15-11:45 / Seminarraum 4017
Thomas Kesselheim

Achtung: Am 15.10.2007 ist dies.

Inhalt der Vorlesung

Mit Hilfe spieltheoretischer Methoden können vielfältige strategische Entscheidungsprozesse modelliert werden. Ursprünglich entstammt das große Gebiet der Spieltheorie der Ökonomie. In dieser Vorlesung betrachten wir sowohl spieltheoretische Anwendungen im Bereich der Informatik (z.B. für Routing- und Lastbalancierungsprobleme, bei denen individuelle Teilnehmer eigennützig agieren) als auch umgekehrt Beiträge der Informatik für die Spieltheorie, z.B. Algorithmen zur Berechnung von Gleichgewichten.

Inhalt (vorläufig)

  1. Einführung in die Spieltheorie
    2. Skript zu diesem Teil
    1. Einfache Lösungskonzepte: Dominanz und Rationalisierbarkeit
    2. Gleichgewichte in Nullsummenspiele
    3. Existenz von Nash-Gleichgewichten
    4. Die Komplexität von Nashgleichgewichten
    5. Berechnung von Nash-Gleichgewichten
      (Vom Lemke-Howson-Algorithmus ist nur die geometrische Interpretation prüfungsrelevant.)
    6. Evolutionäre Spieltheorie
  2. Das Routingmodell von Wardrop
    1. Spieltheoretische Formulierung des Routingproblems
    2. Existenz und Berechnung von Gleichgewichten
    3. Kosten der Stabilität
    Zu diesem und dem nächsten Teil gibt es ein stichpunktartiges Skript in Englisch, das im wesentlichen die beiden folgenden, gut zu lesenden Artikel zusammenfasst:
    • José R. Correa, Andreas S. Schulz, and Nicolás E. Stier-Moses: "On the inefficiency of equilibria in nonatomic congestion games." In Proc. 11th International Integer Programming and Combinatorial Optimization Conf. (IPCO), volume 2509 of Lecture Notes in Computer Science, pages 167–181. Springer, 2005.
    • Tim Roughgarden and Éva Tardos: "How bad is selfish routing?" Journal of the ACM, 49(2):236–259, 2002.
  3. Auslastungsspiele
    1. Existenz von Gleichgewichten
    2. Berechnung von Gleichgewichten in symmetrischen Netzwerkcongestionspielen
    3. PLS-Schwere von Gleichgewichten in asymmetrischen Netzwerkcongestionspielen
    Dieser Teil basiert auf den Artikeln:
    • Alex Fabrikant, Christos Papadimitriou, and Kunal Talwar: The complexity of pure Nash equilibria. In Proc. 36th Annual ACM Symposium on Theory of Computing (STOC), pages 604–612, 2004.
    • Robert W. Rosenthal: A class of games possessing pure-strategy Nash equilibria. International Journal of Game Theory, 2:65–67, 1973.
    • Heiner Ackermann, Heiko Röglin, and Berthold Vöcking. On the impact of combinatorial structure on congestion games. In Proc. 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 613–622, 2006.
  4. Lastbalancierung

    Die Vorlesung folgt Kapitel 20 aus dem Buch: Noam Nisan, Tim Roughgarden, Éva Tardos und Vijay V. Vazirani (Hrsg.): Algorithmic Game Theory, 2007

    Prüfungsrelevant sind die Abschnitte 20.1, 20.2.1, 20.3.1 und 20.4.1.
  5. Mechanism Design
    1. Auktionen
    2. Cost Sharing

Übung