Investigating the impact of agent observations on stabilization of the iterated Multiplayer Knowledge Based Subset Construction

Abstract: Multi-agent games and strategy synthesis within them is of great interest to several applications, for example robotics and manufacturing. The Multiplayer Knowledge Based Subset Construction (MKBSC) could be a useful tool for such strategy synthesis. The MKBSC processes games and creates structures that allow for synthesis of knowledge based strategies that consider the players’ knowledge of the game state as well as the players’ knowledge about the other players’ knowledge. This study investigates some specific conditions under which the MKBSC will not terminate and gets stuck in a loop of ever increasing knowledge, this phenomenon is referred to as stabilization/non- stabilization. Knowledge about the properties of the games that cause the MKBSC to not terminate could be of great interest to further research. It could also be useful for future implementations of the MKBSC as this information could be used for optimizations of the program. This study finds that being hierarchical is not a sufficient condition for a game to stabilize. It also finds that in the specific case of the synchronization game that when one player can not distinguish between any of the games states and the other player only have two states that are indistinguishable to them the game is non-stabilizing under iterated application of the MKBSC only when the end states 1 and 4 are in the pair of states that are indistinguishable to the second player.