Occupation Games

Abstract

Graph games are played on a directed or un-directed graphs with two or more players. Each game differs from one another in the actions available for each player and the constraints present. The different constraints offer a wide variety of interesting situations to analyze. They help in modelling real life interactive situations and have a wide variety of applications. In this project we will be studying logical aspects of a graph game known as occupation game. The occupation game is a two player, turn-based game played on a graph in which each player starts in certain vertices of a un-directed graph and takes turns in moving to their adjacent vertices. Each player “poisons" the vertex they are currently on, thereby restricting their opponent’s movement to that vertex in the graph. The winner is the player who reaches her goal state first. This game is an extension of the poison game, which was introduced by P. Duchet and H. Meyniel in 1993. Poison game is a two player graph game where only a single player “poisons" the vertices. This game has been well studied both graphically and in terms of a logical language, termed as Poison Modal Logic (PML). To characterize the occupation game, we develop a modal logic, called occupation logic that extends the PML in two dimensions. To the best of our knowledge, such two dimensional models have not been studied extensively before. In this project we study the model-theoretic properties and decidability of the occupation logic and also use the logic to express the winning positions in the game.