Graph games are a mathematical framework to analyze reactive systems. A reactive system interacts with an environment and it consists of several variables. Consider the example of a train-gate controller, where there is a variable for the gate position (say, open, closed, closing), and a variable to denote positions of trains (say, away, approaching, at gate, crossed, gone). A state of the system is a valuation to the variables, such as the gate being open and train being away, or a train is approaching and the gate is closing. In graph games vertices of the graph represent states of the reactive system, edges of the graph represent transition of the reactive systems, paths of the graph represent behaviors of the system, and different interacting agents represent the different players. The associated research problem is the algorithmic and computational complexity analysis of games on graphs. In deterministic reactive systems, these questions have been quite deeply studied. The significant theoretical achievements have resulted in several algorithms and satisfactory computational complexity results for deterministic graph games with respect to omega-regular objectives (omega- regular objectives can express all commonly used properties of reactive systems). These algorithms can be used in practice, such as, automatically deriving AMBA-Bus protocol, widely used in industries, and the game- theoretic algorithms are routinely used in correctness analysis of complex, safety-critical systems.

Stochastic games comprise a general model for the study and analysis of dynamic interactions in economic and technological contexts. It includes the theory of repeated games, stopping games, differential games and mean-field games. Since its beginning, the main fields where repeated games are applied are economics, finance, biology, engineering and computer science, and it is impossible to overestimate the impact that the theory of stochastic games has had in these fields – as evidenced by the many game theorists that have been awarded the Nobel memorial prize in economics for their contributions to the theory of stochastic games. Recent advances in stochastic games include new computational tools, and approaches in continuous time, which are also the main tasks of this working group. Faced by the new applications and problems described in WGs 2 and 3, the role of this WG is to support the applications in these fields, by developing the rigorous mathematical foundations for the game problems arising therein.