@article {2314,
	title = {Complexity and Effective Prediction},
	journal = {Games and Economic Behavior},
	year = {2010},
	pages = {165-168},
	abstract = {Let 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 {\textquotedblleft}smart{\textquotedblright} in the sense that k is large but player 2 is {\textquotedblleft}much smarter{\textquotedblright} in the sense that m\&gt;\&gt;k. Let S(g) be the value of G where the second player is clairvoyant, i.e., would know the player 1{\textquoteright}s move in advance. The threshold for clairvoyance is shown to occur for m near min(|I|, | J |) to the power 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).},
	author = {Abraham Neyman and Joel Spencer}
}
