Games on Graphs

Jan - Apr 2023


Instructor :   B Srivathsan
 


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

Module 5: Extensive Form Games

Previous versions of this course: 2018    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

Lecture 1 03.01.2023 (Tue) Introduction to games on graphs; formalism; strategies; determinacy, examples Section 3.1 from [1]
Module 1: Parity games
Lecture 2 05.01.2023 (Thu) Reachability games, Büchi games: positional determinacy and algorithm Section 3.2 from [1]
Lecture 3 10.01.2023 (Tue) Zeilonka's Divide and conquer algorithm for parity games Section 3.3.1 from [1]
Lecture 4 12.01.2023 (Thu) Divide and conquer with dominion preprocessing Section 3.3.2 from [1]
Lecture 5 19.01.2023 (Thu) Small progress measures algorithm: single player case Notes
Lecture 6 25.01.2023 (Wed) Small progress measures algorithm: two player case
Module 2: Mean-payoff games
Lecture 7 31.01.2023 (Tue) Mean-payoff games: introduction, first-cycle version [11] Notes
Lecture 8 08.02.2023 (Wed) Mean-payoff games: positional determinacy [11] Notes
Lecture 9 09.02.2023 (Thu) Mean-payoff games: value iteration, computing uniform positional strategies [8] Notes
Lecture 10 14.02.2023 (Tue) Problem solving session Problem sheet
Module 3: Markov Decision Processes (MDPs) and Simple Stochastic Games (SSGs)
Lecture 11 28.02.2023 (Tue) Markov Chains, Markov Decision Processes (MDPs): value vector, optimality equations and optimal strategies Notes
Lecture 12 01.03.2023 (Thu) MDPs: strategy improvement, linear programming, value iteration Notes
Lecture 13 07.03.2023 (Tue) SSGs: definition, value vector, optimality equations, unique solution, strategy improvement algorithm to compute value vector Sections 1, 2 of [4] Notes
Lecture 14 09.03.2023 (Thu) SSGs: solution via quadratic programming Sections 2.1, 3.1 of [6]
Problem Sheet 2     Problem Sheet 3
Lecture 15 18.03.2023 (Sat) Solutions to Problem sheets Sheet 2 solutions    

Sheet 3 solutions
Lecture 16 23.03.2023 (Thu) Discounted Payoff games: definition, value vector, optimality equations
Lecture 17 30.03.2023 (Thu) MPGs to DPGs; DPGs to arbitrary SSGs; Arbitrary SSGs to Condon style SSGs Sections 5 and 6 of [8]
Module 4: Cops and robbers game
Lecture 18 04.04.2023 (Tue) Cops and robbers game; tree-width; tree-width k implies k+1 cops can find robber Section 1 of [9]