On Stochastic Games with Multiple Objectives

D 2013

On Stochastic Games with Multiple Objectives

CHEN, Taolue, Vojtěch FOREJT, Marta KWIATKOWSKA, Aistis SIMAITIS, Clemens WILTSCHE et. al.

Základní údaje

Originální název

On Stochastic Games with Multiple Objectives

Autoři

CHEN, Taolue (156 Čína), Vojtěch FOREJT (203 Česká republika, garant, domácí), Marta KWIATKOWSKA (826 Velká Británie a Severní Irsko), Aistis SIMAITIS (440 Litva) a Clemens WILTSCHE (40 Rakousko)

Vydání

Berlin, Heidelberg, Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13), od s. 266-277, 12 s. 2013

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/13:00072858

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-40312-5

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-40313-2_25

UT WoS

000342994500025

Klíčová slova anglicky

multi-objective verification; stochastic games

Štítky

core_A, firank_A

Změněno: 11. 4. 2015 15:23, RNDr. Vojtěch Forejt, Ph.D., LL.B. (Hons)

Anotace

V originále

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.

Návaznosti

LG13010, projekt VaV

Název: Zastoupení ČR v European Research Consortium for Informatics and Mathematics (Akronym: ERCIM-CZ)

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Zastoupení ČR v European Research Consortium for Informatics and Mathematics

MUNI/33/IP1/2013, interní kód MU

Název: Podpora perspektivních výzkumných týmů Fakulty informatiky a vynikajících vědeckých pracovníků z jiných institucí působících na Fakultě informatiky (Akronym: PVT-VVPZ)

Investor: Masarykova univerzita, Podpora perspektivních výzkumných týmů Fakulty informatiky a vynikajících vědeckých pracovníků z jiných institucí působících na Fakultě informatiky

Citovat

CHEN, Taolue, Vojtěch FOREJT, Marta KWIATKOWSKA, Aistis SIMAITIS a Clemens WILTSCHE. On Stochastic Games with Multiple Objectives. In Krishnendu Chatterjee and Jiri Sgall. Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13). Berlin, Heidelberg: Springer, 2013, s. 266-277. ISBN 978-3-642-40312-5. Dostupné z: https://dx.doi.org/10.1007/978-3-642-40313-2_25.

@inproceedings{1174048,
   author = {Chen, Taolue and Forejt, Vojtěch and Kwiatkowska, Marta and Simaitis, Aistis and Wiltsche, Clemens},
   address = {Berlin, Heidelberg},
   booktitle = {Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13)},
   doi = {http://dx.doi.org/10.1007/978-3-642-40313-2_25},
   editor = {Krishnendu Chatterjee and Jiri Sgall},
   keywords = {multi-objective verification; stochastic games},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Berlin, Heidelberg},
   isbn = {978-3-642-40312-5},
   pages = {266-277},
   publisher = {Springer},
   title = {On Stochastic Games with Multiple Objectives},
   year = {2013}
}

TY  - JOUR
ID  - 1174048
AU  - Chen, Taolue - Forejt, Vojtěch - Kwiatkowska, Marta - Simaitis, Aistis - Wiltsche, Clemens
PY  - 2013
TI  - On Stochastic Games with Multiple Objectives
PB  - Springer
CY  - Berlin, Heidelberg
SN  - 9783642403125
KW  - multi-objective verification
KW  - stochastic games
N2  - 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.
ER  -

CHEN, Taolue, Vojtěch FOREJT, Marta KWIATKOWSKA, Aistis SIMAITIS a Clemens WILTSCHE. On Stochastic Games with Multiple Objectives. In Krishnendu Chatterjee and Jiri Sgall. \textit{Proc. 38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13)}. Berlin, Heidelberg: Springer, 2013, s.~266-277. ISBN~978-3-642-40312-5. Dostupné z: https://dx.doi.org/10.1007/978-3-642-40313-2\_{}25.

Podrobný výpis o publikaci