Stabilization in hierarchical multiagentgames against nature

Abstract: Game theory is a way of modeling interactions between intelligent agents, for example, robots working on an assembly line where they need to take input from their environment to know how to act. When discussing these types of games, an important aspect is that of knowledge. If, for example, one of the robots has a broken sensor, and cannot access all available information about the situation, the game becomes one of imperfect information. Knowledge-based subset construction (KBSC) is a method for taking games of imperfect information and constructing new game states based on the player’s knowledge about the states, and build up a new game of perfect information from that. There is also a multi-player counterpart: Multi-agent knowledge- based subset construction (MKBSC). However, unlike in the single-player case, the MKBSC is not guaranteed to result in a perfect information game. If the MKBSC is iteratively applied to a game some games will reach a point where each concurrent game will be identical to the previous one. This is called stabilization. It is currently unknown what conditions determine whether a certain game stabilizes or not. In this thesis, we study stabilization regarding hierarchical games (that is, games where the agents can be ordered in a way so that every agent’s knowledge is a subset of the previous agent’s). We design several game models and generate every hierarchical permutation of the players’ knowledge for each game. We then apply the MKBSC iteratively on each game until it either stabilizes, or we can be almost certain that it will not. The results ended up disproving the hypothesis, as we find several hierarchical games that do not stabilize. We also conclude that one player having perfect knowledge is not a sufficient condition for a hierarchical game to stabilize and try to discuss some of the reasons a game would not stabilize.