Lower bounds for multiplayer noncooperative games of incomplete information

This paper (see also [1]) extends the alternating Turing machine (A-TM) of Chandra, Kozen and Stockmeyer [2], the private and the blind alternating machines of Reif [3,4] to model multiplayer games of incomplete information. We use these machines to provide matching lower bounds for our decision algorithms described in our companion paper [5]. We also apply multiple person alternation to other machine types. We show that multiplayer games of incomplete information can be undecidable general. However, one form of incomplete information games that is decidable we term as hierarchical games (defined later in this paper). In hierarchical multiplayer games, each additional clique (subset of players with same information) increases the complexity of the outcome problem by a further exponential. Consequently, if a multiplayer game of incomplete information with k cliques has a space bound of S(n), then its outcome can be k repeated exponentials harder than games of complete information with the same space bound S(n). This paper proves that this exponential blow-up must occur in the worst case. We define TEAM-PRIVATE-PEEK and TEAM-BLIND-PEEK, extending the previous models of PEEK. These new games can be shown to be complete for their respective classes. We use these games to establish lower bounds on complexity of multiplayer games of incomplete information and blindfold multiplayer games. We analyze the time bounded alternating machines, and conclude that time is not a very critical resource for multiplayer alternation. We also show DQBF (a variant of QBF) to be complete in NEXPTIME.