First-cycle games

Abstract

First-cycle games (FCG) are played on a finite graph by two players who push a token along the edges until a vertex is repeated, and a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of labels of the edges (or nodes) forming this cycle. These games are intimately connected with classic infinite-duration games such as parity and mean-payoff games. We initiate the study of FCGs in their own right, as well as formalise and investigate the connection between FCGs and certain infinite-duration games. We establish that (for efficiently computable Y) the problem of solving FCGs is Pspace-complete; we show that the memory required to win FCGs is, in general, Θ(n)! (where n is the number of nodes in the graph); and we give a full characterisation of those properties Y for which all FCGs are memoryless determined. We formalise the connection between FCGs and certain infinite-duration games and prove that strategies transfer between them. Using the machinery of FCGs, we provide a recipe that can be used to very easily deduce that many infinite-duration games, e.g., mean-payoff, parity, and energy games, are memoryless determined.