PhD in Computer Science

PhD Course on "Game Theory"

February 11 - March 3

Series to which this belongs

33° ciclo
34° ciclo
35° ciclo


The aim of this course consists of providing the foundations of synthesis problems and how they are strongly connected to the winning strategies for games on graphs.
The course is divide into four main topics:
(i) first we will de_ne the sysnthesis problem in its general form and we will establish a connection to games on graph with single-objective;
(ii) in the second part we will analyze the algorithms, and the related complexity, for solving single-objective games on graphs;
(iii) then we will to analyze recent results, both positive and negative w.r.t. to decidability, on multi-objective games on graphs;
(iv) finally we consider how to solve stochastic games on graphs.
At the end of this course the student will be able to:
 a) formalize and analyze real-world synthesis problems;
b) find the right technnique and tools for solving a synthesis problem;
c) know the basic results underlying graph games together with an idea of the main research directions in the field.
1 The synthesis problem (5 hours)
2 Graph games with single objective (5 hours)
3 Graph games with multiple objectives (5 hours)
4 Stochastic games (5 hours)


  • pdf   Flyer   (pdf, it, 387 KB, 27/05/20)