BRENGUIER, Romain and Vojtěch FOREJT. Decidability Results for Multi-objective Stochastic Games. In Artho C., Legay A., Peled D. International Symposium on Automated Technology for Verification and Analysis. Germany: Springer, 2016, p. 227-243. ISBN 978-3-319-46519-7. Available from: https://dx.doi.org/10.1007/978-3-319-46520-3_15.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Decidability Results for Multi-objective Stochastic Games
Authors BRENGUIER, Romain (250 France) and Vojtěch FOREJT (203 Czech Republic, guarantor, belonging to the institution).
Edition Germany, International Symposium on Automated Technology for Verification and Analysis, p. 227-243, 17 pp. 2016.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form printed version "print"
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/16:00094154
Organization unit Faculty of Informatics
ISBN 978-3-319-46519-7
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-319-46520-3_15
Keywords in English stochastic games; multi-criteria optimisation
Tags core_A, firank_A
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 27/4/2017 07:18.
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 an 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.
PrintDisplayed: 25/5/2024 12:42