Exam Dates

• The Endterm will take place on 15.02.2027 from 08:20-10:00
• The Retake will take place on 02.04.2027 from 11:00-12:30 in MW 1250

Additional Lecture on Friday, 13.02.26

We will make up the lecture we skipped before Christmas on Friday the 13th of February in room 00.08.038 (The same one as usual).

Material

Lecture Slides and Exercise sheets will be published in our Moodle-Course

Content

In the module students are introduced to the theory of games played on a (finite) graph (also: recursive games with finite state space). 
By means of different variants of reachability games (with/without chance, turn-based/concurrent moves) the students learn the basic definitions and algorithms in the field of mathematical game theory.
Building up on the reachability games more involved quantitative (e.g. Markov decision processes, discouted-payoff games, mean-payoff games, Shapely's stochastic games) and qualitative (e.g. Parity, Rabin, Muller, Streett) variants are discussed.
Further topics include e.g. techniques for reducing memory consumption (e.g. BDDs), tool presentations (e.g. PRISM), games with partial observations, games on pushdown graphs, relations to logics and set theory (e.g. Gale-Stewart games and Martin's determinacy result), or the synthesis of controllers.

Literature

• Filar, Vrieze: Competitive Markov Decision Processes, Springer, 1996
• Grädel, Thomas, Wilke: Automata, Logics, and Infinite Games, Springer 2002
• Perrin, Pin: Infinite Words – Automata, Semigroups, Logics and Games, Elsevier 2004