Zur Seitenansicht


First-cycle games
Verfasser / Verfasserin Aminof, Benjamin ; Rubin, Sasha
Erschienen in
Information and Computation, 2017, Jg. 254, H. 2, S. 195-216
ErschienenElsevier, 2017
Submitted version
DokumenttypAufsatz in einer Zeitschrift
Schlagwörter (EN)Graph games / Cycle games / Memoryless determinacy / Parity games / Mean-payoff games / Energy games
Projekt-/ReportnummerVienna Science Fund (WWTF): ICT12-059
URNurn:nbn:at:at-ubtuw:3-3826 Persistent Identifier (URN)
 Das Werk ist frei verfügbar
First-cycle games [0.46 mb]
Zusammenfassung (Englisch)

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.

Das PDF-Dokument wurde 7 mal heruntergeladen.