TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES

DOI10.1142/S0218196711006674zbMath1239.14054arXiv0912.2462OpenAlexW3099589436MaRDI QIDQ2882394

Marianne Akian, Stéphane Gaubert, Alexander E. Guterman

Publication date: 4 May 2012

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0912.2462

zbMATH Keywords

assignment problemPerron-Frobenius theorylinear independencenonexpansive mapstropical algebramean-payoff gamestropical polyhedra

Mathematics Subject Classification ID

Discrete-time games (91A50) Max-plus and related algebras (15A80)

Related Items

Algebraic solutions of tropical optimization problems ⋮ Rank functions of tropical matrices ⋮ Weighted digraphs and tropical cones ⋮ A convergent hierarchy of non-linear eigenproblems to compute the joint spectral radius of nonnegative matrices ⋮ Weakly linear systems for matrices over the max-plus quantale ⋮ On max-plus linear dynamical system theory: the regulation problem ⋮ Tropically convex constraint satisfaction ⋮ Tropicalizing the Simplex Algorithm ⋮ On the coincidence of the factor and Gondran-Minoux rank functions of matrices over a semiring ⋮ Pure dimension and projectivity of tropical polytopes ⋮ Tropical differential equations ⋮ Multivariate volume, Ehrhart, and \(h^\ast \)-polynomials of polytropes ⋮ The level set method for the two-sided max-plus eigenproblem ⋮ Tropical Fourier–Motzkin elimination, with an application to real-time verification ⋮ An algorithm for solving an overdetermined tropical linear system using the analysis of stable solutions of subsystems ⋮ Tropical Gaussians: a brief survey ⋮ Two concepts of singularity for matrices over semirings ⋮ Max-plus approximation for reinforcement learning ⋮ Generic uniqueness of the bias vector of finite zero-sum stochastic games with perfect information ⋮ Solving generic nonarchimedean semidefinite programs using stochastic game algorithms ⋮ A contribution to the determinization of max-plus automata ⋮ When do the \(r\)-by-\(r\) minors of a matrix form a tropical basis? ⋮ Upper and lower bounds for the iterates of order-preserving homogeneous maps on cones ⋮ Perron-Frobenius theorem for nonnegative multilinear forms and extensions ⋮ A characterization of bases of tropical kernels in terms of Cramer's rule ⋮ The Tropical Nullstellensatz and Positivstellensatz for Sparse Polynomial Systems ⋮ Abstract tropical linear programming ⋮ Tropical pseudolinear and pseudoquadratic optimization as parametric mean-payoff games ⋮ Toward a sparsity theory on weighted lattices ⋮ The polyhedral geometry of truthful auctions ⋮ Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria ⋮ The Gaussian entropy map in valued fields ⋮ Tropical combinatorial Nullstellensatz and sparse polynomials ⋮ Presentations of transversal valuated matroids ⋮ Tropical Complementarity Problems and Nash Equilibria ⋮ Computing the vertices of tropical polyhedra using directed hypergraphs ⋮ Tropical optimization problems with application to project scheduling with minimum makespan ⋮ Complexity of solving tropical linear systems ⋮ Tropical linear-fractional programming and parametric mean payoff games ⋮ New algorithms for solving tropical linear systems ⋮ An algorithm for the largest eigenvalue of nonhomogeneous nonnegative polynomials ⋮ Complete solution of tropical vector inequalities using matrix sparsification. ⋮ On the vectors associated with the roots of max-plus characteristic polynomials. ⋮ On two-sided max-linear equations ⋮ Dependence of supertropical eigenspaces ⋮ Matrices with different Gondran-Minoux and determinantal ranks over MAX-algebras ⋮ A note on tropical linear and integer programs ⋮ Tropical effective primary and dual Nullstellensätze ⋮ The tropical analogue of the Helton-Nie conjecture is true ⋮ Max-Closed Semilinear Constraint Satisfaction ⋮ Computing the smallest fixed point of order-preserving nonexpansive mappings arising in positive stochastic games and static analysis of programs ⋮ Approximating the volume of tropical polytopes is difficult ⋮ Tropical polar cones, hypergraph transversals, and mean payoff games ⋮ The \(4\times 4\) minors of a \(5\times n\) matrix are a tropical basis ⋮ Inequalities for Gondran-Minoux rank and idempotent semirings ⋮ Best approximation in max-plus semimodules ⋮ Spectral inequalities for nonnegative tensors and their tropical analogues ⋮ Matrix Invariants over Semirings ⋮ On Solving Mean Payoff Games Using Pivoting Algorithms ⋮ Complexity of deciding whether a tropical linear prevariety is a tropical variety ⋮ Uniqueness of the fixed point of nonexpansive semidifferentiable maps ⋮ Quantitative simulations by matrices ⋮ Submathematics and tropical mathematics ⋮ On the spectrum in max algebra ⋮ On Special Cases of the Generalized Max-Plus Eigenproblem ⋮ Tropical representations and identities of plactic monoids ⋮ Sparse approximate solutions to max-plus equations ⋮ The Perron--Frobenius Theorem for Multihomogeneous Mappings ⋮ The operator approach to entropy games ⋮ An informal overview of triples and systems ⋮ A multidimensional tropical optimization problem with a non-linear objective function and linear constraints ⋮ Parametric Shortest-Path Algorithms via Tropical Geometry ⋮ A strongly polynomial method for solving integer max-linear optimization problems in a generic case ⋮ Complexity of tropical and MIN-plus linear prevarieties

Cites Work

• Unnamed Item
• The number of extreme points of tropical polyhedra
• Minimal half-spaces and external representation of tropical polyhedra
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games
• The Minkowski theorem for max-plus convex sets
• Generators, extremals and bases of max cones
• Hard problems in max-algebra, control theory, hypergraphs and other areas
• Exponential behaviour of the Butkovič-Zimmermann algorithm for solving two-sided linear systems in max-algebra
• The tropical analogue of polar cones
• Convexity and log convexity for the spectral radius
• Positional strategies for mean payoff games
• Eigenvalues of dynamic max-min systems
• The complexity of stochastic games
• Strong regularity of matrices -- a survey of results
• Min-max functions
• The complexity of mean payoff games on graphs
• Duality and separation theorems in idempotent semimodules.
• Maximal minors and their leading terms
• From max-plus algebra to nonexpansive mappings: A nonlinear theory for discrete event systems.
• Max-algebra: The linear algebra of combinatorics?
• Carathéodory, Helly and the others in the max-plus world
• A strongly polynomial algorithm for solving two-sided linear systems in max-algebra
• Tropical convexity via cellular resolutions
• Duality Between Invariant Spaces for Max-Plus Linear Discrete Event Systems
• A Deterministic Subexponential Algorithm for Solving Parity Games
• Cyclic games and an algorithm to find minimax cycle means in directed graphs
• The Tropical Rank of a Tropical Matrix
• Invariant Half-Lines of Nonexpansive Piecewise-Linear Transformations
• The duality theorem for min-max functions
• Topical and sub-topical functions, downward sets and abstract convexity
• Scheduling with AND/OR Precedence Constraints
• Extension of order-preserving maps on a cone
• The Perron-Frobenius theorem for homogeneous, monotone functions
• -convexity
• A constructive fixed point theorem for min-max functions
• Max-Plus $(A,B)$-Invariant Spaces and Control of Timed Discrete-Event Systems
• Stochastic Games with Perfect Information and Time Average Payoff
• Max-plus convex sets and max-plus semispaces. I
• Tropical algebraic geometry
• An operator approach to zero-sum repeated games
• Idempotent functional analysis: An algebraic approach

This page was built for publication: TROPICAL POLYHEDRA ARE EQUIVALENT TO MEAN PAYOFF GAMES