Approximating Values of Generalized-Reachability Stochastic Games

ASHOK, Pranav; Krishnendu CHATTERJEE; Jan KŘETÍNSKÝ; Maximilian WEININGER a Tobias WINKLER. Approximating Values of Generalized-Reachability Stochastic Games. In LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020. ACM, 2020, s. 102-115. ISBN 9781450371049. Dostupné z: https://doi.org/10.1145/3373718.3394761.

Základní údaje

Originální název

Approximating Values of Generalized-Reachability Stochastic Games

Autoři

ASHOK, Pranav; Krishnendu CHATTERJEE; Jan KŘETÍNSKÝ; Maximilian WEININGER a Tobias WINKLER

Vydání

LICS '20: 35th Annual ACM/IEEE Symposium on Logic in Computer Science, Saarbrücken, Germany, July 8-11, 2020. od s. 102-115, 14 s. 2020

Nakladatel

ACM

---

Další údaje

Typ výsledku

Stať ve sborníku

Označené pro přenos do RIV

Ne

Organizační jednotka

Fakulta informatiky

ISBN

9781450371049

DOI

https://doi.org/10.1145/3373718.3394761

---

Anotace

V originále

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.