News

• The lecture will be held in-person.
• Remember to bring a valid 3G-certificate and ID to each lecture/exercise class.
• Please refer to the Moodle course room for all further information and material (please write us an email if you do not have access to Moodle).

Schedule

Type	Date				Location		Organizer
V4	Tu	12:30	–	14:00	1010|141 (IV)	Begin 12th October	E. Grädel
	We	12:30	–	14:00	1010|101 (I)	Begin 13th October	E. Grädel
Ü2	Th	12:30	–	14:00	1010|141 (IV)	Begin 21th October	M. Naaf

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 Naaf