Investigating Strategic Hierarchical Information

Sammanfattning: Multi-agent strategic planning is a field that seeks to model groups of agents who must cooperate to fulfil some goal. It is closely connected to the field of game theory, as games are used to model the interactions between players. An important problem is to determine, for a given game and win condition, whether there exists any strategy that guarantees victory. Under conditions of imperfect information, where some players do not know the current state of the game, this problem is known to be undecidable. This means that there cannot exist any general algorithm that correctly determines whether there exists a winning strategy, for any game and any win condition. To circumvent this problem, researchers have identified some conditions such that, if a game fulfils one of the conditions, the problem of finding a winning strategy is decidable. One such condition is that of hierarchical information. This requires that, if you put the players in some total order, p1  p2  …  pn, then players earlier in the order should always know at least as much about the game as players later in the order. For example, if pi  pj, then pi should know everything that pj knows, regardless of what happens in the game. There exist multiple variations of this hierarchical principle, but none of them consider that players can be aware of the strategies that other players have been using, or even that they can remember the actions they themselves have taken. Thus, when evaluating what the players know, information about what actions have been taken is disregarded. In this thesis, we define strategic hierarchical information as a total preorder between players where the earlier players know at least as much as later players, if they know their own and later players’ strategies (regardless of what these strategies are). We prove that it is decidable whether a game with strategic hierarchical information has a winning strategy. We also consider games where strategic hierarchical information is not always present, but can be guaranteed for some strategies. We say that a strategy maintains strategic hierarchical information if, given that all players are following it and that each player knows that all later players have been following it, any player will know everything that players later in the hierarchy knows. We show that is is decidable whether any game contains a winning strategy that maintains strategic hierarchical information, and describe a way of synthesizing such strategies.