Accession Number : ADA114647

Title :   The Complexity of Two Player Games of Incomplete Information.

Descriptive Note : Technical rept.,

Corporate Author : HARVARD UNIV CAMBRIDGE MA AIKEN COMPUTATION LAB

Personal Author(s) : Reif,John H

PDF Url : ADA114647

Report Date : Oct 1981

Pagination or Media Count : 56

Abstract : We consider two-player games of incomplete information in which certain portions of positions are private to each player and cannot be viewed by the opponent. We provide asymptotically optimal decision algorithms for space bounded games. We present various games of incomplete information which are shown to be universal in the sense that they are the hardest of all reasonable games of incomplete information. The problem of determining the outcome of these universal games from a given initial position is shown to be complete in doubly-exponential time. We also define 'private alternating Turing machines' which are a new type of alternating Turing machines with certain private types. The space complexity S(n) of these machines is characterized in terms of the complexity of deterministic Turing machines, with time bounds doubly-exponential in S(n). We also consider blindfold games, which are restricted games in which the second player is not allowed to modify the common position. We provide asymptotically optimal decision algorithms for space bounded blindfold games.

Descriptors :   *Algorithms, *Decision making, *Computations, *Game theory, Data management, Global, Optimization, Asymptotic series

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE