Title: First-cycle games
Language: English
Authors: Aminof, Benjamin
Rubin, Sasha
Category: Research Article
Keywords: Graph games; Cycle games; Memoryless determinacy; Parity games; Mean-payoff games; Energy games
Issue Date: 2017
Journal: Information and Computation
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.
DOI: 10.1016/j.ic.2016.10.008
Library ID: AC15150649
URN: urn:nbn:at:at-ubtuw:3-3826
ISSN: 0890-5401
Organisation: E192 - Institut für Logic and Computation 
Publication Type: Article
Appears in Collections:Article

Files in this item:

File Description SizeFormat
First-cycle games.pdf477 kBAdobe PDFThumbnail
Show full item record

Page view(s)

checked on Feb 26, 2021


checked on Feb 26, 2021

Google ScholarTM


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.