First-cycle games

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, Theta(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. (C) 2016 Elsevier Inc. All rights reserved.