What are strategies in delay games? Borel determinacy for games with lookahead

DOI10.4230/LIPICS.CSL.2015.519zbMATH Open1434.03123arXiv1504.02627OpenAlexW2963179057MaRDI QIDQ5351978FDOQ5351978

Authors: Felix Klein, Martín G. Zimmermann

Publication date: 31 August 2017

Abstract: We investigate determinacy of delay games with Borel winning conditions, infinite-duration two-player games in which one player may delay her moves to obtain a lookahead on her opponent's moves. First, we prove determinacy of such games with respect to a fixed evolution of the lookahead. However, strategies in such games may depend on information about the evolution. Thus, we introduce different notions of universal strategies for both players, which are evolution-independent, and determine the exact amount of information a universal strategy needs about the history of a play and the evolution of the lookahead to be winning. In particular, we show that delay games with Borel winning conditions are determined with respect to universal strategies. Finally, we consider decidability problems, e.g., "Does a player have a universal winning strategy for delay games with a given winning condition?", for omega-regular and omega-context-free winning conditions.

Full work available at URL: https://arxiv.org/abs/1504.02627

Recommendations

zbMATH Keywords

determinacy infinite games Borel hierarchy delay games

Mathematics Subject Classification ID

Games involving topology, set theory, or logic (91A44) Determinacy principles (03E60)

Cited In (8)

This page was built for publication: What are strategies in delay games? Borel determinacy for games with lookahead

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5351978)