Decidability Results for Multi-objective Stochastic Games

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Decidability Results for Multi-objective Stochastic Games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Decidability Results for Multi-objective Stochastic Games

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

International Symposium on Automated Technology for Verification and Analysis

ISBN

9783319465197

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

17

Strana od-do

227-243

Název nakladatele

Springer

Místo vydání

Germany

Místo konání akce

Germany

Datum konání akce

1. 1. 2016

Typ akce podle státní příslušnosti

CST - Celostátní akce

Kód UT WoS článku

—