Recursive knowledge representation for multi-agent games over graphs

Sammanfattning

In this thesis I explore a construction for Multi-Agent Games of Imperfect Information Against Nature (MAGIIAN) introduced by Gurov et al. called the Multiplayer Knowledge-Based Subset Construction (MKBSC). Multi-agent games of imperfect information are games played over graphs with multiple agents where each agent is allowed to have different information about which state the game currently is in. Applying the MKBSC to a MAGIIAN yields a new MAGIIAN where each agent’s knowledge is encoded into the states. Iteratively applying the MKBSC leads to games where the states contain each agent’s knowledge of the other agents’ knowledge. Certain games reach stabilization after a finite number of iterations, meaning that the resulting game is isomorphic to the game the MKBSC was applied to. The knowledge contained within the states can be expressed in a tree form, and when we continue to iterate on a stable game these knowledge-trees continue to grow indefinitely. Gurov et al. hypothesise that, upon stabilization, a game has been saturated with information and thus it may be possible to summarize the knowledge in a recursive manner avoiding the need for further iterations. The aim of this thesis is to test this hypothesis, and if it is valid, to formally define such a recursive representation and prove its validity. In order to achieve this I used a tool developed by Nylen et al. to explore the knowledge trees of stable games. I developed and tested various hypotheses and finally came up with a recursive representation which I was able to show is equivalent to the non-recursive knowledge trees.