Algorithmische Spieltheorie 1+2 (WiSe 2021)

Bitte schauen Sie regelmäßig hier vorbei, und verwenden Sie Ihre studentische E-Mail-Adresse (…@stud.uni-frankfurt.de), wenn Sie uns E-Mails schreiben. Wir haben immer wieder Probleme, dass unsere Antworten in Spamfiltern landen.

Die Veranstaltung ‘Algorithmische Spieltheorie’ findet teilweise in Präsenz statt. In den Räumen der Goethe Uni gelten die 3G Regeln. Der zweite Teil (AST 2) wird aufgezeichnet, und die entsprechenden Links dazu rechtzeitig online gestellt. (Ein Video von der ‘Algorithmischen Spieltheorie’ Vorlesung von Prof. Hoefer aus 2018 ist von dieser Webseite unten erreichbar.)

Vorlesung

Dr. Annamaria Kovacs

Mittwoch 10:00 - 12:00
Donnerstag 12:00 - 14:00 H4 Hörsaalgebäude Bockenheim

ACHTUNG! Die Vorlesung am Mittwoch 26.1. findet online statt. Den Link zum BBB Raum finden Sie hier

Die Vorlesung und Übung jeden Donnerstag finden weiterhin in Präsenz statt; die Übung in R-M Str.11-15, SR 11. Die Vorlesung in H.4., und wird vom StudiumDigitale aufgezeichnet. Den Link der Donnerstag Aufzeichnung finden Sie hier. Im BBB Raum findet freitags das kurze online-Tutorium statt.

Zur Corona Lage:

  • Sollte sich jemand (der/die den Unterricht besucht) mit Corona infiziert haben, sind wir für eine Meldung dankbar, damit wir diese Info anonym weitergeben können.

Der Termin für die Klausur ist der Donnerstag 10.3.2022.

(Alle Klausurtypen (AST1,2,1+2) finden zu diesem Termin statt. Die Uhrzeit wird von der Uni-Administration festgelegt. Eine Nachklausur wird voraussichtlich nicht stattfinden, aber mündliche Prüfungen werden ab Anfang Mai möglich sein.)

Übungsbetrieb

Conrad Schecker

Donnerstag 14:00 - 16:00 SR 11. (R.-M. Straße 11-15.)

  • Bitte melden Sie sich für die Teilnahme an den Übungen per E-Mail bei Conrad Schecker (schecker@em.uni-frankfurt.de) an. Geben Sie dabei Ihren (vollständigen) Namen und Ihre Matrikelnummer an. Geben Sie auch Ihre studentische E-Mail-Adresse an, falls Sie für die Anmeldung eine andere E-Mail-Adresse verwenden.
    Nur wer zu den Übungen angemeldet ist, wird seine/ihre Übungsblätter abgeben können.
    Mit Vorrechnen in den Übungen können Übungspunkte erworben werden (siehe unten).
    Die Teilnahme an den Übungen wird sehr empfohlen! Eine Plusnote zur Klausur kann erworben werden (siehe unten).

Die Teilnahme am Übungsbetrieb wird dringend empfohlen, ist jedoch nicht verpflichtend. Durch die Aufgaben wird Bekanntes vertieft und weiterführende Inhalte vermittelt. Des Weiteren kann durch das Lösen der Aufgaben 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 wurde.

Es besteht die Möglichkeit, durch Vorrechnen in den Tutorien Bonuspunkte zu erwerben, welche zu den erworbenen Übungspunkten hinzuaddiert werden. Dabei gelten die folgenden Regeln:

  • Pro Übungsblatt wird der Bonus höchstens einmal pro Person vergeben.
  • Beim ersten Vorrechnen gibt es 5 Bonuspunkte.
  • Beim zweiten Vorrechnen gibt es 4 Bonuspunkte.
  • Beim dritten Vorrechnen gibt es 3 Bonuspunkte.
  • Beim vierten Vorrechnen gibt es 2 Bonuspunkte.
  • Jedes weitere Vorrechnen gibt 1 Bonuspunkt.

Die Bearbeitung der Aufgaben in Gruppen wird begrüßt, jedoch muss von jedem Teilnehmer eine individuelle Ausarbeitung eingereicht werden. Blätter, auf denen plagiierte oder kopierte Lösungen gefunden werden, werden für jeden Betroffenen nicht bewertet. Im Wiederholungsfall kann es zur Aberkennung sämtlicher Bonifikation kommen.

Hinweise zu den Übungsabgaben

  • Übungsblätter werden in der Regel wöchentlich freitags ausgegeben.
  • Die Abgabefrist für ein Blatt endet jeweils 10 Tage später, am Montag um 12:00 Uhr.
  • Da es eine Online-Abgabe gibt, ist eine Abgabe per E-Mail dieses Semester nicht vorgesehen.

Zur Online-Abgabe:

  • Die Abgabe wird Ihnen automatisch zugeordnet; bitte vermerken Sie trotzdem Ihren Namen und Ihre Matrikelnummer darauf.
  • Laden Sie Ihre Lösung nicht in der letzten Minute hoch. Wir können den reibungslosen Ablauf nicht garantieren, wenn alle 5 Minuten vor Schluss abgeben wollen.
  • Wir nehmen Lösungen nur als eine PDF-Datei entgegen. Bitte stellen Sie sich darauf ein und testen Sie vorher.
    • Am besten ist es, wenn Sie gleich LaTeX verwenden. Das ist gut lesbar und erzeugt kleine Dateien. Wir bieten auch eine LaTeX Vorlage an.
    • Zur Not können Sie Scans oder Bilder zu einer PDF 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.

Inhalt

  • 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:

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

Klausur (90 Min für 5 CP; 180 Min für 10 CP) oder mündliche Prüfung.

Materialien

Skript

LaTeX Zusammenfassung des Skripts

Handschriftliches Skript

AST 1

Woche 1 (zusätzlich vom Roughgarden Buch: 1.1 und 1.3)

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

Woche 3 (zusätzlich vom Roughgarden Buch: 11.1-2, Easley-Kleinberg: 24.2) Artikel Hardin Science (1968)

Woche 4 (zusätzlich vom Roughgarden Buch: Lecture 2) Artikel FAZ

Woche 5 (zusätzlich vom Roughgarden Buch: 9.4, 10.1)

Woche 6 (zusätzlich vom Roughgarden Buch: 3.1, 3.2)

Woche 7 Teil 1 (zusätzlich vom Roughgarden Buch: 3.3, Lecture 7)

Woche 7 Teil 2

Woche 8 Teil 1

AST 2

Woche 8 Teil 2 (Nisan: AMD-Through the Lens of…)

Woche 9 (Nisan: AMD-Through the Lens of…)

Woche 10

Woche 11 (zusätzlich vom Roughgarden Buch: 2.6 (und für Interessierte 3), Easley-Kleinberg Ch 15.7, 15.8 )

Woche 12

Folien

AST 1

Spieltheorie Grundlagen

Spiele in Netzwerken (Videos V05, V06 von Prof. Hoefer)

Eingutauktionen (Video V13 von Prof. Hoefer)

Mechanismen ohne Geld (Video V21, V22, V23 von Prof. Hoefer)

Einfache VCG Mechanismen (Video V13 von Prof. Hoefer)

Cake Cutting siehe auch 1 2 3

AST 2

Multiunit Auktionen

Matching Markets

Verteilte Mechanismen

Spieltheorie Fortsetzung

Übungen

AST 1

Übung 1 (LaTeX Datei)

Übung 2 (LaTeX Datei)

Übung 3 (LaTeX Datei)

Übung 4 (LaTeX Datei)

Übung 5 (LaTeX Datei)

Übung 6 (LaTeX Datei)

Übung 7 (LaTeX Datei)

AST 2

Übung 8 (LaTeX Datei)

Übung 9 (LaTeX Datei)

Übung 10 (LaTeX Datei)

Übung 11 (LaTeX Datei)

Übung 12 (LaTeX Datei)

Videoaufnahme der Vorlesungen von Prof. Hoefer aus 2018

HIER (Benutzername und Passwort werden analog zu unseren gebildet, mit ‘g’ statt ‘s’.)

LaTeX

Nützliches

Klausuren und Prüfungsmaterial

… wird zeitlich bereitgestellt.