Lower bounds for multiplayer noncooperative games of incomplete information

Lower bounds for multiplayer noncooperative games of incomplete information

0.00 Avg rating0 Votes
Article ID: iaor20021349
Country: United States
Volume: 41
Issue: 7/8
Start Page Number: 957
End Page Number: 992
Publication Date: Apr 2001
Journal: Computers & Mathematics with Applications
Authors: , ,
Keywords: computational analysis
Abstract:

This paper extends the alternating Turing machine (A-TM) of Chandra, Kozen and Stockmeyer, the private and the blind alternating machines of Reif, to model multiplayer games of incomplete information. We use these machines to provide matching lower bounds for our decision algorithms described. We also apply multiple person alternation to other machine types. We show that multiplayer games of incomplete information can be undecidable in general. However, one form of incomplete information games that is decidable we term as hierarchical games. 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.

Reviews

Required fields are marked *. Your email address will not be published.