Investigation on stability of Knowledge Based Subset Construction in Multi-Agent Games

Abstract: Many real life problems can be modelled using multi-agent games played on finite graphs. When an agent cannot differentiate between game states, for example when a robot operates with a broken sensor, the game is classified as a game of imperfect information. This report focuses on non-deterministic multi-agent games of imperfect information or Multi-Agent Games of Imperfect Information Against Nature (MAGIIAN). Finding optimal strategies for these games is very hard due to the element of imperfect information as well as taking into account the multiple cooperating agents. Using a generalised version for multi-agent games of the known Knowledge Based Subset Construction (KBSC) algorithm may solve the problem of strategy synthesis for MAGIIAN. While the KBSC transforms the game into a game with perfect information, the multi-agent variant (MKBSC) instead yields another MAGIIAN. When applying the algorithm iteratively some games stop expanding while others expand seemingly boundlessly. This is referred to as stability and divergence respectively. Our research focuses on different patterns, called structural conditions, in the MAGIIAN and how they affect stability. By using an existing implementation of the MKBSC along with some newly developed algorithms we were able to iterate over different games and analyse different structural conditions. We have identified several structural conditions which affect stability. By reducing divergent games to only their core components with respect to divergence, a more careful examination of what causes divergence could be done. It reaffirmed earlier research that cycles are necessary in order for games to diverge. Observation overlap was found to not be a necessary condition for divergent games as counter examples to this was found. Games containing well formed observations were found to stabilise within one iteration. Our research has also lead us to believe that it is impossible for structural conditions to properly classify divergence.