"Memoryless Determinacy of Cycle Games"
Sasha Rubin
(TU Wien & IST Austria)
Wednesday, January 22nd, 2014, 2:00pm
EBU3B, Room 4140
Abstract:
Finite 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 X of this cycle. These games are traditionally of interest because of their connection with infinite-duration games such as parity games and mean-payoff games.
In this work we study some aspects of the memory requirements for winning strategies of FCGs and their infinite-duration counterparts. We exhibit a simple class of FCGs that are not memoryless determined and prove that solving games in this class is in fact PSPACE-complete. This corrects a mistake in "Memoryless determinacy of parity and mean payoff games: a simple proof" by Björklund, Sandberg & Vorobyov (2004) that claims that all FCGs for which X is closed under cyclic permutations are memoryless determined. On the positive side, we revisit the proof in "Positional strategies for mean payoff games" by Ehrenfeucht & Mycielski (1979) that finite-cycle mean-payoff games, and their infininite duration counterpart, are memoryless determined. We identify easy to check conditions on the property X (i.e., X and its complement are closed under cyclic permutations and interleavings) that are sufficient to ensure that the corresponding FCGs and their associated infinite-duration games are memoryless determined.
This is work in progress with Benjamin Aminof.