On Stochastic Games with Multiple Objectives
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F13%3A00072858" target="_blank" >RIV/00216224:14330/13:00072858 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1007/978-3-642-40313-2_25" target="_blank" >http://dx.doi.org/10.1007/978-3-642-40313-2_25</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-40313-2_25" target="_blank" >10.1007/978-3-642-40313-2_25</a>
Alternative languages
Result language
angličtina
Original language name
On Stochastic Games with Multiple Objectives
Original language description
We study two-player stochastic games, where the goal of one player is to satisfy a formula given as a positive boolean combination of expected total reward objectives and the behaviour of the second player is adversarial. Such games are important for modelling, synthesis and verification of open systems with stochastic behaviour. We show that finding a winning strategy is PSPACE-hard in general and undecidable for deterministic strategies. We also prove that optimal strategies, if they exist, may require infinite memory and randomisation. However, when restricted to disjunctions of objectives only, memoryless deterministic strategies suffice, and the problem of deciding whether a winning strategy exists is NP-complete. We also present algorithms to approximate the Pareto sets of achievable objectives for the class of stopping games.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/LG13010" target="_blank" >LG13010: Czech Republic representation in the European Research Consortium for Informatics and Mathematics (ERCIM)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2013
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
Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13)
ISBN
9783642403125
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
266-277
Publisher name
Springer
Place of publication
Berlin, Heidelberg
Event location
Klosterneuburg, Austria
Event date
Jan 1, 2013
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—