Complexity and effective prediction
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).
Year of publication: |
2010
|
---|---|
Authors: | Neyman, Abraham ; Spencer, Joel |
Published in: |
Games and Economic Behavior. - Elsevier, ISSN 0899-8256. - Vol. 69.2010, 1, p. 165-168
|
Publisher: |
Elsevier |
Saved in:
Saved in favorites
Similar items by person
-
Complexity and Effective Prediction
Neyman, Abraham, (2006)
-
Complexity and Effective Prediction
Neyman, Abraham, (2006)
-
Complexity and effective prediction
Neyman, Abraham, (2010)
- More ...