Skip to main content

Why play and how to win infinite games?

Marcin Jurdzinski ( University of Warwick )
Infinite games arise in areas as diverse as set theory, logic and
automata theory, verification and controller synthesis, artificial
intelligence, algorithms, computational complexity, and operations
research.  This talk will first mention some applications of infinite
games by providing motivating examples.  It will then survey zero-sum
infinite-duration games played on finite graphs and the computational
complexity of solving them, i.e., of computing optimal strategies for
both players.

In particular, parity, average-reward, and discounted games will be
defined and related to fundamental algorithmic problems in automata
theory, logic, and verification.  A survey of diverse algorithmic
techniques for solving infinite games will be given, including
divide-and-conquer, dynamic programming, local search, and
mathematical programming.  The intriguing complexity-theoretic status
of infinite games on graphs will be discussed and related to the,
recently resolved, computational complexity of computing Nash
equilibria in matrix games.

Share this: