Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games

Richard Mayr, Mohan Dantam

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

We consider simple stochastic games G with energy-parity objectives, a combination of quantitative rewards with a qualitative parity condition. The Maximizer tries to avoid running out of energy while simultaneously satisfying a parity condition.

We present an algorithm to approximate the value of a given configuration in 2-NEXPTIME. Moreover, ε-optimal strategies for either player require at most O(2-EXP(|G|)⋅log(1/ε)) memory modes.
Original languageEnglish
Title of host publication48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages38:1-38:15
Number of pages15
Volume272
ISBN (Electronic)9783959772921
DOIs
Publication statusPublished - 28 Aug 2023
Event48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) - Bordeaux, France
Duration: 28 Aug 20231 Sept 2023
https://mfcs2023.labri.fr/

Publication series

Name
ISSN (Electronic)1868-8969

Conference

Conference48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Abbreviated titleMFCS 2023
Country/TerritoryFrance
CityBordeaux
Period28/08/231/09/23
Internet address

Keywords / Materials (for Non-textual outputs)

  • Energy-Parity Games
  • Simple Stochastic Games
  • parity
  • energy

Fingerprint

Dive into the research topics of 'Approximating the Value of Energy-Parity Objectives in Simple Stochastic Games'. Together they form a unique fingerprint.

Cite this