Games on Graphs - Memory Requirements and Strategy Analysis

Explore a comprehensive seminar lecture from the Kolmogorov Seminar series that delves into the fascinating world of graph-based games and their strategic complexity. Learn about various types of strategies including positional strategies, finite memory, and infinite memory approaches while examining specific game types such as parity and mean-payoff games. Discover the fundamental memory requirements for different game scenarios and gain insights into the current state of knowledge in this mathematical field. Originally presented as part of the prestigious Kolmogorov seminar series on computational and descriptional complexity, which was established by Kolmogorov himself in 1979.