Abstract
We investigate a phenomenon of "onetotwoplayer lifting" in infiniteduration twoplayer games on graphs with zerosum objectives. More specifically, let 𝒞 be a class of strategies. It turns out that in many cases, to show that all twoplayer games on graphs with a given payoff function are determined in 𝒞, it is sufficient to do so for oneplayer games. That is, in many cases the determinacy in 𝒞 can be "lifted" from oneplayer games to twoplayer 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 arenaindependent finitememory strategies. Informally, these are finitememory 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 oneplayer games. Then what can be said about its memory complexity in twoplayer 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 oneplayer games is sublinear in n on some infinite subsequence. Then the chromatic memory complexity in twoplayer games is finite.
 We provide an example in which (a) the chromatic memory complexity in oneplayer games is linear in n; (b) the memory complexity in twoplayer games is infinite. Thus, we obtain the exact barrier for the onetotwoplayer lifting theorems in the setting of chromatic finitememory strategies. Previous results only cover payoff functions with constant chromatic memory complexity.
BibTeX  Entry
@InProceedings{kozachinskiy:LIPIcs.STACS.2022.43,
author = {Kozachinskiy, Alexander},
title = {{OneToTwoPlayer Lifting for Mildly Growing Memory}},
booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
pages = {43:143:21},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772228},
ISSN = {18688969},
year = {2022},
volume = {219},
editor = {Berenbrink, Petra and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15853},
URN = {urn:nbn:de:0030drops158535},
doi = {10.4230/LIPIcs.STACS.2022.43},
annote = {Keywords: Games on graphs, onetotwoplayer lifting, strategy complexity, positional determinacy, finitememory determinacy}
}
Keywords: 

Games on graphs, onetotwoplayer lifting, strategy complexity, positional determinacy, finitememory determinacy 
Collection: 

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022) 
Issue Date: 

2022 
Date of publication: 

09.03.2022 