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

• 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.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

Publikations- och innehållstyp

vet (ämneskategori)

rap (ämneskategori)