Decidability Results for Multi-objective Stochastic Games

D 2016

Decidability Results for Multi-objective Stochastic Games

BRENGUIER, Romain a Vojtěch FOREJT

Základní údaje

Originální název

Decidability Results for Multi-objective Stochastic Games

Autoři

BRENGUIER, Romain (250 Francie) a Vojtěch FOREJT (203 Česká republika, garant, domácí)

Vydání

Germany, International Symposium on Automated Technology for Verification and Analysis, od s. 227-243, 17 s. 2016

Nakladatel

Springer

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Forma vydání

tištěná verze "print"

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/16:00094154

Organizační jednotka

Fakulta informatiky

ISBN

978-3-319-46519-7

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-46520-3_15

UT WoS

000389808100015

Klíčová slova anglicky

stochastic games; multi-criteria optimisation

Štítky

core_A, firank_A

Změněno: 25. 10. 2024 16:28, Mgr. Natálie Hílek

Anotace

V originále

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.

Citovat

BRENGUIER, Romain a 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, s. 227-243. ISBN 978-3-319-46519-7. Dostupné z: https://dx.doi.org/10.1007/978-3-319-46520-3_15.

@inproceedings{1378305,
   author = {Brenguier, Romain and Forejt, Vojtěch},
   address = {Germany},
   booktitle = {International Symposium on Automated Technology for Verification and Analysis},
   doi = {http://dx.doi.org/10.1007/978-3-319-46520-3_15},
   editor = {Artho C., Legay A., Peled D.},
   keywords = {stochastic games; multi-criteria optimisation},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Germany},
   isbn = {978-3-319-46519-7},
   pages = {227-243},
   publisher = {Springer},
   title = {Decidability Results for Multi-objective Stochastic Games},
   year = {2016}
}

TY  - JOUR
ID  - 1378305
AU  - Brenguier, Romain - Forejt, Vojtěch
PY  - 2016
TI  - Decidability Results for Multi-objective Stochastic Games
PB  - Springer
CY  - Germany
SN  - 9783319465197
KW  - stochastic games
KW  - multi-criteria optimisation
N2  - 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.
ER  -

BRENGUIER, Romain a Vojtěch FOREJT. Decidability Results for Multi-objective Stochastic Games. In Artho C., Legay A., Peled D. \textit{International Symposium on Automated Technology for Verification and Analysis}. Germany: Springer, 2016, s.~227-243. ISBN~978-3-319-46519-7. Dostupné z: https://dx.doi.org/10.1007/978-3-319-46520-3\_{}15.

Podrobný výpis o publikaci