Scalable Algorithms (ITI)

Proseminar Algorithmische Spieltheorie

im Sommersemester 2024

Thema

Die Spieltheorie ist ein Werkzeug zur mathematischen Modellierung von Situationen in denen verschiedene Akteure strategische Entscheidungen treffen und dadurch miteinander interagieren. Die algorithmische Spieltheorie beschäftigt sich mit algorithmischen Fragestellungen, die in diesem Kontext auftreten. Das Seminar dient als Einführung in die algorithmische Spieltheorie und vermittelt anhand von ausgewählten Beispielen einen Überblick über das Forschungsgebiet. Dabei werden insbesondere Fragen der folgenden Art betrachtet: Hat jedes Spiel ein Gleichgewicht, also einen Zustand in dem alle Akteure mit ihrer Strategie zufrieden sind? Kann man diese Gleichgewichte effizient berechnen? Wie gut oder schlecht sind diese Gleichgewichte verglichen mit einem sozialen (globalem) Optimum? Wie kann man Auktionen entwerfen, sodass alle Bietende einen Anreiz haben, die Wahrheit zu sagen? Wie entwirft man ein gutes Wahlsystem?

Aktuelles

  • Die Homepage wurde mit allgemeinen Informationen zum Ablauf eingerichtet
  • Zeitplan eingefügt
  • Themen aufgelistet

Voraussetzungen

  • Dieses Proseminar hat keine besonderen Voraussetzungen

Allgemeines

Quellen und Betreuung

  • Die Themen werden am 15.04. vorgestellt und verteilt.
  • Jeder Teilnehmer wird von einem Mitarbeiter oder einer Mitarbeiterin betreut. Diese Mitarbeiter stehen für Fragen und Hinweise nach voriger Absprache zur Verfügung.
  • Wir verwenden das Buch „Algorithmic Game Theory“ von Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani (https://doi.org/10.1017/CBO9780511800481)

Anmeldung

  • Alle Plätze sind belegt.

Ablauf

  • Alle Seminarteilnehmer:innen halten einen fünfminütigen Kurzvortrag und einen 35-minütigen Vortrag im Proseminar und steht danach für Fragen der anderen Teilnehmer:innen zur Verfügung.
  • Eine regelmäßige Teilnahme am Seminar wird vorausgesetzt.
  • Spätestens zwei Wochen vor dem Vortragstermin ist das Vortragskonzept mit den jeweiligen Betreuer:innen zu besprechen.
  • Ein vorläufiger Foliensatz ist eine Woche vor dem eigenen Vortrag bei der jeweiligen Betreuer:in abzugeben.
  • Wir empfehlen zu Beginn der Ausarbeitung eine grobe Gliederung mit den jeweiligen Betreuer:innen abzusprechen
  • Die Ausarbeitungen sind spätestens am 15.07. für Feedback an die jeweiligen Betreuer:in abzugeben. Die finale Abgabe erfolgt am 29.07.
  • Die Seminarnote ergibt sich aus der Note für den Vortrag und die Ausarbeitung, sowie der Beteiligung am Seminar.

Zeitplan

Datum Thema Vortrag Betreuung
15.04 Einführung Max
22.04 How To Vortrag + Introduction Torsten
13.05 Kurzvorträge alle
03.06 Grundlagen der Spieltheorie Ruthva Torsten Ueckerdt
Kapitel 1.1-1.3
Nash-Gleichgewicht Franka Max Göttlicher
Kapitel 1.3-1.8
10.06 Komplexität des Nash-Gleichgewichtes Jens Jean-Pierre von der Heydt
Kapitel 2-2.6.5
Network Creation Games Linus Adrian Feilhauer
Kapitel 19-19.3
17.06 Ineffizienz von Gleichgewichten Tobias Marcus Wilhelm
Kapitel 17.3, 21.2-21.3
Routing Games Ella Michael Zündorf
Kapitel 18-18.4
24.06 Selfish Load Balancing Linda Thomas Bläsius
Kapitel 20-20.3
Kooperative Spiele Sophia Laura Merker
Kapitel 15.2-15.6
01.07 Online-Mechanismen Tobi Torsten Ueckerdt
Kapitel 16-16.3.2
Voting Systems and Auctions Manuel Max Göttlicher
Kapitel 9-9.4
08.07 Mechanismus-Design Karina Miriam Goetze
Kapitel 9.4-9.5
Mechanismus-Design ohne Geld Lennard Wendy Yi
Kapitel 10-10.3
15.07 Feedbackabgabe alle
29.07 Finale Abgabe alle

Vorlagen

Für die Ausarbeitung verwenden Sie bitte diese Vorlage.