✦ LIBER ✦
Memoryless determinacy of parity and mean payoff games: a simple proof
✍ Scribed by Henrik Björklund; Sven Sandberg; Sergei Vorobyov
- Publisher
- Elsevier Science
- Year
- 2004
- Tongue
- English
- Weight
- 287 KB
- Volume
- 310
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
We give a simple, direct, and constructive proof of memoryless determinacy for parity and mean payo games. First, we prove by induction that the ÿnite duration versions of these games, played until some vertex is repeated, are determined and both players have memoryless winning strategies. In contrast to the proof of Ehrenfeucht and Mycielski, Internat. J. Game Theory, 8 (1979) 109-113, our proof does not refer to the inÿnite-duration versions. Second, we show that memoryless determinacy straightforwardly generalizes to inÿnite duration versions of parity and mean payo games.