Complexity and effective prediction

B-Tier
Journal: Games and Economic Behavior
Year: 2010
Volume: 69
Issue: 1
Pages: 165-168

Authors (2)

Score contribution per author:

1.005 = (α=2.01 / 2 authors) × 1.0x B-tier

α: calibrated so average coauthorship-adjusted count equals average raw count

Abstract

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

Technical Details

RePEc Handle
repec:eee:gamebe:v:69:y:2010:i:1:p:165-168
Journal Field
Theory
Author Count
2
Added to Database
2026-01-26