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.