Combined Objectives in Simple Stochastic Games

CAU Kiel Seminar , Kiel, DE

SSG are turn-based, perfect information games where states are controlled by Adam, Eve or a randomized environment. The two opposing players compete to maximize/minimize the probability of a given winning condition (the objective of the game).

I will outline a line of research that studies combinations of objectives classically studied for the verification of reactive systems, such as Parity, Mean-Payoff or limit-reward criteria. The aim is to study under which conditions, to what extend, and with how much extra effort a player can achieve multiple objectives simultaneously.

Time permitting, I will outline a recent result that exposes a subtle bug in the literature and shows how to fix it.