Modul: Algorithmische Spieltheorie (Algorithmic Game Theory)

Wintersemester 2022/2023

• Vorlesung (4 SWS):
  • Dienstag im Hörsaal 5A (Geb. 25.11) und
  • Donnerstag im Hörsaal 5D (Geb. 25.21),
  jeweils von 14:30 Uhr bis 16:30 Uhr (mit einer kurzen Pause in der Mitte).
• Übungen (2 SWS): siehe HIS-LSF.

Dozent: Prof. Dr. Jörg Rothe

Übungsleitung: Dr. Anna Kerkmann, Joanna Kaczmarek, Tessa Seeger und Roman Zorn

---

Allgemeines:

• Diese Veranstaltung kann im Master-Studiengang Informatik besucht werden. Studierende im Bachelor-Studiengang Informatik können dieses Modul auch besuchen und sich später anrechnen lassen.

• Außer den formalen Zugangsvoraussetzungen für WP-Module im Master sind keinerlei spezielle Vorkenntnisse nötig. Es wird nur ein grundlegendes Verständnis mathematischer und informatischer (z.B. algorithmischer) Begriffe vorausgesetzt und ein Interesse am Spielen und der Theorie des Spielens erwartet.

• Für dieses Modul müssen Sie sich im LSF anmelden, damit Sie sich später beim Prüfungsamt für die Prüfung anmelden können.

• Für das Modul "Algorithmische Spieltheorie" gibt es 10 Leistungspunkte.

• Weitere Informationen finden Sie auf der ILIAS-Seite für dieses Modul.

Prüfung:

• Die Prüfung findet in Form einer schriftlichen Klausur am Montag, dem 6. Februar 2023, ab 8:30 Uhr in den Hörsälen 5A und 5E statt.

• Zulassungsvoraussetzung: Man muss dreimal in den Übungen vorrechnen und dabei eine größtenteils korrekte Lösung präsentieren.

• Anmeldung: beim Akademischen Prüfungsamt über das Studierendenportal.

• Bitte bringen Sie Ihren Personal- und Studierendenausweis mit zur Klausur. Falls der Platz auf den von uns ausgeteilten Klausurblättern nicht reicht, sollten Sie sich auch eigene Blätter mitbringen.

• Erlaubte Hilfsmittel: Vorlesungsmitschriften, Bücher, Übungsblätter, Gedächtnis.

• Nicht erlaubte Hilfsmittel: Mobiltelefone und ähnliche Kommunikationsgeräte, Kommiliton/inn/en, programmierbare Taschenrechner.

• Hat man sich zur Klausur angemeldet, so kann man bis eine Woche vor der Klausur noch zurücktreten, ohne dass dies als ein Fehlversuch gewertet wird. Die Abmeldung von der Klausur muss über das Akademische Prüfungsamt erfolgen. Bitte sagen Sie auch mir Bescheid (am besten per E-Mail).

• Wer zur Klausur nicht zugelassen ist, aber angemeldet war, muss sich nicht extra beim Prüfungsamt abmelden, sondern wir teilen dem Prüfungsamt die Nichtzulassung mit, die nicht als Fehlversuch gewertet wird.

Probeklausur:

Übungen:

• Der Übungsbetrieb beginnt in der zweiten Woche der Vorlesungszeit, in der das erste Übungsblatt besprochen wird.

• Die Übungen werden betreut von Dr. Anna Kerkmann, Joanna Kaczmarek, Tessa Seeger und Roman Zorn.

• Für die Übungen sind die Aufgaben auf den Übungsblättern zu lösen. Die Lösungen werden in den Übungen besprochen und es wird eine aktive Beteiligung aller Studierenden erwartet (d.h., man muss dreimal in den Übungen vorrechnen und dabei eine größtenteils korrekte Lösung präsentieren).

• Die Übungsblätter können am Dienstag hier von dieser Website heruntergeladen werden. Das erste Blatt erscheint am 11.10.2022.

  Woche Nr.	Übungsblätter	Musterlösungen
  1	Übungsblatt 1	Musterlösung 1
  2	Übungsblatt 2	Musterlösung 2
  3	Übungsblatt 3	Musterlösung 3
  4	Übungsblatt 4	Musterlösung 4
  5	Übungsblatt 5	Musterlösung 5
  6	Übungsblatt 6	Musterlösung 6
  7	Übungsblatt 7	Musterlösung 7
  8	Übungsblatt 8	Musterlösung 8
  9	Übungsblatt 9	Musterlösung 9
  10	Übungsblatt 10	Musterlösung 10
  11	Übungsblatt 11	Musterlösung 11
  12	Übungsblatt 12	Musterlösung 12

Pingo:

• Pingo 1
• Pingo 2
• Pingo 3
• Pingo 4
• Pingo 5
• Pingo 6
• Pingo 7
• Pingo 8
• Pingo 9
• Pingo 10
• Pingo 11

Empfohlene Literatur:

Jörg Rothe (ed.): "Economics and Computation: An Introduction to Algorithmic Game Theory, Computational Social Choice, and Fair Division", Springer-Verlag, 2015 Für die Vorlesung relevant sind: Chapter 2: "Noncooperative Game Theory", Piotr Faliszewski · Irene Rothe · Jörg Rothe, pp. 41 - 134 Chapter 3: "Cooperative Game Theory", Edith Elkind · Jörg Rothe, pp. 135 - 193

Jörg Rothe, Dorothea Baumeister, Claudia Lindner, and Irene Rothe: "Einführung in Computational Social Choice: Individuelle Strategien und kollektive Entscheidungen beim Spielen, Wählen und Teilen", Spektrum Akademischer Verlag, 2011 Für die Vorlesung relevant sind: Kapitel 2: "Nichtkooperative Spiele: Gegeneinander spielen", Irene Rothe · Jörg Rothe, pp. 25 - 91 Kapitel 3: "Kooperative Spiele: Miteinander spielen", Jörg Rothe, pp. 93 - 118

Ergänzende Literatur:

• G. Chalkiadakis, E. Elkind and M. Wooldridge: "Computational Aspects of Cooperative Game Theory", Morgan and Claypool Publishers, 2011

• N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani: "Algorithmic Game Theory", Cambridge University Press, 2007

• B. Peleg and P. Sudhölter: "Introduction to the Theory of Cooperative Games", Kluwer Academic Publishers, 2003

• M. Osborne and A. Rubinstein: "A Course in Game Theory", MIT Press, 1994

• J. von Neumann and O. Morgenstern: "Theory of Games and Economic Behavior", Princeton University Press, 1944

Skript:

• Chapter 1: Noncooperative Game Theory
  • Section 1.1: Foundations of Noncooperative Game Theory
  • Section 1.2: Nash Equilibria in Mixed Strategies
  • Section 1.3: Checkmate: Trees for Games with Perfect Information
  • Section 1.4: Full House: Games with Incomplete Information
  • Section 1.5: How Hard Is It to Find a Nash Equilibrium?

• Chapter 2: Cooperative Game Theory
  • Section 2.1: Foundations of Cooperative Game Theory
  • Section 2.2: Convex Games, Simple Games, and Weighted Voting Games
  • Section 2.3: Power Indices in Simple Games
  • Section 2.4: Complexity of Problems for Weighted Voting Games
  • Section 2.5: Hedonic Games (nicht prüfungsrelevant)

© Copyright seit 2000 Komplexitätstheorie & Kryptologie • Impressum • Datenschutz • Kontakt