Algorithmische Spieltheorie 1+2 (WiSe 2021)

Vorlesung

Dr. Annamaria Kovacs

Mittwoch 10:00 - 12:00
Donnerstag 12:00 - 14:00

Übungsbetrieb

Conrad Schecker

Donnerstag 14:00 - 16:00

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)
  • Eingutauktionen
  • Grundlagen des Mechanismusdesign und VCG Mechanismen
  • Multi-unit Auktionen als ‘einfachste’ kombinatorische Auktionen I-II (Repraesentation, Gebotssprachen, Algorithmen und Komplexitaet, Ehrlichkeit)
  • Spektrum Auktionen
  • Gerechte Teilung (Fair Division - Cake Cutting)
  • Mechanismen ohne Geld (Abstimmungsmechanismen, Single-Peaked Praeferenzen, Stable Matching) I-II
  • Märkte und Sponsored Search
  • Spieltheorie II-III (Nullsummenspiele und das Yao-Prinzip, Wiederholte Spiele, evtl. kooperative Spiele)

Literatur

Eine Auswahl an empfohlener Literatur:

  • Nisan et Al.: Algorithmic Game Theory
  • Schnitger: Internet Algorithmen Teil III.
  • Easley-Kleinberg: Networks, Crowds, and Markets
  • Rothe et Al.: Einfuehrung in Computational Social Choice
  • Nisan: Algorithmic Mechanism Design – Through the lens of Multi-unit auctions
  • Cramton: Spektrum Auction Design
  • Holler-Illing: Einfuehrung in die Spieltheorie

Leistungsnachweise

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

Materialien

Skript

… wird zeitlich bereitgestellt.

Handschriftliches Skript

… wird zeitlich bereitgestellt.

Folien

… wird zeitlich bereitgestellt.

Übungen

… wird zeitlich bereitgestellt.

LaTeX

Nützliches

Klausuren und Prüfungsmaterial

… wird zeitlich bereitgestellt.