Games on Graphs

Aug - Nov 2018


Instructor :   B Srivathsan
 
Teaching Assistant:    Thejaswini K S



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

Previous versions of this course: 2017    2016

Prerequisites

A course on Algorithms


References

[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] The complexity of mean payoff games on graphs Uri Zwick and Mike Paterson, Theoretical Computer Science 158 (1996) 343 - 359

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

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

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

Lectures

Module 1: Parity games
Lecture 1 07.08.2018 (Tue) Course overview; Solving reachability games, Büchi games and co-Büchi games Sections 3.1 and 3.2 from [1]
Lecture 2 10.08.2017 (Fri) Mixing Büchi and co-Büchi conditions; Divide and conquer algorithm for parity games Section 3.3.1 from [1] Exercise Set 1
Lecture 3 13.08.2018 (Mon) Divide and conquer with dominion preprocessing
Sections 3.3.2 from [1]
Original paper
Exercise Set 2
Lecture 4 21.08.2018 (Tue) Progress measures I Pages 1 - 4 of Notes
22.08.2018 (Wed) Problem solving session by Thejaswini
Lecture 5 23.08.2018 (Thu) Progress measures II Pages 4 - 10 of Notes Exercise Set 3
Lecture 6 28.08.2018 (Tue) Quasipolynomial algorithm by Calude et al I
Original paper
Shorter proof
Chapter 3 in Automata-Toolbox Book
Lecture 7 30.08.2018 (Thu) Quasipolynomial algorithm by Calude et al II
04.09.2018 (Tue) Review of running times of algorithms by Thejaswini
06.09.2018 (Thu) Problem solving session by Thejaswini
Module 2: Mean-payoff games
Lecture 8 11.09.2017 (Tue) Mean-payoff games; Examples [11]