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