Logik und Spiele

WS 2018/19

Aktuelles

  • Due to problems with editing this website we will use the L2P for announcements and for publishing exercise sheets. If you do not have access to this lecture's L2P room, please write to dannert@logic.rwth-aachen.de so you can be added.
  • There will be no lecture on Tuesday, November 20th.
  • Please hand in the solutions to the exercises in groups of two. You may write in either german or english and are free to write per hand or print your solution.

Termine

Art Termin Ort   Veranstalter
V4 Di 10:30 – 12:00 2350|009 (AH I) Beginn 9. Oktober E. Grädel
Do 12:30 – 14:00 1010|101 (I) Beginn 11. Oktober E. Grädel
Ü2 Fr 14:30 – 16:00 2350|314.1 (AH III) Beginn 19. Oktober

Ü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, Katrin Dannert, Richard Wilke