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

---

MOCs

• Logic, Automata and Games

---

References