论文标题
玩有限的自动机
Playing odds and evens with finite automata
论文作者
论文摘要
本文涉及重复的“赔率和埃文斯”游戏的渐近行为，并采用有限自动机代表的两个玩家的策略。事实证明，对于每$ n $，都有一个带有$ 2^n \ cdot \ mathrm {poly}（n）$状态的自动机，它击败了每一个$ n $ state automaton，从某种意义上说，除了有限的许多人以外，它都会赢得所有回合。此外，每个这样的自动机都有至少$ 2^n \ cdot（1 -o（1））$状态，这意味着上限紧密到多项式因素。在“赔率和逃避”的特殊情况下，这是Ben-Porath的经典结果的重大改进。此外，我推测该方法可以推广到任意的零和游戏。
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.
