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

 

Abstract:

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.