Logic and Games

WS 2018/19

News

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

Schedule

Type Date Location   Organizer
V4 Tu 10:30 – 12:00 2350|009 (AH I) Begin 9th October E. Grädel
Th 12:30 – 14:00 1010|101 (I) Begin 11th October E. Grädel
Ü2 Fr 14:30 – 16:00 2350|314.1 (AH III) Begin 19th October

Coursework

Lecture Notes

Content

Objective

Understanding the fundamental concepts and problems of algorithmic game theory, especially the connection of logic and game theory. Knowledge of the logical and algorithmical methods to handle infinite games. Using infinite games as a model to evaluate logical formulae on reactive systems.

Topics

Fundamental concepts in game theory, these include finite and infinite games, model-checking games, determinism, non-determinism, Borel-games, Muller-games and parity games. Complexity and definability of winning regions, algorithmic synthesis and optimisation of winning strategies. Mupltiplayer games and strategic games.

Literature

[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.

Prerequisites

  • Mathematical Logic

Classification

  • 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

Contact

Erich Grädel, Matthias Hoelzel, Katrin Dannert, Richard Wilke