Decision algorithms for multiplayer noncooperative games of incomplete information (Q1609052): Difference between revisions

This paper deals with the computational complexity of multiplayer games in which the players are grouped in two teams playing a positional game against each other. One team \(T_0\) is represented by a single player, the other \(T_1\) by a set of players with differing information. The most important theorem, 5.2.1 deals with hierarchical games, that is the information of the players of \(T_1\) is linearly ordered. It says that in this case, adding another player at most exponentiates the complexity. The authors state that they have proved elsewhere that the algorithms used in this reduction are asymptotically optimal. They also deal with questions of strategies dependent on a bounded number of past positions, of time complexity, and of relating space and time complexities in this framework.