Games on Graphs

Aug - Nov 2017


Instructor :   B Srivathsan
 
Teaching Assistant:    Thejaswini K S


Hours

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.

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 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] Exercise Set 2
Lecture 4 29.08.2017 (Tue) Divide and conquer with dominion preprocessing Sections 3.3.2 from [1] Exercise Set 3
Lecture 5 30.08.2017 (Wed) Progress measures I Pages 1 - 5 of Notes
31.08.2017 (Thu) Problem solving session by Thejaswini
Lecture 6 05.09.2017 (Tue) Progress measures II Notes Exercise Set 4
Module 2: Mean-payoff games
Lecture 7 07.09.2017 (Thu) Mean-payoff games; Computing values using First cycle version [11]
Lecture 8 12.09.2017 (Tue) Proof of positional determinacy; Value iteration algorithm; Uniform positional strategies [11], Sections 1,2,3 of [8]
13.09.2017 (Wed) Problem solving session by Thejaswini
14.09.2017 (Thu) Quiz 1 - Syllabus: Lectures 1 - 6
Module 3: Simple Stochastic Games
Lecture 9 19.09.2017 (Tue) Introduction to Markov chains; Markov Decision processes Notes
Lecture 10 21.09.2017 (Thu) Solving MDPs: strategy improvement, linear programming, value iteration
10.10.2017 (Tue) Problem solving (MDPs) Exercise Set 5
12.10.2017 (Thu) Problem solving (Mean Payoff games) Exercise Set 6
17.10.2017 (Tue) Quiz 2: Syllabus - Lectures 7 - 10
Lecture 11 19.10.2017 (Thu) SSGs: introduction, optimality equations, strategy improvement Lemmas 4,5,6 of [4]
Lecture 12 24.10.2017 (Tue) SSGs: formulation using Quadratic Programming Sections 2.1, 3.1 of [6]
Lecture 13 31.10.2017 (Tue) Converting MPGs to SSGs via Discounted Payoff Games Sections 5 and 6 of [8]
2.11.2017 (Thu) Problem solving (SSG) Exercise Set 7
07.11.2017 (Tue) Quiz 3: Syllabus - Lectures 11 - 13
Module 4: Graph searching games
Lecture 14 09.11.2016 (Thu) Graph searching games: introduction to visible cops and robbers game, tree width Section 1 of [9]
Lecture 15 14.11.2017 (Tue) Connection between tree-width and strategies for cops; havens; brambles (screens) Section 1 of [9]
Lecture 16 11.11.2016 (Fri) Relating tree width and bramble number Lemmas 12.3.1, 12.3.8 and Theorem 12.3.9 from [10]