Gastvortrag: Mahsa Shirmohammadi: Stochastic games and strategy complexity
Montag, 03.04.2023, 16.30 Uhr
Ort: RWTH Aachen University, Informatikzentrum - Ahornstr. 55, Erweiterungsgebäude E3, Raum 9222
Vortragende: Mahsa Shirmohammadi
This talk is about winning strategies in Markov decision processes and stochastic games and is aimed at a general computer science audience.
We start by recalling some of the basic notions in game theory, such as values, strategies, and the memory requirements of optimal and ε-optimal strategies. We will describe a set of recent advances on strategy complexity of verification-centered objectives, such as subclasses of parity objectives, in terms of parameters such as the cardinality of the state space, branching factor of the transition function, and whether the game is concurrent or turn-based.