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.STACS.2022.43
URN: urn:nbn:de:0030-drops-158535
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15853/
Kozachinskiy, Alexander
One-To-Two-Player Lifting for Mildly Growing Memory
Abstract
We investigate a phenomenon of "one-to-two-player lifting" in infinite-duration two-player games on graphs with zero-sum objectives. More specifically, let ? be a class of strategies. It turns out that in many cases, to show that all two-player games on graphs with a given payoff function are determined in ?, it is sufficient to do so for one-player games. That is, in many cases the determinacy in ? can be "lifted" from one-player games to two-player games. Namely, Gimbert and Zielonka (CONCUR 2005) have shown this for the class of positional strategies. Recently, Bouyer et al. (CONCUR 2020) have extended this to the classes of arena-independent finite-memory strategies. Informally, these are finite-memory strategies that use the same way of storing memory in all game graphs.
In this paper, we put the lifting technique into the context of memory complexity. The memory complexity of a payoff function measures, how many states of memory we need to play optimally in game graphs with up to n nodes, depending on n. We address the following question. Assume that we know the memory complexity of our payoff function in one-player games. Then what can be said about its memory complexity in two-player games? In particular, when is it finite?
In this paper, we answer this questions for strategies with "chromatic" memory. These are strategies that only accumulate sequences of colors of edges in their memory. We obtain the following results.
- Assume that the chromatic memory complexity in one-player games is sublinear in n on some infinite subsequence. Then the chromatic memory complexity in two-player games is finite.
- We provide an example in which (a) the chromatic memory complexity in one-player games is linear in n; (b) the memory complexity in two-player games is infinite. Thus, we obtain the exact barrier for the one-to-two-player lifting theorems in the setting of chromatic finite-memory strategies. Previous results only cover payoff functions with constant chromatic memory complexity.
BibTeX - Entry
@InProceedings{kozachinskiy:LIPIcs.STACS.2022.43,
author = {Kozachinskiy, Alexander},
title = {{One-To-Two-Player Lifting for Mildly Growing Memory}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {43:1--43:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-222-8},
ISSN = {1868-8969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15853},
URN = {urn:nbn:de:0030-drops-158535},
doi = {10.4230/LIPIcs.STACS.2022.43},
annote = {Keywords: Games on graphs, one-to-two-player lifting, strategy complexity, positional determinacy, finite-memory determinacy}
}
|
Keywords: |
|
Games on graphs, one-to-two-player lifting, strategy complexity, positional determinacy, finite-memory determinacy |
|
Collection: |
|
39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
09.03.2022 |
