combinatorial games on graphs

Graph games are at the heart of many automated design problems in formal methods and AI. These games are played by a number of players moving a token along the edges of a graph. Who controls the movement of the token at each step is determined according to predefined rules. A player wins the game if the path traversed by the token fulfills a given property.

I study questions like the decidability and algorithmic complexities for computing winning policies in various forms of graph games. One of the ongoing projects studies bidding games, in which the players participate in auctions to decide who moves the token at a given step.