2021/07/21 by Bouyer, Patricia, Roux, Stéphane Le, Thomasset, Nathan
#Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2107.09945
We study infinite two-player win/lose games (A,B,W) where A,B are finite and W ⊆ (A × B)ω. At each round Player 1 and Player 2 concurrently choose one action in A and B, respectively. Player 1 wins iff the generated sequence is in W. Each history h ∈ (A × B)^* induces a game (A,B,Wh) with Wh := \ρ∈ (A × B)ω| h ρ∈ W\. We show the following: if W is in Δ02 (for the usual topology), if the inclusion relation induces a well partial order on the Wh's, and if Player 1 has a winning strategy, then she has a finite-memory winning strategy. Our proof relies on inductive descriptions of set complexity, such as the Hausdorff difference hierarchy of the open sets. Examples in Σ02 and Π02 show some tightness of our result. Our result can be translated to games on finite graphs: e.g. finite-memory determinacy of multi-energy games is a direct corollary, whereas it does not follow from recent general results on finite memory strategies.