Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Stéphane Gaubert - INRIA and CMAP, École Polytechnique, CNRS, France

Non-linear Perron-Frobenius theory applied to zero-sum games

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

Xavier Allamigeon - CMAP, École Polytechnique, France

Tropicalizing semialgebraic pivoting rules

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.

Letzte Aktualisierung: 10.04.2014