Perfect-information stochastic games with generalized mean-payoff objectives

DOI10.1145/2933575.2934513zbMATH Open1401.68238arXiv1604.06376OpenAlexW2341066496MaRDI QIDQ4635880FDOQ4635880

Authors: Krishnendu Chatterjee, Laurent Doyen 

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: Graph games provide the foundation for modeling and synthesizing reactive processes. In the synthesis of stochastic reactive processes, the traditional model is perfect-information stochastic games, where some transitions of the game graph are controlled by two adversarial players, and the other transitions are executed probabilistically. We consider such games where the objective is the conjunction of several quantitative objectives (specified as mean-payoff conditions), which we refer to as generalized mean-payoff objectives. The basic decision problem asks for the existence of a finite-memory strategy for a player that ensures the generalized mean-payoff objective be satisfied with a desired probability against all strategies of the opponent. A special case of the decision problem is the almost-sure problem where the desired probability is 1. Previous results presented a semi-decision procedure for epsilon-approximations of the almost-sure problem. In this work, we show that both the almost-sure problem as well as the general basic decision problem are coNP-complete, significantly improving the previous results. Moreover, we show that in the case of 1-player stochastic games, randomized memoryless strategies are sufficient and the problem can be solved in polynomial time. In contrast, in two-player stochastic games, we show that even with randomized strategies exponential memory is required in general, and present a matching exponential upper bound. We also study the basic decision problem with infinite-memory strategies and present computational complexity results for the problem. Our results are relevant in the synthesis of stochastic reactive systems with multiple quantitative requirements.

Full work available at URL: https://arxiv.org/abs/1604.06376

Recommendations

• Perfect-information stochastic mean-payoff parity games
• The complexity of stochastic Müller games
• Optimal Strategy Synthesis in Stochastic Müller Games
• Stochastic Games with Finitary Objectives
• Automata, Languages and Programming

zbMATH Keywords

Markov decision processesstochastic gamesmean-payoff

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Cited In (20)

• Automata-based controller synthesis for stochastic systems: a game framework via approximate probabilistic relations
• Foundations of Software Science and Computation Structures
• Optimal Strategy Synthesis in Stochastic Müller Games
• Combinations of Qualitative Winning for Stochastic Parity Games
• Compositional strategy synthesis for stochastic games with multiple objectives
• Perfect-information stochastic mean-payoff parity games
• Strategy synthesis for stochastic games with multiple long-run objectives
• Submixing and shift-invariant stochastic games
• Random fruits on the zielonka tree
• Perfect Information Stochastic Priority Games
• Multi-objective optimization of long-run average and total rewards
• Stochastic games with lexicographic objectives
• Stochastic games with disjunctions of multiple objectives
• Saddle point conditions for a class of stochastic dynamical games with imperfect information
• Stochastic games with lexicographic reachability-safety objectives
• Perfect information two-person zero-sum Markov games with imprecise transition probabilities
• Playing stochastic games precisely
• On stochastic games with multiple objectives
• Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs
• Meet your expectations with guarantees: beyond worst-case synthesis in quantitative games

This page was built for publication: Perfect-information stochastic games with generalized mean-payoff objectives

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635880)