In this paper, we investigate the connection between game theory and interactive computation. We formalize the notion of a "polynomially defineable game system" for the language L, which, informally, consists of two arbitrarily powerful players P1 and PP2 and a polynomial-time referee V with a common input w. Player P1 claims that w is in L, and player P2 claims that w is not in L; the referee's job is to decide which of these two claims is true. In general, we wish to study the following question:
What is the effect of varying the system's game-theoretic properties on the class of languages recognizable by polynomially definable game systems?
There are many possible game-theoretic properties that we could investigate in this context. The focus of this paper is the question of what happens when one or both of the players P1 and P2 have imperfect information or or imperfect recall.
We use polynomially definable game systems to derive new charactizations of the complexity classes NEXP and coNEXP. We also derive partial results about other exponential complexity classes and isolate some intriguing open questions about the effects of imperfect information and imperfect recall. These results make use of recent work on complexity-theoretic aspects of games, e.g., [Koller et al., Proc. 26th ACM Symposium on Theory of computing, 1994, pp. 750-759] and [Newman, Information Processing Letters, 39 [1991), pp.~67-71.]
These results were presented in preliminary form at the 10th IEEE Structure in Complexity Theory Conference, Minneapolis MN, June 1995.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1995/95-21.ps.gz
DIMACS Home Page