Algorithmische Spieltheorie 1+2 (Sommer 2018)
Aktuelles
- Zum Logbuch.
Organisatorisches
- Dozent: Prof. Dr. Martin Hoefer
- Übungsbetrieb: Paresh Nakhe
- Einträge im LSF: Teil 1, Teil 2
- Vorlesung: Dienstag und Donnerstag, 10:15 Uhr - 11:45 Uhr, Magnus-Hörsaal (R.M.S. 11-15)
- Übung: Dienstag, 14:15 - 15:45 Uhr, Hörsaal H9, Jügelhaus
Materialien
Vorlesungsfolien
| Kapitel | Stand | Vorlesungen | |
|---|---|---|---|
| Organisatorisches | Folien | 10.04.2018 | |
| Teil 1: | |||
| Braess-Paradoxon und Preis der Anarchie | Folien | 12.04.2018 | 10.04. |
| Strategische Spiele und Nash-Gleichgewichte | Folien | 04.05.2018 | 12.04. - 19.04. |
| Reine Nash-Gleichgewichte | Folien | 24.10.2018 | 24.04. - 08.05. |
| Online Lernen und korrelierte Gleichgewichte | Folien | 27.05.2018 | 15.05. - 22.05. |
| Preis der Anarchie und Preis der Stabilität | Folien | 22.05.2018 | 24.05. |
| Teil 2: | |||
| Entwurf anreizkompatibler Mechanismen | Folien | 15.06.2018 | 29.05. - 14.06. |
| Sekretäre und Propheten | Folien | 25.06.2018 | 19.06. - 21.06. |
| Mechanismen als Spiele | Folien | 28.06.2018 | 26.06. - 28.06. |
| Mechanismen ohne Geld | Folien | 05.07.2018 | 03.07. - 12.07. |
Videos
Verfügbar auf dieser Seite (mit Zugangsbeschränkung)
Übungsblätter
Teil 1:- Blatt 1, Ausgabe: 11.04.2018. Abgabe bis 17.04.2018, 10:15 Uhr.
- Blatt 2, Ausgabe: 17.04.2018. Abgabe bis 24.04.2018, 10:15 Uhr.
- Blatt 3, Ausgabe: 24.04.2018. Abgabe bis 08.05.2018, 10:15 Uhr.
- Blatt 4, Ausgabe: 08.05.2018. Abgabe bis 15.05.2018, 10:15 Uhr.
- Blatt 5, Ausgabe: 16.05.2018. Abgabe bis 22.05.2018, 10:15 Uhr.
- Blatt 6, Ausgabe: 23.05.2018. Abgabe bis 29.05.2018, 10:15 Uhr.
Teil 2:
- Blatt 7, Ausgabe: 29.05.2018. Abgabe bis 12.06.2018, 10:15 Uhr.
- Blatt 8, Ausgabe: 12.06.2018. Abgabe bis 19.06.2018, 10:15 Uhr.
- Blatt 9, Ausgabe: 21.06.2018. Abgabe bis 03.07.2018, 10:15 Uhr.
- Blatt 10, Ausgabe: 03.07.2018. Abgabe bis 10.07.2018, 10:15 Uhr.
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.
Empfohlene Literatur
Mit direktem Bezug zum Stoff der Vorlesung:
- [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.
Für Hintergrund und Kontext in Spieltheorie gibt es viele Standardwerke, wie zum Beispiel
- [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...