Guest Talk: Mahsa Shirmohammadi: Stochastic games and strategy complexity
Monday, April 03, 2023, 4:30pm
Location: RWTH Aachen University, Department of Computer Science - Ahornstr. 55, building E3, room 9222
Speaker: 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.