Source-linked AI summary
Tropical polyhedra are equivalent to mean payoff games
Marianne Akian, Stephane Gaubert, Alexander Guterman
TL;DR
The paper asks how decision problems in max-plus and tropical convexity relate to zero-sum game problems. It establishes correspondences using non-linear Perron-Frobenius methods, showing that tropical polyhedra represent finite-action deterministic games and that associated polyhedra determine winning positions. The results also connect tropical rank with tropical linear independence and provide explicit representations of game potentials.
Problem
The paper addresses tropical feasibility, tropical polyhedron emptiness, and tropical linear dependence, including their computational relationship to mean payoff games.
Method
The authors use non-linear Perron-Frobenius theory to connect tropical convex sets with mean payoff games, with Kohlberg’s theorem handling the polyhedral setting.
Results
The paper establishes equivalences between tropical decision problems and mean payoff games, and gives an explicit representation of the bias or potential vectors certifying nonnegative or nonpositive game values.
Takeaways & Limitations
Tropical algebra problems can be addressed with game-theoretic algorithms, while tropical structures can transfer results and certificates back to mean payoff games.
Takeaways & Limitations
Computing tropical rank is NP-hard, although checking whether rank is at most k is polynomial-time and some near-maximal-rank cases reduce to mean payoff games.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper studies decision problems in tropical algebra and connects them to mean payoff games. Its results use non-linear Perron-Frobenius theory to relate tropical feasibility, game winning positions, and tropical linear dependence.
- Problems: The paper formulates three problems: tropical cone non-triviality, tropical polyhedron emptiness, and tropical linear dependence.The first two concern tropical convex sets; the third asks whether matrix columns are tropically dependent.
- Game correspondence: Tropical polyhedra represented by inequalities correspond to mean payoff games, with polyhedral cases yielding finite action spaces.More general tropical convex cones correspond to games with infinite action spaces, including stochastic mean payoff games.
- Main results: The decision problems are polynomial-time equivalent to mean payoff game problems, and tropical linear dependence reduces to a mean payoff game problem.This establishes a two-way connection between tropical algebraic decision problems and game-theoretic methods.
- Proof strategy: Non-linear Perron-Frobenius theory handles infinite coordinates and infinite inequality systems, while Kohlberg’s theorem supports the polyhedral case.The approach characterizes tropical feasibility through the existence of winning initial states in an associated game.
- Consequences: The paper transfers structure in both directions: game algorithms can solve tropical problems, while tropical polyhedra explicitly represent game bias or potential vectors.These vectors certify that a mean payoff game has a nonnegative or nonpositive value.
- Tropical rank: Tropical linear independence of matrix columns is equivalent to the existence of a tropically non-singular square submatrix, while computing tropical rank remains NP-hard.Checking whether tropical rank is at most k is polynomial-time, and near-maximal-rank cases reduce to mean payoff games.
2. Preliminary results
This section defines the tropical and mean-payoff-game framework, establishes the associated dynamic-programming operators, and states spectral and strategic results for finite-action games.
- Game correspondence: The framework allows infinite action sets and includes stochastic mean payoff games, while tropical polyhedral cones correspond precisely to finite state spaces.The paper associates infinite systems of inequalities with games having infinite action sets.
- Tropical cones: Tropical cones are represented by systems of inequalities, with polyhedral cones arising when the inequality index set is finite.The associated matrices have entries in the max-plus semiring, whose addition is maximum and multiplication is ordinary addition.
- Mean payoff games: The associated zero-sum game alternates between states in the inequality index set and variable states, with matrix entries determining available moves and payments.For finite systems, this game is represented by a weighted bipartite directed graph.
- Mean payoff: Under the stated availability assumptions, finite-horizon game values exist, and the mean-payoff value is defined as the asymptotic average payment per turn.The asymptotic growth rate χ(f) exists for the dynamic-programming operator.
- Dynamic programming: The paper uses order-preserving, additively homogeneous dynamic-programming maps and their associated tropical linear operators to analyze game values.The operator B is induced by the reward kernel, while A and its residuated operator provide the corresponding inequality machinery.
- Spectral and strategic results: The Collatz-Wielandt framework identifies the asymptotic growth rate with spectral quantities and yields positional strategies certifying lower and upper mean-payoff bounds.For finite action sets, positional strategies characterize the value, and the maximizing one-player problem can be solved in polynomial time via maximal circuit mean.
3. The correspondence between tropical convexity and mean payoff games
The paper establishes a correspondence between tropical inequality systems and mean payoff games, identifying tropical-polyhedral feasibility and winning positions through nonlinear Perron–Frobenius methods.
- Game association: The system Ax ⩽Bx is associated with the mean payoff game whose dynamic programming operator is f = A♯B.This construction underlies the correspondence between tropical polyhedral cones and games.
- Scope and method: The approach extends beyond finite systems and coordinates, covering infinite inequality systems and infinite action spaces while retaining a nonlinear Perron–Frobenius proof strategy.For polyhedral sets, the associated action spaces become finite; integer feasibility also preserves the finite-coordinate support pattern.
- Game association: Theorem 3.2 identifies the support of the tropical cone P with the initial states having a nonnegative game value.The support is also the maximal support of an element of P.
- Finite systems: For finite systems, Ax ⩽Bx has a finite solution exactly when every initial state of the associated game has nonnegative value.This is the full-support specialization of the support correspondence.
- Affine polyhedra: An affine tropical polyhedron is nonempty exactly when the associated game has nonnegative value from its added initial state n + 1.Affine inequalities are converted to a cone by appending a coordinate encoding the constants.
- Converse reduction: Conversely, threshold questions about a game state’s value reduce to nonemptiness of a tropical polyhedron, making tropical emptiness and prescribed-state winning equivalent problems.The correspondence applies to inequalities χr(f) ⩾ λ and to the decision problems stated in Corollary 3.7.
4. Mean payoff games expressing tropical linear independence
The paper extends tropical linear algebra to an extended semiring and connects tropical linear independence with mean payoff game conditions. This connection yields equivalent characterizations through game operators, inequalities, and tropically nonsingular submatrices.
- Extended tropical semiring: The extended tropical semiring distinguishes whether a maximum is attained once, at least twice, or at −∞.Real and ghost elements encode these attainment patterns, while the construction extends the basic max-plus setting.
- Tropical linear dependence: Tropical linear dependence is defined by a nonzero vector whose matrix product balances to zero in the extended semiring.For matrices injected from Rmax, this means each relevant maximum is attained at least twice or equals −∞.
- Permanents and nonsingularity: Tropical linear independence is controlled by permanents, whose projection gives the optimal assignment value and whose type records whether the optimum is unique.A matrix is tropically nonsingular exactly when its permanent is invertible, corresponding to a unique optimal assignment in the max-plus case.
- Game operator: Under the no-ghost-column assumption, the matrix induces a min-max operator f whose inequalities characterize tropical dependence and game behavior.The operator is defined coordinatewise by minimizing over incident rows and maximizing over alternative columns.
- Nonsingular certificates: For m ⩾ n, tropical linear independence of the columns is equivalent to the existence of an n × n tropically nonsingular submatrix.The result transfers the game characterization to a permanent-based certificate of independence.
- Game-theoretic equivalence: The columns of A are tropically independent if and only if the associated mean payoff game has no winning state for Player Max.Equivalent conditions include a negative cycle mean and the nonexistence of a nontrivial vector u satisfying u ⩽ f(u).
0. Since F adj
The paper derives rank consequences from the game characterization of tropical independence. It proves that row rank, column rank, and tropical rank coincide, while fixed-rank threshold tests reduce to mean payoff games.
- Assignment certificate: The game inequalities select minimizing rows and induce assignment structure through an injective choice of row indices.The resulting selected submatrix has a unique optimal assignment and is therefore tropically nonsingular.
- Dependence bounds: Any m + 1 vectors in T_e^m are tropically linearly dependent.This is obtained by applying the nonsingular-submatrix characterization to an m × (m + 1) matrix.
- Rank equivalence: The maximal numbers of tropically independent rows and columns equal the maximal size of a tropically nonsingular submatrix.Transposing the matrix transfers the column result to rows.
- Tropical rank: Over Rmax, tropical rank, maximal row rank, and maximal column rank coincide.Tropical rank is defined as the largest size of a tropically nonsingular submatrix.
- Algorithmic consequences: For fixed k, testing whether tropical rank is at least n − k reduces to solving a polynomial number of mean payoff game problems.The reduction checks every subset of n − k columns for tropical independence and is pseudo-polynomial for fixed k.
- Complexity boundary: Computing tropical rank in general is NP-hard, although checking whether rank is below a fixed threshold k is polynomial via singular k × k submatrices.The paper notes that the difficulty may concentrate on intermediate-rank instances.
- Geometric example: In the geometric example, a tropical hyperplane contains points a, b, c, d, but no tropical hyperplane contains those five points together with e.The associated power algorithm reaches the fixed point (0, −2, −1), whose coefficients determine the half-space containing a, b, c, d.