TY - JOUR

T1 - Complexity and effective prediction

AU - Neyman, Abraham

AU - Spencer, Joel

N1 - Funding Information:
✩ This research was supported in part by Israel Science Foundation grants 263/03 and 1123/06. The authors enjoyed the hospitality, generosity and stimulating atmosphere of Microsoft Research (Redmond) in the initial phases of this research. * Corresponding author. E-mail addresses: aneyman@math.huji.ac.il (A. Neyman), joelspencer@cims.nyu.edu (J. Spencer).

PY - 2010/5

Y1 - 2010/5

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

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

KW - C44

KW - C73

KW - D83

UR - http://www.scopus.com/inward/record.url?scp=77951642478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77951642478&partnerID=8YFLogxK

U2 - 10.1016/j.geb.2009.05.007

DO - 10.1016/j.geb.2009.05.007

M3 - Article

AN - SCOPUS:77951642478

SN - 0899-8256

VL - 69

SP - 165

EP - 168

JO - Games and Economic Behavior

JF - Games and Economic Behavior

IS - 1

ER -