# Ambitropical geometry, hyperconvexity and zero-sum games

Marianne Akian  INRIA and CMAP, IP Paris, École polytechnique, CNRS. Postal
address: CMAP, École polytechnique, 91128 Palaiseau Cédex
<EMAIL_ADDRESS>,  Stéphane Gaubert  INRIA and CMAP, IP Paris, École
polytechnique, CNRS. Postal address: CMAP, École polytechnique, 91128
Palaiseau Cédex<EMAIL_ADDRESS>and  Sara Vannucci  Czech Technical
University in Prague<EMAIL_ADDRESS>
###### Abstract.

Shapley operators of undiscounted zero-sum two-player games are order-
preserving maps that commute with the addition of a constant. We characterize
the fixed point sets of Shapley operators, in finite dimension (i.e., for
games with a finite state space). Some of these characterizations are of a
lattice theoretical nature, whereas some other rely on metric or tropical
geometry. More precisely, we show that fixed point sets of Shapley operators
are special instances of hyperconvex spaces: they are sup-norm non-expansive
retracts of $\mathbb{R}^{n}$, and also lattices in the induced partial order.
Moreover, they retain properties of convex sets, with a notion of “convex
hull” defined only up to isomorphism. This provides an effective construction
of the injective hull or tight span, in the case of additive cones. For
deterministic games with finite action spaces, these fixed point sets are
supports of polyhedral complexes, with a cell decomposition attached to
stationary strategies of the players, in which each cell is an alcoved
polyhedron of $A_{n}$ type. We finally provide an explicit local
representation of the latter fixed point sets, as polyhedral fans canonically
associated to lattices included in the Boolean hypercube.

###### 2020 Mathematics Subject Classification:

14T90; 91A25; 91A68

Version of . This work was initiated when Sara Vannucci was with Università di
Salerno. This work was partially supported by the National Group for Algebraic
and Geometric Structures, and their Applications (GNSAGA - INdAM)

##  1\. Introduction

inline]mention the flip $X\to-X$ which preserves ambitropical sets, SV:
mentioned at page 22

###  1.1. Motivation

Shapley operators play a fundamental role in the study of zero-sum repeated
games, see [Sha53, Ney03, MSZ15a]. For infinite horizon problems, including
the cases of a discounted payoff, of a total payoff up to a stopping time, or
of a mean payoff (in which the payoff is given by a time average), the fixed
point of a suitable Shapley operator determines the value of the game as well
as optimal stationary strategies. The mean payoff problem is somehow the most
difficult one. Then, the notion of fixed point is defined in a projective
sense (up the action of additive constants), see [Mou76, Th. VI.1]. The
existence and uniqueness of such fixed points have been investigated in the
setting of non-linear Perron-Frobenius theory [GG04, LN12, AGH20]. The absence
of fixed points is tied to the time-dependent nature of the nearly optimal
strategies [BF68, BK76], whereas multiple fixed points yield multiple optimal
stationary strategies [KY92].

The structure of the fixed point set of Shapley operators has been studied
especially in the deterministic one player case, as part of tropical spectral
theory [BCOQ92, KM97a, AGW09], or in the setting of viscosity solutions of
ergodic Hamilton-Jacobi partial differential equations and weak-KAM theory,
see [FS05, IM07, Fat08]. The results there show in particular that fixed
points are uniquely determined by their restriction to a suitable subset or
“boundary” of the state space, in a way somehow analogous to the Poisson-
Martin representation of harmonic functions [Dyn69]. For one player
deterministic problems, the role of the “boundary” is played either by a
distinguished subset of the state space (“critical nodes” [BCOQ92], “projected
Aubry set” [FS05]) or by a metric boundary (the horoboundary) of the state
space [IM07, AGW09]. Fixed point sets appear to be wilder objects in the two-
player case, even when the space space is finite. The geometry of these fixed
point sets is the main subject of this paper.

A further motivation arises from algebra in characteristic one [CC19] and
tropical geometry [MS15]. In this setting, one needs to work in categories in
which the objects are tropical analogues of linear spaces, and the arrows are
linear maps. However, tropical duality results require to consider at the same
time properties of linearity in a primal and in a dual sense, and sometimes to
compose maps that are linear in each of these senses (e.g., compositions of
min-plus and max-plus linear maps). This is the case, for instance, of
projections onto linear spaces, which are generally non-linear [CGQ96, CGQ04],
but which are still Shapley operators. Hence, it may be desirable to develop a
broader, “self-dual”, framework, in which the objects include both tropical
(max-plus) linear spaces and their duals, and the arrows are Shapley
operators.

Thinking of Shapley operators in abstract terms leads to a metric geometry
approach, exploiting a connection with the theory of nonexpansive mappings.
Recall that a self-map $T$ of a metric space $(X,d)$ is nonexpansive if
$d(T(x),T(y))\leqslant d(x,y)$. For undiscounted games with state space $[n]$,
the Shapley operators are precisely the self-maps $T$ of $\mathbb{R}^{n}$ that
are nonexpansive with respect to the metric associated with the sup-norm and
that commute with the action of additive constants [CT80, KM97a]. As shown in
[GK95], this is equivalent to $T$ being nonexpansive in the weak (non-
symmetric) metric $d(x,y)=\mathsf{t}(y-x)$ where $\mathsf{t}(z):=\max_{i\in
n}z_{i}$. The map $\mathsf{t}(\cdot)$ here is an example of weak Minkowski
norm or hemi-norm, and it is a special case of the local norm associated to
the Finsler structure of the “Funk metric”, studied in Hilbert’s geometry, see
[PT09, Wal18, GV12].

From this perspective, the study of fixed point sets of Shapley operators
becomes tied to the classical topic of fixed point sets of nonexpansive
mappings and nonexpansive retracts (i.e., fixed points of idempotent
nonexpansive maps) in Banach spaces, see [KR07] for background. Recall that a
nonexpansive retract $C$ of a Banach space $X$ that satisfies a technical
condition (the so called fixed point property for spheres) valid in particular
in finite dimension, must be metrically convex [Bru73], meaning that for all
$x,y\in C$ and for all $\alpha,\beta\geqslant 0$ such that $\alpha+\beta=1$,
there must exist a point $z$ in $C$ such that $d(x,z)=\alpha d(x,y)$ and
$d(z,y)=\beta d(x,y)$. In particular, nonexpansive retracts of strictly convex
Banach spaces are closed and convex. Conversely, any closed and convex subset
$C$ of a Hilbert space $X$ is a nonexpansive retract of this space, and
indeed, a retraction is given by the best approximation map, which associates
to a point of $X$ the nearest point in $C$, see e.g. [GR84, Th. 3.6].
Moreover, if $X$ is a Banach space of dimension at least $3$, it is known that
all the closed and convex subsets of $X$ are nonexpansive retracts if and only
if $X$ is a Hilbert space, see [Rei77, Prop. 2.2], and also [Kak39, Kle60,
Bru74] for earlier results of this nature.

In this way, classical convexity appears to be linked to the geometry of
Euclidean retractions. Then, one may wonder whether other types of (weak)
metric spaces are tied to interesting convexity theories. In particular, we
may ask whether fixed point sets of Shapley operators may be thought of as
“convex sets” in a useful sense. We give here a positive answer to this
question, by establishing links between the theory of fixed point sets of
Shapley operators, tropical geometry, order preserving retracts of lattices,
and hyperconvexity. We focus on the finite dimensional case.

###  1.2. Summary of results

We define a subset $C$ of $\mathbb{R}^{n}$ to be an ambitropical cone if $C$
is invariant by translation by constant vectors, and if $C$ is a lattice in
the order induced by the standard partial order of $\mathbb{R}^{n}$ (but not
necessarily a sublattice of $\mathbb{R}^{n})$. This includes as special cases
the max-plus and min-plus convex cones arising in idempotent analysis [LMS01]
and tropical geometry [CGQ04, DS04]. In contrast with the classes of max-plus
and min-plus cones, the class of ambitropical cones is self-dual since it is
invariant by the “flip” (change of sign) operation. Hence, we use the name
ambitropical, as it includes both tropical convexity and its dual. We call
Shapley retract the image of an idempotent Shapley operator.

3.8 below shows that Shapley retracts are precisely closed ambitropical cones.
Further, we show that there are canonical retractions on a closed ambitropical
cone $C$, characterized as the composition of nearest point projection
mappings on the tropical convex cone and dual tropical convex cone generated
by $C$, see 4.7. This leads to a further characterization of ambitropical
cones, by an analogue of the “best co-approximation property” arising in the
theory of Banach spaces [PS79], see 4.12 below. We also show that the class of
ambitropical cones admits an analogue of the “convex hull” operation: although
the intersection of ambitropical cones may not be ambitropical, there is a
well defined notion of ambitropical hull, the minimal closed ambitropical cone
containing a given set, which is unique up to isomorphism (the morphisms being
Shapley operators). One main result, 5.6, shows that ambitropical cones are
precisely hyperconvex sets that are additive cones. Since we provide an
effective construction of the ambitropical hull, in terms of the range of a
tropical Petrov-Galerkin projector (4.17), this leads to an explicit
construction of the hyperconvex hull of an additive cone.

We subsequently study ambitropical cones with a semilinear structure, which we
call ambitropical polyhedra. The building blocks of ambitropical polyhedra are
the alcoved polyhedra of the root system $A_{n}$, studied in [LP07], which
include as special cases Stanley’s order polyhedra [Sta86]. Ambitropical
polyhedra are defined as ambitropical cones that are finite unions of alcoved
polyhedra. 8.8 shows that ambitropical polyhedra coincide with fixed point
sets of Shapley operators of deterministic games with finite action spaces.
Further, we show that ambitropical polyhedra are polyhedral complexes whose
cells are associated to pairs of stationary policies of both players that are
optimal in the mean payoff problem, see 8.3. We study, in particular, the case
of homogeneous ambitropical polyhedra, i.e., ambitropical polyhedra that are
invariant by the multiplicative action of positive scalars. We show that
homogeneous ambitropical polyhedra arise when considering tangent cones of
ambitropical polyhedra, so, they provide a local description of these sets.
9.6 provides a characterization of homogeneous ambitropical polyhedra, as
polyhedral fans associated to subsets of $\\{0,1\\}^{n}$ that are lattices in
the induced order.

The hierarchy of classes of sets considered in this paper is presented on
Table 1.

hyperconvex sets
---
5.1
ambitropical cones
---
closed ambitropical cones
---
Theorems 3.8, 4.12
closed tropical conesclosed dual tropical cones ambitropical polyhedral cones
---
8.8
tropical polyhedral conesdual tropical polyhedral cones homogeneous
ambitropical polyhedra
---
$\simeq$ lattices in $\\{0,1\\}^{n}$
9.6
alcoved polyhedraorder polyhedradual tropical polyhedral cones Table 1. The
hierarchy of ambitropical cones

###  1.3. Related work

As indicated in §1.1, the present results are related to several series of
works. A first source of inspiration is the theory of “best approximation” in
tropical geometry [CGQ04, AGNS11], in which (non-linear) projectors onto max-
plus / min-plus spaces have been studied. In particular, the canonical
retractions on ambitropical cones turn out to coincide with the tropical
analogue of Petrov-Galerkin projectors, introduced in [CGQ96] and applied in
[AGL08] to the numerical solution of optimal control problems.

The representation of ambitropical polyhedra (8.3) as the support of a
polyhedral complex is somehow inspired by the characterization of Develin and
Sturmfels [DS04] of polyhedral complexes arising from tropical polyhedral
cones, in terms of the duals to regular subdivisions of the product of two
simplices. The latter property makes use of (classical) convex duality, and so
this does not carry over to the ambitropical case given its “minimax” nature.
However, we still get a complete combinatorial characterization in the special
case of homogeneous ambitropical polyhedra, see 9.6, showing these are
equivalent to lattices included in $\\{0,1\\}^{n}$ with the induced order.
Such lattices are precisely the order preserving retracts of $\\{0,1\\}^{n}$
studied by Crapo [Cra82].

inline]SV : I removed the above part (you can find it in the source file with
percentage symbol) because it refereed to the lattice section that we deleted
Moreover, sup-norm nonexpansive retracts (not necessarily order preserving)
have been studied in the setting of hyperconvexity, a notion introduced by
Aronszajn and Panitchpakdi [AP56], see [Bai88, EK01] for more information.
Hyperconvex spaces are metrically convex spaces in which the collection of
closed balls has Helly number two. It follows from [AP56, Th. 9] that the sup-
norm nonexpansive retracts of $\mathbb{R}^{n}$ are precisely the closed
subsets of $\mathbb{R}^{n}$ that are hyperconvex. Hence, closed ambitropical
cones are special instances of closed hyperconvex sets, with an additional
structure induced by the order and the additive homogeneity. Furthermore, an
equivalence holds, namely that an additive cone of $\mathbb{R}^{n}$ is a
closed ambitropical cone if and only if it is hyperconvex for the sup-norm
metric. This result allows us to compute the hyperconvex hull of an additive
cone. The problem of computing the hyperconvex hull has received much
attention, Isbell and Dress [Isb64, Dre84] shows that this hull can be
realized as a “tight-span”. Even in dimension $2$, computations of hyperconvex
hull are difficult [KcK16]. Our results solve this problem for the special
case of additive cones.

As mentioned above, it is an open problem to understand what Fathi’s
characterization of weak-KAM solutions, as spaces of Lipchitz functions on the
“projected Aubry set” [FS05, Fat08], becomes in the “two-player” case. Our
results answers the analogue of this question in the discrete, finite
dimensional case: whereas one-player solution spaces are alcoved polyhedra, in
the two-player case, we show that the solution spaces are precisely
ambitropical sets, which in the finite action case are obtained by gluing
alcoved polyhedra. This interpretation is elaborated in 8.3.

inline]I added the above part regarding the results that we have in the
hyperconvex section

Finally, our treatment of Shapley operators is inspired by the “operator
approach” of zero-sum games, early work in these directions include [Eve57,
Koh74, BK76], see [RS01a, Ren11, BGV15, Zil16] for more recent developments.

##  2\. Preliminary results

In this section, we establish, or recall, basic results concerning tropical
cones.

###  2.1. Additive cones, tropical cones and semimodules

The tropical semifield, $\mathbb{R}_{\max}$, is the set
$\mathbb{R}\cup\\{-\infty\\}$ equipped with the addition $(x,y)\mapsto x\vee
y:=\max(x,y)$ and with the multiplication $(x,y)\mapsto x+y$. It admits a zero
element, equal to $-\infty$, and a unit element, equal to $0$. We shall also
use the min-plus version of the tropical semifield, $\mathbb{R}_{\min}$, which
is the set $\mathbb{R}\cup\\{+\infty\\}$ equipped with the addition
$(x,y)\mapsto x\wedge y:=\min(x,y)$ and with the multiplication $(x,y)\mapsto
x+y$. The semifields $\mathbb{R}_{\max}$ and $\mathbb{R}_{\min}$ are
isomorphic. We denote by $\leqslant$ the partial coordinatewise order of
$(\mathbb{R}\cup\\{\pm\infty\\})^{n}$, and we use the notation
$\lambda+x:=(\lambda+x_{i})_{i\in[n]}$, for all $\lambda\in\mathbb{R}_{\max}$
and $x\in(\mathbb{R}_{\max})^{n}$, and similarly for
$\lambda\in\mathbb{R}_{\min}$ and $x\in(\mathbb{R}_{\min})^{n}$. We extend the
notation $\vee$ to denote the supremum of vectors of
$(\mathbb{R}\cup\\{\pm\infty\\})^{n}$. Similarly, $\wedge$ denote the infimum
of vectors.

######  Definition 2.1.

An additive cone of $\mathbb{R}^{n}$ is a subset $C$ of $\mathbb{R}^{n}$ such
that

  1. (1)

$x\in C,\lambda\in\mathbb{R}\implies\lambda+x\in C$.

A tropical cone is an additive cone $C$ such that:

  1. (2)

$x,y\in C\implies x\vee y\in C$.

A dual tropical cone is defined similarly, by requiring that $x,y\in C\implies
x\wedge y\in C$, instead of (2).

Tropical cones are, essentially, special cases of semimodules over the
tropical semifield. Recall that semimodules (modules over semirings) are
defined in a way similar to modules over rings, see [CGQ04]. In particular,
semimodules over idempotent semirings have been studied under the name of
idempotent spaces in [LMS01]. A simple example of semimodule over
$\mathbb{R}_{\max}$ is the $n$-fold Cartesian product of $\mathbb{R}_{\max}$,
$(\mathbb{R}_{\max})^{n}$; the internal law is $(x,y)\mapsto x\vee
y:=(x_{i}\vee y_{i})_{i\in[n]}$, for $x,y\in(\mathbb{R}_{\max})^{n}$, and the
action of $\mathbb{R}_{\max}$ on $(\mathbb{R}_{\max})^{n}$ is defined by
$(\lambda,x)\mapsto\lambda+x$. This yields a free, finitely generated
semimodule. If $C\subset\mathbb{R}^{n}$ is a tropical cone, then
$C\cup\\{(-\infty,\dots,-\infty)\\}$ is a subsemimodule of
$(\mathbb{R}_{\max})^{n}$, and vice versa.

We shall consider, in particular, tropical cones satisfying a topological
assumption. We equip $\mathbb{R}_{\max}$ with the topology defined by the
metric $(a,b)\mapsto|e^{a}-e^{b}|$. The semimodule $(\mathbb{R}_{\max})^{n}$,
equipped with the topology of the metric
$d_{\infty}(x,y)=\max_{i\in[n]}|e^{x_{i}}-e^{y_{i}}|$ is a topological
semimodule (meaning that the structure laws are continuous). Observe that the
induced topology on $\mathbb{R}^{n}\subset(\mathbb{R}_{\max})^{n}$ is the
Euclidean topology. Dual considerations apply to $(\mathbb{R}_{\min})^{n}$.

######  Definition 2.2.

Given a subset $C\subset\mathbb{R}^{n}$, we define the lower closure of $C$,
$\operatorname{clo}^{\downarrow}C\subset(\mathbb{R}_{\max})^{n}$, to be the
set of limits of nonincreasing sequences of elements of $C$. Similarly, we
define the upper closure
$\operatorname{clo}^{\uparrow}C\subset(\mathbb{R}_{\min})^{n}$ to be the set
of limits of nondecreasing sequences of elements of $C$.

For instance, if $C=\\{x\in\mathbb{R}^{2}\mid|x_{1}-x_{2}|\leqslant 1\\}$,
$\operatorname{clo}^{\downarrow}C=C\cup\\{(-\infty,-\infty)\\}$, whereas if
$C=\\{x\in\mathbb{R}^{2}\mid x_{1}\geqslant x_{2}\\}$,
$\operatorname{clo}^{\downarrow}C=\\{x\in(\mathbb{R}_{\max})^{2}\mid
x_{1}\geqslant x_{2}\\}$. The following proposition shows a correspondence
between closed tropical cones and a class of closed tropical subsemimodules.

######  Proposition 2.1.

The map $C\mapsto V:=\operatorname{clo}^{\downarrow}C$ establishes a bijective
correspondence between the nonempty closed tropical cones
$C\subset\mathbb{R}^{n}$ and the closed subsemimodules $V$ of
$(\mathbb{R}_{\max})^{n}$ such that $V\cap\mathbb{R}^{n}\neq\emptyset$. The
inverse map is given by $V\mapsto V\cap\mathbb{R}^{n}$.

The dual property, concerning $\operatorname{clo}^{\uparrow}C$ and
$(\mathbb{R}_{\min})^{n}$ instead of $\operatorname{clo}^{\downarrow}C$ and
$(\mathbb{R}_{\max})^{n}$, also holds. We denote by
$\operatorname{supp}y:=\\{i\in[n]\mid y_{i}>-\infty\\}$ the support of a
vector $y\in(\mathbb{R}_{\max})^{n}$.

###### Proof.

Suppose $C\subset\mathbb{R}^{n}$ is a tropical cone. Since
$(\mathbb{R}_{\max})^{n}$ is a topological semimodule,
$\operatorname{clo}^{\downarrow}C$ is a semimodule over $\mathbb{R}_{\max}$.
We next show that $\operatorname{clo}^{\downarrow}C$ is closed. Let $x^{k}$
denote a sequence of elements of $\operatorname{clo}^{\downarrow}C$ converging
to an element $x\in(\mathbb{R}_{\max})^{n}$. Let $\epsilon_{k}$ denote an
arbitrary sequence of positive numbers decreasing to $0$. Let
$y^{k}:=x^{k}+\epsilon_{k}e\in\operatorname{clo}^{\downarrow}C$. Observe that
$\eta_{k}:=d_{\infty}(x^{k},y^{k})=(e^{\epsilon_{k}}-1)\max_{i\in[n]}e^{x^{k}_{i}}\to
0$ as $k\to\infty$. Moreover, by definition of
$\operatorname{clo}^{\downarrow}C$, we can find $z^{k}\in C$ such that
$y^{k}\leqslant z^{k}$ and $d_{\infty}(y^{k},z^{k})\leqslant\eta_{k}$. It
follows that the sequence $z^{k}$ also converges to $x$. We claim that there
is a subsequence $z^{n_{k}}$ of $z^{k}$ that is nonincreasing. Indeed, suppose
by induction that $z^{n_{1}}\geqslant\cdots\geqslant z^{n_{k}}$ has already
been selected. Let $I:=\operatorname{supp}x$. Since $z^{l}\to x$ as
$l\to\infty$, we get $z^{l}_{i}\to x_{i}\in\mathbb{R}$ for $i\in[n]$, and
$z^{l}_{i}\to-\infty$ for $i\in[n]\setminus I$. However, by construction,
$z^{n_{k}}\geqslant\epsilon_{n_{k}}e+x$, and so
$z^{n_{k}}_{i}\geqslant\epsilon_{n_{k}}+x_{i}$ for all $i\in I$. We deduce
that there is an index $l$ such that $z^{l}\leqslant z^{n_{k}}$, and we set
$n_{k+1}:=l$. This shows that $x\in\operatorname{clo}^{\downarrow}C$, and so,
$\operatorname{clo}^{\downarrow}C$ is closed.

Conversely, suppose that $V$ is a closed subsemimodule of
$(\mathbb{R}_{\max})^{n}$. Then, it is immediate that $V\cap\mathbb{R}^{n}$ is
a closed tropical cone. It remains to show that the correspondence is
bijective. We have trivially
$\operatorname{clo}^{\downarrow}C\cap\mathbb{R}^{n}=C$ for all nonempty closed
tropical cones $C\subset\mathbb{R}^{n}$. Conversely, if $V$ is a closed
tropical subsemimodule of $(\mathbb{R}_{\max})^{n}$ such that
$V\cap\mathbb{R}^{n}$ is nonempty, we must show that
$V=\operatorname{clo}^{\downarrow}(V\cap\mathbb{R}^{n})$. let $x\in V$, and
let us choose an arbitrary element $y\in V\cap\mathbb{R}^{n}$. Then, the path
$\lambda\mapsto\gamma(\lambda):=x\vee(\lambda+y)$, defined for
$\lambda\in(-\infty,0]$ is such that $\gamma(\lambda)\in V\cap\mathbb{R}^{n}$,
and $\lim_{\lambda\to-\infty}\gamma(\lambda)=x$. It follows that
$x\in\operatorname{clo}^{\downarrow}(V\cap\mathbb{R}^{n})$, hence,
$V\subset\operatorname{clo}^{\downarrow}(V\cap\mathbb{R}^{n})$. The other
inclusion is immediate. ∎

Recall that an element $u$ of a tropical subsemimodule
$V\subset(\mathbb{R}_{\max})^{n}$ is an extreme generator of $V$ if $u=v\vee
w$ with $v,w\in V$ implies that $u=v$ or $u=w$. A tropical linear combination
of elements of $V$ is a vector of the form $\vee_{i\in I}(\lambda_{i}+a_{i})$
where $(\lambda_{i})_{i\in I}\subset\mathbb{R}_{\max}$ and $(a_{i})_{i\in
I}\subset V$ are finite families. We say that $G\subset V$ is a tropical
generating set if every element of $V$ is a tropical linear combination of a
family of elements of $G$. We say also that two vectors are tropically
proportional if they differ by an additive constant. The next result
summarizes results from [GK07, BSS07]; it shows that a closed tropical
subsemimodule of $(\mathbb{R}_{\max})^{n}$ is generated by its extreme rays.

######  Theorem 2.2 (See Theorem 3.1 in [GK07] or Theorem 14 in [BSS07]).

Suppose that $V$ is a closed tropical subsemimodule of
$(\mathbb{R}_{\max})^{n}$. Then, every element of $V$ is a tropical linear
combination of at most $n$ extreme generators of $V$. Moreover, these extreme
generators are characterized as follows. For all $i\in[n]$, let
$V_{i}:=\\{x\in V\mid x_{i}=0\\}$, and let $\operatorname{Min}V_{i}$ denote
the set of minimal elements of $V_{i}$. Then, every extreme generator of $V$
is tropically proportional to an element of
$\cup_{i\in[n]}\operatorname{Min}V_{i}$.

This is reminiscent of the classical Carathéodory theorem for closed convex
pointed cones.

###  2.2. Alcoved polyhedra and metric closures

An important class of tropical cones and dual tropical cones consists of
alcoved polyhedra. The latter were introduced in [LP07]: in general, an
alcoved polyhedron associated to a root system is a polyhedron whose facets
have normals that are proportional to vectors of this root system. Here, the
root system is $A_{n}$, the collection of vectors $\\{e_{i}-e_{j}\mid
i,j\in[n],i\neq j\\}$, where $e_{i}$ denotes the $i$th vector of the canonical
basis of $\mathbb{R}^{n}$.

######  Definition 2.3.

An alcoved polyhedron [LP07] is a polyhedron of the form

(1) $\displaystyle\mathscr{A}(M)=\\{x\in\mathbb{R}^{n}\mid x_{i}\geqslant
M_{ij}+x_{j},\quad\forall 1\leqslant i,j\leqslant n\\}$

for some matrix $M=(M_{ij})\in(\mathbb{R}_{\max})^{n\times n}$.

Order polyhedra are remarkable examples of alcoved polyhedra. They are of the
form $\\{x\in\mathbb{R}^{n}\mid x_{i}\geqslant x_{j}\text{ if }(i,j)\in E\\}$
where $E\subset[n]\times[n]$ is a partial order relation on the set $[n]$.
Intersection of order polyhedra with the hypercube $[0,1]^{n}$ are known as
order polytopes, they were studied by Stanley [Sta86].

We shall denote by $\vee$ the tropical addition of matrices, so that, for all
$A,B\in(\mathbb{R}_{\max})^{m\times n}$, $(A_{ij})\vee(B_{ij}):=(A_{ij}\vee
B_{ij})\in(\mathbb{R}_{\max})^{m\times n}$. The tropical multiplication of
matrices will be denoted by concatenation, i.e, for
$A\in(\mathbb{R}_{\max})^{m\times n}$ and $B\in(\mathbb{R}_{\max})^{n\times
p}$, $AB\in(\mathbb{R}_{\max})^{m\times p}$ is the matrix with $(i,j)$-entry
$\vee_{k\in[n]}(A_{ik}+B_{kj})$. Then, when $m=n$, for all $r$, the $r$th
tropical power of $A$ is denoted by $A^{r}:=A\cdots A$ ($A$ is repeated $r$
times).

There are well known relations between alcoved polyhedra and operations of
metric closures which we next recall. The tropical Kleene star of $M$ is
defined by $M^{*}:=I\vee M\vee M^{2}\vee\cdots$. This supremum may be
infinite, i.e., in general $(M^{*})_{ij}$ may take the value $+\infty$. Recall
that to the matrix $M$ is associated a digraph with set of nodes $[n]$ and an
arc $i\to j$ of weight $M_{ij}$ whenever $M_{ij}>-\infty$. Then,
$(M^{k})_{ij}$ yields the maximal weight of a path of length $k$ from $i$ to
$j$, and $(M^{*})_{ij}$ yields the supremum of the weights of paths from $i$
to $j$, of arbitrary length. We have $(M^{*})_{ij}<+\infty$ for all $i,j$ if
and only if there is no circuit with positive weight in the digraph of $M$.
Then, $M^{*}=M^{0}\vee\dots\vee M^{n-1}$, see e.g. Prop 2.2 of [AGW05].

The critical circuits of the matrix $M^{*}$ are the circuits in the digraph of
$M^{*}$ with weight $0$. The union of the critical circuits constitutes the
critical digraph. The following result is well known: the first statements
follow readily from the results recalled above, whereas the characterization
of generators is a special case of the characterization of tropical
eigenspaces, see e.g. [BCOQ92, Th. 3.100], Theorem 6.4 of [AGW05], or [But10,
Th. 4.4.5].

######  Lemma 2.3.

The polyhedron $\mathscr{A}(M)$ is non-empty if and only there is no circuit
of positive weight in the digraph of $M$. Then,

(2) $\displaystyle\mathscr{A}(M)=\\{x\in\mathbb{R}^{n}\mid M^{*}x\leqslant
x\\}=\\{x\in\mathbb{R}^{n}\mid M^{*}x=x\\}=\\{M^{*}y\mid
y\in\mathbb{R}^{n}\\}\enspace.$

Moreover, a tropical generating set of
$\operatorname{clo}^{\downarrow}\mathscr{A}(M)$ is obtained as follows: denote
by $C_{1},\dots,C_{s}$ the strongly connected components of the critical
digraph of $M^{*}$, and select indices $i_{1}\in C_{1},\dots,i_{s}\in C_{s}$
in an arbitrary manner. Then, the set of columns of $M^{*}$ indexed by
$i_{1},\dots,i_{s}$ tropically generates
$\operatorname{clo}^{\downarrow}\mathscr{A}(M)$, and every generating set of
$\operatorname{clo}^{\downarrow}\mathscr{A}(M)$ contains at least one scalar
multiple of each of these columns. ∎

######  Remark 2.4.

It follows from 2.3 that the minimum number of elements of a tropical
generating family of the tropical semimodule
$\operatorname{clo}^{\downarrow}\mathscr{A}(M)\subset(\mathbb{R}_{\max})^{n}$
never exceeds $n$. The same observation applies to dual tropical generating
families of $\operatorname{clo}^{\uparrow}\mathscr{A}(M)$. In contrast, there
are finitely generated tropical subsemimodules of $(\mathbb{R}_{\max})^{n}$
with an arbitrarily large number of generators, see e.g. [AGG13].

##  3\. Shapley operators and Ambitropical Cones

###  3.1. Abstract Shapley Operators

Shapley operators are dynamic programming operators allowing one to compute
the value function of zero-sum games. The typical example of Shapley operator
$T:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is of the form

(3) $\displaystyle T_{i}(x)=\inf_{a\in A_{i}}\sup_{b\in
B_{i}}(r_{i}^{ab}+\sum_{j\in[n]}P_{ij}^{ab}x_{j})\enspace,$

where $[n]=\\{1,\dots,n\\}$ is the state space, $A_{i},B_{i}$ are the sets of
actions available in state $i$, of the two players, called “Min” and “Max”,
$r_{i}^{ab}$ is a payment made by by Player Min to Player Max at a given
stage, assuming that Min selected action $a$ and that Max selected action $b$,
and $P_{ij}^{ab}\geqslant 0$ is the probability of transition from $i$ to $j$,
so that $\sum_{j}P_{ij}^{ab}=1$. Such operators capture zero-sum perfect or
“turned based” information games, without discount. In the original model
considered by Shapley, the two players play simultaneously and the actions are
randomized, which can be cast as (3), in which $A_{i}$ and $B_{i}$ are
simplices [RS01a, Ney03]. Actually, many variants of Shapley operators
(depending on the nature of the turns and on the information structure) can be
considered, and so, it will be convenient to introduce a general definition.

######  Definition 3.1 (Shapley operator).

An (abstract) Shapley operator is a map $T:\mathbb{R}^{n}\to\mathbb{R}^{p}$
with the following properties:

  1. (1)

$x\leqslant y$ implies $T(x)\leqslant T(y)$, for all $x,y\in\mathbb{R}^{n}$;

  2. (2)

$T(\lambda+x)=\lambda+T(x)$, for all $x\in\mathbb{R}^{n}$ and
$\lambda\in\mathbb{R}$.

The example (3) of Shapley operator obviously satisfies these properties.
Conversely, Kolokoltsov showed that every abstract Shapley operator
$\mathbb{R}^{n}\to\mathbb{R}^{n}$ can be written as (3) (see [KM97b]) and
Singer and Rubinov [RS01b] showed that the transition probabilities can even
be chosen to be $0/1$.

Note that, taking into account the semimodule structure of $\mathbb{R}^{n}$
and $\mathbb{R}^{p}$, the canonical choice of morphisms to consider would be
tropically linear maps (maps that commute with the supremum and with the
addition of a constant). Shapley operators constitute a larger class of maps
and they are precisely canonical morphisms of additive cones (see Def. 3.1).

In the square case, i.e., when $n=p$, Shapley operators arise as dynamic
programming operators of two-player zero-sum games, see e.g. [RS01a, Ney03].
It is known that Shapley operators are nonexpansive in the sup-norm; this
observation plays a key role in the “operator approach” of zero-sum games
[CT80, RS01a, Ney03, GV12]. Furthermore, the following observation, made in
[GK95, Prop. 1.1], shows that Shapley operators are characterized by a
nonexpansiveness property. Recall that $\mathbf{t}({x}):=\max_{i\in[n]}x_{i}$
denotes the “top” hemi-norm of a vector $x\in\mathbb{R}^{n}$. It will also be
convenient to use the notation
$\mathbf{b}({x}):=-\mathbf{t}{(-x)}=\min_{i\in[n]}x_{i}$.

######  Proposition 3.1 ([GK95, Prop. 1.1]).

Let $T:\mathbb{R}^{n}\to\mathbb{R}^{p}$. The following assertions are
equivalent:

  1. (i)

$T$ is a Shapley operator;

  2. (ii)

$\mathbf{t}{(T(x)-T(y))}\leqslant\mathbf{t}{(x-y)}$ for all
$x,y\in\mathbb{R}^{n}$;

  3. (iii)

$\mathbf{b}{(T(x)-T(y))}\geqslant\mathbf{b}{(x-y)}$ for all
$x,y\in\mathbb{R}^{n}$.

The following result is a consequence of a general result on [BNS03]
concerning the continuous extension of positive homogeneous maps defined on
the interior of polyhedral cones.

######  Proposition 3.2 (Corollary of [BNS03, Theorem 3.10]).

A Shapley operator $T:\mathbb{R}^{n}\to\mathbb{R}^{p}$ admits a unique
continuous extension
$T_{-}:(\mathbb{R}_{\max})^{n}\to(\mathbb{R}_{\max})^{p}$, given by

${T}_{-}(x)=\inf\\{T(y)\mid y\geqslant x,\;y\in\mathbb{R}^{n}\\}\enspace.$

Similarly, $T$ has a unique continuous extension
$(\mathbb{R}_{\min})^{n}\to(\mathbb{R}_{\min})^{p}$, given by

${T}_{+}(x)=\sup\\{T(y)\mid y\leqslant x,\;y\in\mathbb{R}^{n}\\}\enspace.$

######  Remark 3.3.

3.2 provides only one-sided extensions of $T$, either to
$(\mathbb{R}\cup\\{-\infty\\})^{n}$ or to $(\mathbb{R}\cup\\{+\infty\\})^{n}$.
A Shapley operator defined on $\mathbb{R}^{n}$ generally does not extend
canonically to $(\mathbb{R}\cup\\{\pm\infty\\})^{n}$ (consider $n=2$ and
$T_{i}(x)=((x_{1}+x_{2})/2)$ for $i=1,2$).

A Shapley operator is said to be tropically linear if $T(x\vee y)=T(x)\vee
T(y)$ holds for all $x,y\in\mathbb{R}^{n}$. It is said to be dual tropically
linear if $T(x\wedge y)=T(x)\wedge T(y)$. Denoting by
$e^{\operatorname{trop}}_{j}:=(-\infty,\dots,-\infty,0,-\infty,\dots$,
$-\infty)$ (with $0$ in the $j$th position) the $j$th vector of the tropical
canonical basis of $(\mathbb{R}_{\max})^{n}$, and
$M_{ij}:=(T_{-}(e^{\operatorname{trop}}_{j}))_{i}$, we see that if $T$ is
tropically linear, then

$(T(x))_{i}=\vee_{j\in[n]}(M_{ij}+x_{j})\enspace,$

i.e., $T$ is represented by a matrix product. A similar representation holds
for dual tropically linear Shapley operators.

###  3.2. Ambitropical cones

We next introduce our main object of study: ambitropical cones. We are looking
for a class of objects which includes tropical cones and their duals. This
leads to the following definitions. We recall that $\mathbb{R}^{n}$ is
equipped with the standard partial order.

######  Definition 3.2.

An ambitropical cone is a non-empty additive cone $C$ of $\mathbb{R}^{n}$ such
that $C$ is a lattice in the induced order of $(\mathbb{R}^{n},\leqslant)$.

Recall that $C$ being a lattice means that every two elements $x,y$ of $C$
have a least upper bound

$x\vee^{C}y:=\min\\{z\in C\mid z\geqslant x,\;z\geqslant y\\},$

and a greatest lower bound

$x\wedge^{C}y=\max\\{z\in C\mid z\leqslant x,\;z\leqslant y\\},$

where the symbols “max” and “min” indicate the greatest and smallest elements
of a set. Similarly, we will use the notation $\operatorname{sup}^{C}X$ and
$\operatorname{inf}^{C}X$ for the least upper bound and greatest lower bound
in $C$ of a subset $X\subset C$, when it exists. In particular,
$x\vee^{c}y=\operatorname{sup}^{C}\\{x,y\\}$ and
$x\wedge^{c}y=\operatorname{inf}^{C}\\{x,y\\}$. The operations
$\operatorname{sup}^{C}$ and $\operatorname{inf}^{C}$ defined for subsets of
$C$ should not be confused with the restriction of the operations
$\sup=\operatorname{sup}^{\mathbb{R}^{n}}$ and
$\inf=\operatorname{inf}^{\mathbb{R}^{n}}$ defined for subsets of
$\mathbb{R}^{n}$: indeed, for all $X\subset C$ that has a least upper bound in
$C$, $\operatorname{sup}^{C}X\geqslant\sup X$, and similarly
$\operatorname{inf}^{C}X\leqslant\inf X$ if $X$ has a greatest lower bound in
$C$. In other words, an ambitropical cone is a lattice but it may not be a
sublattice of $\mathbb{R}^{n}$.

We shall especially consider ambitropical cones satisfying the following
property.

######  Definition 3.3 (Conditionally complete lattice).

A lattice $L$ is said conditionally complete if every nonempty subset of $L$
that has an upper bound has a join (a least upper bound), and if every
nonempty subset of $L$ that has a lower bound has a meet (a greatest lower
bound).

The following observation is elementary.

######  Lemma 3.4.

Let $C$ be an ambitropical cone. A subset of $\mathbb{R}^{n}$ is bounded from
above by an element of $\mathbb{R}^{n}$ if and only if it is bounded from
above by an element of $C$. The dual statement holds for subsets bounded from
below.

###### Proof.

Let $X\subset\mathbb{R}^{n}$ and suppose that there exists
$u\in\mathbb{R}^{n}$ such that $x\leqslant u$ holds for all $x\in X$. Let
$y\in C$. Then, $u\leqslant z:=y+\mathbf{t}(u-y)$. It follows that $x\leqslant
z\in C$ holds for all $x\in X$. ∎

######  Proposition 3.5.

An ambitropical cone is a conditionally complete lattice if and only if it is
closed in the Euclidean topology.

###### Proof.

Suppose that the ambitropical cone $C$ is closed in the Euclidean topology,
and let $X\subset C$ be a nonempty set bounded above by some element $y\in C$.
Let $\mathscr{P}_{\\!f}(X)$ denote the set of nonempty finite subsets of $X$.
For all $F\in\mathscr{P}_{\\!f}(X)$, let $u_{F}:=\operatorname{sup}^{C}F$.
Then, $(u_{F})_{F\in\mathscr{P}_{\\!f}(X)}$ is a nondecreasing net of elements
of $C$, bounded above by $y$. Since $C$ is closed in the Euclidean topology,
the limit of a net of elements of $C$ belongs to $C$, and so
$u:=\lim_{F}u_{F}\in C$. By construction, $u\geqslant x$ holds for all $x\in
X$. Moreover, if $z\in C$ is an upper bound of $X$, we get $z\geqslant u_{F}$
for all $F\in\mathscr{P}_{\\!f}(X)$, and so $z\geqslant u$. This shows that
$u$ is the least upper bound of $X$. A dual argument works for greatest lower
bounds. Hence, $C$ is a conditionally complete lattice.

Conversely, suppose that $C$ is a conditionally complete lattice. Observe that
for every bounded sequence $(x_{k})$ of elements of $C$, the following
“liminf” and “limsup” constructions both define elements that belong to $C$:

$\operatorname{limsup}^{C}_{k\to\infty}x_{k}:=\operatorname{inf}^{C}_{k\geqslant
1}\operatorname{sup}^{C}_{\ell\geqslant
k}x_{\ell},\qquad\operatorname{liminf}^{C}_{k\to\infty}x_{k}:=\operatorname{sup}^{C}_{k\geqslant
1}\operatorname{inf}^{C}_{\ell\geqslant k}x_{\ell}\enspace.$

We shall use the fact that
$\operatorname{limsup}^{C}_{k\to\infty}x_{k}\geqslant\operatorname{liminf}^{C}_{k\to\infty}x_{k}$.
This inequality, which is standard when $C=\mathbb{R}^{n}$, is still valid in
general. Indeed, for all $k,m\geqslant 1$, we have
$\operatorname{sup}^{C}_{\ell\geqslant
k}x_{\ell}\geqslant\operatorname{inf}^{C}_{\ell\geqslant m}x_{\ell}$, and so
$\operatorname{sup}^{C}_{\ell\geqslant
k}x_{\ell}\geqslant\operatorname{sup}^{C}_{m\geqslant 1}\inf_{\ell\geqslant
m}x_{\ell}=\operatorname{liminf}^{C}_{r\to\infty}x_{r}$. Hence,

(4)
$\displaystyle\operatorname{limsup}^{C}_{k\to\infty}x_{k}=\operatorname{inf}^{C}_{k\geqslant
1}\operatorname{sup}^{C}_{\ell\geqslant
k}x_{\ell}\geqslant\operatorname{liminf}^{C}_{r\to\infty}x_{r}\enspace.$

Suppose that the sequence $(x_{k})_{k\geqslant 1}$ of elements of $C$
converges to $x\in\mathbb{R}^{n}$. Then, for all $\epsilon>0$, there exists an
index $m$ such that $\|x_{\ell}-x\|\leqslant\epsilon$ for all $\ell\geqslant
m$. In particular, $x_{\ell}\leqslant\|x_{\ell}-x_{m}\|+x_{m}\leqslant
2\epsilon+x_{m}$. We deduce that
$\operatorname{limsup}^{C}_{\ell\to\infty}x_{\ell}\leqslant
2\epsilon+x_{m}\leqslant 3\epsilon+x$. Since the latter inequality holds for
all $\epsilon>0$, we deduce that
$\operatorname{limsup}^{C}_{\ell\to\infty}x_{\ell}\leqslant x$. A dual
argument sows that $\operatorname{liminf}^{C}_{\ell\to\infty}x_{\ell}\geqslant
x$. Using (4), we conclude that
$x=\operatorname{limsup}^{C}_{\ell\to\infty}x_{\ell}=\operatorname{liminf}^{C}_{\ell\to\infty}x_{\ell}\in
C$, showing that $C$ is closed in the Euclidean topology. ∎

In the sequel, when writing that an ambitropical is closed, we shall always
refer to the Euclidean topology.

We define, for all closed ambitropical cones $C$, and for all
$x\in\mathbb{R}^{n}$, the following canonical retractions:

(5) $\displaystyle{Q}^{-}_{C}(x):=\operatorname{sup}^{C}\\{y\in C\mid
y\leqslant x\\}\enspace,\qquad{Q}^{+}_{C}(x):=\operatorname{inf}^{C}\\{y\in
C\mid y\geqslant x\\}\enspace.$

We shall denote by $\operatorname{Im}f:=\\{f(x)\mid x\in X\\}$ the image or
range of a map $f:X\to Y$. Recall that a retraction onto $C$ is a map
$P:\mathbb{R}^{n}\to C$ that is a continuous, idempotent map from
$\mathbb{R}^{n}$ to $\mathbb{R}^{n}$ with range $C$. Then, $C$ is a retract of
$\mathbb{R}^{n}$. The following result shows that any closed ambitropical cone
is a Shapley retract, i.e., the image of a retraction that is a Shapley
operator.

######  Proposition 3.6.

Suppose that $C$ is a closed ambitropical cone of $\mathbb{R}^{n}$. Then,
${Q}^{-}_{C}$ is an idempotent Shapley operator, i.e.,
$({Q}^{-}_{C})^{2}={Q}^{-}_{C}$, and the range of ${Q}^{-}_{C}$ is $C$. The
same is true for ${Q}^{+}_{C}$.

###### Proof.

Since $C$ is conditionally complete, for all $x\in\mathbb{R}^{n}$,
${Q}^{-}_{C}(x)$ is well defined and ${Q}^{-}_{C}(x)\in C$. Moreover,
${Q}^{-}_{C}$ trivially fixes $C$, implying that
$\operatorname{Im}{Q}^{-}_{C}=C$ and $({Q}^{-}_{C})^{2}={Q}^{-}_{C}$. We also
have, for all $x\in\mathbb{R}^{n}$ and $\lambda\in\mathbb{R}$,
${Q}^{-}_{C}(\lambda+x)=\operatorname{sup}^{C}\\{y\in C\mid
y\leqslant\lambda+x\\}=\operatorname{sup}^{C}\\{y\in C\mid-\lambda+y\leqslant
x\\}=\operatorname{sup}^{C}\\{\lambda+z\in C\mid z\leqslant
x\\}=\lambda+{Q}^{-}_{C}(x)$. The operator ${Q}^{-}_{C}$ is trivially order
preserving, hence it is a Shapley operator. Dual arguments apply to
${Q}^{+}_{C}$. ∎

######  Theorem 3.7.

Let $C$ be a closed ambitropical cone contained in $\mathbb{R}^{n}$. The set
of Shapley retractions onto $C$ (i. e. idempotent Shapley operators with range
$C$) constitutes a complete lattice, with bottom element ${Q}^{-}_{C}$ and top
element ${Q}^{+}_{C}$.

###### Proof.

First of all, we shall prove that for any Shapley retraction $P$ onto $C$ and
for every $x\in\mathbb{R}^{n}$ ${Q}^{-}_{C}(x)\leqslant
P(x)\leqslant{Q}^{-}_{C}(x)$ . Let $y\in C$ such that $y\leqslant x$, we get
$y=P(y)\leqslant P(x)\in C$, and so
${Q}^{-}_{C}(x)=\operatorname{sup}^{C}\\{y\in C\mid y\leqslant x\\}\leqslant
P(x)$. Similarly, $P(x)\leqslant{Q}^{+}_{C}(x)$. Let $(Q_{\alpha})_{\alpha\in
A}:\mathbb{R}^{n}\to\mathbb{R}^{n}$ be a collection of Shapley retractions
onto $C$. Since ${Q}^{-}_{C}(x)\leqslant Q_{\alpha}(x)\leqslant{Q}^{+}_{C}(x)$
for all $x\in\mathbb{R}^{n}$, the family

$(Q_{\alpha}(x))_{\alpha\in A}\subset C$

is bounded from above and from below. By 3.5 $C$ is conditionally complete,
which allows us to define

$Q(x)=\operatorname{sup}^{C}\\{Q_{\alpha}(x)\mid\alpha\in A\\}.$

It is immediate that $Q$ is a Shapley operator that fixes $C$ and that $C$ is
its range. So, $Q$ is the least upper bound of the family
$(Q_{\alpha})_{\alpha\in A}$ in the set of Shapley retractions. ∎

3.6 shows that closed ambitropical cone are Shapley retracts of
$\mathbb{R}^{n}$. The following result shows that we have actually an
equivalence.

######  Theorem 3.8.

Let $E$ be a subset of $\mathbb{R}^{n}$. The following assertions are
equivalent

  1. (1)

$E$ is a closed ambitropical cone;

  2. (2)

$E$ is a Shapley retract of $\mathbb{R}^{n}$;

  3. (3)

$E$ is the fixed point set of a Shapley operator;

###### Proof.

(1) $\Rightarrow$ (2). If $E$ is a closed ambitropical cone, then, by 3.6, $E$
is the image of ${Q}^{-}_{E}$ and ${Q}^{-}_{E}$ is an idempotent Shapley
operator.

(2) $\Rightarrow$ (3) is trivial.

(3) $\Rightarrow$ (1). Since $E$ is the fixed point set of a Shapley operator
$T$, $E$ is a closed cone. We shall now show that it is also a lattice in the
induced order. Let $x,y\in E$ and we claim that
$x\vee_{E}y=\lim_{k\to\infty}T^{k}(x\vee_{\mathbb{R}^{n}}y)$. We have that
$x,y\leqslant x\vee_{\mathbb{R}^{n}}y$, so $x=T(x)\leqslant
T(x\vee_{\mathbb{R}^{n}}y)$ and $y=T(y)\leqslant T(x\vee_{\mathbb{R}^{n}}y)$.
Applying again $T$ to these inequalities and passing to the limit, we obtain
that $\lim_{k\to\infty}T^{k}(x\vee_{\mathbb{R}^{n}}y)$ is an upper bound of
$x$ and $y$. Let $z\in E$ such that $x,y\leqslant z$. Then
$x\vee_{\mathbb{R}^{n}}y\leqslant z$ and $T(x\vee_{\mathbb{R}^{n}}y)\leqslant
T(z)=z$; applying again $T$ to this inequality and passing to the limit, we
obtain that $\lim_{k\to\infty}T^{k}(x\vee_{\mathbb{R}^{n}}y)\leqslant z$. We
have now to prove that $\lim_{k\to\infty}T^{k}(x\vee_{\mathbb{R}^{n}}y)\in E$.
$T(\lim_{k\to\infty}T^{k}(x\vee_{\mathbb{R}^{n}}y))=\lim_{k\to\infty}T^{k}(x\vee_{\mathbb{R}^{n}}y)$
by definition. So, $\lim_{k\to\infty}T^{k}(x\vee_{\mathbb{R}^{n}}y)$ is a
fixed point of $T$ and it belongs to $E$. The case of $\inf$ is dual.

∎

##  4\. From tropical hulls to ambitropical hulls

###  4.1. Decomposition of canonical retractions in terms of projections on
tropical cones

Appropriate tropical analogues of Hilbert’s spaces are obtained by considering
spaces that are closed by taking suprema [LMS01, CGQ04]. Considering suprema
of bounded sets leads to the notion of b-complete idempotent spaces in
[LMS01], whereas allowing unconditional suprema leads to the notion of
complete semimodules [CGQ04].

Hence, we shall perform a (one sided) conditional completion. If $E$ is a
nonempty subset of $\mathbb{R}^{n}$, we shall denote by $E^{\max}$ the subset
of $\mathbb{R}^{n}$ consisting of tropical linear combinations of possibly
infinite families of elements of $E$, i.e., the set of elements of the form

(6) $\displaystyle\sup\\{\lambda_{f}+f\mid f\in E\\}$

where the $\lambda_{f}\in\mathbb{R}_{\max}$ are such that the family of
elements $(\lambda_{f}+f)_{f\in E}$ is bounded from above and the
$\lambda_{f}$ are not identically $-\infty$. Up to the adjunction of a bottom
element, the set $E^{\max}$ is the b-complete idempotent space generated by
$E$ in the sense of [LMS01].

We shall also need to consider the $\mathbb{R}_{\max}$-semimodule obtained by
taking the lower closure of $E^{\max}$, a notion already introduced in
Definition 2.2:

$\bar{E}^{\max}:=\operatorname{clo}^{\downarrow}E^{\max}\enspace.$

Similarly, we shall denote by $E^{\min}$ the set of elements of the form
$\inf\\{\lambda_{f}+f\mid f\in E\\}$ where the
$\lambda_{f}\in\mathbb{R}_{\min}$ are such that the family of elements
$(\lambda_{f}+f)_{f\in E}$ is bounded from below, and the $\lambda_{f}$ are
not identically $+\infty$. We also set
$\bar{E}^{\min}:=\operatorname{clo}^{\uparrow}E^{\min}$.

######  Proposition 4.1.

Let $C\subset\mathbb{R}^{n}$ be an additive cone. Then, the following
statements are equivalent:

  1. (1)

$C$ is closed;

  2. (2)

$C$ is stable by limits of bounded nondecreasing sequences;

  3. (3)

$C$ is stable by limits of bounded nonincreasing sequences.

###### Proof.

The implication (1)$\Rightarrow$(2) is trivial.

We next show that (2)$\Rightarrow$(3). Let $x_{k}$ be a bounded nonincreasing
sequence of elements of $C$ converging to $x\in\mathbb{R}^{n}$. Consider the
sequence $y_{k}:=x_{k}-2\|x-x_{k}\|_{\infty}e\in C$. We have
$y_{k}\leqslant-\|x-x_{k}\|_{\infty}e+x$. Moreover, $y_{k}$ also converges to
$x$. It follows that for all $k$, we can find an index $l\geqslant k$ such
that $y_{l}\geqslant y_{k}$. Hence, we can construct a nondecreasing
subsequence $y_{n_{k}}$ converging to $x$. Applying (2), we conclude that
$x\in C$.

We finally show that (3)$\Rightarrow$(1). Suppose $x_{k}$ is a sequence of
elements of $C$ converging to $x\in\mathbb{R}^{n}$. Consider now
$y_{k}:=2\|x-x_{k}\|_{\infty}+x_{k}$. Then, arguing as in the proof of the
previous implication, we deduce that we can construct a nonincreasing
subsequence $y_{n_{k}}$ still converging to $x$. Applying (3), we conclude
that $x\in C$. ∎

######  Corollary 4.2.

Let $E$ denote a non-empty subset of $\mathbb{R}^{n}$. Then, $E^{\max}$ is a
closed tropical cone. Similarly, $E^{\min}$ is a closed dual tropical cone.

###### Proof.

By definition, $E^{\max}$ is a tropical cone. Let us consider a bounded
nondecreasing sequence $x_{k}\in E^{\max}$. We can write
$x_{k}=\sup\\{\lambda_{f}^{k}+f\mid f\in E\\}$ where for each $k$, the family
$(\lambda_{f}^{k})_{f\in F}$ is not identically $-\infty$. Let
$x:=\lim_{k}x_{k}=\sup_{k}x_{k}\in\mathbb{R}^{n}$. From
$\lambda_{f}^{k}+f\leqslant x_{k}\leqslant x$, we deduce that
$\lambda_{f}^{k}\leqslant\mathbf{b}(x-f)$. So, the sequence
$(\lambda_{f})_{k\geqslant 1}$ is bounded from above. It follows that
$\lambda_{f}:=\sup\\{\lambda_{f}^{k}\mid k\geqslant 1\\}<+\infty$. Moreover,
using the associativity of the supremum operation, we get $x=\sup
x_{k}=\sup\\{\lambda_{f}+f\mid f\in E\\}\in E^{\max}$. Hence, $E^{\max}$ is
stable by limits of nondecreasing sequences. It follows from 4.1 that
$E^{\max}$ is closed in the Euclidean topology. A dual argument applies to
$E^{\min}$. ∎

If $C$ is a closed tropical cone, then $C$ is closed by tropical linear
combinations, and it is also closed by taking the supremum of nondecreasing
sequences, it follows that the supremum $\operatorname{sup}^{C}$ relative to
$C$ coincides with the supremum of $\mathbb{R}^{n}$. We deduce the following
result.

######  Lemma 4.3.

If $C$ is a closed tropical cone, then ${Q}^{-}_{C}\leqslant I$. Similarly, if
$C$ is a closed dual tropical cone, then ${Q}^{+}_{C}\geqslant I$. ∎

######  Corollary 4.4.

Let $E$ denote a non-empty subset of $\mathbb{R}^{n}$. Then, $\bar{E}^{\max}$
is a closed subsemimodule of $(\mathbb{R}_{\max})^{n}$. Similarly,
$\bar{E}^{\min}$ is a closed subsemimodule of $(\mathbb{R}_{\min})^{n}$

###### Proof.

By definition, $E^{\max}$ is a tropical cone, and by 4.2, it is a closed
subset of $\mathbb{R}^{n}$. Then, it follows from 2.1 that
$\bar{E}^{\max}=\operatorname{clo}^{\downarrow}E^{\max}$ is a closed
subsemimodule of $(\mathbb{R}_{\max})^{n}$. ∎

For all nonempty subsets $E$ of $\mathbb{R}^{n}$, and for all
$x\in\mathbb{R}^{n}$, we define the tropical projections

$P^{\max}_{E}(x):=\sup\\{y\in E^{\max}\mid y\leqslant x\\}\enspace,\qquad
P^{\min}_{E}(x):=\inf\\{y\in E^{\min}\mid y\geqslant x\\}\enspace.$

This is a specialization of the notion of projectors ${Q}^{-}_{C}$ and
${Q}^{+}_{C}$ to $C=E^{\max}$ or $C=E^{\min}$, introduced in (5). Indeed, if
$C=E^{\max}$, the operation $\operatorname{sup}^{C}$ coincides with the
ordinary supremum $\sup$ of $\mathbb{R}^{n}$. The dual property holds for
$C=E^{\min}$. If $G$ is any tropical generating set of $E^{\max}$, then, we
have the explicit representation

(7) $\displaystyle P^{\max}_{E}(x)=\sup_{g\in
G}\Big{(}\mathbf{b}(x-g)+g\Big{)}\enspace,\qquad\forall
x\in\mathbb{R}^{n}\enspace,$

see [CGQ04, Th. 5], and a dual formula applies to $P^{\min}_{E}$. The next
proposition tabulates elementary properties of these projectors.

######  Proposition 4.5.

Let $E$ be a nonempty subset of $\mathbb{R}^{n}$. Then, $P^{\max}_{E}$ and
$P^{\min}_{E}$ are Shapley operators from $\mathbb{R}^{n}\to\mathbb{R}^{n}$
such that:

(8) $\displaystyle P^{\max}_{E}$ $\displaystyle\leqslant I,\qquad
P^{\min}_{E}\geqslant I\enspace.$ (9)
$\displaystyle\operatorname{Im}P^{\max}_{E}$
$\displaystyle=E^{\max},\qquad\operatorname{Im}P^{\min}_{E}=E^{\min}\enspace.$
(10) $\displaystyle P^{\max}_{E}$ $\displaystyle=(P^{\max}_{E})^{2},\qquad
P^{\min}_{E}=(P^{\min}_{E})^{2}\enspace.$

###### Proof.

The inequalities (8) follow from 4.3. By definition, $P^{\max}_{E}$ fixes
$E^{\max}$, and $P^{\max}_{E}(\mathbb{R}^{n})\subset E^{\max}$, so
$P^{\max}_{E}=(P^{\max}_{E})^{2}$. The same property holds for $P^{\min}$,
showing (10). The last claim follows from the fact that $P^{\max}_{E}$ fixes
$E^{\max}\supset E$, and from the same property for $P^{\min}_{E}$. ∎

The maps $\bar{Q}^{-}_{E}$ and $\bar{Q}^{+}_{E}$ defined in the next
proposition will play a key role.

######  Proposition 4.6.

Let $E$ be a nonempty subset of $\mathbb{R}^{n}$. Then, the maps

$\bar{Q}^{-}_{E}:=P^{\min}_{E}\circ
P^{\max}_{E},\quad\text{and}\quad\bar{Q}^{+}_{E}:=P^{\max}_{E}\circ
P^{\min}_{E}$

satisfy the following properties

  1. (i)

$\bar{Q}^{-}_{E}$; $\bar{Q}^{+}_{E}$ are Shapley operators;

  2. (ii)

$\bar{Q}^{-}_{E}$ and $\bar{Q}^{+}_{E}$ fix $E$;

  3. (iii)

$(\bar{Q}^{-}_{E})^{2}=\bar{Q}^{-}_{E}$;
$(\bar{Q}^{+}_{E})^{2}=\bar{Q}^{+}_{E}$;

  4. (iv)

$\bar{Q}^{+}_{E}\circ\bar{Q}^{-}_{E}\circ\bar{Q}^{+}_{E}=\bar{Q}^{+}_{E}$;
$\bar{Q}^{-}_{E}\circ\bar{Q}^{+}_{E}\circ\bar{Q}^{-}_{E}=\bar{Q}^{-}_{E}$;

  5. (v)

$\bar{Q}^{+}_{E}\leqslant\bar{Q}^{-}_{E}\circ\bar{Q}^{+}_{E}$;
$\bar{Q}^{-}_{E}\geqslant\bar{Q}^{+}_{E}\circ\bar{Q}^{-}_{E}$.

###### Proof.

(i). We showed in 4.5 that $P^{\min}_{E}$ and $P^{\max}_{E}$ are both Shapley
operators. The collection of Shapley operators is stable by composition.

(ii). This follows from the fact that $P^{\min}_{E}$ and $P^{\max}_{E}$ fix
$E^{\max}$ and $E^{\min}$, respectively (4.5), which both contain $E$.

(iii). Using the second inequality in (8), and the first equality in (10), we
get $(\bar{Q}^{-}_{E})^{2}=P^{\min}_{E}\circ P^{\max}_{E}\circ
P^{\min}_{E}\circ P^{\max}_{E}\geqslant P^{\min}_{E}\circ P^{\max}_{E}\circ
P^{\max}_{E}=P^{\min}_{E}\circ P^{\max}_{E}$. Using now the first inequality
in (8), and the second equality in (10), we get $P^{\min}_{E}\circ
P^{\max}_{E}\circ P^{\min}_{E}\circ P^{\max}_{E}\leqslant P^{\min}_{E}\circ
P^{\min}_{E}\circ P^{\max}_{E}=P^{\min}_{E}\circ P^{\max}_{E}$, showing that
$(\bar{Q}^{-}_{E})^{2}=\bar{Q}^{-}_{E}$. The second property in (iii) is dual.

(iv). Using (10), we get
$\bar{Q}^{+}_{E}\circ\bar{Q}^{-}_{E}\circ\bar{Q}^{+}_{E}=P^{\max}_{E}\circ
P^{\min}_{E}\circ P^{\min}_{E}\circ P^{\max}_{E}\circ P^{\max}_{E}\circ
P^{\min}_{E}=P^{\max}_{E}\circ P^{\min}_{E}\circ P^{\max}_{E}\circ
P^{\min}_{E}=(\bar{Q}^{+}_{E})^{2}=\bar{Q}^{+}_{E}$, by (iii). The second
property is dual.

(v). We have that $\bar{Q}^{-}_{E}\circ\bar{Q}^{+}_{E}=P^{\min}_{E}\circ
P^{\max}_{E}\circ P^{\max}_{E}\circ P^{\min}_{E}=P^{\min}_{E}\circ
P^{\max}_{E}\circ P^{\min}_{E}\geqslant P^{\max}_{E}\circ
P^{\min}_{E}(z)=\bar{Q}^{+}_{E}$, using $P^{\min}_{E}\geqslant I$. The second
inequality is dual. ∎

The next theorem motivates the introduction of the operators $\bar{Q}^{-}_{E}$
and $\bar{Q}^{+}_{E}$ above, it deals with the situation in which $E$ is a
closed ambitropical cone.

######  Theorem 4.7 (Factorizations of canonical retractions on closed
ambitropical cones).

For all closed ambitropical cones $C$, we have

${Q}^{-}_{C}=\bar{Q}^{-}_{C}=P^{\min}_{C}\circ
P^{\max}_{C}\quad\text{and}\quad{Q}^{+}_{C}=\bar{Q}^{+}_{C}=P^{\max}_{C}\circ
P^{\min}_{C}$

###### Proof.

Suppose $C$ is a closed ambitropical cone. Observe first that for all $z$ in
$\mathbb{R}^{n}$,

(11) $\displaystyle P^{\max}_{C}(z)=\sup\\{x\in C\mid x\leqslant
z\\}\enspace.$

Indeed, $P^{\max}_{C}(z)=\sup\\{x\in C^{\max}\mid x\leqslant
z\\}\geqslant\sup\\{x\in C\mid x\leqslant z\\}$. However, an element
$u\leqslant z$ of $C^{\max}$ can be written as $u=\vee_{y\in
C}(\lambda_{y}+y)$ with $\lambda_{y}\in\mathbb{R}_{\max}$, and
$\lambda_{y}+y\leqslant z$. So, $\lambda_{y}+y\leqslant\sup\\{x\in C\mid
x\leqslant z\\}$, and so, $u\leqslant\sup\\{x\in C\mid x\leqslant z\\}$, which
entails (11). Dually, $P^{\min}_{C}(z)=\inf\\{x\in C\mid x\geqslant z\\}$.

Using (11), and the dual property, we get

$\displaystyle\bar{Q}^{-}_{C}(x)=P^{\min}_{C}\circ P^{\max}_{C}(x)$
$\displaystyle=\inf\\{y\in C\mid y\geqslant P^{\max}_{C}(x)\\}$
$\displaystyle=\inf\\{y\in C\mid y\geqslant\sup\\{z\in C\mid z\leqslant
x\\}\\}$ $\displaystyle=\inf\\{y\in C\mid(z\leqslant x,z\in C)\implies
z\leqslant y\\}$ $\displaystyle=\operatorname{sup}^{C}\\{z\in C\mid z\leqslant
x\\}={Q}^{-}_{C}(x)\enspace.$

The proof that $\bar{Q}^{+}_{C}={Q}^{+}_{C}$ is dual. ∎

For closed tropical cones $C$, the projection $Q_{C}^{-}=P^{\max}_{C}$ has the
property that $Q_{C}^{-}(x)$ is a point of $C$ with minimal distance to $C$
with respect to Hilbert’s seminorm, see [CGQ04], hence, it is a tropical
analogue of the “nearest point projection” arising in Euclidean spaces. A
basic property of this projection on a closed convex set of an Euclidean space
is that it is sunny. Recall that a retraction $F$ from $\mathbb{R}^{n}$ to a
subset of $\mathbb{R}^{n}$ is _sunny_ if, given $x$, $y\in\mathbb{R}^{n}$, for
every $z$ in the segment $[x,y]$, $F(x)=y\implies F(z)=y$. The following
result shows that the canonical projections on closed tropical or dual
tropical cone are also sunny.

######  Proposition 4.8.

If $C$ is a closed tropical cone, then, the projection
$Q_{C}^{-}=P^{\max}_{C}$ is sunny. Similarly, if $C$ is a closed dual tropical
cone, then, the projection $Q_{C}^{+}=P^{\min}_{C}$ is sunny.

###### Proof.

It is trivial that $Q_{C}^{-}=P^{\min}_{C}\circ P^{\max}_{C}=P^{\max}_{C}$.
Let $y:=P^{\max}_{C}(x)$, so by (8) $y\leqslant x$. Then any point
$z=(1-t)y+tx$ with $0<t<1$ satisfies $y\leqslant z\leqslant x$, and so,
$y=P^{\max}_{C}(y)\leqslant P^{\max}_{C}(z)\leqslant P^{\max}(x)=y$, implying
that $P^{\max}_{C}$ is a sunny retraction. ∎

However, the following example shows that 4.8 does not carry over to closed
ambitropical cones, the canonical retractions $Q_{C}^{-}=P^{\min}_{C}\circ
P^{\max}_{C}$ and $Q_{C}^{+}=P^{\max}_{C}\circ P^{\min}_{C}$ are generally not
sunny.

######  Example 4.9.

Consider the Shapley operator

$T\left(\begin{array}[]{c}x_{1}\\\ x_{2}\\\
x_{3}\end{array}\right)=\left(\begin{array}[]{c}\max(x_{1},x_{3})\\\
\max(x_{2},x_{3})\\\ -\frac{1}{2}+\frac{x_{1}+x_{2}}{2}\end{array}\right)$

The fixed point set of $T$ is the closed ambitropical cone
$E=\\{x\in\mathbb{R}^{3}\mid\frac{x_{1}+x_{2}}{2}=x_{3}+\frac{1}{2},x_{1}\geqslant
x_{3},x_{2}\geqslant x_{3}\\}$ shown on Figure 1. The cross section of $E$ in
$\mathbb{R}^{2}$ defined by $x_{3}=0$ is displayed by the black segment, as
well as the cross section of $E^{\max}$ (triangle in light gray above this
segment) and the cross section of $E^{\min}$ (triangle in dark gray below this
segment). In this case $P^{\min}_{E}\circ P^{\max}_{E}$ is not a sunny
retraction. Indeed, consider the point $x=(2,\alpha,0)$, with $0<\alpha<1$. We
have $P^{\max}_{E}(x)=u:=(1,\alpha,0)$, and
$P^{\min}_{E}(u)=y:=(1-\alpha/2,\alpha/2,0)$. However, consider the mid-point
$x^{\prime}:=(y+x)/2=(3/2-\alpha/4,3\alpha/4,0)$. We have
$u^{\prime}:=P^{\max}_{E}(x^{\prime})=(1,3\alpha/4,0)$ and
$y^{\prime}:=P^{\min}_{E}(u^{\prime})=(1-3\alpha/8,3\alpha/8,0)\neq y$ showing
that $P^{\min}_{E}\circ P^{\max}_{E}$ is not sunny. This is illustrated in the
figure.

$E^{\max}$$E^{\min}$$E$$x$$u$$y$$P^{\max}_{E}$$P^{\min}_{E}$$x^{\prime}$$u^{\prime}$$y^{\prime}$
Figure 1. An ambitropical cone such that the canonical retractions
$Q_{E}^{\pm}$ are not sunny.

###  4.2. Characterization of ambitropical cones in terms of best co-
approximation

We saw in 4.7 that the two canonical retractions ${Q}^{-}_{C}$ and
${Q}^{+}_{C}$ on a closed ambitropical cone can be decomposed in terms of the
projection operators $P^{\max}_{C}$ and $P^{\min}_{C}$. In a perhaps
surprising way, we shall see that this leads to an order-theoretical analogue
of a notion of best co-approximation, introduced by Papini and Singer [PS79]
to characterize nonexpansive retracts. If $E$ is a subset of a Banach space
$(X,\|\cdot\|)$, $E$ is said to be a _set of existence of best co-
approximation_ if, for all $z\in X$, the set

$B^{\|\cdot\|}_{E}(z):=\\{x\in X\mid\|y-x\|\leqslant\|y-z\|,\;\forall y\in
E\\}$

contains an element of $E$. It is immediate that if $E$ is a nonexpansive
retract of $X$, then $E$ is a set of existence of best co-approximation. The
converse is known to hold in $L^{p}$ spaces with $1\leqslant p<\infty$, see
[Wes92] and the references therein. Here we shall be interested in Shapley
retracts of $\mathbb{R}^{n}$. By 3.1, these are precisely the images of
$\mathbb{R}^{n}$ by idempotent maps that are nonexpansive in the “top” hemi-
metric $\mathbf{t}{x}=\max_{i\in[n]}x_{i}$. In view of this property, we
introduce the following analogue of the set $B_{E}^{\|\cdot\|}(z)$.

######  Definition 4.1.

Let $E$ be a subset of $\mathbb{R}^{n}$. For any $y,z\in\mathbb{R}^{n}$ we
define $B(y,z)=\\{x\in\mathbb{R}^{n}\mid y+\mathbf{b}(z-y)\leqslant x\leqslant
y+\mathbf{t}(z-y)\\}$ where $\mathbf{t}(x)=\max_{i\in[n]}x_{i}$ and
$\mathbf{b}(x)=\min_{i\in[n]}x_{i}$ for any $x\in\mathbb{R}^{n}$. Then, we
define $B_{E}(z)=\cap_{y\in E}B(y,z)$.

######  Definition 4.2.

Let $E$ be a subset of $\mathbb{R}^{n}$, we say that $E$ is a _set of
existence of best tropical co-approximation_ if $B_{E}(z)\cap E\neq\emptyset$
for every $z\in\mathbb{R}^{n}$.

######  Lemma 4.10.

We have $B_{E}(z)=\\{x\in\mathbb{R}^{n}\mid P^{\max}_{E}(z)\leqslant
x\leqslant P^{\min}_{E}(z)\\}$.

###### Proof.

We shall prove that $\sup_{y\in
E}(\mathbf{b}(z-y)+y)=P^{\max}_{E}(z)=\sup\\{x\in E^{\max}\mid x\leqslant
z\\}$. Let $x\in E^{\max}$, $x=\sup_{y\in E}(\lambda+y)$. Suppose $x\leqslant
z$, then we have that
$\lambda\leqslant\mathbf{b}(x-y)\leqslant\mathbf{b}(z-y)$. In a similar way,
we see that $P^{\min}_{E}(z)=\inf_{y\in E}\mathbf{t}(z-y)+y$. ∎

######  Lemma 4.11.

Let $E$ be a subset of $\mathbb{R}^{n}$. If $E$ is a set of existence of best
tropical co-approximation, then
$\bar{B}_{E}(z):=[\bar{Q}^{-}_{E}(z),\bar{Q}^{+}_{E}(z)]\cap E\neq\emptyset$
for any $z\in\mathbb{R}^{n}$.

###### Proof.

We know that, if $E$ is a set of best tropical co-approximation then for any
$z\in\mathbb{R}^{n}$, there exists $u\in E$ such that
$P^{\max}_{E}(z)\leqslant u\leqslant P^{\min}_{E}(z)$. Composing the first
inequality by $P^{\min}_{E}$, and composing the second inequality by
$P^{\max}_{E}$, we get $\bar{Q}^{-}_{E}(z)=P^{\min}_{E}\circ
P^{\max}_{E}(z)\leqslant P^{\min}_{E}(u)=u$, and $u=P^{\max}_{E}(u)\leqslant
P^{\max}_{E}\circ P^{\min}_{E}(z)=\bar{Q}^{+}_{E}(z)$. ∎

The following result completes 3.8, it characterizes ambitropical cones in
terms of best co-approximation and of the projections $P^{\max}_{E}$ and
$P^{\min}_{E}$.

######  Theorem 4.12.

Let $E$ be a subset of $\mathbb{R}^{n}$. The following assertions are
equivalent

  1. (1)

$E$ is a closed ambitropical cone of $\mathbb{R}^{n}$;

  2. (2)

$E$ is a set of existence of best tropical co-approximation;

  3. (3)

for all $z\in\mathbb{R}^{n}$, $[P^{\max}_{E}(z),P^{\min}_{E}(z)]\cap
E\neq\emptyset$;

  4. (4)

$P^{\min}_{E}(z)\in E$ holds for all $z\in E^{\max}$;

  5. (5)

$P^{\max}_{E}(z)\in E$ holds for all $z\in E^{\min}$;

  6. (6)

$E$ is the fixed point set of the operator $\bar{Q}^{+}_{E}=P^{\max}_{E}\circ
P^{\min}_{E}$;

  7. (7)

$E$ is the fixed point set of the operator $\bar{Q}^{-}_{E}=P^{\min}_{E}\circ
P^{\max}_{E}$.

###### Proof.

(1) $\Rightarrow$ (2). By 3.8, we have that $E=P(\mathbb{R}^{n})$ where
$P=P^{2}$ is a Shapley operator. Then, for all $y\in E$, and for all
$z\in\mathbb{R}^{n}$,
$\mathbf{t}{(P(z)-y)}=\mathbf{t}{(P(z)-P(y))}\leqslant\mathbf{t}{(z-y)}$,
i.e., $P(z)\leqslant\mathbf{t}{(z-y)}+y$, and dually,
$P(z)\geqslant\mathbf{b}{(z-y)}+y$, showing that $P(z)\in E\cap B_{E}(z)$.

(2) $\Rightarrow$ (3). This follows from 4.10.

(3) $\Rightarrow$ (4). We first observe that

(12) $\displaystyle\forall
z\in\mathbb{R}^{n},\;[P^{\max}_{E}(z),P^{\min}_{E}(z)]\cap
E\neq\emptyset\Rightarrow\forall z\in E^{\max},[z,P^{\min}_{E}(z)]\cap
E\neq\emptyset\enspace.$

Now, the condition $[z,P^{\min}_{E}(z)]\cap E\neq\emptyset$ is equivalent to:
$\exists u\in E$ such that $z\leqslant u\leqslant P^{\min}_{E}(z)$. However,
$P^{\min}_{E}(z)$ is the minimal vector $v\in E^{\min}$ such that $v\geqslant
z$, it follows that $P^{\min}_{E}(z)\leqslant u$, and so $P^{\min}_{E}(z)=u\in
E$.

(4) $\Rightarrow$ (5). By hypothesis, we have that for any $z\in E^{\max}$,
$P^{\min}_{E}(z)\in E$, so in particular $[z;P^{\min}_{E}(z)]\cap
E\neq\emptyset$. Consider an arbitrary $z\in\mathbb{R}^{n}$. Then, we have
that $P^{\max}_{E}(z)\in E^{\max}$ and, consequently
$[P^{\max}_{E}(z),P^{\min}_{E}(P^{\max}_{E}(z))]\cap E\neq\emptyset$.
Recalling that
$[P^{\max}_{E}(z),P^{\min}_{E}(P^{\max}_{E}(z))]\subseteq[P^{\max}_{E}(z),P^{\min}_{E}(z)]$
since $P^{\max}_{E}\leqslant I$, we have that for any $z\in\mathbb{R}^{n}$,
$[P^{\max}_{E}(z);P^{\min}_{E}(z)]\cap E\neq\emptyset$. In particular, let
$z\in E^{\min}$, then we have that $[P^{\max}_{E}(z),z]\cap E\neq\emptyset$
and by the dual argument of the previous implication we obtain that
$P^{\max}_{E}(z)\in E$.

(5) $\Rightarrow$ (6). We will denote with
$\operatorname{Fix}(\bar{Q}^{+}_{E})$ the fixed points set of
$\bar{Q}^{+}_{E}$. Since any element of $E$ is fixed by $\bar{Q}^{+}_{E}$,
$E\subseteq\operatorname{Fix}(\bar{Q}^{+}_{E})$. We shall now prove the other
inclusion. Let $z\in\mathbb{R}^{n}$ such that
$P^{\max}_{E}(P^{\min}_{E}(z))=z$. Since $P^{\min}_{E}(z)\in E^{\min}$,
$z=P^{\max}_{E}(P^{\min}_{E}(z))\in E$.

(6) $\Rightarrow$ (7). By the idempotency $\bar{Q}^{+}_{E}$ we have that
$P^{\max}_{E}\circ P^{\min}_{E}(y)\in E$ for every $y\in\mathbb{R}^{n}$, in
particular for any $y\in E^{\min}$, $P^{\max}_{E}(y)\in E$. As in the previous
implication we know that $E\subseteq\operatorname{Fix}(\bar{Q}^{-}_{E})$ and
we shall now prove the other inclusion. Let $z\in\mathbb{R}^{n}$ such that
$P^{\min}_{E}(P^{\max}_{E}(z))=z$, so $z\in E^{\min}$ and consequently
$P^{\max}_{E}(z)\in E$. Since $E$ is fixed by $P^{\min}_{E}$, we have that
$z=P^{\min}_{E}(P^{\max}_{E}(z))\in E$.

(7) $\Rightarrow$ (1). This follows from 4.6, ((iii)) and 3.8.

∎

######  Corollary 4.13.

Let $E$ be a non-empty subset of $\mathbb{R}^{n}$, included in a closed
ambitropical cone $F$. Then, $E^{\max}\cap E^{\min}\subset F$.

###### Proof.

The set $E^{\max}\cap E^{\min}$ is fixed both by $P^{\max}_{E}$ and
$P^{\min}_{E}$. If $E\subset F$, the fixed point set of $P^{\max}_{E}$ is
included in the fixed point set of $P^{\max}_{F}$. The same is true for
$P^{\min}_{E}$ and $P^{\min}_{F}$. So, $E^{\max}\cap E^{\min}$ is included in
the fixed point set of $P^{\min}_{F}\circ P^{\max}_{F}$, which by 4.12,(7),
coincides with $F$. ∎

######  Corollary 4.14.

Suppose $C$ is a closed ambitropical cone. Then $C=C^{\max}\cap C^{\min}$.

###### Proof.

The inclusion $C^{\max}\cap C^{\min}\subset C$ follows from 4.13. The other
inclusion is trivial. ∎

######  Example 4.15.

Conversely, given an additive cone $E\subset\mathbb{R}^{n}$, the condition
that $E=E^{\max}\cap E^{\min}$ does not imply that $E$ is an ambitropical
cone. Consider, for example, the set $E=(a+\mathbb{R})\cup(b+\mathbb{R})$
where $a=(1,0,0)$ and $b=(0,1,0)$. This set, as well as the spaces $E^{\max}$
and $E^{\min}$, are shown on Figure 8. We see that $E=E^{\max}\cap E^{\min}$
but since $E$ is disconnected, it cannot be ambitropical.

###  4.3. Ambitropical hull

The intersection of ambitropical cones is generally not ambitropical, so the
notion of ambitropical hull of a set $E$ cannot be defined in the naïve
manner, as the intersection of ambitropical cones containing $E$. However, we
shall see that there is a proper notion of ambitropical hull, unique up to
isomorphism.

######  Definition 4.3.

Let $E\subset\mathbb{R}^{n}$. We say that $\tilde{E}\subset\mathbb{R}^{n}$ is
a ambitropical hull of $E$ if $\tilde{E}$ is a closed ambitropical cone which
is a superset of $E$ and if it is minimal with respect to inclusion.

######  Proposition 4.16.

For each nonempty subset $E\subset\mathbb{R}^{n}$, the sets
$\operatorname{Im}\bar{Q}^{-}_{E}$ and $\operatorname{Im}\bar{Q}^{+}_{E}$ are
closed ambitropical cones containing $E$ that are isomorphic.

###### Proof.

If $E\subset\mathbb{R}^{n}$ is non-empty, the operator $\bar{Q}^{-}_{E}$ maps
$\mathbb{R}^{n}$ to $\mathbb{R}^{n}$, and it follows from its definition that
it satisfies the axioms of Shapley operators (3.1). Moreover, we have seen in
4.6, (iii) that $\bar{Q}^{-}_{E}$ is idempotent. It follows that
$\operatorname{Im}\bar{Q}^{-}_{E}=\bar{Q}^{-}_{E}(\mathbb{R}^{n})$ is a
Shapley retract, and so $\operatorname{Im}\bar{Q}^{-}_{E}$ is ambitropical.
Moreover, $\operatorname{Im}\bar{Q}^{-}_{E}\supset E$. By duality, the same is
true for $\operatorname{Im}\bar{Q}^{+}_{E}$. By Prop. 4.6, (iv), the map
$\bar{Q}^{+}_{E}$ is a bijection from $\operatorname{Im}\bar{Q}^{-}_{E}$ to
$\operatorname{Im}\bar{Q}^{+}_{E}$ with inverse map $\bar{Q}^{-}_{E}$. ∎

The next result shows that if $F$ is a closed ambitropical cone containing
$E$, then, there is a Shapley operator which injects
$\operatorname{Im}{Q}^{-}_{E}$ into $F$.

######  Theorem 4.17 (Ambitropical hulls).

Let $E$ be a non-empty subset of $\mathbb{R}^{n}$, and suppose that $F$ is a
closed ambitropical cone containing $E$. Then,

  1. (i)

$\bar{Q}^{+}_{E}\circ\bar{Q}^{-}_{F}\circ\bar{Q}^{+}_{E}=\bar{Q}^{+}_{E}$;

  2. (ii)

$\bar{Q}^{-}_{E}\circ\bar{Q}^{+}_{F}\circ\bar{Q}^{-}_{E}=\bar{Q}^{-}_{E}$;

Moreover, $\operatorname{Im}\bar{Q}^{+}_{E}$ is isomorphic to a subset $F^{+}$
of $F$, analogously $\operatorname{Im}\bar{Q}^{-}_{E}$ is isomorphic to a
subset $F^{-}$ of $F$ and $F^{+}$ is isomorphic to $F^{-}$. In particular,
both $\operatorname{Im}\bar{Q}^{+}_{E}$ and $\operatorname{Im}\bar{Q}^{-}_{E}$
are ambitropical hulls of $E$, and all the ambitropical hulls of $E$ are
isomorphic.

###### Proof.

Observe first that since $E\subset F$,

(13) $\displaystyle P^{\min}_{E}\circ P^{\min}_{F}=P^{\min}_{E}$

Indeed, $E\subset F$ implies that $P^{\min}_{F}\leqslant P^{\min}_{E}$. Hence,
$P^{\min}_{E}\circ P^{\min}_{F}\leqslant P^{\min}_{E}\circ
P^{\min}_{E}=P^{\min}_{E}$. Moreover, since $P^{\min}_{F}\geqslant I$,
$P^{\min}_{E}\circ P^{\min}_{F}\geqslant P^{\min}_{E}$, which shows (13).
Since $E^{\max}\subset F^{\max}$, $P^{\max}_{F}$ which fixes
$E^{\max}=\operatorname{Im}P^{\max}_{E}$, we have

(14) $\displaystyle P^{\max}_{F}\circ P^{\max}_{E}=P^{\max}_{E}$

Using (13) and (14), we get
$\bar{Q}^{+}_{E}\circ\bar{Q}^{-}_{F}\circ\bar{Q}^{+}_{E}=P^{\max}_{E}\circ
P^{\min}_{E}\circ P^{\min}_{F}\circ P^{\max}_{F}\circ P^{\max}_{E}\circ
P^{\min}_{E}=P^{\max}_{E}\circ P^{\min}_{E}\circ P^{\max}_{E}\circ
P^{\min}_{E}=(\bar{Q}^{+}_{E})^{2}=\bar{Q}^{+}_{E}$, by 4.6, (v). This shows
(i). The proof of (ii) is dual.

Let $F^{+}=\bar{Q}^{-}_{F}(\operatorname{Im}\bar{Q}^{+}_{E})\subseteq F$ and
consider

$\bar{Q}^{-}_{F}:\operatorname{Im}\bar{Q}^{+}_{E}\to
F^{+},\qquad\bar{Q}^{+}_{E}:F^{+}\to\operatorname{Im}\bar{Q}^{+}_{E}\enspace;$

they are inverses to each other by (i), so $\operatorname{Im}\bar{Q}^{+}_{E}$
and $F^{+}$ are isomorphic. Analogously, by (i),
$\operatorname{Im}\bar{Q}^{-}_{E}$ is isomorphic to the subset of $F$,
$F^{-}=\bar{Q}^{+}_{F}(\operatorname{Im}\bar{Q}^{-}_{E})$. Moreover, by
Corollary 4.16,
$\operatorname{Im}\bar{Q}^{+}_{E}\cong\operatorname{Im}\bar{Q}^{-}_{E}$ and
consequently $F^{-}\cong F^{+}$. Finally, let $\tilde{E}$ be an ambitropical
hull of $E$, then $\operatorname{Im}\bar{Q}^{+}_{E}$ is isomorphic to a subset
$\tilde{E}^{+}$ of $\tilde{E}$ but, since $\tilde{E}$ is minimal for
inclusion, we have that
$\tilde{E}\cong\tilde{E}^{+}\cong\operatorname{Im}\bar{Q}^{+}_{E}$. ∎

We next point out an elementary metric property of ambitropical cones. Recall
that a geodesic between $x$ and $y$ with respect to a seminorm $\|\cdot\|$ on
$\mathbb{R}^{n}$ is a map $\gamma:[0,1]\to\mathbb{R}^{n}$ such that
$\gamma(0)=x$, $\gamma(1)=y$, and
$\|\gamma(t_{2})-\gamma(t_{1})\|+\|\gamma(t_{3})-\gamma(t_{2})\|=\|\gamma(t_{3})-\gamma(t_{1})\|$,
for all $0\leqslant t_{1}<t_{2}<t_{3}\leqslant 1$.

######  Proposition 4.18.

If $E$ is a closed ambitropical cone of $\mathbb{R}^{n}$, then, for any two
points $x,y$ of $E$, there is a curve connecting $x$ and $y$ and included in
$E$ that is a geodesic both in Hilbert’s seminorm and in the sup-norm.

###### Proof.

Since $E$ is closed and ambitropical, there is an idempotent Shapley operator
$P$ such that $E=P(\mathbb{R}^{n})$. Let $x,y\in E$, and consider the ordinary
line segment, $\gamma(s)=x+s(y-x)$, for $s\in[0,1]$, which connects $x$ and
$y$ in $\mathbb{R}^{n}$, and is a geodesic in any semi-norm, in particular, in
Hilbert’s semi-norm and in the sup-norm. Then, since $P$ is nonexpansive both
in Hilbert’s seminorm and in the sup-norm, the map $s\mapsto P(\gamma(s))$ is
still a geodesic, both in Hilbert’s seminorm and in the sup-norm, and it is
included in $E$. ∎

##  5\. Ambitropical convexity and hyperconvexity

We relate here the above notions of ambitropical cones and of ambitropical
hull with hyperconvexity. This notion was introduced by Aronszajn and
Panitchpadki [AP56], We refer the reader to [Isb64, Dre84, Bai88, EK01] for
insights on hyperconvex spaces and on the related notions of injective metric
spaces and tight-span.

######  Definition 5.1.

A metric space $M$ is said to be _hyperconvex_ if
$\bigcap_{\alpha\in\Gamma}B(x_{\alpha},r_{\alpha})\neq\emptyset$ for any
collection of points $\\{x_{\alpha}\\}_{\alpha\in\Gamma}$ in $M$ and positive
numbers $\\{r_{\alpha}\\}_{\alpha\in\Gamma}$ such that
$d(x_{\alpha},x_{\beta})\leqslant r_{\alpha}+r_{\beta}$ for any $\alpha$,
$\beta\in\Gamma$.

We recall that a metric space $M$ is said to be _injective_ if for every $X,Y$
metric spaces, where $Y$ is a subspace of $X$ and $f\colon Y\to M$
nonexpansive, there exists an extension of $f$, $f^{\prime}\colon X\to M$,
that is nonexpansive. (Note that injective metric spaces do not coincide with
injective objects in the category of metric spaces with nonexpansive maps.
Indeed, it is true that every injective object is an injective metric space
but the converse does not hold since the inverse of a nonexpansive map need
not be nonexpansive.) Hyperconvex spaces are complete metric spaces and they
are exactly injective metric spaces [Isb64, Dre84].

3.8 shows that closed ambitropical cones are Shapley retracts of
$\mathbb{R}^{n}$. Therefore, they are particular cases of sup-norm
nonexpansive retracts of $\mathbb{R}^{n}$, so we get by [AP56, Th. 9], that
they are hyperconvex subsets of $\mathbb{R}^{n}$ with sup-norm metric, which
are, in addition, additive cones. We next show that the converse implication
holds.

######  Theorem 5.1.

Let $E$ be an additive cone of $\mathbb{R}^{n}$. The following assertions are
equivalent

  1. (1)

$E$ is a closed ambitropical cone;

  2. (2)

$E$ is hyperconvex for the sup-norm metric.

###### Proof.

We only need to show that $\eqref{hyperconvex}\implies\eqref{ambitropical-2}$.
Suppose that $E$ is an additive cone which is hyperconvex in the sup-norm
metric. Since an hyperconvex space is complete, and $E$ is a subspace of
$\mathbb{R}^{n}$, $E$ must be closed in the Euclidean topology. By 3.2, it is
enough to prove that $E$ is a lattice in the induced order. Let $x,y\in E$ and
let, for any $s\leqslant r\in\mathbb{R}$,

(15) $B^{r}_{s}(u)=\\{x\in E\mid u+s\leqslant x\leqslant
u+r\\}=B(u+(s+r)/2,(r-s)/2)$

Let $U=\\{u\in E\mid u\leqslant x,\quad u\leqslant y\\}$. We want to prove
that there exists a maximal element $z$ of $U$, that is an element $z\in E$
such that $z\leqslant x$, $z\leqslant y$ and $u\leqslant z$ for every $u\in
U$.

This is equivalent to $z\in B^{0}_{r_{x}}(x)$, $z\in B^{0}_{r_{y}}(y)$ for
some $r_{x}$, $r_{y}<0$ and, for every $u\in U$, $z\in B_{0}^{r_{u}}(u)$ for
some $r_{u}>0$. Let us choose $r_{x}$ and $r_{y}$ such that
$x+r_{x}/2\leqslant y$, $y+r_{y}/2\leqslant x$, and $r_{u}$ such that, for all
$u\in U$, $x\leqslant u+r_{u}$ and $y\leqslant u+r_{u}$. Then, we assume
without loss of generality that $r_{x}\geqslant r_{y}$, and observe that
$x+r_{x}/2\in B^{0}_{r_{x}}(x)\cap B^{0}_{r_{y}}(y)$. Moreover, $x\in
B^{0}_{r_{x}}(x)\cap B_{0}^{r_{u}}(u)$ holds for all $u\in U$. Hence, we have
that the balls in the above family have pairwise nonempty intersections.
Therefore, using (15), they can be rewritten as balls satisfying the
conditions in 5.1. So, using the hyperconvexity of $E$, we obtain an element
$z\in E$ belonging to the intersection of all the balls, and such an element
is the maximal element of $U$. ∎

######  Definition 5.2.

Let $E$ be a metric space and let denote the metric by $d$. We call $E$ a
_metric space with a real action_ if there is an action of the additive group
$(\mathbb{R},+,0)$ on $E$, denoted by $(\lambda,x)\in\mathbb{R}\times
E\mapsto\lambda\cdot x\in E$, such that

(16a) $\displaystyle d(\lambda\cdot x,\lambda^{\prime}\cdot
x)=|\lambda-\lambda^{\prime}|\enspace,$ (16b) $\displaystyle d(\lambda\cdot
x,\lambda\cdot x^{\prime})=d(x,x^{\prime})\enspace,$

for any $x,x^{\prime}\in E$ and any $\lambda,\lambda^{\prime}\in\mathbb{R}$.

Let us consider the category of metric spaces with a real action, with the
nonexpansive, action-preserving maps. In the same spirit as for metric spaces,
we say that $C$ is an _injective metric space with a real action_ if for any
metric space with a real action $Y$ and any subset $X$ of $Y$ which is closed
by the real action on $Y$, every nonexpansive, action-preserving map from $X$
to $C$ has an extension from $Y$ to $C$ that is nonexpansive and action-
preserving. Note that, as for metric spaces, this definition does not coincide
with the usual definition of injective objects in the above category.

A prominent example of hyperconvex space is given by the tight span of a
metric space, which provides its hyperconvex or injective hull [Isb64, Dre84].
We now recall the definition and basic results regarding the tight span.

######  Definition 5.3 (Tight span of a metric space [Isb64, Dre84]).

Let $X$ be any metric space with a metric $d$. The tight span $T(X)$ is the
set of functions $f\colon X\to\mathbb{R}_{\geqslant 0}$ satisfying one of the
two equivalent properties:

  1. (1)

$f(x)=\sup_{y\in X}(d(x,y)-f(y))$, for all $x\in X$;

  2. (2)

$f(x)+f(y)\geqslant d(x,y)$, for all $x,y\in X$, and $f$ is minimal among the
functions with this property.

The second property in 5.3 was used in the original construction of Isbell,
where a map $f$ satisfying this property is called an extremal function. The
first property in 5.3 was used by Dress, who noted the equivalence with the
second one and established a number of additional properties [Dre84, Th. 3].
The injectivity hull property of the tight span and some other properties were
proved in [Isb64, Section 2]. We gather below some of the properties
established in [Dre84, Th. 3] or in [Isb64, Section2], that will be used in
the sequel.

We equip $T(X)$ with the supremum distance

$d_{\infty}(f,g)=\sup_{x\in X}|f(x)-g(x)|\enspace.$

######  Theorem 5.2 ([Dre84, Th. 3] and [Isb64, Section 2]).

For any $x\in X$, we denote by $e(x)=d(x,\cdot)$ the map $y\in X\mapsto
d(x,y)$. We have the following properties

  1. (1)

Any element $f$ of $T(X)$ is $1$-Lipschitz continuous, that is
$|f(x)-f(y)|\leqslant d(x,y)$.

  2. (2)

For all $x\in X$ and $f\in T(X)$, we have $d_{\infty}(e(x),f)=f(x)$.

  3. (3)

For all $x\in X$, $e(x)\in T(X)$, and the map $e:X\to T(X),\;x\mapsto e(x)$ is
an isometry. Then, $X$ is isometric to the range $e(X)\subset T(X)$ of $e$,
and can be identified to a subset of $T(X)$.

  4. (4)

Any nonexpansive map $\phi$ from $T(X)$ to itself that fixes $e(X)$ is the
identity map.

  5. (5)

$T(X)$ is an hyperconvex, or equivalently, injective metric space.

  6. (6)

$T(X)$ is the injective hull of $X$ in the category of metric spaces, meaning
that for any injective space $Y$ such that $X\subset Y$, or such that there is
an isometry $\iota$ from $X$ to $Y$, there exists an isometry $\varphi$ from
$T(X)$ to $Y$ such that $\iota=\varphi\circ e$.

Recall also that in 5.2, Item 6 follows from Item 5 and Item 4.

We now show that when $X$ is a metric space with a real action, the tight span
$T(X)$ is canonically equipped with a structure of metric space with real
action.

######  Proposition 5.3.

Assume that $X$ is a metric space with a real action
$(\lambda,x)\in\mathbb{R}\times X\mapsto\lambda\cdot x\in X$. For all $f\in
T(X)$ and $\lambda\in\mathbb{R}$, we set

$\lambda\cdot f:X\to\mathbb{R},\quad y\in X\mapsto(\lambda\cdot
f)(y)=f((-\lambda)\cdot y)\enspace.$

Then, $\lambda\cdot f\in T(X)$. Moreover, the map
$(\lambda,f)\in\mathbb{R}\times T(X)\mapsto\lambda\cdot f\in T(X)$ yields a
real action on $T(X)$, and, together with the supremum distance $d_{\infty}$,
this equips $T(X)$ with a structure of metric space with real action.
Moreover, the map $e:X\to T(X)$ of (3) of 5.2 is an action-preserving
isometry.

###### Proof.

Using that (16b) holds for the metric and action of $X$, we shall deduce that
$\lambda\cdot f\in T(X)$ holds for any $f\in T(X)$ and $\lambda\in\mathbb{R}$.
Indeed, for any $x\in X$, we have

$\displaystyle\sup_{y\in X}(d(x,y)-(\lambda\cdot f)(y))=\sup_{y\in
X}(d(x,y)-f((-\lambda)\cdot y))=\sup_{z\in X}(d(x,\lambda\cdot z)-f(z))$
$\displaystyle\quad=\sup_{z\in X}(d((-\lambda)\cdot
x,z)-f(z))=f((-\lambda)\cdot x)=(\lambda\cdot f)(x)\enspace,$

where the first equality in the second line follows from (16b), and the second
one holds since $f\in T(X)$. So, by 5.3 (first property), $\lambda\cdot f\in
T(X)$. It follows that the map $(\lambda,f)\mapsto\lambda\cdot f$ defines an
action of the group $(\mathbb{R},+,0)$ on $T(X)$.

We now show that the axioms (16) are satisfied, i.e., in the present setting:

(17a) $\displaystyle d_{\infty}(\lambda\cdot f,\lambda^{\prime}\cdot
f)=|\lambda-\lambda^{\prime}|\enspace,$ (17b) $\displaystyle
d_{\infty}(\lambda\cdot f,\lambda\cdot
f^{\prime})=d_{\infty}(f,f^{\prime})\enspace,$

for all $f,f^{\prime}\in T(X)$ and $\lambda,\lambda^{\prime}\in\mathbb{R}$.
Property (17b) follows from a trivial change of variable:

$\displaystyle d_{\infty}(\lambda\cdot f,\lambda\cdot f^{\prime})=\sup_{x\in
X}|f((-\lambda)\cdot x)-f^{\prime}((-\lambda)\cdot x)|=\sup_{x\in
X}|f(x)-f^{\prime}(x)|=d_{\infty}(f,f^{\prime})\enspace.$

It remains to show (17a). We have

(18) $\displaystyle d_{\infty}(\lambda\cdot f,\lambda^{\prime}\cdot
f)=\sup_{x\in X}|f((-\lambda)\cdot x)-f((-\lambda^{\prime})\cdot
x)|\leqslant\sup_{x\in X}d((-\lambda)\cdot x,(-\lambda^{\prime})\cdot
x)=|\lambda-\lambda^{\prime}|\enspace,$

where the inequality in (18) uses that any element of $T(X)$ is $1$-Lipschitz
continuous, see Item 1 of 5.2. If this inequality is strict for some
$\lambda,\lambda^{\prime}\in\mathbb{R}$ and $f\in T(X)$, then

$\nu:=\sup_{x\in X}|f((-\lambda)\cdot x)-f((-\lambda^{\prime})\cdot
x)|<|\lambda-\lambda^{\prime}|\enspace.$

Denote $\mu=\lambda^{\prime}-\lambda$, then applying a change of variable, we
obtain that

$|f(\mu\cdot x)-f(x)|\leqslant\nu<|\mu|,\quad\text{for all}\;x\in X\enspace.$

In particular, $f(\mu\cdot x)\leqslant f(x)+\nu$, and applying successively
this inequality to the elements $(n\mu)\cdot x$ such that $n$ is an integer,
we get $f((n\mu)\cdot x)\leqslant f(x)+n\nu$, for all $n\geqslant 1$. Since
$f\in T(X)$, we also have $f((n\mu)\cdot x)+f(x)\geqslant d((n\mu)\cdot
x,x)=n|\mu|$, where the last equation follows from (16a). We deduce that
$n|\mu|\leqslant 2f(x)+n\nu$ for all $n\geqslant 1$, which is impossible since
$\nu<|\mu|$. Therefore, the inequality in (18) is an equality, whih proves
(17a).

By (3) of 5.2, the map $e:X\to T(X),x\mapsto d(x,\cdot)$ is an isometry. We
also have that $e(\lambda\cdot x)(y)=d(\lambda\cdot x,y)=d(x,(-\lambda\cdot
y))=e(x)(-\lambda\cdot y)=(\lambda\cdot e(x))(y)$. Hence, $e(\lambda\cdot
x)=\lambda\cdot e(x)$. This shows that $e$ is also action-preserving. ∎

######  Theorem 5.4.

Injective metric spaces with a real action are exactly hyperconvex spaces with
a real action.

###### Proof.

To show that hyperconvex spaces with a real action are injective, we proceed
as in the proof of Theorem 4.2 of [EK01], which shows the analogous property
in the absence of a real action. In the following we will outline the parts
which require to be adjusted.

Let $H$ be an hyperconvex metric space with a real action, we want to prove
that $H$ is injective. We shall consider a metric space with real action
$(M,d)$ and $D$, a subset of $M$ which is closed by the action. Let
$(H,d^{\prime})$ be a metric space with real action and $g\colon D\to H$ a
nonexpansive, action preserving map. To prove that $H$ is injective we shall
show that there exists a nonexpansive and action-preserving extension of $g$
from $M$ to $H$.

Let define $\mathcal{C}$ as follows:

$\mathcal{C}=\\{(T_{F},F)\mid D\subseteq F\subseteq M,\;F\text{ is closed by
the action of }M,\;T_{F}\colon F\to H,\;T_{F}\text{ preserves the action}\\}$

$\mathcal{C}$ is nonempty since it contains $(g,D)$. It is ordered by
$(T_{F},F)\leqslant(T_{F^{\prime}},F^{\prime})$ if $F\subset F^{\prime}$ and
$T_{F^{\prime}}$ is an extension of $T_{F}$ over $F^{\prime}$. We need to show
that any maximal element $(T_{F_{1}},F_{1})$ of $\mathcal{C}$ is such that
$F_{1}=M$. We proceed by contradiction, assuming that there exists $z\in
M\setminus F_{1}$, and constructing $(T_{F},F)\in{\mathcal{C}}$, such that
$(T_{F_{1}},F_{1})<(T_{F},F)$ and $z\in F$. Since the set $F$ must be close
under the action, we take $F=F_{1}\cup\\{\lambda\cdot
z\mid\lambda\in\mathbb{R}\\}$. Also, the extended function $T_{F}$ need to
preserve the action. So we need to choose $x\in H$ and define
$T_{F}(\lambda\cdot z)=\lambda\cdot x$ for all $\lambda\in\mathbb{R}$. Since
we are assuming that $z\notin F_{1}$, we have that for every $\lambda$,
$\lambda\cdot z\notin F_{1}$, so we do not have ambiguities in the definition
of $T_{F}$. Since $H$ is hyperconvex, the arguments of the proof of Theorem
4.2 of [EK01] shows that there exists $x\in H$ such that the map $T_{F}$
restricted to the set $F_{1}\cup\\{z\\}$ is nonexpansive. We need to prove
that $T_{F}$ is nonexpansive on all the metric space $F$. Since $T_{F}$ is
already nonexpansive on $F_{1}$, we only need to check the following
conditions:

$\displaystyle d^{\prime}(T_{F}(\lambda\cdot z),T_{F}(\lambda^{\prime}\cdot
z))\leqslant d(\lambda\cdot z,\lambda^{\prime}\cdot z)\enspace,$
$\displaystyle d^{\prime}(T_{F}(z_{1}),T_{F}(\lambda\cdot z)\leqslant
d(z_{1},\lambda\cdot z)\enspace,$

for all $z_{1}\in F_{1}$ and $\lambda,\lambda^{\prime}\in\mathbb{R}$. Since
$T_{F}(\lambda\cdot z)=\lambda\cdot x$, the first inequality is an equality
and follows from (16a). Since $T_{F}$ is preserving the action on $F$, $F_{1}$
is closed under the action, and $T_{F}$ is nonexpansive on $F_{1}\cup\\{z\\}$,
the first inequality follows from (16b).

To show the converse implication, we shall make use of the properties of the
tight span.

Consider now a metric space with real action $X$ and assume that it is
injective. Then, by (5) of 5.2 and 5.3, $T(X)$ is a hyperconvex set with a
real action, and the map $e:X\to T(X),x\mapsto d(x,\cdot)$ is an action-
preserving isometry. By injectivity of $X$ there exists an action-preserving
nonexpansive map from $h\colon T(X)\to X$ such that $h\circ e$ is the
identity. Indeed, we can consider the identity map on $X$ as the map which
will be expanded. Then, the map $e\circ h:T(X)\to T(X)$ is a nonexpansive map
which fixes $e(X)$.

By Item 4 of 5.2, we have that the map $e\circ h$ is the identity, so $X=T(X)$
and it is hyperconvex. ∎

We deduce the following result.

######  Corollary 5.5.

Assume that $X$ is a metric space with a real action. Then, $T(X)$ is the
injective hull of $X$, meaning that for any injective metric space with a real
action $Y$ such that $X\subset Y$, or such that there is an action preserving
isometry $\iota$ from $X$ to $Y$, there exists an action preserving isometry
$\varphi$ from $T(X)$ to $Y$ such that $\iota=\varphi\circ e$.

###### Proof.

Let $X$ is a metric space with a real action, and let $Y$ be an injective
metric space with a real action such that there is an action preserving
isometry $\iota$ from $X$ to $Y$. As above, by (5) of 5.2 and 5.3, $T(X)$ is a
hyperconvex set with a real action, and the map $e:X\to T(X),x\mapsto
d(x,\cdot)$ is an action-preserving isometry. Moreover, by 5.4, $T(X)$ is
injective.

By injectivity of $Y$ there exists an action-preserving nonexpansive map from
$g\colon T(X)\to Y$ such that $g\circ e=\iota$. By injectivity of $T(X)$ there
exists an action-preserving nonexpansive map from $h\colon Y\to T(X)$ such
that $h\circ\iota=e$. Then, the map $h\circ g:T(X)\to T(X)$ is a nonexpansive
map which satisfies $h\circ g\circ e=h\circ\iota=e$, so it fixes $e(X)$.

By Item 4 of 5.2, we have that the map $h\circ g$ is the identity, so $g$ is
an isometry such that $\iota=g\circ e$. ∎

######  Theorem 5.6.

Let $X\in\mathbb{R}^{n}$ be an additive cone. Then, the ambitropical hull of
$X$ and the injective hull of $X$ are in bijective correspondence under an
action-preserving isometry.

###### Proof.

Let $A\subset\mathbb{R}^{n}$ be an ambitropical hull of $X$, with $\imath:X\to
A$ the canonical injection. By 5.1, $A$ is a hyperconvex additive cone, and by
5.4, it is an injective space with real action, and by 5.5, there is an
action-preserving isometry $\varphi$ from $T(X)$ to a subset of $A$ and such
that $\varphi\circ e=\imath$. Hence, $\varphi(T(X))$ is injective, and by 5.1
and 5.4, it is an ambitropical cone. By minimality of $A$, $A=\varphi(T(X))$
which entails that $T(X)$ and $A$ are in bijective correspondence under the
action preserving isometry $\varphi$. ∎

inline]SG: perhaps move what follows near the examples or delete it In
general, it is already a difficult problem to construct the tight span of
finite metric spaces with more than a few points. A characterization of the
tight span of arbitrary subsets of the plane with the maximum metric is given
in [KcK16]. Thanks to the above theorem, we get a way to compute the tight
span of an additive cone, since this last one is isometric to its ambitropical
hull, see e.g. Figure 3 for an illustration. inline]SV: added Kilic reference
here, added part in the introduction about the results of this section

##  6\. Special classes of ambitropical cones

We next review several canonical classes of sets in tropical geometry, showing
these are special cases of ambitropical cones, that can be characterized by
suitable reinforcements of 3.8.

The simplest examples of ambitropical cones consist of alcoved polyhedra,
discussed in Section 2. Actually, the following result shows that alcoved
polyhedra are characterized by the property of being sublattices of
$\mathbb{R}^{n}$. Observe that all properties but one do not assume
polyhedrality, polyhedrality comes as a consequence of the other properties.

######  Proposition 6.1.

Let $C\subset\mathbb{R}^{n}$. The following statements are equivalent:

  1. (1)

$C$ is an alcoved polyhedron;

  2. (2)

$C$ is a closed tropical cone and a closed dual tropical cone,

  3. (3)

$C$ is a closed ambitropical cone in which the infimum and supremum laws
coincide with the ones of $\mathbb{R}^{n}$.

  4. (4)

There is a tropically linear Shapley operator $T$ such that
$C=\\{x\in\mathbb{R}^{n}\mid T(x)\leqslant x\\}$.

  5. (5)

There is a dually tropically linear Shapley operator $T$ such that
$C=\\{x\in\mathbb{R}^{n}\mid T(x)\geqslant x\\}$.

###### Proof of 6.1.

An alcoved polyhedron is stable by pointwise supremum and pointwise infimum of
vectors, so (1) implies (2). Trivially, (2) implies (3).

Suppose now that (3) holds. Then, by 3.5, $C$ is a conditionally complete
lattice, and the lattice operations of $C$ are the pointwise supremum and
pointwise infimum of vectors. Define, for all $i,j\in[n]$,

$M_{ij}:=\sup\\{\lambda\mid v_{i}\geqslant\lambda+v_{j},\qquad\forall v\in
C\\}$

The latter set is nonempty, it is closed and bounded from above, so that the
supremum is achieved. In particular, we have $M_{ij}\in\mathbb{R}_{\max}$. By
construction, $C\subset\mathscr{A}(M)$, and $M_{ij}=M_{ij}^{*}$. Observe also
that the inequality $v_{i}\geqslant\lambda+v_{j}$, is equivalent to
$w_{i}\geqslant\lambda$ where $w:=v-v_{j}\delta_{j}\in C$ is such that
$w_{j}=0$, denoting by $\delta_{j}=(0,\dots,0,1,0,\dots 0)$ the $j$-th vector
of the canonical basis of $\mathbb{R}^{n}$. It follows that:

$M_{ij}=\inf C_{ij},\;\text{where}\;C_{ij}:=\\{v_{i}\mid v\in
C_{j}\\}\;\text{and}\;C_{j}:=\\{v\in C\mid v_{j}=0\\}\enspace.$

Denoting by $u^{j}$ the $j$th column of the matrix $M$, we deduce that

$u^{j}=\inf C_{j}\in\operatorname{clo}^{\downarrow}C\enspace.$

Define, $A_{j}:=\\{v\in\operatorname{clo}^{\downarrow}C\mid v_{j}=0\\}$. Since
$C$ is a conditionally complete lattice, the set
$A_{j}\subset\operatorname{clo}^{\downarrow}C$ is stable by taking infima.
Hence, the set $\operatorname{Min}A_{j}$ consists of a single point, $u^{j}$.
By 2.2, every element of $C$ is a tropical linear combination of vectors
$u^{j}$. This implies that $\mathscr{A}(M)=\\{M^{*}y\mid
y\in\mathbb{R}^{n}\\}=C$. So (3) implies (1).

If $C=\mathscr{A}(M)$ is an alcoved polyhedron, it follows from (2) that
$C=\\{x\in\mathbb{R}^{n}\mid T(x)\leqslant x\\}$ where $T(x)=M^{*}x$ is a
Shapley operator. So (1) implies (4).

Conversely, if $C=\\{x\in\mathbb{R}^{n}\mid T(x)\leqslant x\\}$ for some
tropically linear Shapley operator, then, for all $x,y\in C$, since $T$ is
order preserving, $T(x\wedge y)\leqslant T(x)\wedge T(y)\leqslant x\wedge y$,
and since $T$ is tropically linear, $T(x\vee y)=T(x)\vee T(y)\leqslant x\vee
y$, showing that $x\wedge y$ and $x\vee y$ belong to $C$. Moreover, $C$ is
closed, since $T$ is continuous (in fact, $T$ is sup-norm nonexpansive). This
shows that (4) implies (3).

(1) and (5) are equivalent. Indeed, observe that $C$ is of the form
$\\{x\in\mathbb{R}^{n}\mid T(x)\leqslant x\\}$ for some tropically linear
Shapley operator iff $-C$ is of the form $\\{x\in\mathbb{R}^{n}\mid
P(x)\geqslant x\\}$ for some dually tropically linear Shapley operator
(consider the involution $T\mapsto P,\;P(x):=-T(-x)$ on the space of Shapley
operators). Moreover, $C$ is an alcoved polyhedron iff $-C$ is an alcoved
polyhedron. Hence, the announced equivalence follows from the equivalence of
(1) and (4), already established. ∎

Note that in the above proof we made use of a particular instantiation of the
"flip" application $X\to-X$ which sends ambitropical cones to ambitropical
cones.

Tropical cones, and dual tropical cones, are also remarkable examples of
ambitropical cones. The relation between these cones and sub or super-fixed
point sets of Shapley operators was already noted in [AGG12].

######  Proposition 6.2.

Let $C\subset\mathbb{R}^{n}$. The following statements are equivalent:

  1. (1)

$C$ is a closed tropical cone;

  2. (2)

$C$ is a closed ambitropical cone in which the supremum law coincides with the
one of $\mathbb{R}^{n}$;

  3. (3)

there is a Shapley operator $T$ such that $C=\\{x\in\mathbb{R}^{n}\mid
T(x)\geqslant x\\}$.

###### Proof.

(1)$\Rightarrow$(2). Suppose that $C$ is a closed tropical cone, and let $X$
denote a non-empty subset of $C$ bounded from above by an element of
$\mathbb{R}^{n}$. Then, for all finite subsets $F\in\mathscr{P}_{\\!f}(X)$,
$\sup F$ belongs to $C$, because $C$ is stable by supremum, and $\sup
X=\lim_{F\in\mathscr{P}_{\\!f}(X)}\sup F\in C$ because $C$ is closed. It
follows that $X$ has a supremum in $C$ which coincides with its supremum in
$\mathbb{R}^{n}$. Suppose now that $X$ is bounded from below by an element $z$
of $\mathbb{R}^{n}$. Consider $Y:=\\{y\in C\mid y\leqslant x,\forall x\in
X\\}$. Then, $Y$ is non-empty and it is bounded from above. It follows from
the previous observation that $\sup Y$ is the supremum of $Y$, in $C$.
Moreover, $\sup Y$ is precisely the infimum of $X$ in $C$, showing that $C$ is
ambitropical.

(2)$\Rightarrow$(3). Since $C$ is a closed ambitropical cone, then, it is the
fixed point set of $z\mapsto{Q}^{-}_{C}(z)=\sup\\{x\in C\mid x\leqslant z\\}$,
and ${Q}^{-}_{C}\leqslant I$. So,
$C=\\{z\in\mathbb{R}^{n}\mid{Q}^{-}_{C}(z)=z\\}=\\{z\in\mathbb{R}^{n}\mid{Q}^{-}_{C}(z)\geqslant
z\\}$.

(3)$\Rightarrow$(1). Suppose that $C=\\{x\in\mathbb{R}^{n}\mid T(x)\geqslant
x\\}$. Since $T$ is continuous, $C$ is closed. Moreover, since $T$ is order
preserving, for all $x,y\in C$, $T(x\vee y)\geqslant T(x)\vee T(y)\geqslant
x\vee y$, showing that $x\vee y\in C$. ∎

We state the following dual version of 6.2.

######  Proposition 6.3.

Let $C\subset\mathbb{R}^{n}$. The following statements are equivalent:

  1. (1)

$C$ is a closed dual tropical cone;

  2. (2)

$C$ is an ambitropical cone in which the infimum law coincides with the one of
$\mathbb{R}^{n}$;

  3. (3)

there is a Shapley operator $T$ such that $C=\\{x\in\mathbb{R}^{n}\mid
T(x)\leqslant x\\}$. ∎

We next define the subclass of homogeneous tropical cones – which will arise
as tangent spaces or recession sets of ordinary tropical cones.

######  Definition 6.1.

An ambitropical cone $C$ is homogeneous if for all $\alpha>0$ and for all
$x\in C$, $\alpha x\in C$. Recall that a Shapley operator
$T:\mathbb{R}^{n}\to\mathbb{R}^{n}$ is homogeneous if $T(\alpha x)=\alpha
T(x)$ holds for all $\alpha>0$ and for all $x\in\mathbb{R}^{n}$.

######  Proposition 6.4.

Let $C\subset\mathbb{R}^{n}$. The following statements are equivalent:

  1. (1)

$C$ is a closed homogeneous ambitropical cone;

  2. (2)

there is an idempotent homogeneous Shapley operator whose fixed point set is
$C$;

  3. (3)

there is a homogeneous Shapley operator whose fixed point set is $C$.

###### Proof.

The implication (2)$\Rightarrow$(3) is immediate. If $C$ is the fixed point
set of an homogeneous Shapley operator $T$, then, we know from 3.8 that $C$ is
an ambitropical cone, and it follows from the homogeneity of $T$ that $C$ is
homogeneous. This shows the implication (3)$\Rightarrow$(1). If $C$ is a
closed homogeneous ambitropical cone, we know from 3.8 that $C$ is the range
of the idempotent Shapley operator $\bar{Q}^{-}_{C}={Q}^{-}_{C}$. Observe
that, for all $\alpha>0$ and $x\in\mathbb{R}^{n}$, ${Q}^{-}_{C}(\alpha
x)=\operatorname{sup}^{C}\\{y\in C\mid y\leqslant\alpha
x\\}=\operatorname{sup}^{C}\\{\alpha\alpha^{-1}y\mid y\in
C,\;\alpha^{-1}y\leqslant x\\}=\operatorname{sup}^{C}\\{\alpha z\mid z\in
C,\;z\leqslant x\\}=\alpha{Q}^{-}_{C}(x)$ since $y\mapsto\alpha^{-1}y$ is a
bijection from $C$ to $C$, which is order preserving and whose inverse also
preserves the order. This shows the implication (1)$\Rightarrow$(2). ∎

##  7\. Correspondence between fixed points of Shapley operators and
calibrated policies

inline]section to be revised

###  7.1. Finitely generated Shapley operators

The following definition is taken from [CTGG99].

######  Definition 7.1.

A min-max function in the variables $x_{1},\dots,x_{n}$ is a map
$f:\mathbb{R}^{n}\to\mathbb{R}$, defined by a term in the context-free grammar
$X\to x_{1},\dots,x_{n},X\vee X,X\wedge X,X+c$ where $c$ stands for any real
constant.

For instance, $f(x_{1},x_{2},x_{3})=((x_{1}\vee(x_{2}+3))\wedge((x_{3}-1)\vee
x_{1}))\vee x_{2}$ is a min-max function. It follows readily from the
definition that the set of min-max functions is stable by the operations
$\vee$, $\wedge$, and by the translation by a constant. Using the
distributivity law, we may always rewrite a min-max function in conjunctive
normal form, i.e.,

(19) $\displaystyle f(x)=\wedge_{k\in[K]}\vee_{i\in[n]}(c_{ki}+x_{i})$

for some integer $K$ and coefficients $c_{ki}\in\mathbb{R}_{\max}$, such that
for all $k\in[K]$, $c_{ki}\neq-\infty$ for some $i\in[n]$. Similarly, we may
rewrite $f$ in disjunctive normal form:

(20) $\displaystyle
f(x)=\vee_{k\in[K^{\prime}]}\wedge_{i\in[n]}(c^{\prime}_{ki}+x_{i})$

for some integer $K^{\prime}$ and coefficients
$c^{\prime}_{ki}\in\mathbb{R}_{\min}$, such that for all $k\in[K^{\prime}]$,
$c^{\prime}_{ki}\neq+\infty$ for some $i\in[n]$. Monotone Boolean functions
are special cases of min-max functions, they are obtained by restricting the
above grammar rule to exclude the derivation $X\mapsto X+c$. For instance,
$(x_{1}\vee x_{2})\wedge x_{3}$ is a monotone Boolean function.

######  Definition 7.2.

A Shapley operator is finitely generated if its coordinates are min-max
functions.

It will be convenient to write finitely generated Shapley operators in an
algebraic way, along the lines of [AGG12], making apparent the game
interpretation. Let $A\in(\mathbb{R}_{\max})^{m\times p}$. The adjoint of the
tropically linear map associated with the matrix $A$ is the dual tropically
linear map

$y\mapsto
A^{\sharp}y,\qquad(A^{\sharp}y)_{k}=\wedge_{i\in[m]}(-A_{ik}+y_{i}),\qquad
k\in[p]\enspace,$

which sends $\mathbb{R}^{m}\to\mathbb{R}^{p}$ if $A$ has no identically
$-\infty$ column. Observe that, for $x\in\mathbb{R}^{p}$ and
$y\in\mathbb{R}^{m}$,

$Ax\leqslant y\iff x\leqslant A^{\sharp}y\enspace.$

If $B\in(\mathbb{R}_{\max})^{m\times n}$ The tropically linear map

$x\mapsto Bx,\qquad(Bx)_{i}=\vee_{j\in[n]}(B_{ij}+x_{j}),\qquad i\in[m]$

sends $\mathbb{R}^{n}$ to $\mathbb{R}^{m}$ if $B$ has not identically
$-\infty$ row. This motivates the following definition.

######  Definition 7.3.

We say that a pair of matrices $A\in(\mathbb{R}_{\max})^{m\times
p},B\in(\mathbb{R}_{\max})^{m\times n}$ is proper if $A$ has no identically
$-\infty$ column, and $B$ has no identically $-\infty$ row.

Given a proper pair of matrices $A\in(\mathbb{R}_{\max})^{m\times
p},B\in(\mathbb{R}_{\max})^{m\times n}$, we consider the operator
$T=A^{\sharp}\circ B$, with coordinates

(21) $\displaystyle
T_{i}(x)=\wedge_{j\in[m]}\Big{(}-A_{ji}+\vee_{k\in[n]}(B_{jk}+x_{k})\Big{)},\qquad
i\in[p]\enspace.$

This is a finitely generated Shapley operator from
$\mathbb{R}^{n}\to\mathbb{R}^{p}$.

######  Proposition 7.1.

Every finitely generated Shapley operator can be written as $T=A^{\sharp}\circ
B$ for some proper pair of matrices $A,B$.

###### Proof.

Every coordinate of $T$ can be represented by a min-max function in
disjunctive normal form, and this representation is of the form (21) (with
$A_{ij}\in\\{0,-\infty\\}$). ∎

Recall that a map $T:\mathbb{R}^{n}\to\mathbb{R}^{p}$ is (positively)
homogeneous (of degree $1$) if $T(\alpha x)=\alpha T(x)$ holds for all
$\alpha>0$ and $x\in\mathbb{R}^{n}$.

######  Proposition 7.2.

If $T$ is a finitely generated homogeneous Shapley operator, then the
coordinates of $T$ are given by monotone Boolean functions, and all the
finitely generated homogeneous Shapley operators arise is this way.

###### Proof.

Suppose that $T=A^{\sharp}\circ B$ as above. Then,
$T_{i}(x)=\alpha^{-1}T_{i}(\alpha x)$, and so,

$\displaystyle T_{i}(x)$
$\displaystyle=\lim_{\alpha\to\infty}\wedge_{j\in[m]}\Big{(}-\alpha^{-1}A_{ji}+\vee_{k\in[n]}(\alpha^{-1}B_{jk}+x_{k})\Big{)}$
$\displaystyle=\wedge_{j\in[m],\;A_{ij}\neq-\infty}\big{(}\vee_{k\in[n],\;B_{jk}\neq-\infty}x_{k}\big{)}$

which is a monotone Boolean function. ∎

######  Proposition 7.3.

Let $T_{1}$, $T_{2}$ be two finitely generated Shapley operators
$\mathbb{R}^{n}\to\mathbb{R}^{p}$. Then the operators $T_{1}\vee T_{2}$ and
$T_{1}\wedge T_{2}$ are finitely generated. Suppose now that $T_{2}$ is a
finitely generated Shapley operator from $\mathbb{R}^{q}\to\mathbb{R}^{n}$.
Then, $T_{1}\circ T_{2}$ is a finitely generated Shapley operator.

###### Proof.

By definition, min-max functions are stable by the laws $\vee$ and $\wedge$.
They are also stable by composition, meaning that if $f(x_{1},\dots,x_{n})$ is
a min-max function in the variables $x_{1},\dots,x_{n}$, and if for all
$i\in[n]$, $g_{i}(y_{1},\dots,y_{q})$ is a min-max function in the variables
$y_{1},\dots,y_{q}$, then
$f(g_{1}(y_{1},\dots,y_{q}),\dots,g_{n}(y_{1},\dots,y_{q}))$ is a min-max
function in the same variables. This implies the announced properties. ∎

###  7.2. Eigenvectors of Shapley operators and Deterministic Mean Payoff
Games

We next recall that the operators of the form (21) are precisely the dynamic
programming operators of deterministic zero-sum games without discount,
referring the reader to [AGG12] for background. We shall also present an
equivalence between the fixed points of the Shapley operator and a remarkable
class of optimal positional policies, calibrated policies.

We associate to the proper pair of matrices $(A,B)$ a game in which two
players, Max and Min, move alternatively a token in a digraph. The set of
states is the disjoint union of the sets $[n]$ and $[m]$. If the token is in a
state $i\in[n]$, Player Min chooses a new state $j\in[m]$ such that $A_{ji}$
is finite, moves the token to this state, and receives a payment $A_{ji}$ from
Max. If the token is in a state $j\in[m]$, Player Max chooses a new state
$k\in[n]$ such that $B_{jk}$ is finite, moves the token to this state, and
receives a payment $B_{jk}$ from Min. The assumption that the pair $(A,B)$ is
proper guarantees that each player has always at least one available action.
Given an initial state $i\in[n]$, and an integer $k$, one can consider the
game in horizon $k$, in which each the two players makes $k$ moves,
alternatively, so that the total payment received by Player Max is

$R^{k}=-A_{j_{1}i_{0}}+B_{j_{1}i_{1}}-A_{j_{2}i_{1}}+B_{j_{2}i_{2}}+\dots-
A_{j_{k}i_{k-1}}+B_{j_{k}i_{k}}$

where $i_{0},j_{1},i_{1},j_{2},\dots,j_{k},i_{k}$ is the sequence of states
that are visited and $i_{0}=i$ is the initial state. A history of the game, at
a given stage, consists of the sequence of visited states, so if $l$ turns
have been played, and if it Min’s turn to play, the history is
$i_{0},j_{1},i_{1},j_{2},\dots,j_{l},i_{l}$ whereas if it is Max’s turn to
play, the history is $i_{0},j_{1},i_{1},j_{2},\dots,j_{l},i_{l},j_{l+1}$. We
assume that the game is in perfect information, meaning that the two players
observe the history. A (pure) strategy of a player is a map which associates
an action to each history. Therefore, the total payment is a function of the
strategies $\sigma$ and $\pi$ of the two players and of the initial state $i$,
i.e., $R^{k}=R^{k}_{i}(\sigma,\pi)$. It follows from dynamic programming
arguments, that the game in horizon $k$ with initial state $i$ has a value,
$v_{i}^{k}$, and that there are associated optimal strategies $\sigma^{*}$ and
$\pi^{*}$, meaning that the following saddle point property holds:

$R_{i}^{k}(\sigma^{*},\pi)\leqslant v_{i}^{k}\leqslant
R_{i}^{k}(\sigma,\pi^{*})$

for all strategies $\sigma$ of Player Min and $\pi$ of Player Max, which
entails in particular that $v_{i}^{k}=R_{i}^{k}(\sigma^{*},\pi^{*})$. Indeed,
the value vector $v^{k}=(v^{k}_{i})_{i\in[n]}\in\mathbb{R}^{n}$ satisfies the
dynamic programming equation

$v^{0}=0,\qquad v^{k}=T(v^{k-1})\enspace,$

and the actions that achieve the min or max in the expression $T_{i}(v^{k-1})$
provide optimal decisions for the two players, depending only on the current
state and on the time remaining to play. We refer the reader to [MSZ15b] for
background on game theory and on the dynamic programming approach.

A deterministic policy of Player Min (resp. Max) is a map $\sigma:[n]\to[m]$
(resp. $\pi:[m]\to[n]$). A deterministic policy of Player Min induces a
stationary positional strategy, obtained by moving to state $\sigma(i)$ when
in state $i\in[n]$, and similarly for Player Max, the state being now
$j\in[m]$.

We are interested in the mean payoff game, in which Player Min wants to
minimize the mean payment per time unit made to Player Max, and Player Max
wants to maximize it. Liggett and Lippman [LL69], and Ehrenfeucht and
Mycielski [EM79] showed that there exists a vector
$\chi=(\chi_{i})_{i\in[n]}\in\mathbb{R}^{n}$ and deterministic policies
$\sigma^{*}$ and $\pi^{*}$, of Player Min and Max, respectively, such that,
for all strategies $\sigma$ and $\pi$ of these two players, and for all
initial states $i\in[n]$,

(22)
$\limsup_{k\to\infty}k^{-1}R_{i}^{k}(\sigma^{*},\pi)\leqslant\chi_{i}\leqslant\liminf_{k\to\infty}k^{-1}R_{i}^{k}(\sigma,\pi^{*})\enspace.$

The number $\chi_{i}$ is known as the value of the mean payoff game with
initial state $i$. Moreover, the vector $\chi$ coincides with the limit
$\lim_{k\to\infty}v^{k}/k$.

A remarkable case arises when the non-linear eigenproblem

$T(u)=\lambda+u,\qquad u\in\mathbb{R}^{n},\lambda\in\mathbb{R}$

is solvable. Then, the value of the mean payoff game $\chi_{i}$ is independent
of the initial state $i$, and optimal deterministic policies can be obtained
from the eigenvector $u$. To explain this relation, it will be convenient to
extend the notion of policy as follows: a nondeterministic policy of Player
Min (resp. Max) is a map $\sigma:[n]\to\mathscr{P}([m])\setminus\emptyset$,
such that $\sigma(i)\subset\\{j\in[m]\mid A_{ji}\,\text{finite}\\}$ for all
$i\in[n]$. Similarly, a nondeterministic policy of Player Max is a map
$\pi:[m]\to\mathscr{P}([n])\setminus\emptyset$, such that
$\pi(j)\subset\\{i\in[n]\mid B_{ji}\,\text{finite}\\}$ for all $j\in[m]$. A
nondeterministic policy of Player Min induces a whole collection of strategies
(not necessarily stationary or positional), obtained by restricting the moves
of Min to the $i\to j\in\sigma(i)$. In particular, it induces deterministic
policies, obtained by selecting, for all $i\in[n]$, a single element in
$\sigma(i)$. We denote by $\mathscr{S}$ the set of nondeterministic policies
of Player Min, and by $\mathscr{P}$ the set of nondeterministic policies of
Player Max.

The following definition extends to the two-player case the notion of
calibrated trajectory introduced by Fathi in the context of weak-KAM theory,
see [FS04, Fat08].

######  Definition 7.4 (calibrated policies).

Given $u\in\mathbb{R}^{n}$, we say that a pair of non-deterministic policies
$(\sigma^{u},\pi^{u})$ is $u$-calibrated if, for some $\lambda\in\mathbb{R}$,

  1. i)

By playing any strategy induced by $\sigma^{u}$, Player Min can guarantee
that, whatever strategy Max chooses, and for all horizons $k$ and initial
states $i_{0}$,

(23) $\displaystyle-A_{j_{0}i_{0}}+B_{j_{0}i_{1}}+\dots-
A_{j_{j-1}i_{k-1}}+B_{j_{k-1}i_{k}}\leqslant
u_{i_{0}}-u_{i_{k}}+k\lambda\enspace,$

  2. ii)

By playing any strategy induced by $\pi^{u}$, Player Max can guarantee that,
whatever strategy Min chooses, and for all horizons $k$ and initial states
$i_{0}$,

(24) $\displaystyle-A_{j_{0}i_{0}}+B_{j_{0}i_{1}}+\dots-
A_{j_{j-1}i_{k-1}}+B_{j_{k-1}i_{k}}\geqslant
u_{i_{0}}-u_{i_{k}}+k\lambda\enspace;$

where $i_{0},j_{0},i_{1},j_{1}\dots,i_{k}$ is the sequence of states that are
visited.

In the special one-player case, assuming for instance that Player Max is a
dummy (with only one possible action in each state), we can replace the
inequality by an equality in (23), and then, we recover the original notion of
calibrated trajectory. In particular, Fathi established a correspondence
between the global viscosity solutions of the ergodic Hamilton-Jacobi PDE and
calibrated trajectories, see [FS04, Prop. 3.5] and [Fat08, Prop 4.1.10]. The
following elementary proposition states an analogous property in the two-
player setting.

######  Proposition 7.4.

Suppose that $T(u)=\lambda+u$, define
$\pi^{*}(j)=\operatornamewithlimits{argmax}_{i}B_{ji}+u_{i}$ and
$\sigma^{*}(i)=\operatornamewithlimits{argmin}_{j}-A_{ji}+(Bu)_{j}$. Then, the
pair of policies $(\sigma^{*},\pi^{*})$ is $u$-calibrated. Moreover, all pairs
of $u$-calibrated policies arise in this way.

To establish this result, it will be convenient to introduce, for all pair of
deterministic policies $(\sigma,\pi)$ of the two players, the operators
$T^{\sigma}$ and ${}^{\pi}T$, $\mathbb{R}^{n}\to\mathbb{R}^{n}$, such that

$T^{\sigma}_{i}(x)=-A_{\sigma(i)i}+\vee_{k}(B_{\sigma(i)k}+x_{k}),\qquad^{\pi}T_{i}(x)=\wedge_{j}(-A_{ji}+B_{j\pi(j)}+x_{\pi(j)})\enspace.$

These operators represent the one-player games obtained by fixing a policy of
one of the players.

###### Proof.

If $T(u)=\lambda+u$, by definition of $\sigma^{*}$ and $\pi^{*}$, we have, for
all deterministic policies $\sigma$ and $\pi$ compatible with $\sigma^{*}$ and
$\pi^{*}$,

$T^{\sigma}(u)=\lambda+u,\qquad^{\pi}T(u)=\lambda+u\enspace.$

It follows that for all $k$, $(T^{\sigma})^{k}(u)=k\lambda+u$, which implies
that (23) holds. Similarly, $(^{\pi}T)^{k}(u)=k\lambda+u$ yields (24).

Conversely, if $\sigma^{*}$ and $\pi^{*}$ are $u$-calibrated, by specializing
(23) to $k=1$, we deduce that $T(u)\leqslant\lambda+u$, and similarly, we
deduce from (24) that $T(u)\geqslant\lambda+u$. ∎

Any deterministic policies $(\sigma^{*},\pi^{*})$ induced by a pair
$(\sigma^{u},\pi^{u})$ of $u$-calibrated policies are optimal in the mean
payoff game, meaning they satisfy the saddle point property (22). However,
being $u$-calibrated is a finer property than being optimal in the mean payoff
game, since it involves not only the mean payoff but also the deviation to the
mean payoff. This is easily seen in the one-player case. Then, playing a
deterministic policy induces state trajectories which ultimately cycle. As
long as the the ultimate cycle reached from each initial state is unchanged,
the mean-payoff optimality is preserved, but not the property of being
calibrated.

######  Example 7.5.

Consider the one player game shown in Figure 2, in which the Player is Max.
This can be represented by the pair of matrices $(A,B)$ where $A$ is the
tropical identity map, meaning that player Min is a dummy, and $B$ is the
matrix of payments shown in the figure. The value of the mean payoff game is
equal to $1$, since it is optimal for Player Max to reach the cycle $4\to 4$
which has the best weight-to-length ratio, equal to $1$. The matrix $B$, and
so, the operator $T=A^{\sharp}\circ B$, has only one eigenvector up to an
additive constant, given by $u=(-2,-2,-1,0)$, and so, by Proposition 7.4,
there is only one $u$-calibrated strategy, namely $1\rightarrow 3$,
$3\rightarrow 4$ and $2\rightarrow 4$. However, the strategy $1\rightarrow 2$,
$3\rightarrow 4$ and $2\rightarrow 4$ is also optimal, since the same ultimate
cycle is reached by any initial state, but it is not $u$-calibrated.

$B=\begin{pmatrix}-\infty&-1&0&-\infty\\\ -\infty&-1&-\infty&-1\\\ -\infty&-\infty&0&0\\\ -\infty&-\infty&-\infty&1\end{pmatrix}$ |  1234-10-10-101
---|---
Figure 2. A one player game (maximizing the average cost), with two optimal
policies, only one of which (going right, in blue) is calibrated.

######  Example 7.6.

An example of calibrated policies arises from the notion of Blackwell
optimality, originally introduced in the one player setting [Bla62]. Let
$0<\alpha<1$ be a discount factor, and consider the value vector $v^{\alpha}$
of the discounted version of the game, so that $v^{\alpha}$ is the unique
solution of the fixed point equation $v^{\alpha}=T(\alpha v^{\alpha})$. It
follows from the result of Kohlberg [Koh80] that, as soon as the mean payoff
of the game is independent of the initial state, $v^{\alpha}$ has a Laurent
series expansion satisfying in particular
$v^{\alpha}=\lambda/(1-\alpha)+u+O(1-\alpha)$, where $\lambda\in\mathbb{R}$ is
the mean payoff, as $\alpha\to 1^{-}$, and we have $T(u)=\lambda+u$. There are
policies $\sigma^{*},\pi^{*}$ such that $T(\alpha
v^{\alpha})=T^{\sigma^{*}}(\alpha v^{\alpha})={}^{\pi^{*}}T(\alpha
v^{\alpha})$ for all values of $\alpha$ close enough to $1$, meaning that
$\sigma^{*},\pi^{*}$ are optimal in all the discounted games with a discount
factor sufficiently close to one (see [AGGCG19, Th. 8] for a proof of this
property in the two player setting). These policies are said to be Blackwell
optimal. They are $u$-calibrated.

##  8\. Ambitropical polyhedra

We now consider ambitropical cones with a polyhedral structure.

######  Definition 8.1.

An ambitropical polyhedron is an ambitropical cone that is a finite union of
alcoved polyhedra. An ambitropical polytope is an ambitropical polyhedron that
is bounded in Hilbert’s seminorm.

Observe that an ambitropical polyhedron is closed. We shall first show that
fixed point sets of finitely generated Shapley operators are ambitropical
polyhedra, and then, we will show that all ambitropical polyhedra arise in
this way and provide a notion of generating family.

###  8.1. Polyhedral structure of the fixed point sets of finitely generated
Shapley operators

Recall that a _polyhedral complex_ $\mathcal{K}$ is a set of polyhedra, called
_cells_ , that satisfies the following conditions: every face of a polyhedron
from $\mathcal{K}$ is also in $\mathcal{K}$; the intersection of any two
polyhedra $\sigma_{1},\sigma_{2}\in\mathcal{K}$ is a face of both $\sigma_{1}$
and $\sigma_{2}$. A polyhedral complex is a _fan_ if every cell is a cone. The
support of a polyhedral complex is the union of its cells. (Here, cone is
understood in the sense of convex analysis, not in the sense of ordered
additive cones.)

Suppose $E$ is the fixed point set of a finitely generated Shapley operator.
So $E=\\{x\mid x=A^{\sharp}\circ Bx\\}$, for some proper pair of matrices
$A,B\in(\mathbb{R}_{\max})^{m\times n}$. We will show that $E$ is the support
of a polyhedral complex, and that the cells of this complex correspond to
calibrated policies of the two players.

inline]to be cleaned

It will be convenient to lift the ambitropical cone, considering

$F:=\\{(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}\mid x=A^{\sharp}y,\;y=Bx\\}$

so that $E=\operatorname{proj}_{x}(F)$, where $\operatorname{proj}_{x}$ is the
projection $(x,y)\mapsto x$ from $\mathbb{R}^{n}\times\mathbb{R}^{m}$ to
$\mathbb{R}^{n}$.

Given any pair of nondeterministic policies
$(\sigma,\pi)\in\mathscr{S}\times\mathscr{P}$ (see §7.2), we denote by
$Z_{\sigma,\pi}$ the set of couples
$(x,y)\in\mathbb{R}^{n}\times\mathbb{R}^{m}$ verifying the following relations

(25a) $\displaystyle x$ $\displaystyle\leqslant A^{\sharp}y,\qquad\qquad
x_{i}\geqslant-A_{ji}+y_{j},\quad\forall i\in[n],\forall j\in\sigma(i)$ (25b)
$\displaystyle y$ $\displaystyle\geqslant Bx\qquad\qquad y_{j}\leqslant
B_{jk}+x_{k},\quad\forall j\in[m],\forall k\in\pi(j)\enspace.$

Let us consider $\sigma^{-1}(j)=\\{i\in[n]\mid j\in\sigma(i)\\}$ and
$\pi^{-1}(i)=\\{j\in[m]\mid i\in\pi(j)\\}$. Observe that
$\cup_{j\in[m]}\sigma^{-1}(j)=[n]$ and $\cup_{i\in[n]}\pi^{-1}(i)=[m]$,
because $\sigma(i)$ and $\pi(j)$ are non-empty, for all $i\in[n]$ and
$j\in[m]$.

######  Proposition 8.1.

We have

(26) $\displaystyle
F=\bigcup_{(\sigma,\pi)\in\mathscr{S}\times\mathscr{P}}Z_{\sigma,\pi}\enspace.$

###### Proof.

The relations (25a) entail that $x=A^{\sharp}y$, and similarly (25b) entail
that $y=Bx$. So, for all $(\sigma,\pi)\in\mathscr{S}\times\mathscr{P}$,
$Z_{\sigma,\pi}\subset F$. Moreover, for all $(x,y)\in F$, taking
$\sigma(i):=\operatornamewithlimits{argmin}_{j\in[m]}(-A_{ji}+y_{j})$, we can
check that (25a) is satisfied by $x=A^{\sharp}y$. Similarly, for all $x$ in
$\mathbb{R}^{n}$, taking
$\pi(j):=\operatornamewithlimits{argmax}_{i\in[n]}(B_{ji}+x_{i})$, we can
check that (25b) is satisfied by $y=Bx$. So, $(x,y)\in Z_{\sigma,\pi}$. ∎

######  Proposition 8.2.

The image $X_{\sigma,\pi}:=\operatorname{proj}_{x}(Z_{\sigma,\pi})$ is
characterized by the relations

(27a) $\displaystyle[(A\vee B)x]_{j}$ $\displaystyle\leqslant
B_{jk}+x_{k},\qquad\forall j\in[m],\forall k\in\pi(j)$ (27b)
$\displaystyle[(A\vee B)x]_{j}$ $\displaystyle\leqslant
A_{ji}+x_{i},\qquad\forall j\in[m],\forall i\in\sigma^{-1}(j)\enspace.$

Moreover, both $Z_{\sigma\pi}$ and $X_{\sigma,\pi}$ are alcoved polyhedra.

###### Proof.

Let $(x,y)\in Z_{\sigma,\pi}$. Since $x\leqslant A^{\\#}y$ is equivalent to
$Ax\leqslant y$, we deduce that $(A\vee B)x\leqslant y$. Moreover, (25) entail
that

(28) $\displaystyle A_{ji}+x_{i}$ $\displaystyle\geqslant y_{j},\quad\forall
j\in[m],\forall i\in\sigma^{-1}(i)\enspace.$

It follows that $x$ satisfies (27). Conversely, suppose that (27) holds, and
let $y:=Bx$. The inequalities in (27a) entail that $[Bx]_{j}\leqslant[(A\vee
B)x]_{j}\leqslant B_{jk}+x_{k}\leqslant[Bx]_{j}$ for all $j\in[m]$ and
$k\in\pi(j)$, so that $B_{jk}+x_{k}=y_{j}=[(A\vee B)x]_{j}$. Then, it follows
from these inequalities that $Ax\leqslant y$, and so $x\leqslant A^{\sharp}y$.
Then, we deduce from (27b) that $y_{j}\leqslant A_{ji}+x_{i}$ for all
$j\in[n]$ and $i\in\sigma^{-1}(j)$, which can be rewritten as
$-A_{ji}+y_{j}\leqslant x_{i}$ for all $i\in[n]$ and $j\in\sigma(i)$, and so
$A^{\sharp}y\leqslant x$, which shows that $(x,y)\in Z_{\sigma,\pi}$.

It is immediate from the form of the constraints in (25) and (27) that
$Z_{\sigma,\pi}$ and $X_{\sigma,\pi}$ are alcoved polyhedra. ∎

We define the type of a point $x\in\mathbb{R}^{n}$ to be the pair of partially
defined maps $\tau:=(\sigma,\pi)$ where for all $j\in[m]$, $\pi(j)$ denotes
the set of $k\in[n]$ such that the relation (27a) holds, and $\sigma^{-1}(j)$
denotes the set of $i\in[n]$ such that (27b) holds. We say that a type is
proper if both $\sigma$ and $\pi$ are policies (this requires the maps
$\sigma$ and $\pi$ to be totally defined). We denote by $\mathcal{T}$ the set
of proper types associated to points $x\in\mathbb{R}^{n}$.

######  Theorem 8.3.

Suppose $E$ is the fixed point set of the finitely generated Shapley operator.
Then, the collection of alcoved polyhedra $(X_{\tau})_{\tau\in\mathscr{T}}$
constitutes a polyhedral complex whose support is $E$. Moreover, the cell
$X_{\tau}$ consists precisely of those fixed points $u$ such that the pair
$\tau$ of nondeterministic policies in the mean payoff game associated to $T$
is $u$-calibrated.

###### Proof.

It follows from (26), $E=\operatorname{proj}_{x}(F)$ and 8.2 that
$E=\bigcup_{\tau}X_{\tau}$. We have to show that the collection of polyhedra
$\\{X_{\tau}\\}_{\tau\in\mathscr{T}}$ is a polyhedral complex.

Consider $\tau=(\sigma,\pi)\in\mathcal{T}$ and
$\tau^{\prime}=(\sigma^{\prime},\pi^{\prime})\in\mathcal{T}$. Let
$\pi^{\prime\prime}\in\mathscr{P}$ be such that
$\pi^{\prime\prime}(j)=\pi(j)\cup\pi^{\prime}(j)$ for all $j\in[m]$, and let
$\sigma^{\prime\prime}\in\mathscr{S}$ be such that
$\sigma^{\prime\prime}(i)=\sigma(i)\cup\sigma^{\prime}(i)$ for all $i\in[n]$.
It is immediate from (27) that $X_{\tau}\cap
X_{\tau^{\prime}}=X_{\tau^{\prime\prime}}$. Let now $x$ be a point in the
relative interior of $X_{\tau^{\prime\prime}}$. For $j\in[m]$, let
$\pi^{\prime\prime\prime}(j)$ be defined as the set of $k$ such that $[(A\vee
B)x)]_{j}\leqslant B_{jk}+x_{k}$. For $i\in[n]$, let
$\sigma^{\prime\prime\prime}(i)$ be defined as the set of $j$ such that
$[(A\vee B)x]_{j}\leqslant A_{ji}+x_{i}$, so that $\tau^{\prime\prime\prime}$
is the type of $x$. Observe that
$\sigma^{\prime\prime\prime}(i)\supset\sigma^{\prime\prime}(i)\supset\sigma^{\prime}(i)\neq\emptyset$,
which entails that $\sigma^{\prime\prime\prime}$ is proper. Similarly,
$\pi^{\prime\prime\prime}$ is proper. Moreover, the inclusion $X_{\tau}\cap
X_{\tau^{\prime}}\supset X_{\tau^{\prime\prime\prime}}$ is trivial. The
reverse inclusion follows from the observation that
$\operatorname{relint}(X_{\tau}\cap X_{\tau^{\prime}})\subset
X_{\tau^{\prime\prime\prime}}$. This follows from the fact that
$\tau^{\prime\prime\prime}$ is the type of any point
$x\in\operatorname{relint}(X_{\tau}\cap X_{\tau^{\prime}})$.

Finally, observing that a face $F^{\prime}$ of $X_{\tau}$ is obtained by
saturating some of the inequalities (27), and taking for $\tau^{\prime}$ the
type of an arbitrary point in the relative interior of this face, it is
immediate that $F^{\prime}=X_{\tau^{\prime}}$.

Moreover, considering the proof of 7.4, we see that a pair of nondeterministic
policies $\tau=(\sigma,\pi)\in\mathcal{T}$ is $u$-calibrated if and only if,
for all deterministic policies $\sigma_{\operatorname{d}}$,
$\pi_{\operatorname{d}}$ induced by $\sigma$ and $\pi$, we have
$u=T(u)=T^{\sigma_{\operatorname{d}}}(u)={}^{\pi_{\operatorname{d}}}T(u)$, and
this means precisely that $u\in X_{\tau}$. ∎

######  Remark 8.4.

The polyhedral complex of 8.3 generalizes the complex introduced by Develin
and Sturmfels to represent tropical polyhedra [DS04]. The latter complex is
recovered by considering the special case in which $A=B$, so that
$T=B^{\sharp}\circ B$. Then, the range of $T$ is precisely the dual tropical
cone generated by the opposite of the columns of $B$. By 8.2, the cell
$X^{\sigma,\pi}$ is given by $\\{x\mid(Bx)_{j}\leqslant
B_{jk}+x_{k},\;k\in\pi(j),\;(Bx)_{j}\leqslant
B_{ji}+x_{i},\;i\in\sigma^{-1}(j)\\}$, and then, we see that this cell
coincides with $X^{\bar{\pi}^{-1},\bar{\pi}}$, in which $\bar{\pi}$ is the
nondeterministic policy whose graphs is the union of those of $\pi$ and
$\sigma^{-1}$. The cells $X^{\bar{\pi}^{-1},\bar{\pi}}$ are precisely the ones
that constitute the polyhedral complex of [DS04] and the policy $\bar{\pi}$ is
equivalent to the combinatorial type defined there. inline]SG: to be checked.
Add that if the cell is of non-empty interior, then the type consists of
deterministic policies. Link with the develin-sturmfels complex when
$T=VV^{\sharp}$.

inline]SG: add discussion of [sturmfels2012combinatorial, tran2014polytropes]

###  8.2. Polyhedral complexes associated with ambitropical polyhedra

inline]SG: to be adapted to the move Whereas ambitropical cones arise as fixed
point sets of Shapley operators, we shall see that ambitropical polyhedra
arise as fixed point sets of finitely generated Shapley operators.

In the special case of alcoved polyhedra, the following lemma shows that these
Shapley operators are simple, and its proof shows that they are associated
with one-player games.

######  Lemma 8.5.

Let $E\subset\mathbb{R}^{n}$ be an alcoved polyhedron,
${Q}^{-}_{E}(x)=\operatorname{sup}^{E}\\{y\in E;y\leqslant x\\}$ and
${Q}^{+}_{E}(x)=\operatorname{inf}^{E}\\{y\in E;y\geqslant x\\}$. Then
${Q}^{-}_{E}$ and ${Q}^{+}_{E}$ are finitely generated Shapley operators.

###### Proof.

Observe first that $\operatorname{sup}^{E}$ coincides with the $\sup$ law of
$\mathbb{R}^{n}$ and that similarly $\operatorname{inf}^{E}$ coincides with
the $\inf$ law of $\mathbb{R}^{n}$, because $E$ is an alcoved polyhedron
(stable by these sup and inf laws). We can find a matrix
$M\in(\mathbb{R}_{\max})^{n\times n}$ such that $E=\mathscr{A}(M)$, i.e.,
$E=\\{x\in\mathbb{R}^{n}\mid x\geqslant Mx\\}$. We claim that
${Q}^{+}_{E}(x)=M^{*}x$. Indeed, by 2.3, $M^{*}x\in\mathscr{A}(M)$. Moreover,
since $M^{*}\geqslant I$, $M^{*}x\geqslant x$, and so ${Q}^{+}_{E}(x)\leqslant
M^{*}x$. Now, if $z\geqslant x$ for some $z\in\mathscr{A}(M)$, we have
$z=M^{*}z\geqslant M^{*}x$, showing that $M^{*}x\leqslant{Q}^{+}_{E}(x)$. The
operator $x\mapsto M^{*}x$ is finitely generated. A dual argument shows that
${Q}^{-}_{E}$ which is also finitely generated. ∎

We now compute a finitely generated Shapley retraction on an ambitropical
polyhedron represented as a union of alcoved polyhedra.

######  Lemma 8.6.

Suppose that $E$ is the union of a finite family of alcoved polyhedra
$(E_{k})_{k\in K}$. Then,

$P^{\max}_{E}=\sup_{l\in K}{Q}^{-}_{E_{l}},\qquad P^{\min}_{E}=\inf_{l\in
K}{Q}^{+}_{E_{l}}\enspace.$

###### Proof.

By definition of ${Q}^{-}_{E_{l}}$, for all $x\in\mathbb{R}^{n}$,
$E_{l}\ni{Q}^{-}_{E_{l}}(x)\leqslant x$. Since $E_{l}\subset E^{\max}$ and
$E^{\max}$ is stable by supremum, we deduce that $E^{\max}\ni\sup_{l\in
K}{Q}^{-}_{E_{l}}(x)\leqslant x$, and so, $P^{\max}_{E}(x)\geqslant\sup_{l\in
K}{Q}^{-}_{E_{l}}(x)$. Moreover, any element $z$ of $E^{\max}$ can be written
as $z=\sup_{l\in K}z^{l}$ for some $z^{l}\in E_{l}$. If $z\leqslant x$, it
follows that $z^{l}\leqslant{Q}^{-}_{E_{l}}(x)$, from which we deduce that
$z\leqslant\sup_{l\in K}{Q}^{-}_{E_{l}}(x)$. Since this holds for all
$E^{\max}\ni z\leqslant x$, it follows that $P^{\max}(x)\leqslant\sup_{l\in
K}{Q}^{-}_{E_{l}}(x)$. The proof of the characterization of $P^{\min}_{E}$ is
dual. ∎

######  Corollary 8.7.

Let $E$ be the union of a finite family of alcoved polyhedra $(E_{k})_{k\in
K}$. Then

(29) $\displaystyle{Q}^{-}_{E}(x)$ $\displaystyle=\inf_{k\in
K}{Q}^{+}_{E_{k}}(\sup_{l\in
K}{Q}^{-}_{E_{l}}(x)),\qquad{Q}^{+}_{E}(x)=\sup_{k\in
K}{Q}^{-}_{E_{k}}(\inf_{l\in K}{Q}^{+}_{E_{l}}(x))\enspace.$

###### Proof.

This follows from 4.7 and 8.6. ∎

######  Theorem 8.8.

Let $E$ be a subset of $\mathbb{R}^{n}$, then the following are equivalent:

  1. (1)

$E$ is an ambitropical polyhedron

  2. (2)

There exists a finitely generated Shapley operator $P$ such that $P=P^{2}$ and
$E=\\{x\in\mathbb{R}^{n}|x=P(x)\\}$.

  3. (3)

$E$ is the fixed point set of a finitely generated Shapley operator;

  4. (4)

$E$ is a closed ambitropical cone and $\bar{E}^{\max}$ and $\bar{E}^{\min}$
are finitely generated as modules over $\mathbb{R}_{\max}$ and
$\mathbb{R}_{\min}$, respectively.

###### Proof.

(1)$\Rightarrow$(2). The set $E$ is the range of the idempotent Shapley
operator $\bar{Q}^{-}_{E}$, and it follows from 8.7 and 8.5 that this Shapley
operator is finitely generated.

$\eqref{ie-3}\Rightarrow\eqref{ie-1}$ is obvious.