Logistics:

Credits:	4
Meetings:	Tuesdays and Thursdays, 1:30pm to 2:30pm
Location:	AC-04-705

Course Description: Games on graphs are combinatorial games that provide a mathematical footing for a variety of two-player games of perfect information on discrete objects. In this study module, we will look at some algorithmic problems in the following games, along with their connections to logic, automata, verification, synthesis, and reinforcement learning:

1. Regular Games: Including reachability games, büchi games and their connection to temporal specification and reactive synthesis, and parity games.
2. Ehrenfeucht-Fraïssé Games: Including its equivalence to monadic second-order logic and game characterization of regular languages.
3. Stochastic Games: Including markov decision processes, simple stochastic games, and their connection to reinforcement learning.

Resources and References:

1. Games on Graphs, edited by Nathanaël Fijalkow (2023).
2. Languages, Automata, and Logic, by Wolfgang Thomas (1996).
3. Lectures in Game Theory for Computer Scientists, edited by Krzysztof R. Apt and Erich Grädel (2011).

Grading Rubric: The course will have reading, discussions, scribing, and an end-semester exam.

1. Scribing: 40%
2. Attendance and class-participation: 30%
3. End-semester Exam: 30%

Attendance Policy: The study module will require 100% attendance.