Finite-Memory Strategies for Games in Two-Player Games

We study infinite two-player win/lose games (A, B, W) where A, B are finite and W is the winning set. At each round Player 1 and 2 concurrently chose one action in A and B respectively. Player 1 wins iff the generated sequence is in W. We show that, under some topological conditions on the shape of the winning set (it can be expressed both as a countable union of closed sets and a countable intersection of open sets) as well as a well-partial order condition on the winning sets induced by the histories, when Player 1 has a winning strategy she has a finite-memory one. This result was presented at CSL 2022. We will see how this result can be applied to well-studied classes of games (e. g. energy games, reachability games), as well as provide counter-examples that show that it is tight. Co-authors: Patricia Bouyer, Stéphane Le Roux, Nathan Thomasset

Authors

• Nathan Thomasset

Keywords

No keywords are indexed for this paper.