We give a simple, direct, and constructive proof of memoryless determinacy for Parity and Mean Payoff Games. First, we prove by induction that the finite-duration versions of these games, played until some vertex is repeated, are determined and both players have memoryless winning strategies. In contrast to [Ehrenfeucht-Mycielski79], our proof does not refer to the infinite-duration versions. Second, we show that the results straightforwardly generalize to infinite duration games.
Note: Updated journal version, March 2003, available at http://www.it.uu.se/research/publications/reports/2002-033/2002-033-journal
Available as compressed Postscript (264 kB), Postscript (237 kB), compressed Postscript (92 kB), and Postscript (754 kB)
Download BibTeX entry.