Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games Are All LP-Type Problems

Memoryless determinacy of parity and mea

Memoryless determinacy of parity and mean payoff games: a simple proof

✍ Henrik Björklund; Sven Sandberg; Sergei Vorobyov 📂 Article 📅 2004 🏛 Elsevier Science 🌐 English ⚖ 287 KB

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 contra