Monday, April 28, 2014
Technische Universität Berlin
Fakultät II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
We will survey some recent applications
of operator methods to zero-sum two player games. The latter are
governed by Shapley operators. These are order preserving sup-norm
nonexpansive maps. They can be thought of as non-linear Perron-Frobenius maps
deformed by log-glasses.
Then, the study of the asymptotic behavior of the
value of the game as the horizon tends to infinity, as well as mean
payoff problems, reduce to non-linear fixed point problems.
This allows us to apply methods from non-linear analysis
to derive game results with a combinatorial flavor.
These include: ergodicity
conditions for games -- which guarantee that the mean payoff is
independent of the initial state --, asymptotic results (existence of
states achieving the best mean payoff, minimax characterization
à la Collatz-Wielandt of the mean payoff), characterization of the
convergence rate of value iteration in terms of non-linear spectral
radii. An application
of these methods to the complexity analysis of
policy iteration for zero sum games will be finally presented.
This lecture is based on joint works with Marianne Akian, Jerôme Bolte, Roger Nussbaum, and Guillaume Vigeral (see arXiv:1112.5968, 1012.4765, 1201.1536, 1301.1967, and 1310.4953)
Colloquium - 16:00
Abstract:
In this talk, we show that the simplex algorithm endowed with a large class of pivoting rules can be transposed to the tropical setting. Our motivation is to define new algorithms to solve mean payoff games, which can be reduced to tropical linear programming.
Our approach handles "semi-algebraic" pivoting rules, ie which are based on the computation of the sign of finitely many polynomials. It supports both deterministic and randomized rules. We characterize the complexity of the tropical counterpart of these pivoting rules in terms of the Newton polytopes of the polynomials involved.
As an application, we obtain transfer results from the complexity of the simplex algorithm to the one of mean payoff games.
This is a joint work with P. Benchimol, S. Gaubert, and M. Joswig.