Logik und Spiele

WS 2015

Aktuelles

  • Zum zweiten Prüfungstermin werden mündliche Prüfungen abgehalten. Zur Terminvereinbarung wenden Sie sich bitte an Erich Grädel.
  • Die vorläufigen Klausurergebnisse können hier eingesehen werden. Die Einsicht findet am Donnerstag, den 25.02., zwischen 13 und 14 Uhr im Seminarraum des Lehrstuhls (Raum 4116, E1, Informatikzentrum) statt.
  • Das Skript ist nun in der aktualisierten Fassung verfügbar.
  • Weitere Informationen zu iterierter Regret-Minimierung sind im Abschnitt Literatur zu finden.
  • Die Klausur findet am 22.02. um 14:30 Uhr im AH V statt.
  • Ab dem 06.11. findet die Übung regulär um 10:15 Uhr statt.
  • Studierende im Bachelor Informatik, die die Prüfung für den Bachelor anrechnen lassen, können sich nicht in Campus für die Veranstaltung anmelden. Eine Anmeldung zur Vorlesung und zur Übung ist in diesem Fall nicht notwendig, die Anmeldung zur Prüfung erfolgt per E-Mail an Svenja Schalthöfer. Studierende im Bachelor Mathematik können die Veranstaltung nur als vorgezogene Masterprüfung belegen. Um die Veranstaltung im Anwendungsfach Mathematik für den Master Informatik zu belegen, ist ein Antrag an den Prüfungsausschuss Informatik notwendig.
  • Bitte beachten Sie, dass die erste Übung am 30.10. stattfindet. Die Übungen können in Gruppen bearbeitet werden (max. 3 Studenten) und sind spätestens mittwochs um 13:45 Uhr im Kasten am Lehrstuhl (bzw. zuvor in der Vorlesung) abzugeben. Neue Aufgabenblätter werden in der Regel mittwochs auf der Homepage verfügbar sein. Für die Prüfungszulassung muss die Hälfte der Punkte in den Übungen erreicht werden.

Termine

Art Termin Ort   Veranstalter
V4 Mo 10:15 – 11:45 III Beginn 19. Oktober E. Grädel
Mi 12:00 – 13:30 AH III Beginn 28. Oktober E. Grädel
Ü2 Fr 10:15 – 11:45 AH I Beginn 30. Oktober S. Schalthöfer, M. Hoelzel, W. Pakusa

Übungen

Skript

Inhalt

Lernziele

Verständnis der grundlegenden Begriffe und Probleme der algorithmischen Spieltheorie und der Zusammenhänge von Logik und Spieltheorie. Kenntnis der logischen und algorithmischen Methoden zur Behandlung unendlicher Spiele. Verständnis der Anwendungen unendlicher Spiele als Modell reaktiver Systeme und zur Auswertung logischer Formeln.

Themen

Fundamentale Modelle und Begriffe der Spieltheorie. Endliche und unendliche Spiele. Model-Checking-Spiele. Determinierte und nichtdeterminierte Spiele. Borel-Spiele, Muller-Spiele und Paritätsspiele. Komplexität und Definierbarkeit von Gewinnregionen. Algorithmische Synthese und Optimierung von Gewinnstrategien. Mehrpersonenspiele.

Literatur

[1] K. Binmore. Fun and Games: A Text on Game Theory. D.C. Heath, 1992.
[2] R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about Knowledge. MIT Press, 1995.
[3] J. Filar and K. Vrieze. Competitive Markov decision processes. Springer-Verlag, 1996.
[4] D. Fudenberg and J. Tirole. Game Theory. MIT Press, 1991.
[5] E. Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. Springer-Verlag, 2007.
[6] E. Grädel, W. Thomas, and T. Wilke (Eds.). Automata, Logics, and Infinite Games. Springer-Verlag, 2002.
[7] J. Y. Halpern. Reasoning about Uncertainty. MIT Press, 2003.
[8] J. Y. Halpern and R. Pass. Iterated regret minimization: A new solution concept. Games and Economic Behavior, vol. 74(1), pp. 184–207, 2012.
[9] M. J. Holler and G. Illing. Einführung in die Spieltheorie. Springer-Verlag, 2000.
[10] P. Morris. Introduction to Game Theory. Springer-Verlag, 1994.
[11] R. B. Myerson. Game Theory: Analysis of Conflict. Harvard University Press, 1991.
[12] J. von Neumann and O. Morgenstern. Theory of Games and Economic Behavior. John Wiley and Sons, 1944.
[13] M. J. Osborne. An Introduction to Game Theory. Oxford University Press, 2003.
[14] M. J. Osborne and A. Rubinstein. A Course in Game Theory. MIT Press, 1994.
[15] G. Owen. Game Theory. Academic Press, 1995.
[16] D. Perrin and J. Pin. Infinite Words (Automata, Semigroups, Logic and Games). Elsevier, 2004.

Voraussetzungen

  • Mathematische Logik

Zuordnung

  • Mathematik (M.Sc.): Reine Mathematik
  • Informatik (M.Sc.): Theoretische Informatik
  • Lehramtskandidaten Informatik: Mathematische Methoden der Informatik (C)
  • Software Systems Engineering (M.Sc.): Theoretical Computer Science

Rückfragen

Erich Grädel, Matthias Hoelzel, Svenja Schalthöfer, Wied Pakusa