Determinacy in Stochastic Games with Unbounded Payoff Functions

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

Výsledek na webu

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

Jazyk výsledku

angličtina

Název v původním jazyce

Determinacy in Stochastic Games with Unbounded Payoff Functions

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Determinacy in Stochastic Games with Unbounded Payoff Functions

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GBP202%2F12%2FG061" target="_blank" >GBP202/12/G061: Centrum excelence - Institut teoretické informatiky (CE-ITI)</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2013

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

Mathematical and Engineering Methods in Computer Science (MEMICS 2012)

ISBN

9783642360442

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

12

Strana od-do

94-105

Název nakladatele

Springer

Místo vydání

Heidelberg

Místo konání akce

Znojmo

Datum konání akce

1. 1. 2012

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

EUR - Evropská akce

Kód UT WoS článku

—