Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP

Richard Mayr; Sven Schewe; Patrick Totzke; Dominik Wojtczak

doi:10.1007/978-3-030-71995-1_22

Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP

Richard Mayr, Sven Schewe, Patrick Totzke, Dominik Wojtczak

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

Abstract

We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative ω-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability 1 when starting at a given energy level k, is decidable and in NP∩coNP. The same holds for checking if such a k exists and if a given k is minimal.

Original language	English
Title of host publication	Foundations of Software Science and Computation Structures (FOSSACS 2021)
Publisher	Springer Berlin Heidelberg
Pages	427 - 447
Number of pages	21
ISBN (Electronic)	978-3-030-71995-1
ISBN (Print)	978-3-030-71994-4
DOIs	https://doi.org/10.1007/978-3-030-71995-1_22
Publication status	Published - 23 Mar 2021
Event	24th International Conference on Foundations of Software Science and Computation Structures - Online Duration: 27 Mar 2021 → 1 Apr 2021 https://etaps.org/2021/fossacs

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer, Cham
Volume	12650
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	24th International Conference on Foundations of Software Science and Computation Structures
Abbreviated title	FoSSaCS 2021
City	Online
Period	27/03/21 → 1/04/21
Internet address	https://etaps.org/2021/fossacs

Keywords

Simple Stochastic Games
Parity Games
Energy Games

Access to Document

10.1007/978-3-030-71995-1_22Licence: Creative Commons: Attribution (CC-BY)

2101.06989Accepted author manuscript, 635 KBLicence: Creative Commons: Attribution (CC-BY)
Simple Stochastic Games_MAYR_DOA18122020_VOR_CC-BYFinal published version, 453 KBLicence: Creative Commons: Attribution (CC-BY)

Cite this

@inproceedings{56be7ec7798941b581de37e6325e9805,

title = "Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP",

abstract = "We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative ω-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability 1 when starting at a given energy level k, is decidable and in NP∩coNP. The same holds for checking if such a k exists and if a given k is minimal. ",

keywords = "Simple Stochastic Games, Parity Games, Energy Games",

author = "Richard Mayr and Sven Schewe and Patrick Totzke and Dominik Wojtczak",

note = "Proceedings of FOSSACS 2021. https://etaps.org/2021/fossacs; 24th International Conference on Foundations of Software Science and Computation Structures, FoSSaCS 2021 ; Conference date: 27-03-2021 Through 01-04-2021",

year = "2021",

month = mar,

day = "23",

doi = "10.1007/978-3-030-71995-1_22",

language = "English",

isbn = "978-3-030-71994-4",

series = " Lecture Notes in Computer Science",

publisher = "Springer Berlin Heidelberg",

pages = "427 -- 447",

booktitle = "Foundations of Software Science and Computation Structures (FOSSACS 2021)",

url = "https://etaps.org/2021/fossacs",

}

Mayr, R, Schewe, S, Totzke, P & Wojtczak, D 2021, Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP. in Foundations of Software Science and Computation Structures (FOSSACS 2021). Lecture Notes in Computer Science, vol. 12650, Springer Berlin Heidelberg, pp. 427 - 447, 24th International Conference on Foundations of Software Science and Computation Structures, Online, 27/03/21. https://doi.org/10.1007/978-3-030-71995-1_22

Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP. / Mayr, Richard; Schewe, Sven; Totzke, Patrick et al.

Foundations of Software Science and Computation Structures (FOSSACS 2021). Springer Berlin Heidelberg, 2021. p. 427 - 447 ( Lecture Notes in Computer Science; Vol. 12650).

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

TY - GEN

T1 - Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP

AU - Mayr, Richard

AU - Schewe, Sven

AU - Totzke, Patrick

AU - Wojtczak, Dominik

N1 - Proceedings of FOSSACS 2021. https://etaps.org/2021/fossacs

PY - 2021/3/23

Y1 - 2021/3/23

N2 - We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative ω-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability 1 when starting at a given energy level k, is decidable and in NP∩coNP. The same holds for checking if such a k exists and if a given k is minimal.

AB - We study stochastic games with energy-parity objectives, which combine quantitative rewards with a qualitative ω-regular condition: The maximizer aims to avoid running out of energy while simultaneously satisfying a parity condition. We show that the corresponding almost-sure problem, i.e., checking whether there exists a maximizer strategy that achieves the energy-parity objective with probability 1 when starting at a given energy level k, is decidable and in NP∩coNP. The same holds for checking if such a k exists and if a given k is minimal.

KW - Simple Stochastic Games

KW - Parity Games

KW - Energy Games

U2 - 10.1007/978-3-030-71995-1_22

DO - 10.1007/978-3-030-71995-1_22

M3 - Conference contribution

SN - 978-3-030-71994-4

T3 - Lecture Notes in Computer Science

SP - 427

EP - 447

BT - Foundations of Software Science and Computation Structures (FOSSACS 2021)

PB - Springer Berlin Heidelberg

T2 - 24th International Conference on Foundations of Software Science and Computation Structures

Y2 - 27 March 2021 through 1 April 2021

ER -

Simple Stochastic Games with Almost-Sure Energy-Parity Objectives are in NP and coNP

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this