Approximating Values of Generalized-Reachability Stochastic Games

Pranav Ashok; Krishnendu Chatterjee; Jan Kå™etínský; Maximilian Weininger; Tobias Winkler

doi:10.1145/3373718.3394761

Approximating Values of Generalized-Reachability Stochastic Games

Pranav Ashok
, Krishnendu Chatterjee
, Jan Kå™etínský
, Maximilian Weininger
, Tobias Winkler

Informatics 7 - Associate Professorship of Formal Methods for Software Reliability

Technical University of Munich
Institute of Science and Technology Austria (ISTA)
RWTH Aachen University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

17 Scopus citations

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.

Original language	English
Title of host publication	Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020
Publisher	Association for Computing Machinery
Pages	102-115
Number of pages	14
ISBN (Electronic)	9781450371049
DOIs	https://doi.org/10.1145/3373718.3394761
State	Published - 8 Jul 2020
Event	35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 - Saarbrucken, Germany Duration: 8 Jul 2020 → 11 Jul 2020

Publication series

Name	ACM International Conference Proceeding Series

Conference

Conference	35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020
Country/Territory	Germany
City	Saarbrucken
Period	8/07/20 → 11/07/20

Keywords

Anytime algorithm
Multiple Reachability Objectives
Pareto frontier
Stochastic games

Access to Document

10.1145/3373718.3394761

Cite this

Ashok, P., Chatterjee, K., Kå™etínský, J., Weininger, M., & Winkler, T. (2020). Approximating Values of Generalized-Reachability Stochastic Games. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 (pp. 102-115). Article 3394761 (ACM International Conference Proceeding Series). Association for Computing Machinery. https://doi.org/10.1145/3373718.3394761

@inproceedings{f722e7384ab044769704e07ddffbabb1,

title = "Approximating Values of Generalized-Reachability Stochastic Games",

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.",

keywords = "Anytime algorithm, Multiple Reachability Objectives, Pareto frontier, Stochastic games",

author = "Pranav Ashok and Krishnendu Chatterjee and Jan K{\aa}{\texttrademark}et{\'i}nsk{\'y} and Maximilian Weininger and Tobias Winkler",

note = "Publisher Copyright: {\textcopyright} 2020 Owner/Author.; 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020 ; Conference date: 08-07-2020 Through 11-07-2020",

year = "2020",

month = jul,

day = "8",

doi = "10.1145/3373718.3394761",

language = "English",

series = "ACM International Conference Proceeding Series",

publisher = "Association for Computing Machinery",

pages = "102--115",

booktitle = "Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020",

}

Ashok, P, Chatterjee, K, Kå™etínský, J, Weininger, M & Winkler, T 2020, Approximating Values of Generalized-Reachability Stochastic Games. in Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020., 3394761, ACM International Conference Proceeding Series, Association for Computing Machinery, pp. 102-115, 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020, Saarbrucken, Germany, 8/07/20. https://doi.org/10.1145/3373718.3394761

Approximating Values of Generalized-Reachability Stochastic Games. / Ashok, Pranav; Chatterjee, Krishnendu; Kå™etínský, Jan et al.
Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020. Association for Computing Machinery, 2020. p. 102-115 3394761 (ACM International Conference Proceeding Series).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Approximating Values of Generalized-Reachability Stochastic Games

AU - Ashok, Pranav

AU - Chatterjee, Krishnendu

AU - Kå™etínský, Jan

AU - Weininger, Maximilian

AU - Winkler, Tobias

PY - 2020/7/8

Y1 - 2020/7/8

N2 - 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.

AB - 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.

KW - Anytime algorithm

KW - Multiple Reachability Objectives

KW - Pareto frontier

KW - Stochastic games

UR - https://www.scopus.com/pages/publications/85085951334

U2 - 10.1145/3373718.3394761

DO - 10.1145/3373718.3394761

M3 - Conference contribution

AN - SCOPUS:85085951334

T3 - ACM International Conference Proceeding Series

SP - 102

EP - 115

BT - Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020

PB - Association for Computing Machinery

T2 - 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2020

Y2 - 8 July 2020 through 11 July 2020

ER -

Approximating Values of Generalized-Reachability Stochastic Games

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this