License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2022.22
URN: urn:nbn:de:0030-drops-170854
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17085/
Main, James C. A. ;
Randour, Mickael
Different Strokes in Randomised Strategies: Revisiting Kuhn’s Theorem Under Finite-Memory Assumptions
Abstract
Two-player (antagonistic) games on (possibly stochastic) graphs are a prevalent model in theoretical computer science, notably as a framework for reactive synthesis.
Optimal strategies may require randomisation when dealing with inherently probabilistic goals, balancing multiple objectives, or in contexts of partial information. There is no unique way to define randomised strategies. For instance, one can use so-called mixed strategies or behavioural ones. In the most general settings, these two classes do not share the same expressiveness. A seminal result in game theory - Kuhn’s theorem - asserts their equivalence in games of perfect recall.
This result crucially relies on the possibility for strategies to use infinite memory, i.e., unlimited knowledge of all past observations. However, computer systems are finite in practice. Hence it is pertinent to restrict our attention to finite-memory strategies, defined as automata with outputs. Randomisation can be implemented in these in different ways: the initialisation, outputs or transitions can be randomised or deterministic respectively. Depending on which aspects are randomised, the expressiveness of the corresponding class of finite-memory strategies differs.
In this work, we study two-player turn-based stochastic games and provide a complete taxonomy of the classes of finite-memory strategies obtained by varying which of the three aforementioned components are randomised. Our taxonomy holds both in settings of perfect and imperfect information, and in games with more than two players.
BibTeX - Entry
@InProceedings{main_et_al:LIPIcs.CONCUR.2022.22,
author = {Main, James C. A. and Randour, Mickael},
title = {{Different Strokes in Randomised Strategies: Revisiting Kuhn’s Theorem Under Finite-Memory Assumptions}},
booktitle = {33rd International Conference on Concurrency Theory (CONCUR 2022)},
pages = {22:1--22:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-246-4},
ISSN = {1868-8969},
year = {2022},
volume = {243},
editor = {Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17085},
URN = {urn:nbn:de:0030-drops-170854},
doi = {10.4230/LIPIcs.CONCUR.2022.22},
annote = {Keywords: two-player games on graphs, stochastic games, Markov decision processes, finite-memory strategies, randomised strategies}
}
|
Keywords: |
|
two-player games on graphs, stochastic games, Markov decision processes, finite-memory strategies, randomised strategies |
|
Collection: |
|
33rd International Conference on Concurrency Theory (CONCUR 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
06.09.2022 |
