Decidability results for multi-objective stochastic games

DOI10.1007/978-3-319-46520-3_15zbMATH Open1398.91056arXiv1605.03811OpenAlexW2388209185MaRDI QIDQ1990509FDOQ1990509

Authors: Romain Brenguier, Vojtech Forejt 

Publication date: 25 October 2018

Abstract: We study stochastic two-player turn-based games in which the objective of one player is to ensure several infinite-horizon total reward objectives, while the other player attempts to spoil at least one of the objectives. The games have previously been shown not to be determined, and an approximation algorithm for computing a Pareto curve has been given. The major drawback of the existing algorithm is that it needs to compute Pareto curves for finite horizon objectives (for increasing length of the horizon), and the size of these Pareto curves can grow unboundedly, even when the infinite-horizon Pareto curve is small. By adapting existing results, we first give an algorithm that computes the Pareto curve for determined games. Then, as the main result of the paper, we show that for the natural class of stopping games and when there are two reward objectives, the problem of deciding whether a player can ensure satisfaction of the objectives with given thresholds is decidable. The result relies on intricate and novel proof which shows that the Pareto curves contain only finitely many points. As a consequence, we get that the two-objective discounted-reward problem for unrestricted class of stochastic games is decidable.

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

Recommendations

• On stochastic games with multiple objectives
• Approximating values of generalized-reachability stochastic games
• Pareto curves of multidimensional mean-payoff games
• A Survey of Stochastic Games with Limsup and Liminf Objectives
• Markov Decision Processes with Multiple Objectives

Mathematics Subject Classification ID

2-person games (91A05) Stochastic games, stochastic differential games (91A15) Decidability of theories and sets of sentences (03B25)

Cited In (5)

• Approximating values of generalized-reachability stochastic games
• Compositional strategy synthesis for stochastic games with multiple objectives
• Stochastic games with lexicographic objectives
• Stochastic games with disjunctions of multiple objectives
• On stochastic games with multiple objectives

This page was built for publication: Decidability results for multi-objective stochastic games

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