Notes on Chapter 2

Basics of Infinite Games

• Can be represented as automata
• Different winning conditions, corresponding to various acceptance conditions of automata
• Fundamental questions
  • Game determinacy
  • Complexity of determining winner in a game
  • Identify winning strategy

Strategies and Determinacy

• Transformation of winning conditions is done similarly as that of automata acceptance conditions
  • Particularly, it is sufficient to consider parity games when a regular games are dealt with
• Forgetful strategy
  • A finite memory is needed for a strategy to be carried out
• Memoryless strategy
  • Forgetful strategy that needs no memory
  • Both players win memoryless in any parity game
  • P0 wins memoryless in Rabin game <=> P1 wins memoryless in Streett game
• Both reachability games and 1-games have memoryless determinacy
• Buchi games have memoryless determinacy

Exercises to discuss

• 2.1
• 2.5
• 2.7