Complexity and effective prediction

Abraham Neyman, Joel Spencer

Research output: Contribution to journalArticlepeer-review


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).

Original languageEnglish (US)
Pages (from-to)165-168
Number of pages4
JournalGames and Economic Behavior
Issue number1
StatePublished - May 2010


  • C44
  • C73
  • D83

ASJC Scopus subject areas

  • Finance
  • Economics and Econometrics


Dive into the research topics of 'Complexity and effective prediction'. Together they form a unique fingerprint.

Cite this