Games on Graphs

---

Games are a very elegant way of modelling systems where there are components not under our control. We will discuss games that are played on graphs by 2 players. One of the players will model well behaved parts of the system that are under out control (Elster) and the other player models the environment (Adler).

Game

A game is defined as follows

$$G:=⟨A,v_i,\mathcal{W}⟩$$

where

• $A$ is the Arena,
• $v_i$ is the start vertex and
• $\mathcal{W}$ is the Winning condition.

The Gameplay for Games on Graphs is defined here.

Transclude of Game.excalidraw

---

Notes

• Basics ^68e6da
  • Arenas for Games on Graphs
  • Winning Condition for Games on Graphs
  • Gameplay for Games on Graphs
• Strategy for Games on Graphs
  • Winning Arena for Reachability Games
    • Winning Strategy for Reachability Games
  • Winning Arena for Büchi Games
    • Winning Strategy for Büchi Games
  • Winning Arena for Parity Games
  • Winning Arena for Rabin Games
    • Winning Arena for Rabin Games - Fail
• Sub-Games
• Properties of the Attractor function and Traps
• sigma-paradise
• Banach-Mazur Games
  • Winning Strategy for Player 1 in Banach-Mazur games
  • Winning Strategy for Player 2 in Banach-Mazur games

GOG Course Stuff

• Church Synthesis Problem
• Büchi-McNaughton Theorem
  • Muller Automata to Games
• Look at Basics and Strategy for Games on Graphs.
• Winning Arena for Reachability Games
• Winning Arena for Büchi Games
• Letter Number Game
  • Last Appearance Record
• Muller Games to Parity Games
• Progress Measures (Intuition)
• Parity Progress Measures on Graphs
  • A graph admits a small parity progress measure iff all cycles in the graph are even
• Parity Progress Measures on Games
  • Least Progress Measure
  • Computing the Least Progress Measure
• Zeilonka’s Algorithm for finding Parity Game Strategy
• Parity Games are solvable in Qusaipolynomial time - introduction
• Mean Payoff Games
  • Example of Mean Payoff Games
  • Positional Strategy for Mean Payoff Games
  • First Cycle Mean Payoff Games

GOG Presentation

• Perspective Games
  • Deterministic Perspective Games
  • Probabilistic Perspective Games
• Perspective-ATL*
  • ATL
  • Semantics of ATL*
• Alternating Tree Automata
  • Definition of a Tree as a language over words

---

MOCs

• Logic, Automata and Games

---

References