Tropical algebra, optimization and games

Stéphane Gaubert*

Common lecture to Master Optimization, University Paris-Saclay and IPP and Master Mathématiques de la modélisation, Year 2022-2023. The lecture is in English. It will be scheduled from November to January.

The lectures will take place in Paris, at Sorbonne Université, Campus Jussieu (next to the Jussieu tube station), room 104 in building 15/25, see https://www.ljll.math.upmc.fr/MathModel/info/pour_venir.html for information on how to come to Jussieu.

Here is the schedule: Monday 28th Nov, 9h00-12h30 Monday 5th Dec, 9h00-12h30 Monday 12th Dec, 9h00-12h30 Monday 9th Jan, 9h00-12h30 Monday 16th Jan, 9h00-12h30 Monday 23rd Jan, 9h00-12h30 Monday 30th Jan, 9h00-12h30 Monday 6th February, 9h00-12h30

Further resources (including copy of earlier lectures) are available for registered students on the moodle of the lecture MAP654G. The access to the moodle site of IPP requires a registration, students not belonging to IPP should contact me at the beginning of the lecture to obtain access to this site.

Exam. Choose an article among the ones provides in the directories of http://www.cmap.polytechnique.fr/~gaubert/COURSM2/

Prepare detailed slides + oral presentation 30 minutes , date to be agreed (start Feb).


The dynamic programming approach allows one to deal with deterministic and stochastic optimal control, and more generally, with repeated zero-sum two-player problems, by studying operators introduced by Bellan and Shapley, that propagate the value function. These operators are order preserving, and nonexpansive with respect to natural norms or metrics. For discrete problems, they have a rich combinatorial structure, which can be understood through tropical geometry. The term “Tropical” refers to structures of “characteristic one”, in which the addition is idempotent. The max-plus semifield, which consists of the real numbers equipped with the maximum, thought of as an additive operation, and the addition, thought of as a multiplication operation, is the prototypical example of such structures. The tropical approach provides a geometrical intepretation of repeated zero-sum games, leading to new insights.

The objective of this lecture is to present methods from tropical mathematics and from Perron-Frobenius theory (fixed point theory of nonexpansive and order preserving non-linear mappings), with applications to zero-sum repeated games. We have a special interest in problems with long horizon, in which one is interested in the growth of the income as the horizon tends to infinity, including the “mean payoff problem”. An emphasis is made on combinatorial aspects and computational complexity issues. The lecture is illustrated by applications, with examples of one or two-player games originating from population dynamics, nonnegative matrix theory, discrete event systems, or nonnegative tensors.

The lecture has relatively few prerequisites, except elements of optimisation (convexity, polyhedra) and analysis (fixed point theory). The needed results are systematically recalled. This lecture is primarily of a mathematical nature, however, it comprises a significant part concerning algorithms and modelling, which may be of interest to students interested by the applications of operations research and by games in computer science.

1  Introduction

Various examples of one and two-player games. Examples from population dynamics or discrete event systems that reduce to games. The mean payoff problem for deterministic games - a challenging open problem in computational complexity. First steps in the tropical approach: tropicalization of polynomials, log-convexity of the Laplace transform, generalizations of Cauchy bound on polynomial roots.

2  The dynamic programming approach: from Bellman to Shapley operators

We review the basics of dynamic programming, showing that the value function is governed by Shapley operators, or by Bellman operators in the one player case. First properties of Shapley operators.

3  The one player deterministic problem

The simplest combinatorial case: the one player deterministic problem. Asymptotics of the value function. How it is controlled by non-linear eigenvectors. Structure of the eigenspace. The turnpike property. (properties of optimal strategies when the horizon tends to infinity).

4  Non-linear Perron-Frobenius theory, part I: basics

Order preserving maps on cones. Hilbert’s and Thompson’s metric. Examples of the orthant and of the cone of positive semidefinte matrices. Nonexpansiveness properties in these metrics. The ergodic non-linear eigenproblem, and its applications: Markov decision processes, combinatorial games, matrix scaling problems (entropy maximization), population dynamics.

5  Non-linear Perron-Frobenius theory, part II: spectral theory

Existence and uniqueness of nonlinear fixed-points of non-expansive mappings. Application to the non-linear eigenproblem. Nonlinear généralisations of the Perron-Frobenius theorem.

6  Horoboundaries and what they tell on the dynamics of nonexpansive mappings

The horoboundary of a metric space. A generalized Wolff-Denjoy theorem. Application to the mean payoff problem. Collatz-Wielandt certificates.

7  Algorithms for zero-sum games and complexity issues

Analysis of non-linear power algorithms (aka value iteration). The Birkhoff-Hopf contraction theorem. Dobrushin ergodicity coefficient and its nonlinear extensions. Policy iteration (à la Hoffman-Karp) for zero-sum games. Relation between mean payoff games and linear or semidefinite programming over nonarchimedean fields.

Documents

Page of the lecture:

http://www.cmap.polytechnique.fr/~gaubert/coursodjups/index.html

Références

[abg05]
M. Akian, R. Bapat, and S. Gaubert. Max-plus algebras. In L. Hogben, editor, Handbook of Linear Algebra (Discrete Mathematics and Its Applications), volume 39. Chapman & Hall/CRC, 2006. Chapter 25, Available electronically from http://www.cmap.polytechnique.fr/~gaubert/PAPERS/hla-preprint.pdf.
[spectral2]
M. Akian and S. Gaubert. Spectral theorem for convex monotone homogeneous maps, and ergodic control. Nonlinear Analysis. Theory, Methods & Applications, 52(2):637–679, 2003. arXiv:math.SP/0110108.
[marianne102013]
Marianne Akian and Stéphane Gaubert. Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial, 2013. arXiv:1310.4953.
[AGGut10]
M. Akian, S. Gaubert, and A. Guterman. Tropical polyhedra are equivalent to mean payoff games. International of Algebra and Computation, 22(1):125001 (43 pages), 2012. arXiv:0912.2462, doi:10.1142/S0218196711006674.
[agn12]
M. Akian, S. Gaubert, and R. Nussbaum. Uniqueness of the fixed point of nonexpansive semidifferentiable maps. To appear in Trans. AMS., 2014. arXiv:1201.1536.
[arxiv1]
S. Gaubert and J. Gunawardena. The Perron-Frobenius theorem for homogeneous, monotone functions. Trans. of AMS, 356(12):4931–4950, 2004. arXiv:math.FA/0105091, doi:10.1090/S0002-9947-04-03470-1.
[hansen2011strategy]
T.D. Hansen, P.B. Miltersen, and U. Zwick. Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. In Innovations in Computer Science 2011, pages 253–263. Tsinghua University Press, 2011.
[itenberg]
I. Itenberg, G. Mikhalkin, and E. Shustin. Tropical algebraic geometry. Oberwolfach seminars. Birkhäuser, 2007.
[nussbaum88]
Roger D. Nussbaum. Hilbert’s projective metric and iterated nonlinear maps. Memoirs of the AMS, 75(391), 1988.
[viro]
O. Viro. Dequantization of real algebraic geometry on logarithmic paper. In European Congress of Mathematics, Vol. I (Barcelona, 2000), volume 201 of Progr. Math., pages 135–146. Birkhäuser, Basel, 2001. arXiv:math/0005163.

*
INRIA and CMAP, École Polytechnique, UMR CNRS 7641, 92128 Palaiseau Cedex. Stephane.Gaubert@inria.fr

Ce document a été traduit de LATEX par HEVEA