Informace o publikaci

Determinacy in Stochastic Games with Unbounded Payoff Functions

Autoři

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

Druh Článek ve sborníku
Konference Mathematical and Engineering Methods in Computer Science (MEMICS 2012)
Fakulta / Pracoviště MU

Fakulta informatiky

Citace
WWW http://arxiv.org/abs/1208.1639
Doi http://dx.doi.org/10.1007/978-3-642-36046-6_10
Obor Informatika
Klíčová slova game theory; graph games; determinacy
Popis 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.
Související projekty:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info