Complexity and effective prediction

Let G=〈I,J,g〉 be a two-person zero-sum game. We examine the two-person zero-sum repeated game G(k,m) in which players 1 and 2 place down finite state automata with k,m states respectively and the payoff is the average per-stage payoff when the two automata face off.We are interested in the cases in which player 1 is " smart" in the sense that k is large but player 2 is " much smarter" in the sense that m≫k. Let S(g) be the value of G where the second player is clairvoyant, i.e., would know player 1's move in advance.The threshold for clairvoyance is shown to occur for m near min(I,J)k. For m of roughly that size, in the exponential scale, the value is close to S(g). For m significantly smaller (for some stage payoffs g) the value does not approach S(g).