Determinacy in Stochastic Games with Unbounded Payoff Functions

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

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

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 project: Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)

Investor: Czech Science Foundation

• MUNI/A/0760/2012, interní kód MU: Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace II. (Acronym: FI MAV II.)

Investor: Masaryk University, Category A