Institut für Theoretische Informatik, Algorithmik

Vorlesung Algorithmische Spieltheorie

Sommersemester 2010

Allgemeines

  • Termin: Wöchentlich dienstags, 11.30 - 13.00 Uhr
  • Ort: Seminarraum -120, Informatik-Hauptgebäude
  • Prüfungen: Ab dem 20.7., siehe unten

Beschreibung

Das Internet hat bestehenden Märkte transformiert, informiert, und beschleunigt, und auch neue und bisher unvorstellbare Märkte geschaffen. Algorithmen sind die natürliche Umgebung und Standardplatform für strategische Entscheidungen geworden. Andererseits ist das Internet das erste rechnergestützte Medium, das nicht von einem einzigen Ingenieur, Team oder Firma geschaffen wurde, sondern aus der strategischen wechselseitigen Beeinflussung von vielen. Informatiker haben sich, was nicht überraschend ist, der Spieltheorie zugewandt um dieses Medium und die Mechanismen, nach denen es funktioniert, analysieren zu können. Scott Shenker hat gesagt: „Das Internet ist ein Gleichgewicht, wir müssen nur herausfinden von welchem Spiel.“

Dabei ist eine faszinierende Verbindung von Spieltheorie und Algorithmen enstanden, die bereits erfolgreich genutzt wurde, um die Geheimnisse des Internets zu beleuchten. Diese Verbindung nennen wir Algorithmische Spieltheorie.

In dieser Vorlesung werden wir verschiedene Problemstellungen aus der Algorithmischen Spieltheorie behandeln. Wir werden dabei vor allem auf dem Buch „Algorithmic Game Theory“ von Noam Nisan et al. aufbauen, aber auch zum Teil andere Themen besprechen.

Themenliste

Hier ist eine vorläufige Themenliste:

  • Preisfestsetzung: Preisfestsetzung ohne Neid, Maximierung der Einnahmen: Komplexität und Approximationsalgorithmen
  • Algorithmischer Mechanismenentwurf (Kapitel 9): VCG-Mechanismen, Mechanismen für Scheduling, untere Schranken
  • Kostenanteile (Kapitel 15): Die Core eines Spiels, der Shapley-Wert, Group-Strategyproof Mechanismen, und Cross-Monotonic Kostenanteile (obere und untere Schranken).
  • Ineffizienz von Gleichgewichten (Kapitel 17,18): Preis der Anarchie, Preis der Stabilität, Routing-Spiele, Stauspiele.
  • Kombinatorische Auktionen (Kapitel 11): der VCG-Mechanismus, Walras-Gleichgewicht, zielstrebige Spieler, Approximierung der Gewinnerbestimmung, Berechnungsaspekte.
  • Gesponserte Suchauktionen (Kapitel 28): Modelle und Mechanismen, die von aktuellen Suchmaschinen benutzt werden, Eigenschaften von Gleichgewichten, Online-Zuweisung.
  • Einfluss von sozialen Netzwerken: Einflussmodelle (kritische Masse vs. abnehmende Erträge), Submodularität und der Greedy-Algorithmus.

Termine

Datum Thema Kapitel im AGT-Buch
20.04. Einführung, Nash-Gleichgewichte 1.1-3
27.04. Nullsummenspiele, Beste Antworte 1.4, 2.1
04.05. Algorithmus von Lemke-Howson, PPAD 2.3-4
11.05. Einführung Mechanismen 9.1-3
18.05. Kombinatorische Versteigerungen, fokussierte Agenten 11.1-2
25.05. Fokussierte Agenten, Walrasische Gleichgewichte 11.2-3
1.06. W-G, Algorithmischer Mechanismenentwurf 11.3, AMD
8.06. Wahrheitsliebend Schedulen Archer 2.4, 4.2
15.06. Kostenverteilungsspiele 15.1-2
22.06. Mechanismus von Moulin 15.3
29.06. Primal-dual Algorithmus 15.4
6.07. Preis der Anarchie/Stabilität 1, 2, Kap.17
13.07. Lastenverteilungsspiel 20

Prüfungen

Bachelor-/Masters-Studenten koennen sich ab jetzt in QISPOS anmelden, und sollten mir zusätzlich eine Mail schreiben um einen Termin zu bekommen. Diplomstudenten brauchen den bekannten blauen Zettel, und Austauschstudenten eine Prüfungszulassung.

Die Prüfungen werden stattfinden in Büro 319.

Datum Zeit Name/Nummer
20.07. 11:30 1471530
13:00 D. Toshev
13:30 1437043
14:00 1445392 ( + AO)
15:00 1445529
15:30 1458168
16:00 M. Vinkovits
27.08 11:15 D. Funke ( + AO)
13:30 T. Bittner
14:00 1492484
28.09 14:00 T. Becker