Decision Algorithms for Multiplayer Games of Incomplete Information.

摘要

This paper provides algorithms for deciding the outcome for various classes of multilayer games of incomplete information. The classes of games which our algorithms are applicable include games not previously known decidable; furthermore, many of our algorithms have asymptotically optimal complexity. We apply our algorithms to provide alternative proofs of upper bounds, and new time-space tradeoffs on the complexity of multilayer alternating machines.