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. 

I denna rapport utforskar jag en konstruktion för multi-agent spel med ofullkomlig information mot naturen (MAGIIAN) introducerad av Gurov et al. kallad Multiplayer Knowledge-Based Subset Construction (MKBSC). Multiagent- spel med ofullkomlig information är spel som spelas över grafer med flera agenter där varje agent kan ha skiljande information om vilket tillstånd spelet befinner sig i. Att tillämpa MKBSC på en MAGIIAN ger en ny MAGIIAN där varje agents kunskap kodas in i tillstånden. Om man tillämpar MKBSC iterativt leder det till spel där tillstånden innehåller varje agents kunskap om de andra agenternas kunskap. Vissa spel når stabilisering efter ett begränsat antal iterationer, vilket innebär att det resulterande spelet är isomorft med spelet MKBSC applicerades på. Kunskapen i tillstånden kan uttryckas i trädform, och när vi fortsätter att iterera på ett stabilt spel fortsätter dessa kunskapsträd att växa obegränsat. Gurov et al. spekulerar att när ett spel når stabilisering så är det mättat på information och därmed kan det vara möjligt att sammanfatta kunskapen på ett rekursivt sätt för att undvika behovet av ytterligare iterationer. Syftet med denna rapport är att testa denna hypotes, och om den är giltig, att formellt definiera en sådan rekursiv representation och bevisa dess giltighet. För att uppnå detta använde jag ett verktyg utvecklat av Nylen et al. till att utforska kunskapsträd i stabila spel. Jag utvecklade och testade olika hypoteser och kom till slut fram till en rekursiv representation som jag kunde visa motsvarar de icke-rekursiva kunskapsträden.