Finite-memory strategies in infinite concurrent two-player games

We study infinite two-player win/lose games (A, B, W) where A and B are the action sets for the two players and W the winning set. At each round Player 1 and 2 concurrently choose one action in A and B respectively, generating an infinite sequence. Player 1 wins iff said sequence lies in W. Contrarily to the classical framework of games on graphs, this framework does not allow any observation on the current state of the game other than what the Player can compute on-the-fly from the stream of actions played. We study three different topological classes of winning sets (sets in the Hausdorff difference hierarchy, sets described using a combination of open sets and Büchi conditions, sets described using a combination of open sets and Parity conditions), and show that, under a well partial order condition on the winning sets induced by the histories, if Player 1 has a(n almost-surely) winning strategy, then she has a finite-memory one. These classes include variations of typically well-studied games such as Büchi/Parity games on finite graphs or energy games. Co-authors: Patricia Bouyer and Stéphane Le Roux. Contributed talk given by Nathan Thomasset

Authors

• Nathan Thomasset

Keywords

No keywords are indexed for this paper.