Algorithmische Spieltheorie 1+2 (Sommer 2017)
Aktuelles
- Zum Logbuch.
- Dozent: Prof. Dr. Martin Hoefer
- Übungsbetrieb: Paresh Nakhe
- Klausur: Dienstag 25.07.2017, 9:00-12:00 Uhr, Magnus-Hörsaal (für 5 CP: 9:00-10:30 Uhr).
- Mündliche Prüfungen: 10.-12.10.2017.
- Blatt 1, Abgabe bis 25.04.2017, 10:15 Uhr.
- Blatt 2, Abgabe bis 02.05.2017, 10:15 Uhr.
- Blatt 3, Abgabe bis 16.05.2017, 10:15 Uhr.
- Blatt 4, Abgabe bis 23.05.2017, 10:15 Uhr.
- Blatt 5, Abgabe bis 30.05.2017, 10:15 Uhr.
- Blatt 6, Abgabe bis 06.06.2017, 10:15 Uhr.
- Blatt 7, Abgabe bis 13.06.2017, 10:15 Uhr.
- Blatt 8, Abgabe bis 27.06.2017, 10:15 Uhr.
- Blatt 9, Abgabe bis 06.07.2017, 10:15 Uhr.
- Blatt 10, Abgabe bis 11.07.2017, 10:15 Uhr.
- Blatt 11, Abgabe bis 18.07.2017, 10:15 Uhr.
- Organisatorisches
- Strategische Spiele und Nash-Gleichgewichte (Stand: 25.04.2017)
- Auslastungs- und Potenzialspiele (Stand: 02.05.2017)
- Braess-Paradoxon und der Preis der Anarchie (Stand: 05.05.2017)
- Netzwerkverbindungsspiele und ein Beispiel zur Beste-Antwort-Dynamik (Stand: 14.05.2017)
- Online Lernen (Stand: 18.07.2017)
- Preis der Anarchie (Stand: 31.05.2017)
- Entwurf anreizkompatibler Mechanismen (Stand: 19.09.2017)
- Mechanismen als Spiele (Stand 08.10.2017)
- Mechanismen ohne Geld (Stand 13.07.2017)
- Verfügbar als Stream auf dieser Seite (mit Zugangsbeschränkung)
- Ein Beispiel zu Sperner's Lemma, und ein Video aus den 80ern
- Deutschsprachiger Übersichtsartikel zu Aspekten der Berechnung von Nash-Gleichgewichten.
- [EK] Easley, Kleinberg. Networks, Crowds, and Markets. Cambridge University Press, 2010.
Zugriff mit Lizenz hier. - [NRTV] Nisan, Roughgarden Tardos, Vazirani. Algorithmic Game Theory. Cambridge University Press, 2007.
Non-printable PDF hier. - [R] Roughgarden. Twenty Lectures in Algorithmic Game Theory. Cambridge University Press, 2016.
- [RBLR] Rothe, Baumeister, Lindner, Rothe. Einführung in Computational Social Choice. Spektrum Verlag, 2012.
Zugriff mit Lizenz hier. - [M] Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
- [O] Owen. Game Theory. Academic Press, 2001.
- [OR] Osborne, Runbinstein. A Course in Game Theory. MIT Press, 1995.
- etc...
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 Approximationsalgorithmen, verteiltem Rechnen, und Einsichten aus der Komplexitätstheorie.
Inhalt und Ablauf
| 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