Games on Graphs SS 2015

News | Dates | Grading | Content | Exercises | Material

Expected previous knowledge

Basics of graph theory, formal language theory, probability theory, and logics as taught in the courses IN0015, IN011, and IN0018.

Courses IN2041 (automata and formal languages), IN2049 (logics), and IN2239 (algorithmic game theory) can be of help, but are not required.

Outline (tentative)

• Finite Games:
  • Reachability Games
  • Games with regular winning conditions
• Infinite Games:
  • Büchi Games
  • LTL and Parity Games
• Quantitative games:
  • Mean-payoff games
  • Energy games
  • Applications: verification (simulation and bisimulation games), controller synthesis
• Stochastic Games:
  • Markov Chains
  • Markov Decision processes
  • 2.5-player games
  • Applications: routing, management, scheduling.
• Extensions:
  • Multiplayer games
  • Concurrent games
  • Games with imperfect information
  • Symbolic computation