Vorlesung Algorithmische Spieltheorie

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

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.

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.

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.