The complexity of two-player games of incomplete information

摘要

Two-player games of incomplete information have certain portions of positions which are private to each player and cannot be viewed by the opponent. Asymptotically optimal decision algorithms for space bounded games are provided. Various games of incomplete information are presented 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. “Private alternating Turing machines” are defined to be a new type of alternating Turing machines related to games of incomplete information. 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). Blindfold games are restricted games in that the second player is not allowed to modify the common position. Asymptotically optimal decision algorithms for space bounded blindfold games are provided. Various blindfold games are also shown to have exponential space complete outcome problems and to be universal for reasonable blindfold games. “Blind alternating Turing machines” are defined to be private alternating Turing machines with restrictions similar to those in blindfold games. The space complexity of these machines is characterized in terms of the complexity of deterministic Turing machines with a single exponential increase in space bounds.