Marianne Akian – Mathematics and Decision

$\begin{quote} \begin{center} \textbf{Repeated zero-sum games: from operators to algorithms and tropical geometry} \end{center} \medskip Repeated zero-sum 2-player deterministic or stochastic games with a finite state space can be studied with the help of the Shapley dynamic programming equation. This equation allows one to compute not only the value function but also optimal strategies of the two players. When considering mean-payoff criteria, under an ergodicity condition, the dynamic programming equation reduces to a fixed point problem of a monotone operator acting on a projective space. It is thus related to nonlinear Perron-Frobenius theory. This approach also applies to entropy games -- a multiplicative version of mean-payoff stochastic games. This talk will present an overview of existence and uniqueness results for such non-linear fixed point problems. It will include applications to the convergence and complexity analysis of algorithms, showing also how these techniques can be used to study and solve problems from tropical geometry. This talk is based on joint works with Antoine Bereau, Stéphane Gaubert, Julien Grand Clément, Jérémie Guillaud, Alexander Guterman, Antoine Hochart, Ulysse Naepels, Yang Qi, Omar Saadi, Basile Terver. \end{quote}$