Tropical considerations in dynamic programming
Stephane.Gaubert@inria.fr
INRIA and CMAP, Ecole
Polytechnique
Optimization, Games, and Dynamics
IHP, Paris, November 28-29, 2011
Based on works with Akian,Guterman arXiv:0912.2462 to appear in IJAC,
Allamigeon, Katz JCTA11,LAA11, Vigeral Math. Proc. Phil. Soc.11,
McEneaney, Qu CDC11
Work partially supported by the Arpege programme of ANR and by Digiteo Labs
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
1 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 =
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
2 3 =
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
2 3 =5
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
2 3 =5
5/2 =
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
2 3 =5
5/2 =3
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
2 3 =5
5/2 =3
23 =
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
2 3 =5
5/2 =3
23 =2 2 2 = 6
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
2 3 =5
5/2 =3
23 =2 2 2 = 6
1 =
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
7 0
2
=
3
1
2 3 =5
5/2 =3
23 =2 2 2 = 6
1 =0.5
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
Max-plus or tropical algebra
In an exotic country, children are taught that:
a + b = max(a, b)
a b = a + b
So
2 + 3 = 3
7 0
2
9
=
3
1
4
2 3 =5
5/2 =3
23 =2 2 2 = 6
1 =0.5
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
2 / 85
The notation a b := max(a, b), a b := a + b,
0 := , 1 := 0 is also used in the tropical/max-plus
litterature
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
3 / 85
The sister algebra: min-plus
a + b = min(a, b)
a b = a + b
2 + 3 = 2
2 3 = 5
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
4 / 85
The term tropical is in the honor of Imre Simon,
1943 - 2009
who lived in Sao Paulo (south tropic).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
5 / 85
These algebras were invented by various schools in the
world
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
6 / 85
Cuninghame-Green 1960- OR (scheduling, optimization)
Vorobyev 65 . . . Zimmerman, Butkovic; Optimization
Maslov 80- . . . Kolokoltsov, Litvinov, Samborskii, Shpiz. . . Quasi-classic
analysis, variations calculus
Simon 78- . . . Hashiguchi, Leung, Pin, Krob, . . . Automata theory
Gondran, Minoux 77 Operations research
Cohen, Quadrat, Viot 83- . . . Olsder, Baccelli, S.G., Akian initially
discrete event systems, then optimal control, idempotent probabilities,
combinatorial linear algebra
Nussbaum 86- Nonlinear analysis, dynamical systems, also related work in
linear algebra, Friedland 88, Bapat 94
Kim, Roush 84 Incline algebras
Fleming, McEneaney 00- max-plus approximation of HJB
Puhalskii 99- idempotent probabilities (large deviations)
and now in tropical geometry, after Viro, Mikhalkin, Passare, Sturmfels and
many.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
7 / 85
Menu: connections between. . .
tropical convexity
dynamic programming / zero-sum games
Perron-Frobenius theory
metric geometry
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
8 / 85
Some elementary tropical geometry
A tropical line in the plane is the set of (x, y ) such that
the max in
ax + by + c
is attained at least twice.
max(x, y , 0)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
9 / 85
Some elementary tropical geometry
A tropical line in the plane is the set of (x, y ) such that
the max in
max(a + x, b + y , c)
is attained at least twice.
max(x, y , 0)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
9 / 85
Two generic tropical lines meet at a unique point
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
10 / 85
By two generic points passes a unique tropical line
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
10 / 85
non generic case
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
10 / 85
non generic case resolved by perturbation
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
10 / 85
Tropical segments:
f
g
[f , g ] := {f + g | , R {}, + = 1}.
(The condition , 0 is automatic.)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
11 / 85
Tropical segments:
f
g
[f , g ] := { sup( + f , + g ) | ,
R {}, max(, ) = 0}.
(The condition , is automatic.)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
11 / 85
Tropical convex set: f , g C = [f , g ] C
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
12 / 85
Tropical convex set: f , g C = [f , g ] C
Tropical convex cone: ommit + = 1, i.e., replace
[f , g ] by {sup( + f , + g ) | , R {}}
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
12 / 85
A max-plus tetrahedron?
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
13 / 85
The previous drawing was generated by Polymake of
Gawrilow and Joswig, in which an extension allows one to
handle easily tropical polyhedra. They were drawn with
javaview. See Joswig arXiv:0809.4694 for more information.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
14 / 85
Why?
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
15 / 85
Gelfand, Kapranov, and Zelevinsky defined the amoeba of an
algebraic variety V (C )n to be the log-log plot
A(V ) := {(log |z1 |, . . . , log |zn |) | (z1 , . . . , zn ) V } .
y +x +1=0
max(log |x|, log |y |, 0)
attained twice
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
16 / 85
Gelfand, Kapranov, and Zelevinsky defined the amoeba of an
algebraic variety V (C )n to be the log-log plot
A(V ) := {(log |z1 |, . . . , log |zn |) | (z1 , . . . , zn ) V } .
y +x +1=0
max(log |x|, log |y |, 0)
attained twice
|y | |x| + 1, |x| |y | + 1, 1 |x| + |y |
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
16 / 85
Gelfand, Kapranov, and Zelevinsky defined the amoeba of an
algebraic variety V (C )n to be the log-log plot
A(V ) := {(log |z1 |, . . . , log |zn |) | (z1 , . . . , zn ) V } .
y +x +1=0
max(log |x|, log |y |, 0)
attained twice
X := log |x|, Y := log |y |
Y log(e X + 1), X log(e Y + 1), 1 e X + e Y
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
16 / 85
real tropical lines
y =x +1
Y = max(X , 0)
X = log(e X + 1)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
16 / 85
real tropical lines
x +y =1
max(X , Y ) = 0
log(e X + e Y ) = 1
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
16 / 85
real tropical lines
x =y +1
X = max(Y , 0)
X = log(e X + 1)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
16 / 85
Viros log-glasses, related to Maslovs dequantization
a +h b := h log(e a/h + e b/h ),
h 0+
With h-log glasses, the amoeba of the line retracts to the
tropical line as h 0+
y +x +1=0
max(log |x|, log |y |, 0)
attained twice
max(a, b) a +h b h log 2 + max(a, b)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
17 / 85
Similar to convergence of p-norm to sup-norm
[a, b] := {a +p b, , 0, +p = 1
a +p b = (ap + b p )1/p
The convex hull in the +h / +p sense converges to the
tropical convex hull as h 0 / p (Briec and Horvath).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
18 / 85
All the results of classical convexity have tropical
analogues, sometimes more degenerate. . .
generation by extreme points Helbig; SG, Katz 07;
Butkovic, Sergeev, Schneider 07
projection / best-approximation : Cohen, SG,
Quadrat 01,04; Singer
Hahn-Banach analytic Litvinov, Maslov, Shpiz 00; Cohen,
SG, Quadrat 04; geometric Zimmermann 77, Cohen, SG,
Quadrat 01,05; Develin, Sturmfels 04, Joswig 05
cyclic projections Butkovic, Cuninghame-Green TCS03; SG,
Sergeev 06
Radon, Helly, Caratheodory, Colorful Caratheodory,
Tverberg: SG, Meunier DCG09
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
19 / 85
See Passare & Rullgard, Duke Math. 04 for more information
on amoebas
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
20 / 85
This talk
Tropical convexity is equivalent to dynamic programming
(zero-sum games).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
21 / 85
This talk
Tropical convexity is equivalent to dynamic programming
(zero-sum games).
finite dimensional convex sets (cones) stochastic
games with finite state spaces
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
21 / 85
This talk
Tropical convexity is equivalent to dynamic programming
(zero-sum games).
finite dimensional convex sets (cones) stochastic
games with finite state spaces
infinite dimensional convex cones, spaces of functions
stationnary solutions of Hamilton-Jacobi(-Bellman)
equations (1-player: Fathis weak KAM solutions)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
21 / 85
This talk
Tropical convexity is equivalent to dynamic programming
(zero-sum games).
finite dimensional convex sets (cones) stochastic
games with finite state spaces
infinite dimensional convex cones, spaces of functions
stationnary solutions of Hamilton-Jacobi(-Bellman)
equations (1-player: Fathis weak KAM solutions)
leads to: equivalence (computational complexity)
results, algorithms, approximation methods, . . .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
21 / 85
Shapley operators
X = C (K ), even X = Rn ; Shapley operator T ,
X
Ti (x) = max min riab +
Pijab xj ,
i [n]
aAi bBi,a
1jn
[n] := {1, . . . , n} set of states
a action of Player I, b action of Player II
riab payment of Player II to Player I
Pijab transition probability i j
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
22 / 85
Shapley operators
X = C (K ), even X = Rn ; Shapley operator T ,
X
Ti (x) = max min riab +
Pijab xj ,
i [n]
aAi bBi,a
1jn
T is order preserving and additively homogeneous:
x y = T (x) T (y )
T ( + x) = + T (x),
R
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
22 / 85
Shapley operators
X = C (K ), even X = Rn ; Shapley operator T ,
X
Ti (x) = max min riab +
Pijab xj ,
i [n]
aAi bBi,a
1jn
Conversely, any order preserving additively homogeneous
operator is a Shapley operator (Kolokoltsov), even with
degenerate transition probabilities (deterministic)
Gunawardena, Sparrow; Singer, Rubinov,
Ti (x) = sup Ti (y ) + min (xi yi )
y R
Stephane Gaubert (INRIA and CMAP)
1in
Tropical & dynamic programming
IHP
22 / 85
Variant. T is additively subhomogeneous if
T ( + x) + T (x),
R+
P
This corresponds to 1 j Pijab = death probability > 0.
Order-preserving + additively (sub)homogeneous =
sup-norm nonexpansive
kT (x) T (y )k kx y k .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
23 / 85
Variant. T is additively subhomogeneous if
T ( + x) + T (x),
R+
P
This corresponds to 1 j Pijab = death probability > 0.
Order-preserving + additively homogeneous top
nonexpansive
t(T (x) T (y )) t(x y ),
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
t(z) := max zi .
i
IHP
23 / 85
Variant. T is additively subhomogeneous if
T ( + x) + T (x),
R+
P
This corresponds to 1 j Pijab = death probability > 0.
Order-preserving + additively subhomogeneous
top+ nonexpansive
t+ (T (x)T (y )) t+ (x y ),
Stephane Gaubert (INRIA and CMAP)
t+ (z) := max(max zi , 0) .
Tropical & dynamic programming
IHP
23 / 85
Repeated games
The value of the game in horizon k starting from state i
is (T k (0))i .
We are interested in the long term payment per time unit
(T ) := lim T k (0)/k
k
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
24 / 85
Max and Min flip a coin to decide who makes the move.
Min always pay.
3
2
2
1
Stephane Gaubert (INRIA and CMAP)
8
3
Tropical & dynamic programming
IHP
25 / 85
Max and Min flip a coin to decide who makes the move.
Min always pay.
3
2
2
1
8
3
1
vik+1 = (max(cij + vjk ) + min (cij + vjk )) .
j: ij
2 j: ij
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
25 / 85
3
2
2
1
8
3
v1 = 12 (max(2 + v1 , 3 + v2 , 1 + v3 ) + min(2 + v1 , 3 + v2 , 1 + v3 )
5
0 v2 = 1 (max(1 + v1 , 2 + v2 , 8 + v3 ) + min(1 + v1 , 2 + v2 , 8 + v3 )
2
4
v3 = 12 (max(2 + v1 , 1 + v2 ) + min(2 + v1 , 1 + v2 )
this game is fair
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
26 / 85
1
v = (max vjk + min vjk ) ,
j: ij
2 j: ij
vi , i boundary prescribed:
discrete variant of Laplacian infinity (Oberman), or
Richman games (Tug of war).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
27 / 85
Optimality certificates
More generally, for u Rn and R,
T (u) u = (T ) 0
T (u) u = (T ) 0
T (u) = + u = (T ) = (, . . . , ) .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
28 / 85
Optimality certificates
More generally, for u Rn and R,
T (u) u = (T ) 0
T (u) u = (T ) 0
T (u) = + u = (T ) = (, . . . , ) .
Sufficient condition SG+Gunawardena, TAMS 2004: if G (T ) is
strongly connected, then the additive eigenproblem
T (u) = + u with R is solvable
G (T ): arc i j if lims Ti (sej ) = +.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
28 / 85
T (u) = + u, u Rn may not have a solution.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
29 / 85
T (u) = + u, u Rn may not have a solution.
Indeed, it may happen that j (T ) 6= k (T ) for two
different initial states j, k.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
29 / 85
T (u) = + u, u Rn may not have a solution.
Indeed, it may happen that j (T ) 6= k (T ) for two
different initial states j, k.
(T ) = limk T k (0)/k may even not exist if the action
spaces are infinite (Kohlberg, Neyman)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
29 / 85
T (u) = + u, u Rn may not have a solution.
Indeed, it may happen that j (T ) 6= k (T ) for two
different initial states j, k.
(T ) = limk T k (0)/k may even not exist if the action
spaces are infinite (Kohlberg, Neyman)
However. . .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
29 / 85
T (u) = + u, u Rn may not have a solution.
Indeed, it may happen that j (T ) 6= k (T ) for two
different initial states j, k.
(T ) = limk T k (0)/k may even not exist if the action
spaces are infinite (Kohlberg, Neyman)
However. . .
If the graph of T is semi-algebraic, then (T ) does
exists. Neyman 04, extending Bewley and Kohlberg 76.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
29 / 85
By subadditivity, the following limits (indep of x Rn ) do
exist
kT k (x) xk
kT k (x) xk
= inf
k
k1
k
k
lim
t(T k (x) x)
t(T k (x) x)
= inf
(T ) := lim
k1
k
k
k
b(T k (x) x)
b(T k (x) x)
(T ) := lim
= sup
k
k
k
k1
t(z) := max zi ,
i
Stephane Gaubert (INRIA and CMAP)
b(z) := min zi .
Tropical & dynamic programming
IHP
30 / 85
In general, think of T as a Perron-Frobenius operator in
log-glasses:
F = exp T log,
Rn+ Rn+
F extends continuously from int Rn+ to Rn+ Burbanks,
Nussbaum, Sparrow.
Theorem (non-linear Collatz-Wielandt, Nussbaum, LAA 86)
(F ) = lim kF k (x)k1/k ,
k
x Int Rn+
= max{ R+ | F (v ) = v , v Rn+ , v =
6 0}
= max{ R+ | F (v ) v , v Rn+ , v =
6 0}
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
31 / 85
(T ) := lim max [T k (0)]j /k = log (F )
k 1jn
SG, Gunawardena, TAMS 04: there always exists an initial
state which achieves the best payoff
x Rn ,
j, [T k (x)]j k(T ) + xj ,
Theorem (non-linear Collatz-Wielandt, Nussbaum, LAA 86)
(F ) = lim kF k (x)k1/k ,
k
x Int Rn+
= max{ R+ | F (v ) = v , v Rn+ , v =
6 0}
= max{ R+ | F (v ) v , v Rn+ , v =
6 0}
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
31 / 85
Correspondence between tropical convexity and
zero-sum games
Theorem (Akian, SG, Guterman, arXiv:0912.2462 IJAC)
TFAE:
C closed tropical convex cone
C = {u (R {})n | u T (u)} for some
Shapley operator T
and MAX has at least one winning state ((T ) 0) if
and only if
C 6= {(, . . . , )} .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
32 / 85
Recall C (R {})n is a tropical convex cone if
u, v C , R{} = sup(u, v ) C , +u C .
Easy implication: T order preserving and additively
homogeneous = {u | u T (u)} is a closed tropical
convex cone
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
33 / 85
Recall C (R {})n is a tropical convex cone if
u, v C , R{} = sup(u, v ) C , +u C .
Easy implication: T order preserving and additively
homogeneous = {u | u T (u)} is a closed tropical
convex cone
Remark: {u | u T (u)} is a dual tropical (min-plus)
cone.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
33 / 85
Conversely, any closed tropical convex cone can be
written as
\
C=
Hi
iI
where (Hi )iI is a family of tropical half-spaces.
Hi : Ai x Bi x
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
34 / 85
Conversely, any closed tropical convex cone can be
written as
\
C=
Hi
iI
where (Hi )iI is a family of tropical half-spaces.
Hi : max aij +xj max bik +xk ,
1jn
1kn
aij , bij R{}
[T (x)]j = inf aij + max bik + xk .
iI
Stephane Gaubert (INRIA and CMAP)
1kn
Tropical & dynamic programming
IHP
34 / 85
Conversely, any closed tropical convex cone can be
written as
\
C=
Hi
iI
where (Hi )iI is a family of tropical half-spaces.
Hi : max aij +xj max bik +xk ,
1jn
aij , bij R{}
1kn
[T (x)]j = inf aij + max bik + xk .
iI
1kn
x T (x) max aij + xj max bik + xk , i I .
1jn
Stephane Gaubert (INRIA and CMAP)
1kn
Tropical & dynamic programming
IHP
34 / 85
x3
x3
2x1 x2 3x3
V
b
x1
x2
x1
x2
2 + x1 max(x2 , 3 + x3 )
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
35 / 85
x3
b
x1
x2
c
2 + x1 max(x2 , 3 + x3 )
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
35 / 85
Hi : max aij + xj max bik + xk
1jn
1kn
[T (x)]j = inf aij + max bik + xk .
iI
1kn
Interpretation of the game
State of MIN: variable xj , j {1, . . . , n}
State of MAX: half-space Hi , i I
In state xj , Player MIN chooses a tropical half-space
Hi with xj in the LHS
In state Hi , player MAX chooses a variable xk at the
RHS of Hi
Payment aij + bik .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
36 / 85
Now, (T ) 0 C 6= {} follows from
Nussbaums Collatz-Wielandt theorem, F := exp T log,
(T ) 0
(F ) 1
v Rn+ , v 6 0, F (v ) v
u 6 , T (u) u
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
37 / 85
Polyhedral case
Theorem (Akian, SG, Guterman arXiv:0912.2462 IJAC)
If the game is deterministic with finite action spaces (i.e.
C is a tropical polyhedron), then the set of winning states
is the support of C :
{i | u C , ui 6= } = {i | i (T ) 0}
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
38 / 85
x1 a + max(x2 2, x3 1)
2 + x2 a + max(x1 , x3 1)
max(x2 2, x3 a) x1 + 2
(H1 )
(H2 )
(H3 )
value (T )j = (2a + 1)/2, j.
0
a2
a
2
a1
2
a1
2
a1
2
a1
2
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
3
IHP
39 / 85
x3
x3
H3
H1
x1
H3
H2
H2
x1
x2
x2
H1
a = 3/2, victorious strategy of Min: certificate of
emptyness involving d inequalities (Helly)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
40 / 85
x3
x3
H3
H1
x1
H3
H2
x1
H2
x2
x2
H1
a = 1, victorious strategy of Max: tropical polytrope 6=
included in the convex set
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
40 / 85
Corollary
Feasibiliby in tropical linear programming, i.e.,
?u (R{})n , max aij +uj max bij +uj , 1 i p
j
is polynomial-time equivalent to mean payoff games.
Mean payoff games: Gurvich, Karzanov, Khachyan 86; are in
NP coNP: Zwick, Paterson 96.
Tropical convex sets are log-limits of classical convex sets:
polynomial time solvability of mean payoff games might
follow from a strongly polynomial-time algorithm in linear
programming (Schewe).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
41 / 85
Other problems in tropical programming, like tropical
Farkas (Ax Bx = cx dx?) also equivalent to
mean payoff games by Allamigeon, SG, Katz, LAA 11.
See also SG, Katz, Sergeev for linear-fractional tropical
programming
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
42 / 85
An application: perturbation of eigenvalues
Exercise.
Stephane Gaubert (INRIA and CMAP)
1 4
A = 0 2 ,
2 0
Tropical & dynamic programming
IHP
43 / 85
An application: perturbation of eigenvalues
Exercise.
1 4
A = 0 2 ,
2 0
Show without computation that the eigenvalues have the
following asymptotics as 0
L1 1/3 , L2 j1/3 , L3 j 2 1/3 .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
43 / 85
Assume that the entries of A have Puiseux series
expansions in , or even that A = a + b, a, b Cnn .
L1 , . . . , Ln eigenvalues of A .
v (s): opposite of the smallest exponent of a Puiseux
series s.
1 n : tropical eigenvalues of v (A ).
Theorem (Akian, Bapat, SG CRAS04, arXiv:0402090)
v (L1 ) + + v (Ln ) 1 + + n
and equality holds under generic (Lidski-type) conditions.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
44 / 85
The maximal tropical eigenvalue 1 coincides with the
ergodic constant of the one-player game
+ ui = max val(A )ij + uj , i
1jn
is the maximal circuit mean.
In general, tropical eigenvalues are non-differentiability
points of a parametric optimal assignment problem =
Legendre transform a the generic Newton polygon
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
45 / 85
1 4
A = 0 2 ,
2 0
1 0 4
A = 1 2 .
1 2
We have 1 = 1/3, corresponding to the critical circuit:
2
Eigenvalues:
L1 1/3 , L2 j1/3 , L3 j 2 1/3 .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
46 / 85
More algorithmic issues . . .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
47 / 85
Tropical double description,
Allamigeon,SG, Goubault,
STACS 10
Can compute efficiently all the extreme generators of
P := {x | Ax Bx}, where A, B Rpd
max (analogue of
Fukuda/Motzkin).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
48 / 85
Tropical double description,
Allamigeon,SG, Goubault,
STACS 10
For d = 4 and p = 10, only 24 vertices, but 1215
pseudo-vertices
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
48 / 85
(Coarse) worst case bound of double description
O(p 2 d(d)(p + d)d1 ) where is the inverse of the
Ackermann function.
Better experimental behavior. Implementation in
TPLib/caml (Allamigeon).
Tropical polyhedra have fewer extreme points than in the
classical case (McMullen bound is not tight, Allamigeon,
SG, Katz, JCTA 11, exact bound for the number of extreme
points of Ax Bx: open).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
49 / 85
Bubble sort
Variables : i , j , k , x , y , z
Program :
local t {
i := x ;
j := y ;
k := z ;
i f x > y then
i := y ;
j := x ;
fi ;
i f j > z then
k := j ;
j := z ;
fi ;
i f i > j then
t := j ;
j := i ;
i := t ;
fi ;
};
Can prove
automatically that
k = max(x, y, z)?
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
50 / 85
and even that. . .
y = max(k , y ) ; max(k , z ) = z ;
max( j ,x , z ) = max(x , z ) ;
j = max( j ,k ) ; max(y , z ) = max( j ,y , z ) ;
max ( j , y , z ) = max ( y , z ) ;
z = max ( i , z ) ; x = max(k , x ) ;
max(x , y ) = max( j ,x , y ) ;
i = max( i , x ) ;
max(x ,y , z ) = max( i ,k ) ; x = max ( i , x ) ;
max ( j , x , z ) = max ( x , z ) ;
max ( i , y ) = y ; max ( j , x , y ) = max ( x , y ) ;
j = max ( i , j ) ; k = max ( x , y , z )
Allamigeon, SG, Goubault, SAS08
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
51 / 85
Such invariants can be found by abstract interpretation.
Equivalent to solving a game (monotone fixed point
problem)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
52 / 85
An application of infinite dimensional tropical convexity
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
53 / 85
Lagrange problem / Lax-Oleinik semigroup
Z
v (t, x) =
L(x(s), x(s))ds
+ (x(t))
sup
x(0)=x, x()
Lax-Oleinik semigroup: (S t )t0 , S t := v (t, ).
Superposition principle: R, , ,
S t (sup(, )) = sup(S t , S t )
S t ( + )
= + St
So S t is max-plus linear.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
54 / 85
Lagrange problem / Lax-Oleinik semigroup
Z
v (t, x) =
L(x(s), x(s))ds
+ (x(t))
sup
x(0)=x, x()
Lax-Oleinik semigroup: (S t )t0 , S t := v (t, ).
Superposition principle: R, , ,
S t ( + ) = S t + S t
S t ()
= S t
So S t is max-plus linear.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
54 / 85
The function v is solution of the Hamilton-Jacobi
equation
v
v
= H(x, )
t
x
v (0, ) =
Max-plus linearity Hamiltonian convex in p
H(x, p) = sup(L(x, u) + p u)
u
Hopf formula, when L = L(u) concave:
v (t, x) = sup tL(
y Rn
Stephane Gaubert (INRIA and CMAP)
x y
) + (y ) .
t
Tropical & dynamic programming
IHP
55 / 85
The function v is solution of the Hamilton-Jacobi
equation
v
v
= H(x, )
t
x
v (0, ) =
Max-plus linearity Hamiltonian convex in p
H(x, p) = sup(L(x, u) + p u)
u
Hopf formula, when L = L(u) concave:
Z
v (t, x) = G (x y )(y )dy .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
55 / 85
Max-plus basis / finite-element method
Fleming, McEneaney 00-; Akian, Lakhoua, SG 04-
Approximate the value function by a linear comb. of
basis functions with coeffs. i (t) R:
v (t, ) '
i (t)wi
i[p]
The wi are given finite elements, to be chosen depending
on the regularity of v (t, )
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
56 / 85
Max-plus basis / finite-element method
Fleming, McEneaney 00-; Akian, Lakhoua, SG 04-
Approximate the value function by a linear comb. of
basis functions with coeffs. i (t) R:
v (t, ) ' sup i (t) + wi
i[p]
The wi are given finite elements, to be chosen depending
on the regularity of v (t, )
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
56 / 85
Best max-plus approximation
P(f ) := max{g f | g linear comb. of wi }
linear forms wi : x 7 hyi , xi
hyi , xi
adapted if v is convex
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
57 / 85
Best max-plus approximation
P(f ) := max{g f | g linear comb. of wi }
cone like functions wi : x 7 C kx xi k
xi
adapted if v is C -Lip
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
57 / 85
Use max-plus linearity of S h :
vt =
i (t)wi
i[p]
and look for new coefficients i (t + h) such that
t+h
'
i (t + h)wi
i[p]
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
58 / 85
Use max-plus linearity of S h :
v t+h = S h v t '
i (t)S h wi
i[p]
and look for new coefficients i (t + h) such that
t+h
'
i (t + h)wi
i[p]
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
58 / 85
Use max-plus linearity of S h :
v t+h = S h v t ' sup i (t) + S h wi
i[p]
and look for new coefficients i (t + h) such that
v t+h ' sup i (t + h) + wi
i[p]
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
58 / 85
Max-plus variational approach
Max-plus scalar product
Z
hw , zi := w (x)z(x)dx
For all test functions zj , j [q]
X
t+h
hv , zj i =
i (t + h)hwi , zj i
i[p]
k (t)hS h wk , zj i
k[p]
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
59 / 85
Max-plus variational approach
Max-plus scalar product
hw , zi := sup w (x) + z(x)
x
For all test functions zj , j [q]
sup i (t + h) + hwi , zj i
i[p]
= sup k (t) + hS h wk , zj i
k[p]
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
59 / 85
Theorem (Akian, SG, Lakhoua, SICON 04)
The approximation error of the max-plus finite element
method satisfies
kvht v t k C (t) sup kv s P(v s )k
0st
Results of the same nature (but no so simple) for other
versions of the method (Fleming, McEneaney; McEneaney,
Kluberg)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
60 / 85
McEneaneys curse of dimensionality reduction
Suppose the Hamiltonian is a finite max of Hamiltonians
arising from LQ problems
1
1
H = sup Hi , Hi = ( x Di x + x Ai p + p i p)
2
2
i[r ]
(=LQ with switching). Let S t and Sit denote the
corresponding Lax-Oleinik semigroups, Sit is exactly
known (Riccati!)
Want to solve v = S t v , t 0
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
61 / 85
Choose a quadratic function such that S t v as
t . Then, for t = hk large enough,
v ' (S h )k .
This is a sup of quadratic forms. Inessential terms are
trimmed dynamically using Shor relaxation (SDP)
solution of a typical instance in dim 6 on a single
processor
McEneaney, Desphande, SG; ACC 08; SG, McEneaney, Qu CDC 11
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
62 / 85
Choose a quadratic function such that S t v as
t . Then, for t = hk large enough,
X
v ' (
Sih )k .
i[r ]
This is a sup of quadratic forms. Inessential terms are
trimmed dynamically using Shor relaxation (SDP)
solution of a typical instance in dim 6 on a single
processor
McEneaney, Desphande, SG; ACC 08; SG, McEneaney, Qu CDC 11
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
62 / 85
Choose a quadratic function such that S t v as
t . Then, for t = hk large enough,
X
v '
Sih1 Sihk .
i1 , ,ik [r ]
This is a sup of quadratic forms. Inessential terms are
trimmed dynamically using Shor relaxation (SDP)
solution of a typical instance in dim 6 on a single
processor
McEneaney, Desphande, SG; ACC 08; SG, McEneaney, Qu CDC 11
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
62 / 85
Choose a quadratic function such that S t v as
t . Then, for t = hk large enough,
v'
sup
i1 , ,ik [r ]
Sih1 Sihk .
This is a sup of quadratic forms. Inessential terms are
trimmed dynamically using Shor relaxation (SDP)
solution of a typical instance in dim 6 on a single
processor
McEneaney, Desphande, SG; ACC 08; SG, McEneaney, Qu CDC 11
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
62 / 85
0.2
0.1
0
2
0.1
0.2
2
0
2
2
0
0
2 2
2
0
0
2 2
Figure: Backsubstitution error and optimal policy on the x1 ,x2 plane,
h = 0.1 SG, McEneaney, Qu 11
Error estimates: in terms of projection errors Akian, Lakhoua, SG 04-,
curse of dim free estimates (still exp. blowup) Kluberg, McEneaney 09
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
63 / 85
SG, McEneaney, Qu CDC 11: cant approximate a C 2 strictly
convex function by N affine max-plus finite elements in
dimension d with an approximation error better than
cst
1
N 2/d
Corollary of techniques/results of Gruber on
approximation of convex bodies.
Curse of dim is unavoidable, but certified rough
approximations is possible.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
64 / 85
In program verification, the template method of Manna,
Sankaranarayanan, Sipma is a level-set version of max-plus
basis methods (in such applications 102 , 103 typically)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
65 / 85
Dessert: from games to metric geometry (generalizations
of Denjoy-Wolff)
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
66 / 85
Beyond games, still with a tropical flavor:
nonexpansive mappings
(X , d) metric space, T : X X ,
d(T (x), T (y )) d(x, y ) .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
67 / 85
Beyond games, still with a tropical flavor:
nonexpansive mappings
(X , d) metric space, T : X X ,
d(T (x), T (y )) d(x, y ) .
Define the escape rate
d(x, T k (x))
(T ) := lim
k
k
(independent of x X by nonexpansiveness, existence by
subadditivity).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
67 / 85
Theorem (Kohlberg & Neyman, Isr. J. Math., 81)
Assume (T ) > 0. Then, there exists a linear form
X of norm one such that for all x X ,
(T ) = lim T k (x)/k = inf kT (y ) y k
k
Stephane Gaubert (INRIA and CMAP)
y X
Tropical & dynamic programming
IHP
68 / 85
Corollary (Kohlberg & Neyman, Isr. J. Math., 81, extending Reich 73
and Pazy 71)
The limit
T k (x)
lim
k
k
exists in the weak (resp. strong) topology if X is reflexive and strictly
convex (resp. if the norm of the dual space X ? is Frechet
differentiable).
T k (x)
k
T k (x)
k
R = (T )
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
69 / 85
Compare Collatz-Wielandt
(F ) = max{ R+ | F (v ) v , v Rn+ , v 6= 0}
= inf{ > 0 | F (w ) w , w int Rn+ }
= lim kF k (x)k1/k ,
k
x int Rn+
and so
(F (w ))i
(F (v ))i
=
(F
)
=
max
min
.
w int Rn+ 1in
v Rn+ 1in
wi
vi
inf
max
v 6=0
vi 6=0
with Kohlberg and Neyman
k
T (x)
= inf kT (y ) y k = lim T k (x)/k .
(T ) := lim
k
y X
k
k
Is there an explanation of this analogy ?
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
70 / 85
Collatz-Wielandt and Kohlberg-Neyman are special cases of a general
result.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
71 / 85
Theorem (SG and Vigeral, Math. Proc. Phil. Soc. 11 )
Let T be a nonexpansive self-map of a complete hemi-metric space
(X , d) of non-positive curvature in the sense of Busemann. Let
d(x, T k (x))
k
k
(T ) := lim
Then, there exists a Martin function h such that
h(T (x)) (T ) + h(x),
Moreover,
(T ) = inf d(y , T (y )) .
y X
If in addition X is a metric space and (T ) > 0, then h is an
horofunction.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
72 / 85
Let us explain the different notions appearing in this theorem . . .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
73 / 85
Hemi-metric
is an hemi-metric on X if
(x, z) (x, y ) + (y , z)
(x, y ) = (y , x) = 0 if and only if x = y .
Variant: weak metric of Papadoupoulos, Troyanov.
(X , ) is complete if X is complete for the metric
d(x, y ) := max((x, y ), (y , x)).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
74 / 85
The (reverse) Funk (hemi-)metric on a cone
C closed pointed cone, X = int C 6= ,
(x, y ) = RFunk(x, y ) := log inf{ > 0|x y }
Lemma
F : C C is order preserving and homogeneous of degree 1 iff
RFunk(F (x), F (y )) RFunk(x, y ),
x, y int C .
[simple but useful: Gunawardena, Keane, Sparrow, Lemmens,
Scheutzow, Walsh.]
(y )
(y )
= log max
Extr C (x)
\{0} (x)
yi
= log max
if C = Rn+ ,
1in xi
RFunk(x, y ) = log max
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
75 / 85
Busemann convexity / nonpositive curvature
condition
We say that (X , ) is metrically star-shaped with center x ? if there
exists a family of geodesics {y }y X , such that y joins the center x ?
to the point y , and
(y (s), z (s)) s(y , z),
(y , z) X 2 ,
s [0, 1] .
y
s (y )
x?
s (z)
z
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
76 / 85
The horoboundary of a metric space
Defined by Gromov (81), see also Rieffel (Doc. Math. 02).
Fix a basepoint x X .
i : X C (X ),
i(x) : y [i(x)](y ) := (
x , x) (y , x).
so that
i(x)(
x ) = 0,
x X
Martin space: M := i(X ) (eg: product topology)
Boundary: H := M \ i(X ). An element of H is an horofunction.
A Busemann point is the limit limt i(xt ), where (xt )t0 is an infinite
(almost) geodesic.
Busemann points boundary points, with equality for a polyhedral
norm.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
77 / 85
In the Poincare disk model, the level lines of horofunctions are
horocircles
The Wolff-Denjoy theorem (1926) says that the orbits of a fixed
point free analytic function leaving invariant the open disk converge
to a boundary point (and that horodisks are invariants).
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
78 / 85
Theorem (SG and Vigeral)
Let T be a nonexpansive self-map of a complete hemi-metric space
(X , d) of non-positive curvature in the sense of Busemann. Then,
there exists a Martin function h such that
h(T (x)) (T ) + h(x),
If in addition X is a metric space and (T ) > 0, then h is an
horofunction.
Kohlberg-Neyman is a direct corollary. Since h = lim k x k
modulo constants, h is concave. Take any h(x). Then,
(T k (x) x) h(T k (x)) h(x) k(T ) .
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
79 / 85
Collatz-Wielandt revisited
Let F : C C , where C is a symmetric cone (self-dual cone with a
group of automorphisms acting transitively on it), say C = Rn+ or
C = Sn+ .
Recall F is nonexpansive in RFunk iff it is order preserving and
homogeneous of degree one.
Walsh (Adv. Geom. 08): the horoboundary of C in the (reverse)
Funk metric is the Euclidean boundary: any Martin function h
corresponds to some u C \ {0}:
h(x) = RFunk(x, u) + RFunk(x , u) , x int C ,
h is a horofunction iff u C \ {0}.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
80 / 85
Corollary (Collatz-Wielandt recovered, and more)
Let T : int C int C , order-preserving and positively homogeneous,
C symmetric cone. Then,
RFunk(x, T k (x))
(T ) := lim
,
k
k
= inf RFunk(y , T (y ))
x int C
y int C
= log inf{ > 0 | y int C , T (y ) y }
= max RFunk(T (u), u)
uC \{0}
= log max{ 0 | u C \ {0}, T (u) u}
and there is a generator w of an extreme ray of C such that
log w , T k (x ) log (w , x) + k(T ),
k N
Refines Gunawardena and Walsh, Kibernetica, 03.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
81 / 85
T
T
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
82 / 85
The special case of games recovered
Ti (x) = max min riab +
aAi bBi,a
Pijab xj ,
1i n
1jn
(T k (x))j
k 1jn
k
(T ) = (T ) = lim max
Corollary (SG, Gunawardena, TAMS 04 recovered)
For all x Rn , there exists 1 i n such that
k N .
T k (x) i xi + k(T ),
Initial state i guarantees the best reward per time unit.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
83 / 85
Conclusion
Nonexpansive maps/Perron-Frobenius techniques: tools to prove
combinatorial results.
Symmetric cones have a tropical flavor (log glasses, nonpositive
curvature)
Order preserving homogeneous maps should be thought of as
nonexpansive maps in RFunk(x, y ) := log inf{ > 0|x y }.
this leads to Denjoy-Wolff type results (nested invariant
horoballs)
Collatz-Wielandt and Kohlberg-Neyman recovered as special
cases.
Generalization of Edmondss good characterizations (NP
coNP membership of mean payoff games is a special case).
Current work SG+Zheng Qu: application to various Riccati-type
equations.
Stephane Gaubert (INRIA and CMAP)
Tropical & dynamic programming
IHP
84 / 85
