Determinacy in Stochastic Games with Unbounded Payoff Functions
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F13%3A00065957" target="_blank" >RIV/00216224:14330/13:00065957 - isvavai.cz</a>
Result on the web
<a href="http://arxiv.org/abs/1208.1639" target="_blank" >http://arxiv.org/abs/1208.1639</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1007/978-3-642-36046-6_10" target="_blank" >10.1007/978-3-642-36046-6_10</a>
Alternative languages
Result language
angličtina
Original language name
Determinacy in Stochastic Games with Unbounded Payoff Functions
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Center of excellence - Institute for theoretical computer science (CE-ITI)</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)
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
Mathematical and Engineering Methods in Computer Science (MEMICS 2012)
ISBN
9783642360442
ISSN
0302-9743
e-ISSN
—
Number of pages
12
Pages from-to
94-105
Publisher name
Springer
Place of publication
Heidelberg
Event location
Znojmo
Event date
Jan 1, 2012
Type of event by nationality
EUR - Evropská akce
UT code for WoS article
—