Playing odds and evens with finite automata

This paper is concerned with asymptotic behaviour of a repeated game of “odds and evens”, with strategies of both players represented by finite automata. It is proved that, for every $n$, there is an automaton with $2^n \cdot $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}$(n)$stateswhichdefeatsevery$n$-state automaton, in the sense that it wins all rounds except for finitely many. Moreover, every such automaton has at least $2^n\cdot (1-o(1))$ states, meaning that the upper bound is tight up to polynomial factors. This is a significant improvement over a classic result of Ben-Porath in the special case of “odds and evens”. Moreover, I conjecture that the approach can be generalised to arbitrary zero-sum games.