May 27, 2019
Stéphane Le Roux (LSV - ENS Cachan)Two-player win/lose games of infinite duration are involved in several disciplines including computer science and logic. If such a game has winning strategies, one may ask how simple they can be. The answer may help with actual implementation, or to win despite incomplete information, or to conceal sensitive information.
Given a game, this article considers equivalence relations over sequences of player actions. A classical restriction used here is that equivalent sequences have equal length. A sufficient condition on the equivalence relation is given such that if a player has a winning strategy, she has one that prescribes the same action at equivalent histories. The proof/derivation has three advantages: it is uniform, it preserves memory finiteness, and a counterexample shows how tight the result is.