Investigation of a Knowledge-Based Subset Construction for Multi-Player Games of Imperfect Information

Abstract: Games can be used to model different autonomous decision problems to find strategies ac- cording to which the involved agents should act. When the agents in these problems cannot differentiate between certain states, for example due to a damaged sensor, the modeled game is said to be of imperfect information. The strategies in these types of games are much harder to find compared to games of perfect information, and it becomes even harder to find strategies when several agents are cooperating to solve a specific task in a so-called multi-player game of imperfect information. We study a multi-player variant of a well known knowledge-based subset construction for games of imperfect information, which now considers a coalition of players working towards a common goal. This generalized construction reduces uncertainty in a multi-player game of imperfect information by creating a new, knowledge-based game. This reduction is useful since winning strategies found in the knowledge-based game can be translated back into winning strategies in the original game. The properties of this multi-player knowledge-based subset construction (MKBSC) are still not fully known. Unlike the single-player knowledge-based subset construction, the MKBSC is not guaranteed to give knowledge-based games of perfect information, which complicates the strategy synthesis. It is possible to apply the construction to the new game, creating another knowledge-based game of increased epistemic depth. It- erating the construction on the knowledge-based games may cause an unbounded increase in the number of states, causing the game to diverge. We investigate the MKBSC by applying the construction to different multi-player games of imperfect information and classify the properties in the original game that may cause the constructed game to behave in certain ways. We observe that games which do not contain any observation overlaps or cycles within the game graph always stabilize when the construction is iterated on the game. These types of games are preferred when using the construction to create games which simplify strategy synthesis, since the number and size of created knowledge-based games is limited.