Can I read Playing Odds and Evens with Finite Automata on EtoBox?

Playing Odds and Evens with Finite Automata by Makarov, Vladislav is a scholarly article available to read on EtoBox.

What is Playing Odds and Evens with Finite Automata about?

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{poly}(n)$ states which defeats every $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.

Author

Makarov, Vladislav

Published

2020

Language

EN