Algorithmische Spieltheorie 1+2 (Sommer 2017)


Aktuelles


Beginn 10.10.2017 11.10.2017 12.10.2017
09:20 Uhr ---
10:00 Uhr --- vergeben vergeben
10:40 Uhr --- vergeben
11:20 Uhr ---
14:00 Uhr vergeben vergeben
14:40 Uhr vergeben vergeben
15:20 Uhr
16:00 Uhr vergeben
16:40 Uhr vergeben


Organisatorisches


Di. 10:15 - 11:45 Uhr Vorlesung Magnus-Hörsaal (R.M.S. 11-15)
Do. 10:15 - 11:45 Uhr Vorlesung Magnus-Hörsaal (R.M.S. 11-15)
Di. 14:15 - 15:45 Uhr Übung H 9 (Jügelhaus)


Thema

In modernen Computernetzwerken gibt es häufig Situationen, in denen sich die Beteiligten strategisch verhalten. Service Provider möchten ihre Pakete so schnell oder kostengüstig wie möglich zustellen. Im Cloud-Computing werden Rechenzeit und Speicherplatz geteilt, gemietet oder verkauft, und die Anbieter möchten Gewinne maximieren, die Käufer den Wert ihrer gekauften Services. Anzeigenkunden im Internet möchten ihre Werbebotschaften möglichst billig und sichtbar platzieren, etc. Dadurch entstehen elektronische Märkte, in denen heute Umsätze in Milliardenhöhe erzielt werden. Das Geschäftsmodell von vielen Firmen beruht auf Handel und Vermarktung in solchen Umgebungen.

Die Algorithmische Spieltheorie ist ein junges Teilgebiet der Algorithmentheorie, in dem Systeme analysiert werden, die durch die Interaktion von vielen rationalen Agenten geprägt sind. Die Algorithmen suchen z.B. für einzelne Agenten optimale Strategien, oder sie müssen auf der Systemseite mit strategischem Verhalten von Nutzern umgehen. Typische Fragestellungen betreffen die Analyse der Anreize, sowie den Entwurf von Algorithmen für die Optimierung in diesen Umgebungen. Dazu werden Ideen aus der Spieltheorie kombiniert mit Approximations­algorithmen, verteiltem Rechnen, und Einsichten aus der Komplexitätstheorie.


Inhalt und Ablauf (vorläufig)

Datum Inhalt
18.04. Grundlagen der Spieltheorie, Gleichgewichte
20.04. Existenz und Berechnung von Gleichgewichten, PPAD
25.04. 2-Personen Nullsummenspiele
27.04. Auslastungsspiele: Reine Gleichgewichte, Beste-Antwort-Dynamik
02.05. Auslastungsspiele: Matroidspiele
04.05. Wardropspiele, Braess-Paradoxon, Preis der Anarchie
09.05. Netzwerkverbindungsspiele (Annamaria Kovacs)
11.05. keine Vorlesung
16.05. Online Lernen: Grundlagen
18.05. Online Lernen: Nullsummenspiele
23.05. Online Lernen: Konkave Spiele
25.05. Christi Himmelfahrt, keine Vorlesung
30.05. Online Lernen: Swap-Regret und korrelierte Gleichgewichte
01.06. Preis der Anarchie, Smoothness
Ende Teil 1 -- Beginn Teil 2
06.06. Anreizkompatible Mechanismen: Grundlagen, VCG-Technik
08.06. Anreizkompatible Mechanismen: Myersons Lemma, Single-Parameter
13.06. Anreizkompatible Mechanismen: Optimale Mechanismen
15.06. Fronleichnam, keine Vorlesung.
20.06. Anreizkompatible Mechanismen: Kombinatorische Auktionen, Single-Minded
22.06. keine Vorlesung
27.06. Mechanismen als Spiele: Sponsored Search, Generalized-Second-Price
29.06. Mechanismen als Spiele: Gut-Gebote, Preis der Anarchie, Smoothness
04.07. Mechanismen als Spiele: Walras-Gleichgewicht, ansteigende Auktionen, Spektrumsauktionen
06.07. Mechanismen ohne Geld: Wahlen, Unmöglichkeitsresultate
11.07. Mechanismen ohne Geld: Präferenzen mit Single-Peak, Hausallokation
13.07. Mechanismen ohne Geld: Organspende, Stabiles Matching
18.07. Fragestunde, Wiederholung
20.07. Besprechung Übung 11, Wiederholung

Übungen

In der Regel wird jeden Dienstag ein neues Übungsblatt veröffentlicht. Die Abgabe erfolgt spätestens am folgenden Dienstag vor Beginn der Vorlesung. Alternativ können Lösungen auch bis spätestens Dienstag vor Beginn der Vorlesung in den Briefkasten zwischen Raum 114 und 115 eingeworfen werden. Lösungen können gemeinsam erarbeitet werden, müssen aber individuell aufgeschrieben und abgegeben werden.

Teil 1: Blatt 1-6.
Teil 2: Blatt 7-11.


Material

Foliensätze zu den einzelnen Kapiteln:

Videos:

Zusätzliches Material:


Empfohlene Literatur

Mit direktem Bezug zum Stoff der Vorlesung:


Für Hintergrund und Kontext in Spieltheorie gibt es viele Standardwerke, wie zum Beispiel