Decidability Results for Multi-objective Stochastic Games
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00094154" target="_blank" >RIV/00216224:14330/16:00094154 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-319-46520-3_15" target="_blank" >http://dx.doi.org/10.1007/978-3-319-46520-3_15</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-319-46520-3_15" target="_blank" >10.1007/978-3-319-46520-3_15</a>
Alternative languages
Result language
angličtina
Original language name
Decidability Results for Multi-objective Stochastic Games
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
International Symposium on Automated Technology for Verification and Analysis
ISBN
9783319465197
ISSN
0302-9743
e-ISSN
—
Number of pages
17
Pages from-to
227-243
Publisher name
Springer
Place of publication
Germany
Event location
Germany
Event date
Jan 1, 2016
Type of event by nationality
CST - Celostátní akce
UT code for WoS article
—