Technical Report 2002-033

Memoryless Determinacy of Parity and Mean Payoff Games: A Simple Proof

Henrik Björklund, Sven Sandberg, and Sergei Vorobyov

October 2002

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.