Games on Graphs

Aug - Nov 2016


Instructor :   B Srivathsan
 
Teaching Assistant : Soumyajit Paul


Hours

Lectures Wed   10:30 - 11:45 Lecture Hall 4
Fri   10:30 - 11:45 Lecture Hall 4

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

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] 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.

Lectures

Module 1: Parity games
Lecture 1 10.08.2016 (Wed) Graph games, Payoff function, Strategies, Determinacy, Reachability games Pages 74 - 79 from [1]; Pages 3-6 from [2] Exercise Set 1
Lecture 2 12.08.2016 (Fri) Büchi games; co-Büchi games; a mixed Büchi and co-Büchi objective Pages 79 - 80 from [1] Exercise Set 2
Lecture 3 17.08.2014 (Wed) Parity games; Generalization of Büchi games algorithm to parity games; Complexity; Running time analysis Pages 81 - 85 from [1] Exercise Set 3
Lecture 4 19.08.2016 (Fri) Algorithm for parity games with dominion preprocessing Section 3.3.2 of [1] Exercise Set 4
Lecture 5 24.08.2016 (Wed) Solving parity games using progress measures - I Section 3.3.3 of [1]
Lecture 6 31.08.2016 (Wed) Solving parity games using progress measures - II
Lecture 7 2.09.2016 (Fri) Solving parity games using progress measures - III Section 4 and 5 of [3] Lecture notes
Lecture 8 7.09.2016 (Wed) Dominion preprocessing using progress measures Section 3.3.4 and 3.4 of [1] Exercise Set 5
Module 2: Simple Stochastic games
Lecture 9 14.09.2016 (Wed) Introduction to SSG; Markov Chains and Reachability probabilities Pages 405 - 419 of [5]; Introduction of [4]
Lecture 10 16.09.2016 (Fri) Markov Decision Processes; Policy iteration/Strategy improvement algorithm Lemma 4 of [4]
16.09.2016 (Fri) Quiz 1 (Syllabus: Lectures 1 - 8)
Lecture 11 28.09.2016 (Wed) Overview of algorithms for MDP: policy iteration, linear programming, value iteration Lecture notes
Lecture 12 30.09.2016 (Fri) Algorithms for MDP: Linear Programming, Value iteration Exercise Set 6
04.10.2016 (Fri) Quiz 2 (Syllabus: Lectures 8 - 12)
Lecture 13 05.10.2016 (Wed) SSGs: definition value vector, minimax equilibrium, characterization using min, max equations
Lecture 14 07.10.2016 (Fri) SSGs: Hoffmann-Karp algorithm, proof of correctness, some incorrect algorithms Lemmas 4,5,6 of [4], Sections 2.2, 2.3 of [6]
Lecture 15 12.10.2016 (Wed) SSGs: formulation using Quadratic Programming Sections 2.1, 3.1 of [6]
Lecture 16 19.10.2016 (Wed) SSGs: value iteration, complexity, non-stopping SSGs Lemma 2,3,8 and Theorem 1 of [4]
Module 3: Mean-payoff games
Lecture 17 21.10.2016 (Fri) Finite duration mean-payoff games; positional determinacy [8]
Lecture 18 26.10.2016 (Wed) Positional determinacy of finite duration and infinite duration mean-payoff games [8], Section 4.3 of [2] (check Lecture 24)
Lecture 19 28.10.2016 (Fri)
Computing values in a Mean-Payoff Game (MPG)
Discounted Payoff Games (DPG); Reducing MPGs to DPGs
Reducing DPGs to SSGs
Reducing Parity games to MPGs
Section 2 of [9]
Section 5 of [9]
Section 6 of [9]
Section 4.4 of [2]
Exercise Set 8
Module 4: Graph searching games
Lecture 20 02.11.2016 (Wed) Graph searching games: introduction to visible cops and robbers game, tree width Section 1 of [10]
Lecture 21 04.11.2016 (Fri) Connection between tree-width and strategies for cops; havens; brambles (screens) Section 1 of [10]
04.10.2016 (Fri) Quiz 3 (Syllabus: Lectures 13 - 19)
Lecture 22 11.11.2016 (Fri) Relating tree width and bramble number Lemmas 12.3.1, 12.3.8 and Theorem 12.3.9 from [11]
Lecture 23 14.11.2016 (Mon) Relating tree width and bramble number Theorem 12.3.9 from [11]
Lecture 24 14.11.2016 (Mon) Clarification on positional determinacy of mean-payoff games [12]