Games on Graphs

Aug - Nov 2017

Instructor :   B Srivathsan
Teaching Assistant:    Thejaswini K S


Lectures Tuesday   17:00 - 18:15 Room 804
Thursday   17:00 - 18:15 Room 804

Course Description

Games played on graphs form a powerful tool to reason about various questions arising in Logic and Automata theory. Apart from this, games on graphs are a good model for reactive systems that interact with an unpredictable environment.

The goal of this course is to study algorithmic issues arising in some popular games on graphs. The course would be divided into four modules:

Module 1: Parity games

Module 2: Stochastic games

Module 3: Mean-payoff games

Module 4: Graph searching games

A previous version of this course can be found here.


A course on Algorithms


[1] Lectures in Game Theory for Computer Scientists, edited by Krzysztof R. Apt and Erich Grädel

[2] Infinite games, Master's thesis by Miheer Dewaskar at Chennai Mathematical Institute (2016)     Report    Presentation

[3] Small Progress Measures for Solving Parity Games, M. Jurdzinski (STACS 2000)    PDF

[4] The complexity of stochastic games, Anne Condon, Information and Computation 96, 203 - 224 (1992) Link

[5] Introduction to probability, Grinstead and Snell Link

[6] On algorithms for simple stochastic games Anne Condon, Advances in Computational Complexity Theory 13, 51-73 (1993)

[7] Dynamic Programming and Markov Processes Ronald A. Howard, MIT Press (1960)

[8] Memoryless determinacy of parity and mean payoff games: a simple proof Bjoörklund et al, Theoretical Computer Science 310 (2004) 365 - 378

[9] The complexity of mean payoff games on graphs Uri Zwick and Mike Paterson, Theoretical Computer Science 158 (1996) 343 - 359

[10] Graph searching, and a min-max theorem for tree-width Seymour and Thomas, Journal of Combinatorial Theory Series B 58 (1993) 22-33

[11] Graph Theory Reinhard Diestel, Springer-Verlag New York 1997, 2000

[12] Positional strategies for mean-payoff games Ehrenfreucht and Mycielski, Int. Journal of Game Theory, Vol 8, Issue 2, pg 109-113.


Module 1: Parity games
Lecture 1 08.08.2017 (Tue) Course overview
Lecture 2 10.08.2017 (Thu) Reachability games; Büchi games and co-Büchi games Sections 3.1 and 3.2 from [1] Exercise Set 1
Lecture 3 17.08.2017 (Thu) Divide and conquer algorithm for parity games Sections 3.3.1 from [1]