Algorithmische Spieltheorie 1+2 (WiSe 2025)

Aktuelles

Vorlesung

Dr. Annamaria Kovacs

Mittwoch, 10:00 - 12:00 Uhr im Magnus-Hörsaal (Informatikgebäude)

Donnerstag, 12:00 - 14:00 Uhr im Magnus-Hörsaal (Informatikgebäude)

Übungsbetrieb

Conrad Schecker (schecker@em.uni-frankfurt.de)

Donnerstag, 14:00 - 16:00 Uhr im SR 11 (Informatikgebäude)

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch selbstständiges Lösen der Übungsaufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch die erfolgreiche Teilnahme am Übungsbetrieb eine Bonifikation von bis zu einem Notenschritt für die Prüfung erworben werden. Die Bonifikation wird erst angerechnet, wenn die Klausur selbstständig bestanden und im Tutorium mindestens einmal pro Vorlesungsteil vorgerechnet wurde.

• Übungsblätter werden in der Regel wöchentlich freitags ausgegeben.
• Die Abgabefrist für ein Übungsblatt endet am Samstag in der darauffolgenden Woche um 12:00 Uhr.
• Die Abgabe erfolgt online über einen individuellen Link, den Sie nach erfolgter Anmeldung erhalten haben.
• Die Zuordnung der Abgaben erfolgt automatisch. Dennoch schadet es nicht, Namen oder Matrikelnummer darauf zu vermerken.
• Wir nehmen Abgaben in Form von einer PDF-Datei mit maximal 10MB entgegen. Schwer lesbare Abgaben werden nicht bewertet.
  • Gut lesbare und kleine Dateien erhält man bei der Verwendung von LaTeX. Wir bieten auch eine LaTeX-Vorlage an.
  • Alternativ können Sie auch Scans oder Bilder zu einer PDF-Datei zusammenfügen. Wenn Sie dafür ein Smartphone verwenden, nutzen Sie eine Scannerapp Ihres Vertrauens. Damit lassen sich Ränder wegschneiden und Seiten gerade ziehen.
• Laden Sie Ihre Lösung nicht in letzter Minute hoch. Ein reibungsloser Ablauf kann ansonsten nicht garantiert werden.
• Vergewissern Sie sich, die korrekte Datei hochgeladen zu haben.

Plagiate und KI-Tools

Es wird empfohlen, in Gruppen über die Aufgaben zu diskutieren, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Zur Lösung der Aufgaben ist es nicht nötig, externe Quellen zu verwenden, sofern nicht anders angegeben. Sollten dennoch Quellen verwendet werden, die nicht von uns bereitgestellt wurden, sind diese nach den Regeln der guten wissenschaftlichen Praxis anzugeben. Insbesondere ist die Eigenleistung eindeutig zu kennzeichnen, denn nur diese wird bewertet. Die Verwendung von KI-Tools ist untersagt. Abgaben, die plagiierte, kopierte oder nicht selbstständig erarbeitete Lösungen enthalten, werden für jeden Betroffenen mit 0 Punkten bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Aktive Beteiligung am Tutorium

Eine Bonifikation für die Prüfung wird nur bei aktiver Beteiligung am Tutorium gewährt, daher muss für jeden Vorlesungsteil mindestens einmal vorgerechnet werden. Darüber hinaus können Bonuspunkte durch freiwilliges Vorrechnen gesammelt werden. Dieser Bonus wird pro Person höchstens einmal pro Übungsblatt vergeben. Beim ersten freiwilligen Vorrechnen gibt es 3 Bonuspunkte und beim zweiten freiwilligen Vorrechnen gibt es 2 Bonuspunkte. Danach gibt es für jedes weitere freiwillige Vorrechnen einen Bonuspunkt.

Inhalt

Die Veranstaltung besteht aus zwei Teilen.

• Spieltheorie I (Grundlagen)
• Spiele in Netzwerken
• Einfache ehrliche Mechanismen, Eingutauktionen
• Mechanismen ohne Geld (Abstimmungsmechanismen, Single-Peaked Präferenzen, Stable Matching)
• Gerechte Teilung (Fair Division - Cake Cutting)

• Grundlagen des Mechanismusdesign und VCG Mechanismen

• Multi-unit Auktionen als ‘einfachste’ kombinatorische Auktionen I-II (Repräsentation, Gebotssprachen, Algorithmen und Komplexität, Ehrlichkeit)
• verteilte Mechanismen
• Märkte und Sponsored Search
• Spieltheorie II-III (Nullsummenspiele und das Yao-Prinzip, Wiederholte Spiele, evtl. kooperative Spiele, Komplexität der Berechnung von Nash-Gleichgewichten)

Literatur

Eine Auswahl an empfohlener Literatur:

• Roughgarden: Twenty Lectures on Algorithmic Game Theory
• Easley-Kleinberg: Networks, Crowds, and Markets
• Rothe et Al.: Einführung in Computational Social Choice

• Nisan: Algorithmic Mechanism Design – Through the lens of Multi-unit auctions direkter Zugang

• Nisan-Roughgarden-Tardos-Vazirani: Algorithmic Game Theory
• Holler-Illing: Einführung in die Spieltheorie
• Schnitger: Internet Algorithmen Teil III.
• Cramton: Spektrum Auction Design

Teilnahmevoraussetzungen

• Im Master: keine.

• Im Bachelor PO-2019: 25 CP aus den Basismodulen. Bitte beachten Sie, dass im Bachelor PO19 nur die erste Hälfte (AST1 5CP) angerechnet werden kann. (AST2 kann ggf. für ein zukünftiges Master Studium im Voraus angerechnet werden. Vom Prüfungsamt haben wir folgende Auskunft erhalten: Mastermodule während des Bachelors dürfen “im Voraus” gemacht werden, wenn mindestens 115 CP im Bachelor erfolgreich erbracht wurden und die Basismodule abgeschlossen sind. Die Studierenden müssen die Prüfung dann schriftlich bei uns anmelden.)

Leistungsnachweise

Die Klausur findet am Montag, den 09. März 2026 statt und dauert 180 Minuten, falls AST1+2 geprüft wird; oder 90 Minuten, falls nur AST1 oder nur AST2 geprüft wird.

Materialien

Skript

LaTeX-Zusammenfassung des Skripts

Handschriftliches Skript

AST 1

Woche 1 Ergänzung 1 Ergänzung 2

Woche 2 (zusätzlich vom Roughgarden Buch: 15.1-3)

Folien

AST 1

Spieltheorie Grundlagen

Spiele in Netzwerken (Teil)

Übungen

AST 1

Übungsblatt 1. Abgabe bis 25.10.2025, 12:00 Uhr.

Übungsblatt 2. Abgabe bis 01.11.2025, 12:00 Uhr.

Übungsblatt 3. Abgabe bis 08.11.2025, 12:00 Uhr.

Videos

Vorlesungen von Prof. Hoefer aus 2018. (Benutzername und Passwort werden analog zu unseren gebildet, mit ‘g’ statt ‘s’.)

LaTeX

Nützliches

• LaTeX-Vorlage
• LaTeX-Cheat-Sheet

Klausuren und Prüfungsmaterial

Altklausuren