Games on Graphs (IN2296)
| Lecturer (assistant) | |
|---|---|
| Duration | 4 SWS |
| Term | Winter semester 2026/27 |
| Language of instruction | English,Deutsch |
- 20.11.2026 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 24.11.2026 08:30-10:30 00.04.011, MI Hörsaal 2
- 27.11.2026 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 01.12.2026 08:30-10:30 00.04.011, MI Hörsaal 2
- 04.12.2026 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 08.12.2026 08:30-10:30 00.04.011, MI Hörsaal 2
- 11.12.2026 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 15.12.2026 08:30-10:30 00.04.011, MI Hörsaal 2
- 18.12.2026 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 22.12.2026 08:30-10:30 00.04.011, MI Hörsaal 2
- 08.01.2027 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 12.01.2027 08:30-10:30 00.04.011, MI Hörsaal 2
- 15.01.2027 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 19.01.2027 08:30-10:30 00.04.011, MI Hörsaal 2
- 22.01.2027 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 26.01.2027 08:30-10:30 00.04.011, MI Hörsaal 2
- 29.01.2027 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
- 02.02.2027 08:30-10:30 00.04.011, MI Hörsaal 2
- 05.02.2027 10:00-12:00 00.08.038, Unterrichtsraum ohne Infrastruktur
Material
Lecture Slides and Exercise sheets will be published in our Moodle-Course
In the module students are introduced to the theory of games played on a (finite) graph. The course is divided into four parts:
- Games with qualitative winning conditions: reachability, Büchi, parity games.
- Games with quantitative rewards: discounted-payoff games, mean-payoff games.
- Games with chance: stochastic reachability games
- Games with concurrent moves: matrix games, concurrent games.
In each part, the module shows how to compute the winning regions and a winning strategy for each player.
The module also provides compact introductions to the mathematical techniques is uses: fixpoints, Markov chains, and Linear Programming.
Literature
- Filar, Vrieze: Competitive Markov Decision Processes, Springer, 1996
- Grädel, Thomas, Wilke: Automata, Logics, and Infinite Games, Springer 2002
- Perrin, Pin: Infinite Words – Automata, Semigroups, Logics and Games, Elsevier 2004