First Cycle Games

First cycle games (FCGs) are played on a finite graph by two players who push a token along the edges of the graph until a simple cycle is formed. The winner is determined by some fixed property Y of the sequence of nodes forming this cycle. We are motivated by two questions: Under what conditions on Y is every FCG memoryless determined? What is the connection between FCGs and traditional winning conditions such as mean-payoff games? Our answers to these questions take the following form: we generalise the proof by Ehrenfeucht and Mycielski that mean-payoff games are memoryless determined and then supply a recipe for proving that a winning condition is memoryless determined. All memoryless determined infinite duration games that we are aware of can be proved memoryless determined using this recipe.

Authors

• Sasha Rubin University of Sydney

Keywords

No keywords are indexed for this paper.