Title: Smoothed analysis of deterministic discounted and mean-payoff games
Speaker: Mateusz Skomra (LAAS-CNRS)
Invited by: Bruno Loff (LASIGE, DM/FCUL)
When: March 04 and 05, 2024, 14:00
Where: FCUL, C6.2.33

Video recording: part 1, part 2

Abstract: Deterministic turn-based discounted and mean-payoff games are fundamental classes of games with an unsettled complexity. They belong to the complexity classes NP and coNP, but are not known to be polynomial-time solvable. Furthermore, they are at the bottom of a hierarchy of complexity classes that stratifies the NP search problems. Despite these properties, the problem of solving turn-based games efficiently has been open for 35 years. Nevertheless, even though we do not know how to solve these games in polynomial time in the worst case, practical experiments suggest that solving random games is easy. More precisely, the policy iteration methods, which can take exponentially many steps in the worst case, converge quickly to the solution when the weights of the game are taken at random. The aim of my talk is to give an explanation of this phenomenon using the framework of “smoothed analysis” introduced by Spielman and Teng to explain the real-world efficiency of the simplex method. We prove that if the weights of a turn-based deterministic game are perturbed by a Gaussian noise, then the resulting randomized problem can be solved efficiently by a variant of a policy iteration method. In the talk, I will give an introduction to turn-based discounted and mean-payoff games, explain the basic algorithms that are used to solve them, and finish by discussing the smoothed analysis result. This talk is based on a joint work with Bruno Loff.

Bio: I am a CNRS researcher working in Laboratoire d’analyse et d’architecture des systèmes, within the POP research team. Until September 2020 I was a postdoctoral researcher at École normale supérieure de Lyon, CNRS, Laboratoire de l’Informatique du Parallélisme, within the research team MC2. From 2015 to 2018 I was a doctoral researcher at Centre de Mathématiques Appliquées, École polytechnique, CNRS, Université Paris-Saclay, within INRIA research team Tropical, where I worked under the supervision of Xavier Allamigeon and Stéphane Gaubert. My research is focused on the interplay between tropical geometry, convex optimization, and algorithmic game theory. I am also working on problems related to algebraic complexity.

Note: The entry was updated to include the video recording.

This presentation is supported by the project HOFGA, Grant agreement ID: 101041696, funded by European Reserach Council’s Horizon Europe programme.