Lecture Series in IRIF : Games on Graphs and Linear Programming Abstractions

Two-Player Turn-Based Stochastic Games (2TBSG) on graphs is an intriguing family of games. Mean-payoff Games (MPG), Energy Games (EG) and parity games (PG) are special classes of such games. Parity games are equivalent to some highly motivated problems in automata theory and automatic verification. The decisions problems corresponding to these games are in NP ∩ co-NP . The question whether there is a polynomial time algorithm for solving these games is a major open problem.