Approximating Values of Generalized-Reachability Stochastic Games

RWTH Publications (RWTH Aachen)

Abstract

Simple stochastic games are turn-based 2½-player games with a reachability objective. The basic question asks whether one player can ensure reaching a given target with at least a given probability. A natural extension is games with a conjunction of such conditions as objective. Despite a plethora of recent results on the analysis of systems with multiple objectives, the decidability of this basic problem remains open. In this paper, we present an algorithm approximating the Pareto frontier of the achievable values to a given precision. Moreover, it is an anytime algorithm, meaning it can be stopped at any time returning the current approximation and its error bound.

Authors 5

1. Pranav Ashok

   Technical University of Munich

   Affiliation as printed

   Technical University of Munich, Germany

2. Krishnendu Chatterjee

   Institute of Science and Technology Austria

   Affiliation as printed

   IST Austria, Austria

3. Jan Křetínský

   Technical University of Munich

   Affiliation as printed

   Technical University of Munich, Germany

4. Maximilian Weininger

   Technical University of Munich

   Affiliation as printed

   Technical University of Munich, Germany

5. Tobias Winkler Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Germany