We study games on graphs, where a coalition of agents work against an adversarial nature to achieve an objective. The agents have to collaborate while making their moves simultaneously, while receiving differing information about the state of the game and without a means of agent-to-agent communication. Before the game starts the coalition agrees on a strategy profile, where each agent is provided with a strategy which it acts in accordance to. The challenge of finding a winning strategy profile, wherein the coalition achieves their objective regardless of any influence from the adversarial nature, is called the strategy synthesis problem. For games with coalitions consisting of more than one agent, the general case of the synthesis problem is undecidable. We formalize an abstraction construction of a game where a subset of agents with predetermined strategies are abstracted into the adversarial nature of another game, for the purpose of reducing the size of the coalition of agents and in turn reduce the complexity of the strategy synthesis problem. We then prove that any winning strategy profile in the new game with fewer agents is also winning in the original game when combined with the predetermined strategies. The most interesting case is reducing a game with a coalition of two agents into a game with a single agent, since the strategy synthesis problem is decidable for games with a single agent. This allows us to test the predetermined strategy of the abstracted agent to see if it is possible to create a winning strategy profile using it. If it is not possible then we can try a different strategy. This enables an iterative approach for solving the strategy synthesis problem instead of a deductive one. / I rapporten studeras spel på grafer där ett lag av agenter samarbetar mot en fientlig omvärld för att uppnå ett mål. Agenterna måste samarbeta och göra sina drag på samma gång trots att de inte kan kommunicera med varandra och att de har olika perspektiv på lagets situation. För att lyckas med detta kommer laget överens om en gemensam strategi som består av en specifik strategi för varje individuell agent. Utmaningen att hitta en vinnande gemensam strategi för laget kallas strategisyntesproblemet och är oavgörbart i det allmänna fallet, det finns bevisat ingen algoritm som löser problemet. Vi formaliserar en abstraktionskonstruktion som tar ett spel där en delmängd av agenterna har blivit tilldelade en strategi för att sedan abstrahera de agenterna in i omvärlden i ett annat spel. Tanken är att i-och-med att agenterna redan har strategier vet vi hur de kommer agera och därmed kan vi se dem som en förutsägbar variabel i det nya spelet vi konstruerar. I det nya spelet har vi då färre agenter att skapa strategier för vilket minskar komplexiteten av strategisyntesproblemet. Vi bevisar också att en vinnande gemensam strategi i det nya spelet kan användas tillsammans med de förbestämda strategierna för att vinna det originella spelet. Det mest intressanta fallet för rapporten är om det originella spelet har två agenter i laget, då det finns algoritmer för att lösa strategisyntesproblemet för ensamma agenter. När en agent abstraheras bort och ett spel med en agent kvarstår betyder det att dessa algoritmer kan appliceras. Om en vinnande strategi hittas har problemet lösts, om inte kan man utesluta de förbestämda strategin som den abstraherade agenten använde. Det möjliggör en iterativ testning och uteslutning av strategier som inte funnits tidigare.

Many real life problems can be modelled using multi-agent games played on finite graphs. When an agent cannot differentiate between game states, for example when a robot operates with a broken sensor, the game is classified as a game of imperfect information. This report focuses on non-deterministic multi-agent games of imperfect information or Multi-Agent Games of Imperfect Information Against Nature (MAGIIAN). Finding optimal strategies for these games is very hard due to the element of imperfect information as well as taking into account the multiple cooperating agents. Using a generalised version for multi-agent games of the known Knowledge Based Subset Construction (KBSC) algorithm may solve the problem of strategy synthesis for MAGIIAN. While the KBSC transforms the game into a game with perfect information, the multi-agent variant (MKBSC) instead yields another MAGIIAN. When applying the algorithm iteratively some games stop expanding while others expand seemingly boundlessly. This is referred to as stability and divergence respectively. Our research focuses on different patterns, called structural conditions, in the MAGIIAN and how they affect stability. By using an existing implementation of the MKBSC along with some newly developed algorithms we were able to iterate over different games and analyse different structural conditions. We have identified several structural conditions which affect stability. By reducing divergent games to only their core components with respect to divergence, a more careful examination of what causes divergence could be done. It reaffirmed earlier research that cycles are necessary in order for games to diverge. Observation overlap was found to not be a necessary condition for divergent games as counter examples to this was found. Games containing well formed observations were found to stabilise within one iteration. Our research has also lead us to believe that it is impossible for structural conditions to properly classify divergence. / Olika typer av autonoma problem kan modelleras med hjälp av fleragentsspel spelade på ändliga grafer. Spel där en agent ej kan urskilja mellan två tillstånd, till exempel när en robot arbetar med trasiga sensorer, klassas som spel med ofullständig information. Vår rapport fokuserar på ickedeterministiska fleragentsspel med ofullständig information, även kallat Multi-Agent Games of Imperfect Information Against Nature (MAGIIAN). Att hitta optimala strategier för dessa spel är mycket svårt både på grund av den ofullständiga informationen och på grund av flertalet agenter som ska samarbeta. Användandet av en generaliserad variant för fleragentspel av den kända Knowledge Based Subset Construction (KBSC) algoritmen kan hjälpa att hitta vinnande strategier för MAGIIAN. Medan KBSC algoritmen transformerar spelet till ett spel med fullständig information, så ger fleragentsvarianten istället ännu ett MAGIIAN. Om man applicerar algoritmen många gånger kommer vissa spel sluta att växa medan andra fortsätter växa gränslöst. Detta kallas att spelen är stabila eller divergeranta. Vår rapport fokuserar på olika strukturer i dessa spel och hur dessa påverkar stabiliteten. Genom att använda en implementation av MKBSC tillsammans med nya algoritmer har vi itererat över många olika spel och analyserat olika strukturer. Vi har hittat flertalet strukturer som påverkar stabiliteten. Genom att reducera divergenta spel så att alla kvarvarande komponenter krävs för divergens, kunde divergenses orsaker noggrannt undersökas. Detta bekräftade tidigare påståenden om att cykler krävs för divergens. Därefter motbevisades att överlappande observationer krävdes för divergens med hjälp av motexempel. Spel innehållandes välformade observationer visades stabilisera efter en iteration av MKBSC:n.