Tropical polyhedra are equivalent to mean payoff games

Abstract

We show that several decision problems originating from max-plus or tropical convexity are equivalent to zero-sum two player game problems. In particular, we set up an equivalence between the external representation of tropical convex sets and zero-sum stochastic games, in which tropical polyhedra correspond to deterministic games with finite action spaces. Then, we show that the winning initial positions can be determined from the associated tropical polyhedron. We obtain as a corollary a game theoretical proof of the fact that the tropical rank of a matrix, defined as the maximal size of a submatrix for which the optimal assignment problem has a unique solution, coincides with the maximal number of rows (or columns) of the matrix which are linearly independent in the tropical sense. Our proofs rely on techniques from non-linear Perron-Frobenius theory.

28 pages, 5 figures; v2: updated references, added background materials and illustrations; v3: minor improvements, references updated

References in corpus (5)

• Duality and separation theorems in idempotent semimodules
• The Minkowski Theorem for Max-plus Convex Sets
• Minimal half-spaces and external representation of tropical polyhedra
• The number of extreme points of tropical polyhedra
• The tropical analogue of polar cones

Cited by in corpus (27)

• Tropicalizing the simplex algorithm
• Tropical linear-fractional programming and parametric mean payoff games
• The Perron-Frobenius theorem for multi-homogeneous mappings
• Weighted digraphs and tropical cones
• Pure Dimension and Projectivity of Tropical Polytopes
• A multidimensional tropical optimization problem with nonlinear objective function and linear constraints
• The level set method for the two-sided eigenproblem
• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
• Combinatorial simplex algorithms can solve mean payoff games
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Tropical optimization problems with application to project scheduling with minimum makespan
• Novel Stability Conditions for Nonlinear Monotone Systems and Consensus in Multi-Agent Networks
• Parametric shortest-path algorithms via tropical geometry
• Quantitative Simulations by Matrices
• Presentations of Transversal Valuated Matroids
• Algebraic solutions of tropical optimization problems
• Approximating the Volume of Tropical Polytopes is Difficult
• The tropical analogue of the Helton-Nie conjecture is true
• The Gaussian entropy map in valued fields
• Tropical Gaussians: A Brief Survey
• Multivariate volume, Ehrhart, and $h^{\ast }$-polynomials of polytropes
• The tropical shadow-vertex algorithm solves mean payoff games in polynomial time on average
• Spectral inequalities for nonnegative tensors and their tropical analogues
• On max-plus two-sided linear systems whose solution sets are min-plus linear
• Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games
• Using matrix sparsification to solve tropical linear vector equations
• Convex geometry over ordered hyperfields