Determinacy in Stochastic Games with Unbounded Payoff Functions

D 2013

Determinacy in Stochastic Games with Unbounded Payoff Functions

BRÁZDIL, Tomáš, Antonín KUČERA a Petr NOVOTNÝ

Základní údaje

Originální název

Determinacy in Stochastic Games with Unbounded Payoff Functions

Autoři

BRÁZDIL, Tomáš (203 Česká republika, domácí), Antonín KUČERA (203 Česká republika, garant, domácí) a Petr NOVOTNÝ (203 Česká republika, domácí)

Vydání

Heidelberg, Mathematical and Engineering Methods in Computer Science (MEMICS 2012), od s. 94-105, 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í

elektronická verze "online"

Odkazy

URL

Impakt faktor

Impact factor: 0.402 v roce 2005

Kód RIV

RIV/00216224:14330/13:00065957

Organizační jednotka

Fakulta informatiky

ISBN

978-3-642-36044-2

ISSN

DOI

http://dx.doi.org/10.1007/978-3-642-36046-6_10

Klíčová slova anglicky

game theory; graph games; determinacy

Štítky

formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 8. 4. 2014 16:24, doc. RNDr. Petr Novotný, Ph.D.

Anotace

V originále

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

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

MUNI/A/0760/2012, interní kód MU

Název: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Akronym: FI MAV II.)

Investor: Masarykova univerzita, Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II., DO R. 2020_Kategorie A - Specifický výzkum - Studentské výzkumné projekty

Citovat

BRÁZDIL, Tomáš, Antonín KUČERA a Petr NOVOTNÝ. Determinacy in Stochastic Games with Unbounded Payoff Functions. Online. In Mathematical and Engineering Methods in Computer Science (MEMICS 2012). Heidelberg: Springer, 2013, s. 94-105. ISBN 978-3-642-36044-2. Dostupné z: https://dx.doi.org/10.1007/978-3-642-36046-6_10.

@inproceedings{1076412,
   author = {Brázdil, Tomáš and Kučera, Antonín and Novotný, Petr},
   address = {Heidelberg},
   booktitle = {Mathematical and Engineering Methods in Computer Science (MEMICS 2012)},
   doi = {http://dx.doi.org/10.1007/978-3-642-36046-6_10},
   keywords = {game theory; graph games; determinacy},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Heidelberg},
   isbn = {978-3-642-36044-2},
   pages = {94-105},
   publisher = {Springer},
   title = {Determinacy in Stochastic Games with Unbounded Payoff Functions},
   url = {http://arxiv.org/abs/1208.1639},
   year = {2013}
}

TY  - JOUR
ID  - 1076412
AU  - Brázdil, Tomáš - Kučera, Antonín - Novotný, Petr
PY  - 2013
TI  - Determinacy in Stochastic Games with Unbounded Payoff Functions
PB  - Springer
CY  - Heidelberg
SN  - 9783642360442
KW  - game theory
KW  - graph games
KW  - determinacy
UR  - http://arxiv.org/abs/1208.1639
L2  - http://arxiv.org/abs/1208.1639
N2  - 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.
ER  -

BRÁZDIL, Tomáš, Antonín KUČERA a Petr NOVOTNÝ. Determinacy in Stochastic Games with Unbounded Payoff Functions. Online. In \textit{Mathematical and Engineering Methods in Computer Science (MEMICS 2012)}. Heidelberg: Springer, 2013, s.~94-105. ISBN~978-3-642-36044-2. Dostupné z: https://dx.doi.org/10.1007/978-3-642-36046-6\_{}10.

Podrobný výpis o publikaci