On Multiplayer Non-Cooperative Games of Incomplete Information: Part 2 - Lower Bounds
Salman Azhar, Gary L. Peterson, John H. Reif · 1991
We extend the alternating machine (A-TM) of Chandra, Kozen and Stockmeyer [CKS81], the private and the blind alternating machines of Reif [Reif84] to model multiplayer games of incomplete information. We use these machines to provide matching lower bounds for our decision algorithms described in the first part of this pair of papers [APR91a]. We apply multiple person alternation to other machine types. We show that multiplayer games of incomplete information can be undecidable in general, unless the information is hierarchically arranged (as 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 is k repeated exponentials harder than games of complete information with the same space bound S(n). This paper prov...