On the strategic abilities gained by using knowledge-based strategies for multi-agent teams playing against nature

Abstract: Analogous to how the Knowledge-Based Subset Construct (KBSC) can transform games of imperfect information against nature into games of perfect information, making it easier to find winning strategies for objectives in these games, the multi-agent knowledge-based subset construct (MKBSC) can be used to find winning strategies in multi-agent games of imperfect information. The difference between the two algorithms is that the generalized version can be applied multiple times, which is interpreted as the agent’s considering not just their own knowledge of the game, but also their knowledge of the other agents, and the knowledge of the other agent’s knowledge about their own knowledge, etc... Why higher-level knowledge is required to achieve some objectives is intuitive when the level of knowledge is low. However, we do not know yet of any meaningful objective in a game that requires higher than level two knowledge in order to be achievable, and why this higher level of knowledge is needed. In this report, we try to find an objective that only has a winning strategy for more than level two knowledge and interpret what type of objective this is. A large portion of the work went into finding a way to represent all possible sets of outcomes of a game in a finite manner. This allows us to distinguish the strategic abilities that emerge when considering higher-level knowledge from the strategic abilities that were available at lower levels of knowledge. In the results section, we introduced an approach to analyzing multi-agent games of imperfect information by presenting the outcomes as a graph, termed the graph of outcomes. This representation was applied to a game called the Cart-pushing to illustrate the variation in outcomes of different levels of knowledge. We then listed the graphs of outcomes for knowledge levels 0, 1, 2, 3, and 4. One interesting thing we found is that only the players who consider level-4 knowledge can have a winning strategy for a certain reachability objective, and this objective was not achievable in earlier levels of knowledge.