TITLE: Show that $S$ is a convex set, if it is locally convex everywhere
QUESTION [1 upvotes]: Part 1
$S\subseteq\mathbb R^2$ is locally convex, in the sense that, for any point $x\in\mathbb R^2,$ there exists an open ball $B(x,\epsilon)$, such that $S\cap B$ is convex. Show that $S$ is convex.
This part seems easy. Here I would present a sketch of the proof. First take two balls $B_1$, $B_2$, such that their intersection with $S$ is convex and $(B_1\cap S)\cap (B_2\cap S)\neq\emptyset$. It is not hard to see that $(B_1\cap S)\cap (B_2\cap S)$ is convex and $(B_1\cap S)\cup (B_2\cap S)$ is convex. Since $\mathbb R^2$ must be covered by countable many balls, we can safely use induction to obtain our result.
Part 2
$S\subseteq\mathbb R^2$ is a set satisfying that, for any point $x\in\mathbb R^2,$ there exists an open ball $B(x,\epsilon)$, such that: either 1) $S\cap B$ is convex, or 2) $S^c\cap B$ is convex. Is it possible to show that either $S$ is convex, or $S^c$ is convex?
However the part 2 seems usually hard and I don't know what to do. Maybe we could start with two intersecting epsilon ball $B_1,B_2$. Then they must both satisfy the condition (1), or they must both satisfy the condition (2)?

REPLY [1 votes]: Answer for part 2): Let $S=\mathbb R^{2} \setminus \{x,y\}$ where $x \neq y$. Then neither $S$ nor $S^{c}$ is convex.  If $z \notin \{x,y\}$ it is obvious that the intersection of some ball around $z$ with $S$ is convex. Now let $z=x$. If $B$ is ball around $x$ not containing $y$ then $B \cap S^{c}=\{x\}$ which is convex. Similarly $y$ contains a ball whose intersection with $S^{c}$ is convex.


TITLE: Find $(x + 1)^{−3}$ in $\mathbb{Z}_2[x]/(x^5 + x^4 + 1)$
QUESTION [1 upvotes]: In a previous question, I established that $x^5 + x^4 + 1$ is irreducible in $\mathbb{Z}_2[x]/(x^5 + x^4 + 1)$, so it will not be divisible by $x+1$. Hence $x^5+x^4+1$ will be coprime to $(x+1)^3 = x^3+x^2+x+1$
So far I have used the Euclidean algorithm to get:
$x^5+x^4+1 = (x^3+x^2+x+1)(x^2+1) + x$
$x^3+x^2+x+1 = (x^2+1)(x+1) + 0$
However, I know I have done something wrong - because the Euclidean algorithm should show that the gcd of $x^5+x^4+1$ and $x^3+x^2+x+1$ is $1$, not $(x^2+1)$.

REPLY [0 votes]: Using the algorithm detailed in this answer with polynomials (and writing top to bottom instead of left to right),we get
$$
\begin{array}{c|c|c|c}
x^5+x^4+1&0&1&\\
x^3+x^2+x+1&1&0&\\
x&x^2+1&1&x^2+1\\
1&\color{#C00}{x^4+x^3+x}&x^2+x+1&x^2+x+1\\
0&x^5+x^4+1&x^3+x^2+x+1&x
\end{array}
$$
which says that in $\mathbb{Z}_2$,
$$
(x^3+x^2+x+1)^{-1}=x^4+x^3+x\pmod{x^5+x^4+1}
$$


TITLE: Cancelling special & general relativistic effects
QUESTION [10 upvotes]: We know that for a GPS we need to make a correction for both general and special relativity: general relativity predicts that clocks go slower in a higher gravitational field (the clock aboard a GPS satellite moves faster than a clock down on Earth), while special Relativity predicts that a moving clock is slower than the stationary one (slow the clock compared to the one down on Earth).
My question is this: is it possible, in theory, to set up an orbit so that these two effects cancel each other out, allowing a clock on board a GPS satellite to tick as if it were on Earth? Is there a distance at which the special and general effects cancel?
Sorry if this is a stupid question - I'm still not entirely confident with the theory of general relativity.

REPLY [11 votes]: Yes, for a circular orbit at about $1.50$ Earth radii, the gravitational and special-relativistic time dilations cancel. GPS is modeled with the static weak-field metric (in units of $c = 1$):
$$-d\tau^2 = -(1+2\Phi)dt^2 + (1-2\Phi)\underbrace{(dx^2+dy^2+dz^2)}_{dS^2},$$
so we can approximate
$$d\tau = dt\sqrt{1+2\Phi-(1-2\Phi)\frac{dS^2}{dt^2}}\approx\left[1+\Phi-\frac{v^2}{2}\right]dt,$$
with corrections due to gravitational time dilation and special-relativistic time dilation additively to this order, since the latter gives a factor of $1/\gamma = 1 - \frac{v^2}{2} + \mathscr{O}(v^4)$, while stationary gravitational time dilation would have a factor of $\sqrt{1+2\Phi} = 1 + \Phi + \mathscr{O}(\Phi^2)$.
To the above order of approximation, every clock on the geoid ticks at the same rate because the geoid is an equipotential surface of the sum of the gravitational and centrifugal potentials (this is sometimes called gravity potential). This common factor happens to be $1 - \alpha$, where $\alpha \approx 6.9692\times10^{-10}$.
Since the metric is static, $\partial_t$ is a Killing field producing conservation of orbital specific energy $\epsilon = (1+2\Phi)\frac{dt}{d\tau}$. If we want the satellite to have the same time dilation as the clock on the geoid, then by substitution, $\Phi$ must be a constant, and consequently so must be $v$. In other words, it is not possible to have an orbit that plays off changes in gravitational potential against changes in velocity so as to keep the overall time dilation the same.
Now, if we approximate the Earth as spherically symmetric with gravitational potential $\Phi = -\frac{\mu}{r}$, then it is clear that only circular orbits need be considered, and the same tick rate condition $-\Phi + \frac{v^2}{2} = \alpha$ gives $\alpha = \frac{3}{2}\frac{\mu}{r}$, or $1.50$ Earth radii.

Actually, the gravitational potential in the GPS model is taken to be the monopole and quadrupole terms:
$$\Phi = -\frac{\mu}{r}\left[1-J_2\left(\frac{a_1}{r}\right)^2P_2(\cos\theta)\right],$$
where $\mu = GM_\text{E} = 3.986004418(9)\times 10^{14}\,\text{m}^3/\text{s}^2$ is the standard gravitational parameter, $J_2 = 1.0826300\times10^{-3}$ is the quadrupole moment coefficient, $a_1 = 6.3781370\times10^6\,\text{m}$ is the equatorial radius, $\theta$ is the usual polar angle, and $P_2(x) = \frac{1}{2}(3x^2-1)$ is a Legendre polynomial.
This situation is a bit harder, but you should still be able to get an orbit that gives close agreement in the equatorial plane.


TITLE: Egorychev method how do you derive this geometric sum
QUESTION [1 upvotes]: Example 2:
https://en.wikipedia.org/wiki/Egorychev_method#Example_II
How do you derive the closed-form result from the finite sum?
I tried it myself and the answer is way more complicated https://www.wolframalpha.com/input/?i=sum_%28k%3D1%29%5En++k*+%28z%2F%281-z%29%29%5Ek+
The leading 'k' value in the summation cannot just vanish like it does below? How does the k go away like that?
:
\begin{align}
& \frac{1}{2\pi i}
\int_{|z|=\varepsilon}
\frac{1}{z^{n+1}}
\frac{1}{(1-z)^{n+1}}
\sum_{k\ge 1} k \frac{z^k}{(1-z)^k}
\; dz \\[6pt]
= {} & \frac{1}{2\pi i}
\int_{|z|=\varepsilon}
\frac{1}{z^{n+1}}
\frac{1}{(1-z)^{n+1}}
\frac{z/(1-z)}{(1-z/(1-z))^2}
\; dz \\[6pt]
= {} & \frac{1}{2\pi i}
\int_{|z|=\varepsilon}
\frac{1}{z^{n}}
\frac{1}{(1-z)^n}
\frac{1}{(1-2z)^2}
\; dz.
\end{align}

REPLY [1 votes]: The $k$ goes away using the identity
$$
\sum _{n=1}^\infty nx^n = \frac x {(1-x)^2},
$$
which is valid when $|x|<1$.


text:
\begin{document}
\begin{abstract}
We introduce an algorithm which solves mean payoff games in polynomial time on average, assuming the distribution of the games satisfies a flip invariance property on the set of actions associated with every state. The algorithm is a tropical analogue of the shadow-vertex simplex algorithm, which solves mean payoff games via linear feasibility problems over the tropical semiring $(\R \cup \{-\infty\}, \max, +)$. The key ingredient in our approach is that the shadow-vertex pivoting rule can be transferred to tropical polyhedra, and that its computation reduces to optimal assignment problems through Pl\"ucker relations.
\end{abstract}

\maketitle

\section{Introduction}

A \emph{mean payoff game} involves two opponents, ``Max'' and ''Min'', who alternatively move a pawn over the nodes of a weighted bipartite digraph. The latter consists of two classes of nodes, represented by squares and circles, and respectively indexed by $i \in [m]$ and $j \in [n]$ (we use the notation $[k] := \{1, \dots, k\}$). The weight of the arc $(i,j)$ (resp.\ $(j,i$)) is a real number denoted by $A_{ij}$ (resp.\ $B_{ij}$). We set $A_{ij} := -\infty$ (resp.\ $B_{ij} := -\infty$) when there is no such arc. An example of game
is given in Figure~\ref{fig:game}.

When the pawn is placed over a square node $i$, Player Max selects an outgoing arc $(i,j)$, and then moves the pawn to circle node $j$ and receives the payment $A_{ij}$ from Player Min. Conversely, when the pawn is located on a circle node $j$, Player Min chooses an arc $(j,i')$, moves the pawn to square node $i'$, and Player Max pays her the amount $B_{i'j}$. We assume that $A$ (resp.\ $B$) does not have any identically $-\infty$ row (resp.\ column), so that both players have at least one possible action at every node. The game starts from a circle node $j_0 = j$, and then the two players make infinitely many moves, visiting a sequence $j_0, i_1, j_1, i_2, \dots$ of nodes. The objective of Player Max is to maximize his mean payoff, defined as the liminf of the following ratio when $p \rightarrow + \infty$:
\begin{equation}
 (-B_{i_1 j_0} + A_{i_1 j_1} - B_{i_2 j_1} + A_{i_2 j_2} + \dots - B_{i_p j_{p-1}} + A_{i_p j_p})/p \ . \label{eq:ratio}
\end{equation}
Symmetrically, Player Min aims at minimizing
her
mean loss, defined as the limsup of~\eqref{eq:ratio} when $p \rightarrow + \infty$.
Mean payoff games can be defined more generally
over arbitrary (not necessarily bipartite)
digraphs.
This situation can be reduced to the present one~\cite{ZwickPaterson1996}.

\begin{figure}[t]
\vskip-15ex
\begin{center}
\begin{tikzpicture}[scale=0.9,>=stealth',row/.style={draw,rectangle,minimum size=0.5cm},col/.style={draw,circle,minimum size=0.5cm}]
\node[row] (i1) at (0,0) {$1$};
\node[row] (i2) at (3,0) {$2$};
\node[row] (i3) at (6,0) {$3$};

\node[col] (j1) at (0,2.5) {$1$};
\node[col] (j2) at (3,2.5) {$2$};
\node[col] (j3) at (6,2.5) {$3$};

\draw[->] (i1) to[out=120,in=-120] node[above left=0ex and -0.5ex,font=\small] {$5$} (j1);
\draw[->] (i1) -- node[above right=2ex and -0.5ex,font=\small] {$-2$} (j2);

\draw[->] (j1) to[out=-60,in=60] node[below left=0ex and -0.3ex,font=\small] {$-1$} (i1);
\draw[->] (j1) -- node[below right=1.5ex and 0.5ex,font=\small] {$3$} (i2);

\draw[->] (i2) to[out=20,in=-120] node[above right=2ex and 3.5ex,font=\small] {$2$} (j3);
\draw[->] (j2) to[out=-90,in=90] node[below right=0ex and -0.5ex,font=\small] {$10$} (i2);
\draw[->] (j2) to[out=-20,in=120] node[above=0.5ex,font=\small] {$1$} (i3);

\draw[->] (j3) .. controls (-2.5,5) and (-2,1) .. node[left,font=\small] {$3$} (i1);
\draw[->] (i3) to[out=160,in=-60]  node[above left=1ex and -0.5ex,font=\small] {$0$} (j2);
\end{tikzpicture}
\end{center}
\caption{An example of mean payoff game. Circle node $1$ is a winning initial state for Player Max, while circle node $2$ is losing.} \label{fig:game}
\end{figure}

Mean payoff games were
studied by Ehrenfeucht and Mycielski~in \cite{EhrenfeuchtMycielski1979},
where they
proved
that these games have a value and positional optimal strategies. In more detail, for every initial state $j \in [n]$, there exists a real $\chi_j$ and  positional strategies $\sigma : [m] \rightarrow [n]$ and $\tau : [n] \rightarrow [m]$, such that:
\begin{inparaenum}[(i)]
\item Player Max is certain to win a mean payoff greater than or equal to $\chi_j$ with the strategy $\sigma$ (\ie~by choosing the arc $(i,\sigma(i))$ every time the pawn is on a square node $i \in [m]$),
\item Player Min is sure that
her
mean loss is less than or equal to $\chi_j$ with the strategy $\tau$.
\end{inparaenum}

The decision problem associated with mean payoff games consists in determining whether the initial state $j$ is \emph{winning} for Player Max, \ie~$\chi_j \geq 0$.
The question
of the existence of
a polynomial time algorithm solving this problem
was
first raised by Gurvich, Karzanov and Khachiyan in~\cite{GurvichCMMP1988}.
This problem was shown
to be in $\text{NP} \cap \text{co-NP}$ by Zwick and Paterson in~\cite{ZwickPaterson1996}.
While mean payoff games (and the related class of parity games) received an important attention over the past years~\cite{GurvichCMMP1988,ZwickPaterson1996,Jurdzinski1998,GaubertGunawardena98,VogeJurdzinski2000,BjorklundVorobyovDAM2007,JurdzinskiPatersonZwick2008,Friedmann2009,Briem2011}, all the algorithms developed so far are superpolynomial, and the question raised by Gurvich~\etal{} is still open.

The present work exploits the equivalence between mean payoff games and linear feasibility problems in tropical algebra. Indeed, it was shown by Akian, Gaubert and Guterman in~\cite{AkianGaubertGuterman2012} that the initial state $n$ is winning for Player Max in the game with payments matrices $A,B$ if, and only if, there exists a solution $x \in (\R \cup \{-\infty\})^{n-1}$ to the following system of inequalities:
\begin{multline}
\forall i \in [m], \qquad \max(A_{i1} + x_1, \dots, A_{i(n-1)} + x_{n-1}, A_{in}) \\
\geq \max(B_{i1} + x_1, \dots, B_{i(n-1)} + x_{n-1}, B_{in}) \ . \label{eq:trop_ineq}
\end{multline}
The constraints of the form~\eqref{eq:trop_ineq} correspond to affine inequalities over the tropical (max-plus) semiring, \ie~the set $\trop := \R \cup \{-\infty\}$ endowed with the operations $x \tplus y := \max(x,y)$ as addition, and $x \tdot y := x+y$ as multiplication. The conjunction of finitely many such inequalities defines a \emph{tropical polyhedron}. Solving a mean payoff game consequently amounts to determine whether a tropical polyhedron is empty, which can be thought of as the tropical analogue of the feasibility problem in linear programming.
This is among the motivations leading to the development of
a tropical simplex method
in a previous work of the authors and Joswig~\cite{AllamigeonBenchimolGaubertJoswig2013}. Then, complexity results known for the classical simplex algorithm can be potentially transferred to the tropical setting.
However, the main obstacle is to ``tropicalize'' the pivoting rule involved, \ie~to define a tropical pivoting rule which is both compatible with the classical one, and computable, if possible, with a reasonable time complexity. So far~\cite{AllamigeonBenchimolGaubertJoswig2014}, the only pivoting rules which have been tropicalized are \emph{combinatorial}, \ie~they are defined in terms of the neighborhood of the current basic point in the vertex/edge graph of the polyhedron.

\subsection*{Contributions.} We prove that the shadow-vertex simplex algorithm can be tropicalized. Following the average-case analysis of the shadow-vertex algorithm of Adler, Karp and Shamir in~\cite{AdlerKarpShamir87}, we deduce that the tropical algorithm solves mean payoff games in polynomial time on average (Section~\ref{sec:pcbc}). The complexity bound holds when the distribution of the games satisfies a \emph{flip invariance} property. The latter requires that the distribution of the games is left invariant by every transformation consisting, for an arbitrary node of the game, in flipping the orientation of all the arcs incident to this node.  Equivalently, the probability distribution on the set of payment matrices $A,B$ is invariant by every transformation consisting in swapping the $i$th row of $A$ with the $i$th row of $B$, or the $j$th column of $A$ with the $j$th column of $B$.
Figure~\ref{fig:flip} provides the illustration of a discrete distribution of games satisfying the property.

The key difficulty in our approach is to show that the computation of the tropical shadow-vertex pivoting rule can be done in polynomial time (Section~\ref{sec:shadow_vertex}). To this end, we exploit the fact that the shadow-vertex rule is semi-algebraic, \ie~it is defined in terms of the signs of finitely many polynomials. Under some genericity conditions, we deduce that the tropical rule reduces to classical linear programs over some Newton polytopes, which are actually (Minkowski sums of) bipartite perfect matching polytopes.

\subsection*{Related work.} We are not aware of other works with such average-case complexity results on mean payoff games. In~\cite{RothSODA10}, Roth~\etal{} made a probabilistic analysis of $n \times n$ bi-matrix games with weights chosen independently uniformly in $[0,1]$. Under this assumption, they showed that with high probability (greater than $1 - f(n)$, with $f(n) = o(1/n^c)$ for all constant $c$), such games admit a pure stationary strategy equilibrium parametrized by only $4$ actions. The latter can be consequently found in polynomial time. While this result indicates that complex instances of games are rare, it does not seem to us that it can be used to deduce an average-case complexity bound.

\begin{figure}[t]
\begin{center}
\begin{tikzpicture}[scale=0.9,>=stealth',row/.style={draw,rectangle,minimum size=0.5cm},col/.style={draw,circle,minimum size=0.5cm}]

\begin{scope}
\node[row] (i1) at (0,0) {$1$};

\node[col] (j1) at (2.5,1.15) {$1$};
\node[col] (j2) at (2.5,-1.15) {$2$};

\draw[->] (i1) to[out=40,in=-166] node[above,font=\scriptsize] {$7$} (j1);
\draw[->] (j1) to[out=-140,in=14] node[below right=-0.75ex and 0.5ex,font=\scriptsize] {$5$} (i1);
\draw[->] (i1) to[out=-14,in=140] node[above right=-0.75ex and 0.5ex,font=\scriptsize] {$2$} (j2);
\draw[->] (j2) to[out=166,in=-40] node[below,font=\scriptsize] {$3$} (i1);
\node at (1.25,-2.35)
{
$
\begin{aligned}
A & = (7 \; \, 2)\\[-0.5ex]
B & = (5 \; \, 3)
\end{aligned}
$
};
\end{scope}

\begin{scope}[xshift=4.5cm]
\node[row, very thick] (i1) at (0,0) {$1$};

\node[col] (j1) at (2.5,1.15) {$1$};
\node[col] (j2) at (2.5,-1.15) {$2$};

\draw[->] (i1) to[out=40,in=-166] node[above,font=\scriptsize] {$5$} (j1);
\draw[->] (j1) to[out=-140,in=14] node[below right=-0.75ex and 0.5ex,font=\scriptsize] {$7$} (i1);
\draw[->] (i1) to[out=-14,in=140] node[above right=-0.75ex and 0.5ex,font=\scriptsize] {$3$} (j2);
\draw[->] (j2) to[out=166,in=-40] node[below,font=\scriptsize] {$2$} (i1);
\node at (1.25,-2.35)
{
$
\begin{aligned}
A & = (5 \; \, 3)\\[-0.5ex]
B & = (7 \; \, 2)
\end{aligned}
$
};
\end{scope}

\begin{scope}[xshift=9cm]
\node[row] (i1) at (0,0) {$1$};

\node[col, very thick] (j1) at (2.5,1.15) {$1$};
\node[col] (j2) at (2.5,-1.15) {$2$};

\draw[->] (i1) to[out=40,in=-166] node[above,font=\scriptsize] {$5$} (j1);
\draw[->] (j1) to[out=-140,in=14] node[below right=-0.75ex and 0.5ex,font=\scriptsize] {$7$} (i1);
\draw[->] (i1) to[out=-14,in=140] node[above right=-0.75ex and 0.5ex,font=\scriptsize] {$2$} (j2);
\draw[->] (j2) to[out=166,in=-40] node[below,font=\scriptsize] {$3$} (i1);
\node at (1.25,-2.35)
{
$
\begin{aligned}
A & = (5 \; \, 2)\\[-0.5ex]
B & = (7 \; \, 3)
\end{aligned}
$
};
\end{scope}

\begin{scope}[xshift=13.5cm]
\node[row, very thick] (i1) at (0,0) {$1$};

\node[col, very thick] (j1) at (2.5,1.15) {$1$};
\node[col] (j2) at (2.5,-1.15) {$2$};

\draw[->] (i1) to[out=40,in=-166] node[above,font=\scriptsize] {$7$} (j1);
\draw[->] (j1) to[out=-140,in=14] node[below right=-0.75ex and 0.5ex,font=\scriptsize] {$5$} (i1);
\draw[->] (i1) to[out=-14,in=140] node[above right=-0.75ex and 0.5ex,font=\scriptsize] {$3$} (j2);
\draw[->] (j2) to[out=166,in=-40] node[below,font=\scriptsize] {$2$} (i1);
\node at (1.25,-2.35)
{
$
\begin{aligned}
A & = (7 \; \, 3)\\[-0.5ex]
B & = (5 \; \, 2)
\end{aligned}
$
};
\end{scope}
\end{tikzpicture}
\end{center}
\caption{A distribution of game satisfying the flip invariance property (with $m = 1$ and $n = 2$), together with the payment matrices. The four configurations are supposed to be equiprobable. The nodes on which the flip operations have been performed are depicted in bold.}\label{fig:flip}
\end{figure}

\section{Preliminaries}\label{sec:preliminaries}

\subsection{Tropical arithmetic and generalized Puiseux series}

As previously discussed, the triple $(\trop, \tplus, \tdot)$ forms a semiring, and
the elements $\zero := -\infty$ and $\unit := 0$ correspond to the zero and unit respectively.
The tropical operations can be extended to matrices with entries in $\trop$ in a usual way, by defining $A \tplus B := (A_{ij} \tplus B_{ij})_{ij}$ and $A \tdot B := (\tsum_k A_{ik} \tdot B_{kj})_{ij}$. We also introduce the exponentiation $x^{\tdot k}$ for any $x \in \trop$ and $k \in \mathbb{N}$, which is defined as the product $x \tdot x \tdot \dots \tdot x$ of $k$ occurrences of $x$ (if $k = 0$, it is set to $\unit$).

Even if the addition $\tplus$ does not have an inverse, it is convenient to consider tropical numbers with a negative sign. The sign is encoded in a formal way, by introducing two copies $\trop_+$ and $\trop_-$ of $\trop \setminus \{\zero\}$, respectively consisting of the positive and negative elements. The set $\strop$ of \emph{tropical signed numbers} is defined as $\trop_+ \cup \trop_- \cup \{\zero\}$. The elements of $\trop_+$ are simply denoted by elements $a \in \trop \setminus \{\zero\}$, while the elements of $\trop_-$ are denoted by $\tminus a$.
The \emph{modulus} of $x \in \strop$ is defined as $|x| := a$ if $x = a$ or $x = \tminus a$, and $|\zero| := \zero$. Similarly, the \emph{sign} of $x \in \strop$ is defined by $\sign(x) = +1$ if $x \in \trop_+$, $\sign(x) = -1$ if $x \in \trop_-$, and $\sign(\zero) = 0$.

While the tropical addition of signed elements may not be well defined, we can extend the multiplication over $x, y \in \strop$, by defining $x \tdot y$ as the unique element of $\strop$ with modulus $|x| \tdot |y|$ and sign $(\sign(x) \times \sign(y))$. For instance, $(\tminus 3) \tdot 4 = \tminus 7$, and $(\tminus 2) \tdot (\tminus 4) = 6$.
The exponentiation $x^{\tdot k}$ is generalized to the case  $x \in \strop$ as well.
For any $x \in \strop$, we use the notation $\tminus x$ as a shorthand for the operation $(\tminus \unit) \tdot x$. The \emph{positive} and \emph{negative parts} $x^+$ and $x^-$ of an element $x \in \strop$ are defined by $(x^+, x^-) := (x,\zero)$ if $x \in \trop_+$, $(\zero,\tminus x)$ if $x \in \trop_-$, and $(\zero, \zero)$ if $x = \zero$. We extend this notation to vectors and matrices entrywise.

A matrix $M \in \strop^{n \times n}$ is said to be \emph{generic} if the following maximum
\begin{equation}
\max\big\{|M_{1\sigma(1)}| \tdot \dots \tdot |M_{n\sigma(n)}| : \sigma \in S_n \big\} \label{eq:tper}
\end{equation}
is not equal to $\zero$, and is attained by only one permutation $\sigma$ in the symmetric group $S_n$. A matrix $A \in \strop^{m \times n}$ is \emph{strongly non-degenerate} if all of its square submatrices are generic. In particular, the coefficients of $A$ are not null (tropically).

\subsubsection*{Generalized Puiseux series}

Tropical arithmetic can be intuitively illustrated by the arithmetic over asymptotic orders of magnitude. For instance, if we denote by $\Theta(t^a)$ the equivalence class of real functions of $t$ which belong to some interval $[K t^a, K' t^a]$ when $t \rightarrow +\infty$ ($0 < K \leq K'$), we have $\Theta(t^a) + \Theta(t^b) = \Theta(t^{\max(a,b)})$, and $\Theta(t^a) \times \Theta(t^b) = \Theta(t^{a+b})$. We use generalized Puiseux series as a way to manipulate such orders of magnitude in a formal way.

A \emph{(real) generalized Puiseux series} (or \emph{Puiseux series} for short) is a formal series $\bo x$ in the indeterminate $t$ of the form $x_{\alpha_1} t^{\alpha_1} + x_{\alpha_2} t^{\alpha_2} + \dots$, where $\alpha_i \in \R$, $x_{\alpha_i} \in \R \setminus \{0\}$, and the sequence of the $\alpha_i$ is decreasing, and either finite or unbounded. The set of generalized Puiseux series forms a field that we denote $\puiseux$. Given a Puiseux series $\bo x$ as above, the largest exponent $\alpha_1$ is called the \emph{valuation} of $\bo x$, and is denoted by $\val(\bo x)$. By convention, the valuation of the null series $\bo x = 0$ is defined as $\zero = -\infty$. Thus the valuation $\val(\cdot)$ maps $\puiseux$ to $\trop$.

A Puiseux series $\bo x$ is \emph{positive}, which is denoted by $\bo x > 0$, if the coefficient $x_{\val(x)}$ of the term with largest exponent in $\bo x$ is positive. We denote by $\leq$ the total order over $\puiseux$ defined by $\bo x \leq \bo y$ if $\bo x = \bo y$ or $\bo y - \bo x > 0$. Then, we define the \emph{signed valuation} $\sval(\bo x)$ of $\bo x$ as the element of $\strop$ given by $\val(\bo x)$ if $\bo x > 0$, $\tminus (\val(\bo x))$ if $\bo x < 0$, and $\zero$ if $\bo x = 0$. Given $x \in \strop$, we also denote by $\sval^{-1}(x)$ the set of Puiseux series $\bo x$ such that $\sval(\bo x) = x$. Valuation, signed valuation and its inverse are extended to vectors and matrices coordinate-wise.

As discussed above, the arithmetic operations over $\puiseux$ and $\trop$ are related. For instance, for all $\bo x, \bo y \geq 0$, we have $\val(\bo x + \bo y) = \max(\val(\bo x), \val(\bo y))$. Similarly, if $\bo x, \bo y \in \puiseux$, then $\sval(\bo x \bo y) = \sval(\bo x) \tdot \sval(\bo y)$. More generally, the valuation will be used to transfer ``classical'' results to the tropical setting. In particular, convex polyhedra and linear programs over generalized Puiseux series essentially behave as over $\R$ ($\puiseux$ is a real-closed field~\cite{Markwig2007}, so Tarski's transfer principle applies). The simplex algorithm can be defined over $\puiseux$ as usual, and the valuation map will allow us to relate it with the tropical simplex algorithm.

\subsubsection*{General notations.} Given a matrix $A$ of dimension $m \times n$, and two subsets $I \subset [m]$ and $J \subset [n]$, we denote by $A_{I \times J}$ the submatrix formed by the rows and the columns of $A$ respectively indexed by $i \in I$ and $j \in J$. If $J = [n]$, we simply use the notation $A_I$. Similarly, if $i \in [n]$, $A_i$ represents the $i$-th line of $A$. The transpose matrix of $A$ is denoted by $\transpose{A}$, and the cardinality of a set $I$ by $|I|$. Given $s_1, \dots, s_n$, we denote by $\diag(s_1, \dots, s_n)$ (resp.\ $\tdiag(s_1, \dots, s_n)$) the matrix of dimension $n \times n$, with coefficients $s_i$ on the diagonal, and $0$ (resp.\ $\zero$) elsewhere.

\subsection{The tropical simplex method}\label{subsec:tropical_simplex}

The tropical simplex method, introduced in~\cite{AllamigeonBenchimolGaubertJoswig2013}, allows to solve tropical analogues of linear programming problems:
\begin{equation}
\begin{array}{r@{\quad}l}
\text{minimize} & \transpose{c} \tdot x \qquad (x \in \trop^n) \\
\text{subject to} &
x \geq \zero , \ A^+ \tdot x \tplus b^+ \geq A^- \tdot x \tplus b^-
\end{array} \tag*{$\tropLP(A,b,c)$} \label{eq:trop_lp}
\end{equation}
where $A \in \strop^{m \times n}$, $b \in \strop^m$, and $c \in \strop^n$. We denote by $\Pcal$ the tropical polyhedron defined by the constraints of~\ref{eq:trop_lp}. Note that the inequalities $x \geq \zero$ are trivially satisfied by any $x \in \trop^n$, hence they are superfluous. However, as we shall see, they are involved in the definition of tropical basic points, which is why we need to keep them.

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.65]
\draw[grid] (-0.5,-0.5) grid (9.5,7.5);
\draw[axis] (-0.5,0) -- (9.5,0) node[color=gray!50,above] {$x_1$};
\draw[axis] (0,-0.5) -- (0,7.5) node[color=gray!50,above] {$x_2$};

\draw[orange,ultra thick] (-0.5,2) -- (7,2) -- (7,-0.5);

\draw[blue!50,ultra thick] (7.5,7.5) -- (4,4) -- (4,-0.5);

\filldraw[green!70!black] (4,2) circle (4pt);
\end{tikzpicture}
\end{center}
\caption{Intersection of two tropical hyperplanes in general position. The hyperplanes are given by the equalities $x_1 = \max(x_2, 4)$ (blue) and $\max(-5 + x_1, x_2) = 2$ (orange).}\label{fig:hyperplanes}
\end{figure}

Similarly to the classical simplex method, the principle of the tropical simplex method is to pivot over the (feasible) tropical basic points, while decreasing the objective function $x \mapsto \transpose{c} \tdot x$. It handles tropical linear programs which satisfy a certain non-degeneracy assumption. Here, we will make the following sufficient assumption:
\begin{assumption}\label{assump:non_degenerate}
The matrices $\bigl(A \  b\bigr)$ and $\bigl(\begin{smallmatrix} A \\ c \end{smallmatrix}\bigr)$ are strongly non-degenerate.
\end{assumption}
In this setting, a \emph{basis} is a couple $(I,J)$ where $I \subset [m]$, $J \subset [n]$ satisfy $|I| + |J| = n$. Note that we will often manipulate $(I,J)$ through the disjoint union $I \disjcup J$ of $I$ and $J$. By a tropical analogue of Cramer theorem~\cite{PlusCDC90}, it can be shown that, under Assumption~\ref{assump:non_degenerate}, the system
\begin{equation}
\begin{aligned}
A^+_I \tdot x \tplus b^+_I & = A^-_I \tdot x \tplus b^-_I \\
x_J & = \zero
\end{aligned} \label{eq:basic_point}
\end{equation}
admits at most one solution in $\trop^n$. If this system admits a solution $\bar{x}$, the latter is referred to as the \emph{basic point} associated with the basis $(I,J)$. When $\bar{x}$ belongs to $\Pcal$, it is called a \emph{feasible basic point}, and $(I,J)$ is a \emph{feasible basis}.

\begin{remark}
Every equality in the system described in~\eqref{eq:basic_point} defines a \emph{tropical hyperplane}. Assumption~\ref{assump:non_degenerate} ensures that these hyperplanes are in general position, so that the intersection of $n$ such hyperplanes is either empty, or reduced to a singleton. We refer to Figure~\ref{fig:hyperplanes} for an illustration. This provides a geometric interpretation of basic points in terms of the arrangement of the tropical hyperplanes associated with the system $x \geq \zero$, $A^+ \tdot x \tplus b^+ \geq A^- \tdot x \tplus b^-$.
\end{remark}

The execution of the tropical simplex method on~\ref{eq:trop_lp} is related with the execution of the classical simplex method on a lifting linear program over Puiseux series. More precisely, a \emph{lift} of~\ref{eq:trop_lp} is a linear program over Puiseux series of the form:
\begin{equation}
\begin{array}{r@{\quad}l}
\text{minimize} & \transpose{\bo c} \bo x \qquad (\bo x \in \puiseux^n) \\
\text{subject to} &
\bo x \geq 0 , \ \bo A \bo x + \bo b \geq 0
\end{array} \tag*{$\LP(\bo A,\bo b,\bo c)$} \label{eq:lp}
\end{equation}
where $\bo A \in \sval^{-1}(A)$, $\bo b \in \sval^{-1}(b)$, and $\bo c \in \sval^{-1}(c)$. Let us denote by $\Pbcal$ the convex polyhedron defined by the inequalities of~\ref{eq:lp}. Then, $\Pcal$ and $\Pbcal$ have precisely the same (feasible) bases, and the map $\bo x \mapsto \val(\bo x)$ induces a one-to-one correspondence between their basic points~\cite[Proposition~17]{AllamigeonBenchimolGaubertJoswig2013}. Besides, if $\bo x^* \in \Pbcal$ minimizes the function $\bo x \mapsto \transpose{\bo c} \bo x$, then $\val(\bo x^*) \in \Pcal$ minimizes $x \mapsto \transpose{c} \tdot x$. Note that under Assumption~\ref{assump:non_degenerate}, the linear program $\LP(\bo A,\bo b,\bo c)$ is non-degenerate, in the sense that no minor of $\bigl(\bo A \  \bo b\bigr)$ and $\bigl(\begin{smallmatrix} \bo A \\ \bo c \end{smallmatrix}\bigr)$ is null.

Moreover, both simplex methods iterate over basic points in the same way. Starting from a basic point of basis $(I,J)$, they pivot to an adjacent basic point associated with a basis $(I', J')$ such that $I' \disjcup J' = (I \disjcup J) \setminus \{\vout\} \cup \{\vin\}$, for some $\vout \in I \disjcup J$, $\vin \not \in I \disjcup J$. The element $\vout$ is called the \emph{leaving variable}, and is provided by the pivoting rule. The integer $\vin$
is uniquely determined when the problem is non-degenerate.\footnote{Our terminology follows the one of the dual simplex method. This inversion comes from the fact that our notion of basis actually corresponds to the set of ``non-basic'' variables in a linear program written with slack variables.}

As a consequence, under Assumption~\ref{assump:non_degenerate}, if the classical and tropical simplex methods both start from the basis $(I,J)$ and select the same leaving variable $\vout$, they pivot to the same basis $(I',J')$. In other words, the tropical simplex method traces the image under the map $\val(\cdot)$ of the path followed by the classical simplex method, provided that they use compatible pivoting rules, \ie\ at any feasible basis, both rules select the same leaving variable.

We recall that, given a tropical basic point with basis $(I,J)$ and a leaving variable $\vout$, the operation of pivoting to the next tropical basic point can be done in time $O(n(m+n))$~\cite[Theorem~33]{AllamigeonBenchimolGaubertJoswig2013}. However, this pivoting operation is limited to basic points with no $-\infty$ coefficients. We present in Figure~\ref{fig:tropical_pivoting} a simpler, but more expensive, pivoting operation, which handles the general case. The algorithm $\Call{Pivot}{(I,J),\vout}$ consists in testing all the $m$ possibly entering variables $\vin$ in the complement of $I \disjcup J$. By the non-degeneracy assumptions, only one variable can lead to a feasible basis. Each candidate basic point can be computed in time $O(n^3)$ (see~\cite{PlusCDC90}), and the feasibility can be checked in $O(m n)$ by testing the $m$ inequalities in $A^+ \tdot x \tplus b^+ \geq A^- \tdot x \tplus b^- $. The total complexity of our pivoting operation is therefore in $O(m n(m + n^2))$.

\begin{figure}[t]
\begin{small}
\begin{algorithmic}[1]
\Procedure {Pivot}{$(I,J), \vout$}
\ForAll{$\vin \in ([m] \setminus I) \disjcup ([n] \setminus J)$}
    \State Let $(I',J'$) be defined by $I' \disjcup J' = (I \disjcup J) \setminus \{\vout\} \cup \{\vin\}$
    \If{the system $A^+_{I'} \tdot x \tplus b^+_{I'} = A^-_{I'} \tdot x \tplus b^-_{I'}, \ x_{J'} = \zero$ admits a solution $\bar{x} \in \trop^n$, and $\bar{x} \in \Pcal$}
        \State \Return $(I',J')$
    \EndIf
\EndFor
\EndProcedure
\end{algorithmic}
\end{small}
\caption{A naive implementation of the tropical pivoting operation}\label{fig:tropical_pivoting}
\end{figure}

\begin{remark}\label{remark:edge}
The geometric interpretation of the pivoting operation in the tropical setting is analogous to the classical setting. Let $x$ and $y$ be two adjacent tropical basic points, respectively associated with the bases $(I,J)$ and $(I',J')$, so that $I' \disjcup J' = (I \disjcup J) \setminus \{\vout\} \cup \{\vin\}$ for some $\vout \in I \disjcup J$, $\vin \not \in I \disjcup J$. Let $K \subset [m]$ and $L \subset [n]$ such that $K \disjcup L = (I \disjcup J) \setminus \{ \vout \}$. Then, the set $\Ecal$ of points $z \in \Pcal$ which satisfy the equalities
\[
\begin{aligned}
A^+_K \tdot z \tplus b^+_K & = A^-_K \tdot z \tplus b^-_K \\
z_L & = \zero
\end{aligned}
\]
is called a \emph{tropical edge} of $\Pcal$. Geometrically, it coincides with the \emph{tropical segment} between the two points $x,y$, which consists of the set $\{\lambda \tdot x \tplus \mu \tdot y : \lambda, \mu \in \trop, \ \lambda \tplus \mu = \unit\}$. As shown in~\cite[Proposition~18]{AllamigeonBenchimolGaubertJoswig2013}, this tropical edge is equal to the image under the map $\val(\cdot)$ of the edge $\Ebcal$ of the polyhedron $\Pbcal$ which connects the two basic points associated with the bases $(I,J)$ and $(I', J')$.
\end{remark}

\begin{example}
We provide in Figure~\ref{fig:tropical_polyhedron} an example of tropical polyhedron in dimension $2$. It is defined by the following five inequalities:
\[
\begin{aligned}
\max(x,1 + y) & \geq 3 \\
y & \geq \max(-10 + x, 1) \\
\max(y, 4) & \geq -3 + x \\
8 & \geq \max(x, 2 + y) \\
4 + x & \geq \max(y, 5)
\end{aligned}
\]
or, equivalently, by the system $x \geq \zero, \ A^+ \tdot x \tplus b^+ \geq A^- \tdot x \tplus b^-$ where:
\[
A = \begin{pmatrix} 0 & 1 \\ \tminus (-10) & 0 \\ \tminus (-3) & 0 \\ \tminus 0 & \tminus 2 \\ 4 & \tminus 0 \end{pmatrix} \qquad
b = \begin{pmatrix} \tminus 3 \\ \tminus 1 \\ 4 \\ 8 \\ \tminus 5\end{pmatrix} \ .
\]
Note that the inequalities $x \geq \zero$ are never active (our polyhedron is bounded in $\R^2$), so that all feasible bases are of the form $(I, \emptyset)$, where $I \subset [5]$ has cardinality $2$. The basic points associated with the bases $(\{2,3\}, \emptyset)$ and $(\{3, 4\}, \emptyset)$ are depicted in blue and orange respectively. The tropical edge between them is represented in green.
\end{example}

\begin{figure}
\begin{center}
\begin{tikzpicture}[scale=0.65]
\draw[grid] (-0.5,-0.5) grid (9.5,7.5);
\draw[axis] (-0.5,0) -- (9.5,0) node[color=gray!50,above] {$x_1$};
\draw[axis] (0,-0.5) -- (0,7.5) node[color=gray!50,above] {$x_2$};

\filldraw[convex] (1,2) -- (3,2) -- (3,1) -- (7,1) -- (7,4) -- (8,5) -- (8,6) -- (2,6) -- (1,5) -- cycle;
\draw[convexborder] (1,2) -- (3,2) -- (3,1) -- (7,1) -- (7,4) -- (8,5) -- (8,6) -- (2,6) -- (1,5) -- cycle;

\draw[green!70!black, line width=1.5pt] (7,1) -- (7,4) -- (8,5);
\filldraw[point] (7,1) circle (4pt);
\filldraw[orange] (8,5) circle (4pt);

\end{tikzpicture}
\end{center}
\caption{A tropical polyhedron (in gray), two basic points (in blue and orange) and a tropical edge (in green).}\label{fig:tropical_polyhedron}
\end{figure}

\section{Tropicalizing the shadow-vertex simplex algorithm}\label{sec:shadow_vertex}

\subsection{The classical shadow-vertex pivoting rule}

Given $\bo u, \bo v \in \puiseux^{n}$, the shadow-vertex rule aims at solving the following parametric family of linear programs for increasing values of $\bo \lambda \geq 0$:
\begin{equation}
\begin{array}{r@{\quad}l}
\text{minimize} & (\transpose{\bo u} - \bo \lambda \transpose{\bo v}) \bo x \qquad (\bo x \in \puiseux^n) \\
\text{subject to} &
\bo x \geq 0 , \ \bo A \bo x + \bo b \geq 0
\end{array}  \label{eq:parametric_lp}
\end{equation}
The vectors $\bo u$ and $\bo v$ are respectively called \emph{objective} and \emph{co-objective} vectors. The input of~\eqref{eq:parametric_lp} is supposed to satisfy a genericity property. Here, we will assume that no minor of $\bigl(\bo A \ \bo b \bigr)$ and $\bigl(\transpose{\bo A} \ \bo u \ \bo v\bigr)$ is null.

When $\bo \lambda$ is continuously increased from $0$, the basic points of $\Pbcal$ minimizing the function $\bo x \mapsto (\transpose{\bo u} - \bo \lambda \transpose{\bo v}) \bo x$ form a sequence $\bar{\bo x}^0, \dots, \bar{\bo x}^p$.
The shadow-vertex rule amounts to iterate over this sequence. It relies on the reduced cost vectors w.r.t.\ the objective and co-objective vectors.
Given a basis $(I,J)$, the \emph{reduced cost vector} $\bo y^{(I,J)} \in \puiseux^{I \disjcup J}$ w.r.t.\ the objective vector $\bo u$ is defined as the unique solution $\bo y$ of the system $\transpose{(\bo A'_{I \disjcup J})} \bo y = \bo u$, where $\bo A' = \begin{psmallmatrix} \boid \\ \bo A\end{psmallmatrix}$, and $\boid$ is the identity matrix.
The reduced cost vector $\bo z^{(I,J)}$ w.r.t.\ the co-objective vector $\bo v$ can be defined similarly, by replacing $\bo u$ by $\bo v$.
Then, at basis $(I,J)$, the shadow-vertex rule selects the leaving variable $\vout \in I \disjcup J$ such that $\bo y^{(I,J)}_{\vout} > 0$, $\bo z^{(I,J)}_{\vout} > 0$, and:
\begin{equation}
\bo y^{(I,J)}_{\vout} / \bo z^{(I,J)}_{\vout} =
\min
\bigl\{
\bo y^{(I,J)}_l / \bo z^{(I,J)}_l : l \in I \disjcup J, \ \bo y^{(I,J)}_l > 0 \ \text{and} \ \bo z^{(I,J)}_l > 0
\bigr\} \ . \label{eq:shadow_vertex}
\end{equation}
Note that $\vout$ is unique under the non-degeneracy assumptions. We refer to~\cite[Chapter~1.3]{Borgwardt1987} for a proof of~\eqref{eq:shadow_vertex}.
In the following, we will denote by $\sigmags(\bo A, \bo u, \bo v)$ the function which, given a basis $(I,J)$, returns the leaving variable provided by the shadow-vertex rule with objective and co-objective vectors $\bo u$ and $\bo v$. If there is no $l \in I \disjcup J$ such that $\bo y^{(I,J)}_l > 0$ and $\bo z^{(I,J)}_l > 0$, the function $\sigmags(\bo A, \bo u, \bo v)(I,J)$ will be supposed to return the  special value $\None$. It can be shown that this happens if, and only if, the basic point associated with the basis $(I,J)$ maximizes the co-objective function $\bo x \mapsto \transpose{\bo v} \bo x$ (see~\cite[Chapter~1.3]{Borgwardt1987}).

\subsection{Semi-algebraic pivoting rules and their tropical counterpart}

In this section, we focus on the problem of finding a tropical pivoting rule $\sigmagstrop$ compatible with the shadow-vertex rule $\sigmags$. More formally, we aim at defining a function $\sigmagstrop(A,u,v)$ parametrized by a tropical matrix $A \in \strop^{m \times n}$, and objective and co-objective vectors $u, v \in \strop^{n}$, such that:
\[
\sigmagstrop(A, u, v)(I,J) = \sigmags(\bo A, \bo u, \bo v)(I,J) \qquad \text{for any basis} \ (I,J) \ ,
\]
for all $\bo A \in \sval^{-1}(A)$, $\bo u \in \sval^{-1}(u)$, and $\bo v \in \sval^{-1}(v)$. In this case, $\sigmagstrop$ will be said to be \emph{compatible with} $\sigmags$ \emph{on the instance} $(A,u,v)$.

\subsubsection*{Tropical polynomials.}

The connection we use between the classical and tropical worlds relies on polynomials over generalized Puiseux series.

Let $P \in \puiseux[X_1, \dots, X_p]$ be a multivariate polynomial, and suppose that it is of the form $\sum_{\alpha \in S} \bo c_\alpha X_1^{\alpha_1} \dots X_p^{\alpha_p}$, where $S \subset \mathbb{N}^{p}$, and $\bo c_\alpha \in \puiseux \setminus \{0\}$ for all $\alpha \in S$. The set $S$ is called the \emph{support} of $P$. We associate a tropical polynomial $\tropPol(P) \in \strop[][X_1, \dots, X_p]$ defined as the following formal expression:
\[
\tropPol(P) := \tsum_{\alpha \in S} c_\alpha \tdot X_1^{\tdot \alpha_1} \tdot \dots \tdot X_p^{\tdot \alpha_p} \ ,
\]
with $c_\alpha := \sval(\bo c_\alpha)$ for all $\alpha \in S$. Given $x \in \strop^{p}$, we say that the polynomial $\tropPol(P)$ \emph{vanishes} on $x$ if the following maximum
\begin{equation}
\max\bigl\{ |c_\alpha| \tdot |x_1|^{\tdot \alpha_1} \tdot \dots \tdot |x_p|^{\tdot \alpha_p} : \alpha \in S \bigr\} \label{eq:poly_modulus}
\end{equation}
is reached at least twice, or is equal to $\zero$. If $\tropPol(P)$ does not vanish on $x$, we define $\tropPol(P)(x) \in \strop$ as follows:
\[
\tropPol(P)(x)  := c_{\alpha^*} \tdot x_1^{\tdot \alpha^*_1} \tdot \dots \tdot x_p^{\tdot \alpha^*_p} \ ,
\]
where $\alpha^*$ is the unique element of $S$ reaching the maximum in~\eqref{eq:poly_modulus}.
The following lemma relates the values of $P$ and $\tropPol(P)$:
\begin{lemma}\label{lemma:poly_sign}
Let $x \in \strop^{p}$, and suppose that $\tropPol(P)$ does not vanish on $x$. Then, for any $\bo x \in \sval^{-1}(x)$, we have $\sval(P(\bo x)) = \tropPol(P)(x)$. In particular, the sign of $P(\bo x)$ is equal to the sign of $\tropPol(P)(x)$.
\end{lemma}

\begin{proof}
Let $\bo x \in \sval^{-1}(x)$. Given $\alpha \in S$, the valuation of the term $\bo c_\alpha \bo x_1^{\alpha_1} \dots \bo x_p^{\alpha_p}$ is equal to $|c_\alpha| \tdot |x_1|^{\tdot \alpha_1} \tdot \dots \tdot |x_p|^{\tdot \alpha_p}$. Similarly, its signed valuation is given by $c_\alpha \tdot x_1^{\tdot \alpha_1} \tdot \dots \tdot x_p^{\tdot \alpha_p}$. As the maximum in~\eqref{eq:poly_modulus} is reached by only one element $\alpha^* \in S$, we deduce that $\bo c_{\alpha^*} \bo x_1^{\alpha^*_1} \dots \bo x_p^{\alpha^*_p}$ is the unique monomial with largest valuation in $P(\bo x)$. Thus, the signed valuation of $P(\bo x)$ coincides with the signed valuation of $\bo c_{\alpha^*} \bo x_1^{\alpha^*_1} \dots \bo x_p^{\alpha^*_p}$, and is equal to $\tropPol(P)(x) = c_{\alpha^*} \tdot x_1^{\tdot \alpha^*_1} \tdot \dots \tdot x_p^{\tdot \alpha^*_p}$.
\end{proof}

Following this, we can introduce determinants of tropical matrices. Let us define
\[
\tdet_n(X) := \tsum_{\sigma \in S_n} \tsign(\sigma) \tdot X_{1 \sigma(1)} \tdot \dots \tdot X_{n\sigma(n)} \ ,
\]
where $\tsign(\sigma) := \unit$ if the permutation $\sigma$ is even, $\tminus \unit$ otherwise. The polynomial $\tdet_n$ is simply denoted $\tdet$ when there is no ambiguity. If $M \in \strop^{n \times n}$, the \emph{tropical determinant} of $M$ is defined as $\tdet(M)$ when the polynomial $\tdet$ does not vanish on $M$. Note that the latter condition is equivalent to the fact that $M$ is generic. In this case, $\tdet(M)$ can be computed in time complexity $O(n^3)$, by solving an assignment problem over the bipartite graph with node set $[n] \disjcup [n]$, in which every arc $(i,j)$ is equipped with the weight $|M_{ij}|$. Indeed, the maximum weight matching provides the unique permutation $\sigma^* \in S_n$ reaching the maximum in~\eqref{eq:tper}, and by definition, $\tdet(M)$ is given by $\tsign(\sigma^*) \tdot M_{1 \sigma^*(1)} \tdot \dots \tdot M_{n \sigma^*(n)}$.

\begin{example}
The determinant of $(2 \times 2)$-matrices is given by the polynomial ${\det}_2 = X_{1,1} X_{2,2} - X_{1,2} X_{2,1}$, and the corresponding tropical polynomial is $\tdet_2 = (X_{1,1} \tdot X_{2,2}) \tplus (\tminus (X_{1,2} \tdot X_{2,1}))$. Let us consider the tropical matrix
$M :=
\begin{psmallmatrix}
3 & \tminus 2 \\
1 & \tminus 1
\end{psmallmatrix}$, and let $\bo M := \begin{psmallmatrix}
2 t^{3} + \cdots & -t^{2} + \cdots \\
4 t + \cdots & -9 t + \cdots
\end{psmallmatrix}$ be an arbitrary lift of $M$ (the dots represent terms of the series which have a smaller exponent, which we left unspecified). The tropical polynomial $\tdet_2$ does not vanish on $M$, since we have:
\begin{equation}
\max(|M_{1,1}| \tdot |M_{2,2}|, |M_{1,2}| \tdot |M_{2,1}|) = \max(3 \tdot 1, 1 \tdot 2) = \max(4,3) \ . \label{eq:example}
\end{equation}
Hence, the term reaching the maximum in~\eqref{eq:example} is associated with the monomial $X_{1,1} \tdot X_{2,2}$ of $\tdet_2$, so that $\tdet_2(M) = M_{1,1} \tdot M_{2,2} = \tminus 4$. On the other hand, the determinant of $\bo M$ is of the form $-18 t^{4} + \cdots + 4 t^{3} + \cdots$. Consequently, we indeed have $\sval(\det_2(\bo M)) = \tdet_2(M)$, as expected.

Moreover, the term $|M_{1,1}| \tdot |M_{2,2}|$ attaining the maximum in~\eqref{eq:example} is given by the maximum weight assignment $(1,1), (2,2)$ in the following bipartite graph with weights $|M_{ij}|$:

\begin{center}
\begin{tikzpicture}[scale=0.85,row/.style={draw,cross out,inner sep=0.5ex},col/.style={fill,circle,inner sep=0.5ex}]
\path node[row] (h1) at (0,0) {} (h1) node[left=0.25ex,font=\footnotesize] {$1$};
\path node[col] (j1) at (2,0) {} (j1) node[right=0.25ex,font=\footnotesize] {$1$};
\path node[row] (h2) at (0,-2) {} (h2) node[left=0.25ex,font=\footnotesize] {$2$};
\path node[col] (j2) at (2,-2) {} (j2) node[right=0.25ex,font=\footnotesize] {$2$};

\draw (h1.center) -- node[above] {$3$} (j1.center) -- node[above right=-0.5ex and 1.5ex] {$1$} (h2.center) -- node[below] {$1$} (j2.center) -- node[above left=-0.5ex and 1.5ex] {$2$} (h1.center);
\end{tikzpicture}
\end{center}
\end{example}

\subsubsection*{The shadow-vertex rule as a semi-algebraic rule.} We claim that the shadow-vertex rule is a \emph{semi-algebraic rule}, in the sense that the leaving variable returned by $\sigmags(\bo A, \bo u, \bo v)(I,J)$ only depends on the current basis $(I,J)$ and on the signs of finitely many polynomials taken on the matrix $\bo M := \begin{psmallmatrix}\bo A \\ \transpose{\bo u} \\ \transpose{\bo v}\end{psmallmatrix}$. To make the notations simpler, we fix a basis $(I,J)$, and we respectively denote by $\bo y$ and $\bo z$ the reduced cost vectors $\bo y^{(I,J)}$ and $\bo z^{(I,J)}$. We also define $\compl{J} := [n] \setminus J$.

Let us denote by $P_{K \times L}$ the polynomial given by the $(K \times L)$-minor of the matrix $X = (X_{ij})$ of formal variables, for any $K \subset [m+2]$ and $L \subset [n]$ such that $|K| = |L|$. For instance, if $K = \{1,2\}$ and $L = \{3,4\}$, $P_{K \times L}$ is given by the determinant of the submatrix $\begin{psmallmatrix}
X_{1,3} & X_{1,4} \\
X_{2,3} & X_{2,4}
\end{psmallmatrix}$, \ie~$P_{K \times L} = X_{1,3} X_{2,4} - X_{2,3} X_{1,4}$.  For all $l \in I \disjcup J$, we define two polynomials $Q_l$ and $R_l$ as follows:
\begin{align*}
Q_i & := P_{(I \setminus \{i\} \cup \{m+1\}) \times \compl{J}}  &
R_i & := P_{(I \setminus \{i\} \cup \{m+2\}) \times \compl{J}} && \text{when} \ i \in I \ , \\
Q_j & := P_{(I \cup \{m+1\}) \times (\compl{J} \cup \{j\})}  &
R_j & := P_{(I \cup \{m+2\}) \times (\compl{J} \cup \{j\})}
&& \text{when} \ j \in J \  .
\end{align*}

\begin{lemma}\label{lemma:reduced_cost}
For all $l \in I \disjcup J$,
\[
\bo y_l = s_l \, Q_l(\bo M) / P_{I \times \compl{J}}(\bo M) \ , \qquad
\bo z_l = s_l \, R_l(\bo M) / P_{I \times \compl{J}}(\bo M) \ ,
\]
where $s_l$ is a constant in $\{\pm 1\}$ which only depends on the integer $l$ and the sets $I$ and $J$.
\end{lemma}

\begin{proof}
We restrict our attention to the vector $\bo y$ (the proof is similar for the vector $\bo z$). Recall that $\bo y$ is given by the following system:
\begin{align*}
\bo y_J + \transpose{(\bo A_{I \times J})} \bo y_I & = \bo u_J \\
\transpose{(\bo A_{I \times \compl{J}})} \bo y_I & = \bo u_{\compl{J}}
\end{align*}
By the latter part, for all $i \in I$,
\[
\bo y_i = (-1)^{n-\idx(i)} \det\begin{pmatrix} \bo A_{(I \setminus \{i\}) \times \compl{J}} \\ \transpose{(\bo u_{\compl{J}})}\end{pmatrix} / \det(\bo A_{I \times \compl{J}}) \ ,
\]
where $\idx(i)$ represents the index of $i$ in the ordered set $I$. It follows that for all $j \in J$, we have:
\[
\bo y_j \det(\bo A_{I \times \compl{J}}) = \bo u_j \det(\bo A_{I \times \compl{J}}) - \sum_{i \in I} (-1)^{n-\idx(i)} \bo A_{ij} \det \begin{pmatrix}
\bo A_{(I \setminus \{i\}) \times \compl{J}} \\
\transpose{(\bo u_{\compl{J}})}
\end{pmatrix} \enspace.
\]
By developing the determinant of $\begin{psmallmatrix} \bo A_{I \times (\compl{J} \cup \{j\})} \\ \transpose{(\bo u_{\compl{J} \cup \{j\}})} \end{psmallmatrix}$ w.r.t.~ the column $\begin{psmallmatrix} \bo A_{I \times \{j\}} \\ \bo u_j \end{psmallmatrix}$, we obtain that:
\[
\bo y_j \det(\bo A_{I \times \compl{J}}) =
(-1)^{n + 1 - \idx'(j)} \det \begin{pmatrix} \bo A_{I \times (\compl{J} \cup \{j\})} \\ \transpose{(\bo u_{\compl{J} \cup \{j\}})} \end{pmatrix} \ ,
\]
where $\idx'(j)$ stands for the index of $j$ in the ordered set $\compl{J} \cup \{j\}$.
\end{proof}

As a consequence of Lemma~\ref{lemma:reduced_cost}, the properties $\bo y_l > 0$, $\bo z_l > 0$ can be tested by determining the signs of $Q_l(\bo M)$, $R_l(\bo M)$ and $P_{I \times \compl{J}}(\bo M)$. Moreover, we have:
\[
\bo y_l/\bo z_l = Q_l(\bo M)/R_l(\bo M) \ .
\]
Hence, the comparison of two ratios $\bo y_k / \bo z_k$ and $\bo y_l / \bo z_l$ involved in the shadow-vertex rule can be made by evaluating the sign of a polynomial of the form $T_{kl} := Q_k R_l - Q_l R_k$ on the matrix $\bo M$. This shows that the shadow-vertex rule is semi-algebraic.

\subsubsection*{Tropical shadow-vertex rule.}

Following the previous discussion, we can express $\sigmags(\bo A, \bo u, \bo v)$ as a function defined in terms of the signs of some minors $\det(\bo M_{K \times L})$, and of the signs of the $T_{kl}(\bo M)$ ($k \neq l$). Given tropical entries $(A,u,v)$, we simply define $\sigmagstrop(A, u, v)$ as the same function, in which the minors of $\bo M$ have been substituted by the corresponding tropical minors of the matrix $M := \begin{psmallmatrix} A \\ \transpose{u} \\ \transpose{v} \end{psmallmatrix}$, and the $T_{kl}(\bo M)$ have been replaced by $\tropPol(T_{kl})(M)$.

In more detail, the function $\sigmagstrop(A,u,v)(I,J)$ returns the unique element $\vout \in \Lambda$ such that
\begin{equation}
\sign(\tropPol(T_{\vout l}(M)) = -s_{\vout} s_l \qquad \text{for all} \ l \in \Lambda \setminus \{\vout\} \ , \label{eq:comparison}
\end{equation}
where $\Lambda$ is the set of the elements $l \in I \disjcup J$ such that $\sign(\tropPol(Q_l)(M)) = \sign(\tropPol(R_l)(M)) = s_l \sign(\tdet(M_{I \times \compl{J}}))$. The latter condition is the tropical counterpart of the conditions $\bo y_l, \bo z_l > 0$ in the definition of $\sigmags$. Equation~\eqref{eq:comparison} is the analogue of $\bo y_{\vout}/ \bo z_{\vout} < \bo y_l/ \bo z_l$ for all $l \in \Lambda$, $l \neq \vout$. If the set $\Lambda$ is empty, we set $\sigmagstrop(A,u,v)(I,J)$ to the special value $\None$.

The main result of this section is the following:
\begin{theorem}\label{th:gs_trop}
If the matrix $\begin{psmallmatrix} A \\ \transpose{u} \\ \transpose{v} \end{psmallmatrix}$ is strongly non-degenerate, then $\sigmagstrop$ is compatible with $\sigmags$ on the instance $(A, u, v)$.

Moreover, for all bases $(I,J)$, the leaving variable returned by $\sigmagstrop(A,u,v)(I,J)$ can be computed in time $O(n^4)$.
\end{theorem}

\begin{proof}
Let $\bo A \in \sval^{-1}(A)$, $\bo u \in \sval^{-1}(u)$, and $\bo v \in \sval^{-1}(v)$. By assumption, the matrix $M = \begin{psmallmatrix} A \\ \transpose{u} \\ \transpose{v} \end{psmallmatrix}$ is strongly non-degenerate, so that the sign of every tropical minor $\tdet(M_{K \times L})$ coincides with the sign of the corresponding minor of $\bo M := \begin{psmallmatrix}\bo A \\ \transpose{\bo u} \\ \transpose{\bo v}\end{psmallmatrix}$ by Lemma~\ref{lemma:poly_sign}. Consequently, by Lemma~\ref{lemma:reduced_cost}, the set $\Lambda$ precisely consists of the elements $l \in I \disjcup J$ such that $\bo y_l > 0$ and $\bo z_l > 0$. As discussed earlier, each tropical minor can be computed in time $O(n^3)$. Hence, the set $\Lambda$ can be determined in time $O(n^4)$. It now remains to examine the case of the polynomials $\tropPol(T_{kl})$, and to show in particular that they do not vanish on $M$. For the sake of brevity, we restrict to the case $k,l \in I$. The general case can be handled in a similar way.

Let us write the polynomial $\tropPol(T_{kl})$ under the form $\tsum_{\alpha \in S} c_\alpha \tdot X^{\tdot \alpha}$, where $S$ is the support of $T_{kl}$ (we use the notation $X^{\tdot \alpha}$ as a shorthand of $\tprod_{ij} X_{ij}^{\tdot \alpha_{ij}}$). By definition, $\tropPol(T_{kl})$ does not vanish on $M$ if, and only if, there exists a unique solution to the following maximization problem:
\begin{equation}
\begin{array}{r@{\quad}l}
\text{maximize} & |c_\alpha | \tdot |M|^{\tdot \alpha} \\
\text{subject to} & \alpha \in S
\end{array}
\label{eq:vanish}
\end{equation}
Observe that the coefficients in $T_{kl}$ are integers. Hence, as elements of the field $\puiseux$, they are constant Puiseux series, with valuation $0 = \unit$. Besides, $M_{ij} \neq \zero$ for all $(i,j)$, thanks to the strong non-degeneracy of $M$. Then, we can simply rewrite $|c_\alpha| \tdot |M|^{\tdot \alpha} = \sum_{ij} |M_{ij}| \alpha_{ij}$ for all $\alpha \in S$. As a consequence, Problem~\eqref{eq:vanish} can be solved by considering the following classical linear program:
\begin{equation}
\begin{array}{r@{\quad}l}
\text{maximize} & \sum_{ij} |M_{ij}| \alpha_{ij} \\
\text{subject to} & \alpha \in \new(T_{kl})
\end{array}
\label{eq:lp_over_newton}
\end{equation}
where $\new(T_{kl}) \subset \R^{(m+2) \times n}$ is the \emph{Newton polytope} of the polynomial $T_{kl}$, defined as the convex hull of its support $S$. Since the set of vertices of the polytope $\new(T_{kl})$ is a subset of $S$, it is easy to show that $\tropPol(T_{kl})$ does not vanish on $M$ if, and only if, Problem~\eqref{eq:lp_over_newton} admits a unique solution $\alpha^*$. In this case, we have $\alpha^* \in S$, and the sign of $\tropPol(T_{kl})(M)$ is immediately given by the sign of the term $c_{\alpha^*} \tdot M^{\tdot \alpha^*}$.

It now remains to check that Problem~\eqref{eq:lp_over_newton} indeed has a unique solution, and that the latter can be found efficiently. To this aim, we use Pl{\"u}cker quadratic relations (see for instance~\cite[Chapter 3]{GelfandKapranovZelevinsky}), which provide the identity
$T_{kl} = P_{I \times \compl{J}} \, P_{(I \setminus \{k,l\} \cup \{m+1, m+2\}) \times \compl{J}}$. This implies that the Newton polytope of $T_{kl}$ consists in the Minkowski sum of the two polytopes $\Delta_1 := \new(P_{I \times \compl{J}})$ and $\Delta_2 := \new(P_{(I \setminus \{k,l\} \cup \{m+1, m+2\}) \times \compl{J}})$. As a result, Problem~\eqref{eq:lp_over_newton} can be decomposed into the following two linear programs:
\begin{equation}
\begin{array}{r@{\quad}l}
\text{maximize} & \sum_{ij} |M_{ij}| \alpha_{ij} \\
\text{subject to} & \alpha \in \new(\Delta_i)
\end{array}
\qquad \quad \text{for} \ i \in \{1, 2\} \ .\label{eq:sub_problems}
\end{equation}
More precisely, the set of optimal solutions of Problem~\eqref{eq:lp_over_newton} is precisely the Minkowski sum of the set of optimal solutions of the two problems given in~\eqref{eq:sub_problems}. The polytopes $\new(\Delta_i)$ are bipartite perfect matching polytopes. Consequently, the two problems in~\eqref{eq:sub_problems} correspond to optimal assignment problems, and can be solved in $O(n^3)$. Besides, they both admit a unique solution thanks to the genericity condition on $M$.

To summarize, $\tropPol(T_{kl})$ does not vanish on $M$, and the sign of $\tropPol(T_{kl})(M)$ can be computed in time $O(n^3)$. By Lemmas~\ref{lemma:poly_sign} and~\ref{lemma:reduced_cost}, $\sign(\tropPol(T_{k l}(M)) = -s_k s_l$ if, and only if, $\bo y_k/\bo z_k < \bo y_l/ \bo z_l$. This completes the analysis of the polynomial $\tropPol(T_{kl})$.

We deduce that $\sigmagstrop$ and $\sigmags$ are compatible. The output $\vout$ of $\sigmagstrop(A,u,v)(I,J)$ can be computed by determining the smallest element of the set $\Lambda$ according to the abstract ordering relation $\prec$ defined by $k \prec l \Longleftrightarrow \sign(\tropPol(T_{kl})(M)) = -s_k s_l$. Every comparison has time complexity $O(n^3)$, and so the result can be obtained in time $O(n^4)$.
\end{proof}

\section{Average-case complexity of mean payoff games}\label{sec:pcbc}

\subsection{Tropicalization of the Parametric Constraint-by-Constraint algorithm}\label{subsec:classical_pcbc}

\begin{figure}[t]
\begin{small}
\begin{algorithmic}[1]
\Procedure {PCBC}{$\bo A, \bo b$}
\State $\bo u \gets \transpose{(\bo \eps, \bo \eps^2, \dots, \bo \eps^n)}$ \Comment{$0 < \bo \eps \ll 1$}
\State $\bar{\bo x} \gets \transpose{(0, \dots, 0)}$ \label{line:init}
\For{$k = 1$ to $m$} \label{line:bloop}
\If{$\bo A_k \bar{\bo x} + \bo b_k < 0$}
    \State Starting from $\bar{\bo x}$, iterate over the basic points and edges of $\Pbcal^{(k-1)}$ using the rule $\sigmags(\bo A_{[k-1]}, \bo u, \transpose{(\bo A_k)})$, until finding a point $\bar{\bo x}'$ such that $\bo A_k \bar{\bo x}' + \bo b_k = 0$. \label{line:simplex}
    \sIf{there is no such point $\bar{\bo x}'$} \Return ``Empty'' \label{line:stop}
    \sElse $\bar{\bo x} \gets \bar{\bo x}'$
\EndIf
\EndFor \label{line:eloop}
\State \Return ``Non-empty''
\EndProcedure
\end{algorithmic}
\end{small}
\caption{Parametric Constraint-by-Constraint algorithm}\label{fig:pcbc}
\end{figure}

The ave\-rage-case analysis of~\cite{AdlerKarpShamir87} applies to the so-called \emph{Parametric Constraint-by-Constraint} ($\PCBC$) algorithm. We first recall the principle of this algorithm. We restrict the presentation to polyhedral feasibility problems, following our motivation to their tropical counterparts and mean payoff games.

The $\PCBC$ algorithm is given in Figure~\ref{fig:pcbc}. Given $\bo A \in \R^{m \times n}$, $\bo b \in \R^m$, and $k \in \{0, \dots, m\}$, we denote by $\Pbcal^{(k)}$ the polyhedron defined by the first $n+k$ inequalities of the system $\bo x \geq 0, \ \bo A \bo x + \bo b \geq 0$. The $\PCBC$ algorithm consists in determining by induction on $k = 1, \dots, m$ whether the polyhedron $\Pbcal^{(k)}$ is empty. The invariant of the loop from Lines~\lineref{line:bloop} to~\lineref{line:eloop} is that $\bar{\bo x}$ is the (unique) basic point of $\Pbcal^{(k-1)}$ minimizing the function $\bo x \mapsto \transpose{\bo u} \bo x$, where $\bo u$ is an objective vector fixed throughout the whole execution of $\PCBC$. At the $k$-th iteration of the loop, when $\bar{\bo x}$ does not satisfy the constraint $\bo A_k \bo x + \bo b_k \geq 0$, the simplex algorithm equipped with the shadow-vertex pivoting rule is used. The co-objective vector is set to $\transpose{(\bo A_k)}$. The simplex algorithm thus follows a path in $\Pbcal^{(k-1)}$ consisting of basic points and the edges between them. We stop it as soon as it discovers a point $\bar{\bo x}' \in \Pbcal^{(k-1)}$ such that $\bo A_k \bar{\bo x}' + \bo b_k = 0$ on the path. This point is obviously a basic point of $\Pbcal^{(k)}$. It follows from the definition of the shadow-vertex rule that $\bar{\bo x}'$ minimizes the objective function $\bo x \mapsto \transpose{\bo u} \bo x$ over $\Pbcal^{(k)}$. Then, $\bar{\bo x}'$ can be used as a starting point for the execution of the simplex algorithm during the $(k+1)$-th iteration. If no such point $\bar{\bo x}'$ is discovered, the simplex algorithm stops at a basic point $\bo x''$ associated with a basis $(I'',J'')$ such that $\sigmags(\bo A_{[k-1]}, \bo u, \transpose{(\bo A_k)})(I'', J'') = \None$.\footnote{\label{footnote:ray}As noted in~\cite[Section~4]{AdlerKarpShamir86}, if the simplex algorithm encounters a ray of the polyhedron of $\Pbcal^{(k-1)}$ on the path, it necessarily finds a point $\bar{\bo x}' \in \Pbcal^{(k-1)}$ such that $\bo A_k \bar{\bo x}' + \bo b_k = 0$.} In this case, $\bo x''$ maximizes the function $\bo x \mapsto \bo A_k \bo x$ over $\Pbcal^{(k-1)}$, which shows that $\bo A_k \bo x + \bo b_k < 0$ for all $\bo x \in \Pbcal^{(k-1)}$. Then, the algorithm returns ``Empty''.

The objective vector $\bo u$ is set to $\transpose{(\bo \eps, \bo \eps^2, \dots, \bo \eps^n)}$, where $\bo \eps > 0$ is a sufficiently small scalar. Since $\bo u_j > 0$ for all $j \in [n]$, the vector $\transpose{(0, \dots, 0)}$ is a basic point of $\Pbcal^{(0)} = (\R_+)^n$ minimizing $\bo x \mapsto \transpose{\bo u} \bo x$.

The $\PCBC$ algorithm is still correct when applied on inputs $\bm A, \bm b$ with entries in~$\puiseux$. This suggests to tropicalize it by using the tropical simplex algorithm equipped with the pivoting rule developed in Section~\ref{sec:shadow_vertex}. This is the purpose of the algorithm $\tropPCBC$ given in Figure~\ref{fig:trop_pcbc}. Its principle is analogous to $\PCBC$. It manipulates the sequence of tropical polyhedra $\Pcal^{(k)}$ ($0 \leq k \leq m$), which are respectively defined by the first $n+k$ inequalities of the system $x \geq \zero$, $A^+ \tdot x \tplus b^+ \geq A^- \tdot x \tplus b^-$. It also involves an objective vector of the form $u \gets \transpose{(\eps, \eps^{\tdot 2}, \dots, \eps^{\tdot n})}$, with $\eps < 0$.

Let us describe in more detail the operations performed at Line~\lineref{line:trop_simplex}. For each visited basic point $x$ of $\Pcal^{(k-1)}$, the tropical rule $\sigmagstrop(A_{[k-1]}, u, \transpose{(A_k)})$ determines a variable $\vout$ leaving the basis $(I,J)$ associated with $x$. The tropical simplex algorithm then pivots along the edge $\Ecal$ formed by the points $z \in \Pcal^{(k-1)}$ which activate all the inequalities indexed by $l \in (I \disjcup J) \setminus \{\vout\}$ in the system defining $\Pcal^{(k-1)}$ (see Remark~\ref{remark:edge}). There exists a point $\bar{x}' \in \Ecal$ such that $A^+_k \tdot \bar{x}' \tplus b^+_k = A^-_k \tdot \bar{x}' \tplus b^-_k$ if, and only if, the pair $(I',J')$ given by $I' \disjcup J' = (I \disjcup J) \setminus \{\vout\} \cup \{k\}$ is a feasible basis of $\Pcal^{(k)}$. Indeed, such an $\bar{x}'$ is precisely characterized as the basic point of $\Pcal^{(k)}$ of basis $(I',J')$. Thus, its existence can be checked in time $O(n (m+n^2))$, as explained in Section~\ref{subsec:tropical_simplex}. If there is no such $\bar{x}'$ in $\Ecal$, we use the algorithm $\Call{Pivot}{(I,J),\vout}$ to compute the next basis of $\Pcal^{(k-1)}$.

Note that the condition at Line~\lineref{line:stop} is satisfied when there is no basic point of $\Pcal^{(k-1)}$ to be visited anymore, \ie~when the tropical pivoting rule $\sigmagstrop(A_{[k-1]}, u, \transpose{(A_k)})$ returns $\None$.

\begin{figure}[t]
\begin{small}
\begin{algorithmic}[1]
\Procedure{TropPCBC}{$A, b$}
\State $u \gets \transpose{(\eps, \eps^{\tdot 2}, \dots, \eps^{\tdot n})}$  \Comment{$-\infty < \eps \ll 0$}
\State $\bar{x} \gets \transpose{(\zero, \dots, \zero)}$
\For{$k = 1$ to $m$}
\If{$A^+_k \tdot \bar{x} \tplus b^+_k < A^-_k \tdot \bar{x} \tplus b^-_k$}
    \State Starting from $\bar{x}$, iterate over the tropical basic points and edges of $\Pcal^{(k-1)}$ using the tropical rule $\sigmagstrop(A_{[k-1]}, u, \transpose{(A_k)})$ until finding a point $\bar{x}' \in \Pcal^{(k-1)}$ such that $A^+_k \tdot \bar{x}' \tplus b^+_k = A^-_k \tdot \bar{x}' \tplus b^-_k$. \label{line:trop_simplex}
    \sIf{there is no such point $\bar{x}'$} \Return ``Empty''
    \sElse $\bar{x} \gets \bar{x}'$
\EndIf
\EndFor
\State \Return ``Non-empty''
\EndProcedure
\end{algorithmic}
\end{small}
\vskip-2ex
\caption{Tropicalization of the PCBC algorithm}\label{fig:trop_pcbc}
\end{figure}

In order to use the tropical shadow-vertex rule on the instances $(A_{[k-1]}, u, \transpose{(A_k)})$, we verify that the matrix $\begin{psmallmatrix} A \\ \transpose{u} \end{psmallmatrix}$ is strongly non-degenerate. The following lemma shows that this property holds assuming that $\eps$ is small enough:
\begin{lemma}\label{lemma:eps}
Suppose that the matrix $A$ is strongly non-degenerate, and $\eps < n (\min_{ij} |A_{ij}| - \max_{ij} |A_{ij}|)$. Then, the matrix $\begin{psmallmatrix} A \\ \transpose{u} \end{psmallmatrix}$ is strongly non-degenerate.
\end{lemma}

\begin{proof}
Let $M \in \strop^{K \times L}$ be a square submatrix of $\begin{psmallmatrix} A \\ \transpose{u} \end{psmallmatrix}$. If $M$ is a submatrix of $A$, then it is clear that $M$ is generic. Now, suppose that $M$ involves the last line $\transpose{u}$ (\ie~$m+1 \in K$), and that the maximum
\[
\max \Big\{ \bigodot_{k \in K} |M_{k \sigma(k)}| : \sigma \  \text{is a bijection from} \ K \ \text{to}\  L  \Big\}
\]
is reached at least by two distinct bijections $\sigma^*$ and $\tau^*$. If $\sigma^*(m+1) = \tau^*(m+1)$, this immediately shows that the $(K \setminus \{m+1\}) \times (L \setminus \{\sigma^*(m+1)\})$-submatrix of $A$ is degenerate. Thus, we can suppose that $\sigma^*(m+1)$ and $\tau^*(m+1)$ are distinct, for instance $\sigma^*(m+1) > \tau^*(m+1)$. However, as $\eps < 0$, we have:
\[
\bigodot_{k \in K} |M_{k \sigma^*(k)}| \leq \sigma^*(m+1) \eps + n \max_{ij} |A_{ij}| < \tau^*(m+1) \eps + n \min_{ij} |A_{ij}| \leq \bigodot_{k \in K} |M_{k \sigma^*(k)}| \ .
\]
In any case, we get a contradiction. We deduce that $M$ is generic.
\end{proof}
Note that, under the assumptions of Lemma~\ref{lemma:eps}, if we choose $\bo A \in \sval^{-1}(A)$ and $\bo u \in \sval^{-1}(u)$, no minor of the matrix $\begin{psmallmatrix} \bo A \\ \transpose{\bo u} \end{psmallmatrix}$ is null. This ensures that the application of the classical shadow-vertex pivoting rule also makes sense in the $\PCBC$ algorithm.

Thanks to the compatibility of the tropical shadow-vertex rule with its classical counterpart (Theorem~\ref{th:gs_trop}), we immediately obtain the following result:
\begin{proposition}\label{prop:trop_pcbc}
Let $A \in \strop^{m \times n}$, $b \in \strop^{m}$ such that $(A \ b)$ is strongly non-degenerate, and let $\eps < n (\min_{ij} |A_{ij}| - \max_{ij} |A_{ij}|)$.

Then, the algorithm $\tropPCBC$ correctly determines whether the tropical polyhedron $\{x \in \trop^n : A^+ \tdot x \tplus b^+ \geq A^- \tdot x \tplus b^-\}$ is empty.

Moreover, for all $\bo A \in \sval^{-1}(A)$, $\bo b \in \sval^{-1}(b)$ and $\bo \eps \in \sval^{-1}(\eps)$, the total number of basic points visited by $\tropPCBC(A, b)$ and by $\PCBC(\bo A, \bo b)$ are equal.
\end{proposition}

\begin{proof}
First note that the conditions of Theorem~\ref{th:gs_trop} are satisfied, thanks to Lemma~\ref{lemma:eps}. We are going to show by induction that the algorithms $\PCBC$ and $\tropPCBC$ iterate over the same sequence of bases.
Initially, at Line~\lineref{line:init}, both algorithms start from the basis $(\emptyset, [n])$.

Now, consider the $k$-th iteration of the loop between Lines~\lineref{line:bloop} and~\lineref{line:eloop}. By induction hypothesis, the points $\bar{\bo x}$ and $\bar{x}$ are basic points of $\Pbcal^{(k-1)}$ and $\Pcal^{(k-1)}$ respectively, associated with the same basis $(I_0,J_0)$. The point $\bar{\bo x}$ (resp.\ $\bar{x}$) satisfies the condition $\bo A_k \bar{\bo x} + \bo b_k \geq 0$ (resp.\ $A^+_k \tdot \bar{x} \tplus b^+_k \geq A^-_k \tdot \bar{x} \tplus b^-_k$) if, and only if, $(I_0,J_0)$ is a feasible basis of $\Pbcal^{(k)}$ (resp.\ $\Pcal^{(k)}$). As the polyhedra $\Pbcal^{(k)}$ and $\Pcal^{(k)}$ have the same feasible bases (see~\cite[Proposition~17]{AllamigeonBenchimolGaubertJoswig2013}), we deduce that the two conditions $\bo A_k \bar{\bo x} + \bo b_k \geq 0$ and $A^+_k \tdot \bar{x} \tplus b^+_k \geq A^-_k \tdot \bar{x} \tplus b^-_k$ are equivalent.

If none of these conditions is satisfied, the two algorithms $\PCBC$ and $\tropPCBC$ execute Line~\lineref{line:trop_simplex} and run the classical and tropical shadow-vertex algorithms. Assume that the two latter algorithms are located at basic points $\bo x$ and $x$ of $\Pbcal^{(k-1)}$ and $\Pcal^{(k-1)}$ respectively, associated with the same basis $(I,J)$. Note that $\bo x$ is the final point of the path followed by the classical simplex algorithm if, and only if, $x$ is the final point of the path followed by the tropical simplex algorithm. Indeed, these two statements amount to $\sigmags(\bo A_{[k-1]}, \bo u, \transpose{\bo A_k})(I,J) = \None$ and $\sigmagstrop(A_{[k-1]}, u, \transpose{A_k})(I,J) = \None$ respectively. The equivalence then follows from Theorem~\ref{th:gs_trop}.

If $\bo x$, or equivalently $x$, is not the final point of the path, the pivoting rules $\sigmags$ and $\sigmagstrop$ returns the same leaving variable $\vout \in I \disjcup J$, still by Theorem~\ref{th:gs_trop}. In this case, the classical (resp. tropical) simplex algorithm pivots along the edge $\Ebcal$ (resp. $\Ecal$) formed by the points of $\Pbcal^{(k-1)}$ (resp. $\Pcal^{(k-1)}$) which activate the inequalities indexed by $l \in (I \disjcup J) \setminus \{\vout\}$. Let $I' \subset [m]$ and $J' \subset [n]$ such that  $I' \disjcup J' = (I \disjcup J) \setminus \{\vout\} \cup \{k\}$.

The existence of a point $\bar{\bo x}' \in \Ebcal$ (resp.\ $\bar{x}' \in \Ecal$) such that $\bo A_k \bar{\bo x}' + \bo b_k = 0$ (resp.\ $A^+_k \tdot \bar{x}' \tplus b^+_k = A^-_k \tdot \bar{x}' \tplus b^-_k$) is equivalent to the fact that the basis $(I',J')$ is a feasible basis of $\Pbcal^{(k)}$ (resp.\ of $\Pcal^{(k)}$). Using again the fact that the polyhedra $\Pbcal^{(k)}$ and $\Pcal^{(k)}$ have the same feasible bases, we deduce that the classical simplex algorithm finds a point $\bar{\bo x}'$ such that $\bo A_k \bar{\bo x}' + \bo b_k = 0$ when pivoting along the edge $\Ebcal$ if, and only if, the tropical simplex algorithm discovers a point $\bar{x}' \in \Ecal$ which satisfies $A^+_k \tdot \bar{x}' \tplus b^+_k = A^-_k \tdot \bar{x}' \tplus b^-_k$. In this case, $\bar{\bo x}'$ and $\bar{x}'$ are basic points (of $\Pbcal^{(k)}$ and $\Pcal^{(k)}$ respectively) associated with the same basis $(I',J')$. If no such points $\bar{\bo x}'$ and $\bar{x}'$ exist, the edge $\Ebcal$ is necessarily bounded (see Footnote~\ref{footnote:ray}). Thus, the tropical edge $\Ecal = \val(\Ebcal)$ is also bounded. As a result, the two simplex algorithms both reach new basic points of $\Pbcal^{(k-1)}$ and $\Pcal^{(k-1)}$ respectively. These points are associated with the same basis $(I'',J'')$, given by $I'' \disjcup J'' = (I \disjcup J) \setminus \{\vout\} \cup \{\vin\}$ for some $\vin \not \in I \disjcup J$ (the entering variables in the classical and tropical cases are necessarily identical, by unicity).

This completes the proof by induction, and shows the second part of the proposition. The correctness of the algorithm $\tropPCBC$ immediately follows from the correctness of $\PCBC$, and the fact that $\Pbcal = \emptyset$ if, and only if, $\Pcal = \emptyset$.
\end{proof}

\begin{remark}\label{remark:eps}
As stated in Proposition~\ref{prop:trop_pcbc}, the scalar $\eps$ is supposed to be small enough. We point out that there is no need to choose or manipulate $\eps$ explicitly in the algorithm $\tropPCBC$. Indeed, as shown in the proof of Theorem~\ref{th:gs_trop}, $\eps$ is only involved in optimal assignment problems which arise in the computation of the leaving variable returned by the tropical shadow-vertex rule $\sigmagstrop(A_{[k-1]}, u, \transpose{(A_k)})$ at Line~\lineref{line:trop_simplex} ($k \in [m]$). Let us fix $k$, and let $M := \begin{psmallmatrix} A_{[k-1]} \\ \transpose{u} \\ A_k \end{psmallmatrix} \in \strop^{(k+1) \times n}$. The optimal assignment problems to be solved are associated to weighted bipartite graphs, with node sets $K \subset [k+1]$ and $L \subset [n]$ and weights $|M_{hl}|$ for $h \in K$ and $l \in L$. Let $G$ be such a graph. It involves weights with a dependency on $\eps$ if, and only if, the set $K$ contains the node $k$, which corresponds to the index of the row vector $\transpose{u}$ in the matrix $M$. More precisely, the arcs whose weight depends on $\eps$ are precisely of the form $(k,l)$, for all $l \in L$. Their respective weights are $\eps^{\tdot l} = l \times \eps$. It is clear that for any sufficiently small $\eps < 0$, the (unique) optimal assignment $\sigma^*$ in $G$ is obtained by mapping the node $k$ to the smallest element $l^*$ of $L$, and then by solving the optimal assignment problem in the graph $G'$ obtained from $G$ by removing the nodes $k$ and $l^*$ and their incident arcs. Since the weights of $G'$ do not depend on $\eps$, the optimal assignment problem in $G'$ can be solved numerically, in a standard way.

In other words, the dependency on $\eps$ in the optimal assignment problems can be handled in a symbolic way. This is comparable to the ``lexicographic'' treatment of the scalar $\bm \eps$ in the $\PCBC$ algorithm described in~\cite[Section~6.1]{AdlerKarpShamir87}.
\end{remark}

\subsection{Average-case analysis}

Given $\bo A \in \R^{m \times n}$, $\bo b \in \R^m$ such that no minor of the matrix $(\bo A  \  \bo b)$ is null, the probabilistic analysis of~\cite{AdlerKarpShamir87} applies to polyhedra of the form
\[
\Pbcal_{S, S'}(\bo A, \bo b) = \{ \bo x \in \R^n : \bo x \geq 0, \ (S \bo A S') \bo x + S \bo b \geq 0 \} \enspace,
\]
where $S = \diag(s_1, \dots, s_m)$, $S' = \diag(s'_1, \dots, s'_n)$, and the $s_i$ and $s'_j$ are i.i.d.\ entries with values in $\{\pm 1\}$ such that each of them is equal to $+1$ (resp.\ $-1$) with probability $1/2$. Equivalently, the $2^{m+n}$ polyhedra of the form $\Pbcal_{S, S'}(\bo A, \bo b)$ are equiprobable.

\begin{theorem}[{\cite{AdlerKarpShamir87}}]\label{th:adler}
For any fixed choice of $\bo A$ and $\bo b$ such that no minor of $(\bo A  \  \bo b)$ is null, provided that $\bo \eps$ is sufficiently small, the total number of basic points visited by $\PCBC(S \bo A S',S \bo b)$ is bounded by $O(\min(m^2, n^2))$ on average.
\end{theorem}

It can be verified that the proof of Theorem~\ref{th:adler} is still valid when we replace $\R$ by any real-closed field $K$. Alternatively, it can be shown that Theorem~\ref{th:adler} can be expressed as a first-order sentence, so that Tarski's principle can be used to transpose it to any real-closed field. As a consequence of Proposition~\ref{prop:trop_pcbc}, the algorithm $\tropPCBC$ should visit a quadratic number of tropical basic points on average. This is the way we translate the result of Adler~\etal{} to mean payoff games.
The probability distribution of games is expressed over their payments matrices $A, B$, and must satisfy the following requirements:
\begin{assumption}\label{ass:model}
\begin{enumerate}[(i)]
\item\label{item:cond3} for all $i \in [m]$ (resp.\ $j \in [n]$), the distribution of the matrices $A, B$ is invariant by the exchange of the $i$-th row (resp.\ $j$-th column) of $A$ and $B$.
\item\label{item:cond1} almost surely, $A_{ij}$ and $B_{ij}$ are distinct and not equal to $\zero$ for all $i \in [m]$, $j \in [n]$. In this case, we introduce the signed matrix $W = (W_{ij}) \in \strop^{m \times n}$, defined by $W_{ij} := A_{ij}$ if $A_{ij} > B_{ij}$, and $\tminus B_{ij}$ if $A_{ij} < B_{ij}$.
\item\label{item:cond2} almost surely, the matrix $W$ is strongly non-degenerate.
\end{enumerate}
\end{assumption}
Let us briefly discuss the requirements of Assumption~\ref{ass:model}.

Condition~\eqref{item:cond3} corresponds to the flip invariance property. It handles discrete distributions (see Figure~\ref{fig:flip}) as well as continuous ones. In particular, if the distribution of the payment matrices admits a density function $f$, Condition~\eqref{item:cond3} can be expressed as the invariance of $f$ by exchange operations on its arguments. For instance, if $m = 1$ and $n = 2$, the flip invariance holds if, and only if, for almost all  $a_{ij}, b_{ij}$,
$f(a_{1,1}, a_{1,2}, b_{1,1}, b_{1,2}) =
f(b_{1,1}, b_{1,2}, a_{1,1}, a_{1,2}) =
f(b_{1,1}, a_{1,2}, a_{1,1}, b_{1,2}) =
f(a_{1,1}, b_{1,2}, b_{1,1}, a_{1,2})$.

The requirements $A_{ij}, B_{ij} \neq \zero$ for all $i,j$ in Condition~\eqref{item:cond1} ensure that the flip operations always provide games in which the two players have at least one action to play from every position. The matrix $W$ can be intuitively thought of as a tropical subtraction ``$A \tminus B$'', and the conditions $A_{ij} \neq B_{ij}$ ensure that $W$ is well defined. Then, the following result holds:
\begin{lemma}\label{lemma:trop_pcbc_game}
If $A_{ij} \neq B_{ij}$ for all $i,j$, and $W$ is defined as in Condition~\eqref{item:cond1} of Assumption~\ref{ass:model}, then the initial state $n$ is winning in the game with matrices $A, B$ if, and only if, $\tropPCBC(W_{[m] \times [n-1]}, W_{[m] \times \{n\}})$ returns ``Non-empty''.
\end{lemma}

\begin{proof}
Given $a, b, c, d \in \trop$ such that $a \neq c$, it can be easily proved that the inequality $\max(a + x_1, b) \geq \max(c+x_1, d)$ over $x_1$ is equivalent to $b \geq \max(c+x_1,d)$ if $a < c$, and $\max(a+ x_1, b) \geq d$ if $a > c$. Using this principle, we deduce that the two systems $A_{[m] \times [n-1]} \tdot x \tplus A_{[m] \times \{n\}} \geq B_{[m] \times [n-1]} \tdot x \tplus B_{[m] \times \{n\}}$ and $W_{[m] \times [n-1]}^+ \tdot x \tplus W_{[m] \times \{n\}}^- \geq W_{[m] \times [n-1]}^- \tdot x \tplus W_{[m] \times \{n\}}^-$ are equivalent. As a result, by~\cite[Theorem~3.2]{AkianGaubertGuterman2012}, the initial state $n$ is winning if, and only if, the tropical polyhedron defined by the latter system is non-empty. This provides the expected result, thanks to the first part of Proposition~\ref{prop:trop_pcbc}.
\end{proof}

Finally, Condition~\eqref{item:cond2} is the tropical counterpart of the non-degeneracy assumption used in~\cite{AdlerKarpShamir87} to establish the average-case complexity bound.

We point out that the set of matrices $A, B$ which do not satisfy the requirements stated in Conditions~\eqref{item:cond1} and~\eqref{item:cond2} has measure zero. As a consequence, these two conditions do not impose important restrictions on the distribution of $A, B$, and they can rather be understood as genericity conditions.

We are now ready to establish our polynomial bound on the average-case complexity of mean payoff games.
\begin{theorem}\label{th:game_complexity}
Under a distribution satisfying Assumption~\ref{ass:model}, $\tropPCBC$ determines in polynomial time on average whether an initial state is winning for Player Max in the mean payoff game with payment matrices $A, B$.
\end{theorem}

\begin{proof}
Without loss of generality, we assume that the initial state is the circle node $n$.

Let us fix two payment matrices $A, B$ satisfying Conditions~\eqref{item:cond1} and~\eqref{item:cond2} of Assumption~\ref{ass:model}, and let $W$ as defined in Condition~\eqref{item:cond1}. Starting from the pair $(A, B)$ of matrices, the successive applications of row/column exchange operations precisely yield $2^{m+n-1}$ different pairs of matrices. In particular, without loss of generality, we can assume that the $n$-th columns of $A$ and $B$ have not been switched. Then, the pair of matrices that we obtained are of the form $(A_{s,s'}, B_{s, s'})$, where $s \in \{\unit, \tminus \unit\}^m$, $s' \in \{\unit, \tminus \unit\}^{n-1}$, and $A_{s,s'}$ and $B_{s,s'}$ are the matrices obtained from $A$ and $B$ respectively, by exchanging the rows $i$ and the columns $j$ such that $s_i = \tminus \unit$ and $s'_j = \tminus \unit$. The $(i,j)$-entries of $A_{s,s'}$ and $B_{s,s'}$ are distinct, and so we can define a matrix $W_{s,s'}$ in the same way we have built $W$ from $A$ and $B$. Observe that $(W_{s,s'})_{[m] \times [n-1]} = S \tdot W_{[m] \times [n-1]} \tdot S'$ and $(W_{s,s'})_{[m] \times \{n\}} = S \tdot W_{[m] \times \{n\}}$, where $S := \tdiag(s_1, \dots, s_m)$ and $S' := \tdiag(s'_1, \dots, s'_{n-1})$. Thus, by Lemma~\ref{lemma:trop_pcbc_game}, the $2^{m+n-1}$ games obtained by the successive flipping operations can be solved by calling the algorithm $\tropPCBC(S \tdot W_{[m] \times [n-1]} \tdot S', S \tdot W_{[m] \times \{n\}})$.

Let $\bo W \in \sval^{-1}(W)$ be a fixed lift of $W$. Thanks to Condition~\eqref{item:cond2}, no minor of $\bo W$ is null. Besides, as explained in Remark~\ref{remark:eps}, we do not explicitly manipulate the scalar $\eps$ in the algorithm $\tropPCBC$. Instead, we use a symbolic technique which simulates the behavior of the tropical shadow-vertex rule for any choice of $\eps$ small enough. This ensures that for all $\bm \eps \in \sval^{-1}(\eps)$, the conditions of Theorem~\ref{th:adler} are satisfied on the instance $(\bo W_{[m] \times [n-1]}, \bo W_{[m] \times \{n\}})$. Note that the $2^{n+m-1}$ instances  $(\bo S \bo W_{[m] \times [n-1]} \bo S', \bo S \bo W_{[m] \times \{n\}})$, where $\bo S, \bo S'$ are diagonal matrices with diagonal coefficients in $\{\pm 1\}$, are respectively lifts of the instances $(S \tdot W_{[m] \times [n-1]} \tdot S', S \tdot W_{[m] \times \{n\}})$. Thanks to the second part of Proposition~\ref{prop:trop_pcbc} and Theorem~\ref{th:adler}, it follows that the total number of visited basic points when calling the algorithm $\tropPCBC(S \tdot W_{[m] \times [n-1]} \tdot S', S \tdot W_{[m] \times \{n\}})$ for all $s \in \{\unit, \tminus \unit\}^m$, $s' \in \{\unit, \tminus \unit\}^{n-1}$ is bounded by $O(2^{m+n-1} \min(m^2, n^2))$. Moreover, every iteration of the tropical simplex algorithm at Line~\lineref{line:simplex} of $\tropPCBC$ consists in determining the leaving variable returned by the tropical shadow-vertex rule, and pivoting to the next basis or computing the point $\bar{x}'$. The complexity of the former step is $O(n^3)$ by the second part of Theorem~\ref{th:gs_trop}, and the complexity of the latter step is $O(m n(m + n^2))$. Hence, every iteration is polynomial time. In total, solving the $2^{m+n-1}$ games associated with the matrices $(A_{s,s'}, B_{s,s'})$ can be done in time $O(2^{m+n-1} m n(m + n^2) \min(m^2, n^2))$.

Let $T$ be the random variable corresponding to the time complexity of our method to solve the game with payment matrices $A,B$ drawn from a distribution satisfying Assumption~\ref{ass:model}. Similarly, given $s \in \{\unit, \tminus \unit\}^m$, $s' \in \{\unit, \tminus \unit\}^{n-1}$, let $T_{s,s'}$ be the random variable representing the time complexity to solve the game with matrices $A_{s,s'}, B_{s,s'}$, where $A, B$ are drawn from the latter distribution. Thanks to Condition~\eqref{item:cond3}, $\mathbb{E}[T] = \mathbb{E}[T_{s,s'}]$ for all $s,s'$, and so:
\[
\mathbb{E}[T] = \frac{1}{2^{m+n-1}} \times \mathbb{E} \Big[\sum_{s,s'} T_{s,s'}\Big] \leq \frac{1}{2^{m+n-1}} \times (K 2^{m+n-1} m n(m + n^2) \min(m^2, n^2))
\]
for a certain constant $K > 0$. This concludes the proof.
\end{proof}

\section{Conclusion}

We have defined a tropical analogue of the shadow-vertex simplex algorithm, and shown that every iteration has polynomial time complexity. As a corollary, we have established a polynomial-time average-case result on mean payoff games, based on the analysis of Adler, Karp and Shamir of the classical shadow-vertex algorithm.
The main restriction of the model is the flip invariance property. It is an open question whether the tropical approach can be applied with other probabilistic models. In particular, it would be interesting to transfer smoothed complexity results, \eg~\cite{SpielmanTeng2004}, to the tropical setting.
The results of Section~\ref{sec:shadow_vertex} also suggest that there is a general method to tropicalize any semi-algebraic pivoting rule, based on the characterization of the Newton polytopes involved. This will be addressed in a future work.

\subsubsection*{Acknowledgments.} The authors thank the anonymous reviewers for their helpful comments which contributed to improve the presentation of the paper. We also thank Michael Joswig for many insightful discussions.

\bibliographystyle{alpha}
\newcommand{\etalchar}[1]{$^{#1}$}

config: arxiv


text:
\section{Construction of the Set $K$}

We now begin the proof of Theorem \ref{main}.  It is based
on the following lemma.

\begin{lemma}\label{flag}
In the situation of Theorem \ref{main}, there exist a covector
$l \in \Delta$ (which we regard as a map $l : X \to \C$), a
complete linear flag $\{ p \} = F_0 \subset F_1 \subset \dots
\subset F_d = X$, a closed ball $B \subset X$ around $p$, and an
algebraic Whitney stratification $\cX$ refining $\cS$, such that
the following three conditions hold.

(i)   For $S \in \cX$, if $p \notin \bar S$ then $\bar S \cap B =
\emptyset$.

(ii)  Let $Q_i = X / F_{d-i}$ and $\pi_i : V \to Q_i$ be the
projection.  Then for every $S \in \cX$ of dimension $i > 0$, the
map $\pi_{i - 1} \oplus l : S \cap B \to Q_{i - 1} \oplus \C$
has full rank.

(iii) Let $X_i$ be the union of all $S \in \cX$ with $\dim S
\leq i$.  Then for every $i = 1, \dots, d$, the intersection
$X_i \cap F_{d - i + 1} \cap \ker l \cap B = \{ p \}$.
\end{lemma}

Assuming Lemma \ref{flag} for the moment, we take $f$ in Theorem
\ref{main} to be the real part of the covector $l$, and we let the
ball $B$ to be the same as in the lemma.
We now describe the subset $K \subset B$.  It is defined as a union
$K = K^+ \cup K^-$, where $K^+$ and $K^-$ are constructed inductively.
Let $K^+_0 = K^-_0 = \{ p \}$.  Suppose now $1 \leq i \leq d$, and the
sets $K^\pm_{i-1}$ have been constructed.  We set
$$K^+_i = \{x \in X_i \cap B \,|\, \im l (x) = 0 \;\&\;\exists\; y \in
K^+_{i-1}: \pi_{i - 1} (x) = \pi_{i - 1} (y), \, f(x) \geq f(y)\},$$
$$K^-_i = \{x \in X_i \cap B \,|\, \im l (x) = 0 \;\&\;\exists\; y \in
K^-_{i-1}: \pi_{i - 1} (x) = \pi_{i - 1} (y), \, f(x) \leq f(y)\},$$
where $\im l : X \to \R$ is the imaginary part of $l$.  Lastly, we set
$K^\pm = K^\pm_d$.  It is clear that $K$ is a closed, real
semi-algebraic subset of $B$.

\begin{lemma}  With these definitions, conditions (i) and (ii) of
Theorem \ref{main} are satisfied.
\end{lemma}

\noindent
{\bf Proof:}  To check condition (i), note that $K^\pm \cap X_i =
K^\pm_i$.  We now prove by induction on $i$ that $\dim^{}_\R K^\pm_i
\leq i$.  Indeed, case $i = 0$ is trivial, and the induction step
follows from the definition of $K^\pm_i$ and condition (ii) of Lemma
\ref{flag}.

To check condition (ii), we argue by contradiction.  Suppose the set
$K^+ \cap f^{-1} (0)$ is larger than $\{ p \}$ (the case of $K^-$ is
of course analogous).  Let $i$ be the smallest integer such that
$K^+_i \cap f^{-1} (0)$ contains a point $x \neq p$.  By construction,
there is a $y \in K^+_{i-1}$ with $\pi_{i - 1} (x) = \pi_{i - 1} (y)$
and $f(x) \geq f(y)$.  By the minimality of $i$, we must have $y = p$
and, therefore, $x \in F_{n - i + 1}$.  But $x$ is also in $\ker l$,
since $\re l(x) = 0$ by assumption and $\im l (x) = 0$ by the
construction of $K^+_i$.  Thus we have a contradiction with condition
(iii) of Lemma \ref{flag}.
\hfill$\Box$

\vspace{.1in}

\noindent
{\bf Proof of Lemma \ref{flag}:}  Without loss of generality, we can
assume that every stratum of $\cS$ is connected (i.e., irreducible).
All stratifications in this proof will have connected strata, so we
can refer to ``the generic point of a stratum'' with no ambiguity.
We proceed inductively, starting with $i = 1$ and going up to $i = d$,
to construct the following four things:

$\;\, \bullet \;$  the $i$-plane $F_i \subset V$;

$\;\, \bullet \;$  the set $X_{d-i} \subset X$;

$\;\, \bullet \;$  a covector $l_i \in \Delta$;

$\;\, \bullet \;$  an (algebraic, Whitney) refinement $\cX_i$ of the
stratification $\cS$.

\noindent
When the process is complete, we will take $l = l_d$ and $\cX = \cX_d$.
After the $i$-th step of the construction, the following conditions will
be satisfied:

(1)  $X_{d-i}$ is the union of $S \in \cX_i$ with $\dim S \leq d - i$;

(2)  $\dim X_{d-i} \cap \ker l_i \leq d-i-1$;

(3)  if $i > 1$, every $S \in \cX_{i-1}$ with $\dim S \geq d - i + 2$ is
also a stratum of $\cX_i$;

(4)  if $i > 1$, we have $l_i|^{}_{F_i} = l_{i-1}|^{}_{F_i}$;

(5)  $p$ is an isolated point of $F_i \cap X_{d-i}$;

(6)  for every $S \in \cX_i$ with $\dim S = d - i$ and $p \in \bar S$,
the projection $\pi_{d-i} : S \to Q_{d-i}$ \\
has full rank near $p$;

(7)  $p$ is an isolated point of $F_i \cap X_{d-i+1} \cap \ker l_i$;

(8)  for every $S \in \cX_i$ with $\dim S = d - i + 1$ and
$p \in \bar S$, the map \\
$\pi_{d-i} \oplus l_i: S \to Q_i \oplus \C$ has full rank near $p$.

\noindent
Note that (3) and (4) ensure that (7) and (8) will continue to hold if
we replace $l_i$ by $l_d$ and $\cX_i$ by $\cX_d$.  Thus, our
construction will prove the lemma.

As a base step of the induction, we take $\cX_1 = \cS$, so $X_{d - 1}$
is the union of all but the largest stratum of $\cS$.  Let $C(X_{d-1})$
be the normal cone of $X_{d - 1}$ at $p$.  We take $F_1$ to be any line
not contained in $C(X_{d-1})$, and $l_1$ to be any covector in $\Delta$
which does not vanish on $F_1$.  Conditions (1)--(8) for $i = 1$ are
clearly satisfied.

Assume now $i > 1$, and the first $i-1$ steps of the construction have
been completed.  To select the plane $F_i$, we consider two cones in
$Q_{d-i+1} = X / F_{i-1}$.  First, let $X'_{d-i}$ be the union of all
$S \in \cX_{i-1}$ with $\dim S \leq d - i$, and let $C_1$ be the normal
cone of the image $\pi_{d-i+1} (X'_{d-i})$ at $p$.  It is a proper,
closed cone in $Q_{d-i+1}$.  Second, let $C_2$ be the normal cone at $p$
of $\pi_{d-i+1} (\ker l_{i-1} \cap X_{d-i+1})$.  By part (2) of the
induction hypothesis, this too is a proper, closed cone in $Q_{d-i+1}$.
We now choose any line $L \subset Q_{d-i+1}$ not contained in
$C_1 \cup C_2$, and set $F_i = \pi_{d-i+1} (L) \subset V$.  This also
defines the projection $\pi_{d-i} : V \to Q_{d-i}$.  Let $\Sigma$ be the
set of all $S \in \cX_{i-1}$ with $\dim S = d - i + 1$ and $p \in \bar S$.

\vspace{.1in}

\noindent
{\bf Claim 1:}  For every $S \in \Sigma$, the map
$\pi_{d-i} \oplus l_{i-1}: S \to Q_{d-i} \oplus \C$
has full rank at the generic point of $S$.

\vspace{.1in}

\noindent
{\bf Proof:}  Suppose the claim is false.  Consider the intersection
$\Gamma = F_i \cap S$.  By part (6) of the induction hypothesis,
there is an open neighborhood $U \subset X$ of $p$, such that $\Gamma
\cap U$ is a smooth curve, cut out transversely as the zero set of
$\pi_{d-i}|^{}_{S \cap U}$.  By part (5) of the induction hypothesis,
and because the line $L$ in the construction of $F_i$ was chosen not to
lie in the cone $C_1$, we have $p \in \bar \Gamma$.  Further, since $L$
was also chosen not to lie in the cone $C_2$, we can assume that there
are no critical points of $l_{i-1}|^{}_\Gamma$ in $U$.  This means that
the map $\pi_{d-i} \oplus l_{i-1}: S \to Q_{d-i} \oplus \C$ has full
rank at every point of $\Gamma \cap U$.
\hfill$\Box$

\vspace{.1in}

For $S \in \Sigma$, let $S^\circ$ be the part of $S$ where the map
$\pi_{d-i} \oplus l_{i-1}: S \to Q_{d-i} \oplus \C$ has full rank.
We set
$$X_{d-i} = X'_{d-i} \cup \bigcup_{S \in \Sigma} S \setminus S^\circ.$$
It is clear from the proof of Claim 1 that condition (5) is satisfied.

\vspace{.1in}

\noindent
{\bf Claim 2:}  Let $S \in \Sigma$, and let $T \subset S \setminus
S^\circ$ be an irreducible, smooth, locally closed subvariety with
$\dim T = d - i$ and $p \in \bar T$.  Then the restriction
$\pi_{d-i}|^{}_T$ has full rank at the generic point of $T$.

\vspace{.1in}

\noindent
{\bf Proof:}  Suppose the claim is false.  Then we have
$\dim \pi_{d-i} (\bar T) < d-i$.  Therefore, every fiber of
$\pi_{d-i}|^{}_{\bar T}$ must have positive dimension at every point.
But it is clear from the proof of Claim 1 that $p$ is an isolated
point of $F_i \cap \bar T$.
\hfill$\Box$

\vspace{.1in}

We are now ready to describe the stratification $\cX_i$.  We take every
stratum $S \in \cX_{i-1}$ with $\dim S > d-i$ and $S \notin \Sigma$ to
be also a stratum of $\cX_i$.  This ensures that conditions (1) and (3)
are satisfied.  For $S \in \Sigma$, we take each irreducible component
of $S^\circ$ to be a stratum of $\cX_i$.  It remains to stratify the
set $X_{d-i}$.  By Claim 2, this can be done in such a way that the
resulting stratification $\cX_i$ is a Whitney refinement of $\cX_{i-1}$,
and condition (6) is satisfied.

The last thing to construct is the covector $l_i$.  To satisfy condition
(2) we must ensure that $l_i$ does not vanish identically on any of the
$(d-i)$-dimensional strata of $\cX_i$.  We take $l_i = l_{i-1} + h \circ
\pi_{d-i}$, where $h : Q_{d-i} \to \C$ is a small linear functional in
general position.  It is easy to check using condition (5) that, for a
suitable choice of $h$, we will have $l_i \in \Delta$ and condition (2)
will hold.

This completes the construction of the quadruple $\{ F_i, X_{d-i}, l_i,
\cX_i\}$.  We have already remarked that conditions (1), (2), (3), (5),
and (6) are satisfied.  Condition (4) is clear from the definition of
$l_i$.  Condition (7) follows from the fact that the line $L$ in the
construction of $F_i$ was chosen not to lie in the cone $C_2$, combined
with condition (4) and part (5) of the induction hypothesis.  Finally,
condition (8) follows from the definition of the loci $S^\circ$
($S \in \Sigma$), again combined with condition (4).
\hfill$\Box$


TITLE: Modules that allow an infinite exact sequence on them
QUESTION [2 upvotes]: I'm looking for a characterization of modules that fit the following property:
(*) There's an infinite exact sequence with $\phi_i \neq 0 \space \forall i\in I $
$\require{AMScd}$
\begin{CD}\cdots @>{\phi_i}>>\mathbb{M} @>{\phi_i+1}>> \mathbb{M}  @>{\phi_i+2}>> \cdots \\\end{CD}
I thought about the case of vector spaces and about factor rings $\mathbb{Z}/n\mathbb{Z}$:

For vector spaces V with $dim(V)=1$ it's impossible, but possible for $dim(V)>1$ (Might hold for free modules in general)
For $\mathbb{Z}/n\mathbb{Z}$ it's possible with 1 function, if n is square, with 2 functions as long as n ist not prime and impossible if n is prime.

But that's far from general... I'm also interested if the number of different functions has a deeper meaning.
Thanks in advance.

REPLY [2 votes]: For any two nonzero $R$-modules $A$ and $B$, the maps
$$f(a,b)=(a,0), \quad g(a,b)=(0,b) $$
compose to zero, and moreover the sequence
$$ \cdots \to A \oplus B \xrightarrow{f} A \oplus B \xrightarrow{g} A \oplus B \xrightarrow{f} A \oplus B \to \cdots $$
is exact. This works for any ring, so indeed, if you allow rank at least $2$, this can always happen. Now if you want rank $1$, as you note, you can't allow $R$ to be a field. Indeed if $R$ is even an integral domain, there is no hope of composing two nonzero maps $R\to R$ to get zero. On the other hand, if $R$ is commutative but has zero divisors, you can still concoct an infinite exact sequence.


TITLE: Algebra where operators are assumed as variables.
QUESTION [4 upvotes]: Does there exists any form of Algebra where operators can be assumed as variables?
For example:
$$
1+2\times3=7
$$
can be considered as:
$$
1\:(\mathrm{\,X})\:2\:(\mathrm{Y})\:3=7
$$
?

REPLY [2 votes]: I would say the answer is most definitely yes, if you construe the operators to be functions.  For example, we could represent the "operator" $+$ (on $\mathbb{Z}$, the integers, for example) to be the function $p: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ given by $p(z_1, z_2) = z_1 + z_2$ for $(z_1, z_2) \in  \mathbb{Z} \times \mathbb{Z}$; likewise the "operator" * would be a function $t: \mathbb{Z} \times \mathbb{Z} \to \mathbb{Z}$ such that $t(z_1, z_2) = z_1*z_2$; with these conventions, the equation $1 + 2*3 = 7$ would be written $p(1, t(2, 3)) = 7$.  Now observe that $p$ and $t$ are "merely" elements of the set $\mathcal{F}$ of functions from $\mathbb{Z} \times \mathbb{Z}$ to $\mathbb{Z}$; letting $f_1, f_2$ denote variables ranging over the set $\mathcal{F}$, we see that our expression $p(1, t(2, 3))$ in fact corresponds to letting $f_1 = p$ and $f_2 = t$; clearly many other such choices are possible, though most of them would yield an $f_1(1, f_2(2, 3))$ which is more difficult to compute!  But in fact a similar paradigm occurs over and over again in certain areas of mathematics.
One problem which might be encountered in this approach is that of parsing an expression like $1(X)2(Y)3$ into appropriate functional form, how to group the elements and so forth.  But I'll leave that discussion for future research and questions!
Hope this helps!  Cheers, Bob Lewis.

REPLY [2 votes]: Absolutely! In abstract algebra, you study general operations, besides $+$ and $\times$, that satisfy certain identities. An example of an identity is your equation $1\mathop X (2\mathop{Y}3)=7$. This equation constrains the variables $X$ and $Y$, subject to the constants 1, 2, 3, and 7. So you could say that $X={+}$ and $Y={\times}$ is a "solution" to the equation, whereas $X={\times}$ and $Y={+}$ is not a solution. However, unless you're working with differential equations, I don't think that terminology is very common. Usually you would give a name to a kind of operation that satisfies a given identity. For example, an operation $\circ$ is called commutative if $a\circ b = b\circ a$ for all $a$ and $b$. Then you would say that addition is commutative, but subtraction is not commutative.
In universal algebra, you go even further and treat the identities themselves as variables! From this viewpoint, you can consider all possible sets of identities and their interrelationships. I'm horribly rusty, so please don't ask me to expand on this idea. :)


TITLE: Stochastic Processes & Poisson Process
QUESTION [0 upvotes]: Starting at time t = 0, a ferry service that carries cars across a river. The ferry holds c > 1
cars and waits at the dock until the ferry is full. At that time, the ferry departs and a new
ferry immediately appears and begins waiting and loading newly arriving cars. Cars arrive
as a Poisson process of rate lambda = 0.2 cars per minute.
At time t, let K(t) denote the number of cars on the waiting ferry.
Q1: A car arrives at time t. At time t-, the instant before the arrival, let K = K(t-) denote the number of cars on the waiting ferry. What is the conditional expected time E [T|K = k] the car will wait?
I do not have any idea as to how to solve this question. It will be helpful if someone can give me some pointers to the way to solve this question.
Q2: D(t) is the number of ferries that have departed by time t. TRUE or FALSE: D(t) is a Poisson process. Explain.
According to me it is not a Poisson process because random variables generated for this process will not be independent as when the first ferry leaves then only second ferry arrives and cars starts loading. Correct me if I am wrong.

REPLY [0 votes]: Q2: I would say that D(t) is a mean/expected value at time t. Given Central limit theorem, D(t) comes from Normal distribution and hence is not a Poisson process.