Complexity and Effective Prediction

Abraham Neyman () and Joel Spencer ()

Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem

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

Pages: 9 pages
Date: 2006-10
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp435.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp435.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp435.pdf)

Related works:
Journal Article: Complexity and effective prediction (2010)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:huj:dispap:dp435

Access Statistics for this paper

More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin ().