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 player 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 were the second player is clairvoyant, i.e., would know the 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).

Website