BRÁZDIL, Tomáš, Antonín KUČERA and Petr NOVOTNÝ. Determinacy in Stochastic Games with Unbounded Payoff Functions. In Mathematical and Engineering Methods in Computer Science (MEMICS 2012). Heidelberg: Springer, 2013. p. 94-105. ISBN 978-3-642-36044-2. doi:10.1007/978-3-642-36046-6_10.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Determinacy in Stochastic Games with Unbounded Payoff Functions
Authors BRÁZDIL, Tomáš (203 Czech Republic, belonging to the institution), Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution) and Petr NOVOTNÝ (203 Czech Republic, belonging to the institution).
Edition Heidelberg, Mathematical and Engineering Methods in Computer Science (MEMICS 2012), p. 94-105, 12 pp. 2013.
Publisher Springer
Other information
Original language English
Type of outcome Proceedings paper
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Germany
Confidentiality degree is not subject to a state or trade secret
Publication form electronic version available online
WWW URL
Impact factor Impact factor: 0.402 in 2005
RIV identification code RIV/00216224:14330/13:00065957
Organization unit Faculty of Informatics
ISBN 978-3-642-36044-2
ISSN 0302-9743
Doi http://dx.doi.org/10.1007/978-3-642-36046-6_10
Keywords in English game theory; graph games; determinacy
Tags formela-conference
Tags International impact, Reviewed
Changed by Changed by: RNDr. Petr Novotný, Ph.D., učo 172743. Changed: 8/4/2014 16:24.
Abstract
We consider infinite-state turn-based stochastic games of two play- ers who aim at maximizing and minimizing the expected total reward accumulated along a run, respectively. Since the total accumulated reward is unbounded, the determinacy of such games cannot be deduced directly from Martin’s determinacy result for Blackwell games. We show that these games are determined both for unrestricted (i.e., history-dependent and randomized) strategies and deterministic strategies, and the equilibrium value is the same. Further, we show that these games are generally not determined for memoryless strategies, unless we restrict ourselves to some special classes of games. We also examine the existence and type of (epsilon-)optimal strategies for both players.
Links
GBP202/12/G061, research and development projectName: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)
Investor: Czech Science Foundation, Projects to promote excellence in basic research
MUNI/A/0760/2012, internal MU codeName: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Acronym: FI MAV II.)
Investor: Masaryk University, Grant Agency of Masaryk University, Category A
PrintDisplayed: 5/3/2021 03:19