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.

[12] Succinct progress measures for solving parity games R. Lazic and M. Jurdzinski (LICS 2017)

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.2018 (Tue) Mean-payoff games; Examples [11]
Lecture 9 13.09.2018 (Tue) Positional determinacy in Mean-Payoff games [11]
Special lecture (Thejaswini) 18.09.2018 (Tue) Succinct progress measures for solving parity games [12]
Special lecture (Thejaswini) 20.09.2018 (Thu) Succinct progress measures for solving parity games [12]
Lecture 10 04.10.2018 (Thu) Value iteration algorithm; computing optimal strategies [8] Exercise Set 4
Module 3: Simple stochastic games
Lecture 11 09.10.2018 (Tue) Markov chains Notes
Lecture 12 11.10.2018 (Thu) Optimality equations and Strategy improvement algorithm for MDPS Notes Exercise Set 5
Lecture 13 16.10.2018 (Tue) Solving MDPs using Linear Programming and Value iteration Notes
Lecture 14 23.10.2018 (Tue) Simple Stochastic Games (SSGs), optimality equations, minmax equilibrium Sections 1, 2.1, Lemma 6 of [4]
Lecture 15 25.10.2018 (Thu) SSGs: strategy improvement; formulation using Quadratic Programming Sections 2.1, 3.1 of [6]
Lecture 16 01.11.2018 (Thu) SSGs: value iteration; converting SSGs with arbitrary probabilities to Condon style SSGs Section 6 of [8]
Lecture 17 07.11.2018 (Thu) Converting MPGs to SSGs via Discounted Payoff Games Sections 5 and 6 of [8], Chapter 5 of [2] Exercise Set 6
Module 4: Graph searching games
Lecture 18 13.11.2018 (Thu) Graph searching games: introduction to visible cops and robbers game, tree width Section 1 of [9]
Lecture 19 15.11.2018 (Thu) Connection between tree-width and strategies for cops; havens; brambles (screens) Section 1 of [9]
Lecture 20 20.11.2018 (Tue) Relating tree width and bramble number Lemmas 12.3.1, 12.3.8 and Theorem 12.3.9 from [10]