We look at two player zero-sum games played on trees. When players have perfect information about their state of the game, finding max-min strategies is easily done by a bottom-up scan of the game-tree. If players do not have perfect information about the state of the game, but still, they remember their own history of actions, they are said to have perfect recall. Max-min strategies in perfect recall games can be synthesized in polynomial-time. When players forget even their own history of actions, they are said to have imperfect recall. Solving imperfect recall games is known to be NP-hard.
In this talk, we will present new complexity results for imperfect recall games: firstly, we show that they are as hard as solving certain problems in the first order theory or reals, and secondly, we propose new polynomial-time solvable fragments of imperfect recall games.
Joint work with Hugo Gimbert, Kristoffer Arnsfelt Hansen and Soumyajit Paul.
Short Bio:
B Srivathsan is a faculty member at the Chennai Mathematical Institute. He earned his PhD from the University of Bordeaux, and his Masters and Bachelors from IIT Bombay. His research interests lie in the areas of automata theory, games and formal verification.
