Tropical Polyhedra are Equivalent to mean Payoff Games

Marianne Akian, Stéphane Gaubert, Alexander E. GutermanInt. J. Algebra Comput 2012 · OpenReview

TL;DR

This paper establishes a fundamental equivalence between tropical polyhedra (geometric objects defined by max-plus algebra inequalities) and mean payoff games (strategic games where players aim to maximize their average payoff over infinite turns). This connection allows decision problems about tropical polyhedra to be solved using game theory algorithms, and vice-versa, offering new theoretical and algorithmic insights into both fields.

What Problem Does This Paper Address?

The paper tackles several decision problems in tropical algebra, a mathematical framework based on the "max-plus" semiring. Specifically, it addresses questions like:

  • Is a tropical convex cone non-trivial? (i.e., does it contain any non-trivial solutions?)
  • Is a tropical polyhedron empty? (i.e., does it contain any solutions?)
  • Are a set of vectors tropically linearly dependent?

These problems are crucial for understanding tropical geometry and have applications in areas like discrete event systems and static analysis. While tropical polyhedra can be represented by inequalities, converting these to a more computationally tractable form (like extreme generators) can be exponentially complex. The authors seek a more efficient way to solve these decision problems by leveraging the theory of mean payoff games.

Methods

The core of the paper's contribution lies in establishing a reduction from tropical algebra problems to mean payoff games. They achieve this by:

  • Associating Games to Tropical Structures: They show how tropical convex cones and polyhedra can be naturally represented by mean payoff games. The structure of the game (e.g., finite vs. infinite action spaces) directly corresponds to whether the tropical object is polyhedral or a more general convex cone.
  • Leveraging Game Theory Results: They utilize existing results from mean payoff game theory, particularly those related to Kohlberg's theorem on invariant half-lines and the Collatz-Wielandt property, to analyze the associated games.
  • Non-linear Perron-Frobenius Theory: The proofs heavily rely on techniques from non-linear Perron-Frobenius theory, which provides tools to analyze the spectral properties of operators arising from these games.
  • Extended Tropical Semiring: For problems related to linear independence, they introduce and use an "extended tropical semiring" which can encode information about whether a maximum is attained uniquely or multiple times, a key aspect of tropical linear dependence.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Deep Equivalence: The paper reveals a surprisingly deep and direct equivalence between the existence of solutions to tropical inequalities and the existence of winning strategies in mean payoff games. This is a powerful conceptual link.
  • Algorithmic Bridge: This equivalence acts as an algorithmic bridge, allowing algorithms developed for mean payoff games to be applied to solve problems in tropical algebra, and vice-versa.
  • Tropical Rank and Games: A significant result connects the tropical rank of a matrix (related to its linear independence properties) to the existence of winning states in specific mean payoff games.
  • Extended Tropical Semiring: The introduction of an extended tropical semiring provides a more nuanced algebraic framework to precisely capture tropical linear dependence, going beyond simple max-plus values.

Key Results

  • Problem 1.1 (Tropical Cone Non-triviality): Equivalent to checking if a mean payoff game has at least one winning initial state.
  • Problem 1.2 (Tropical Polyhedron Emptiness): Equivalent to checking if a mean payoff game has a specific winning initial state.
  • Problem 1.3 (Tropical Linear Dependence): Equivalent to checking if a mean payoff game has no winning state.
  • Tropical Rank Characterization: The paper provides game-theoretic characterizations for tropical linear independence and the tropical rank of matrices. For instance, the columns of a matrix are tropically linearly independent if and only if a related mean payoff game has no winning state.

Limitations and Future Work

  • Computational Complexity: While the paper establishes equivalences, the computational complexity of solving the mean payoff games themselves is not the primary focus. The authors mention that existing algorithms for mean payoff games can be applied, and some problems are solvable in pseudo-polynomial time.
  • Generalization: The paper extends results to more general tropical convex sets (not necessarily polyhedral) and uses an extended tropical semiring, suggesting avenues for further research in these more abstract settings.
  • Algorithmic Refinements: The paper hints at power algorithms for checking winning states in mean payoff games, suggesting that specific algorithmic improvements could be derived from the game-theoretic perspective.

Summary updated

BibTeX
@article{akian2012tropical,
  author = {Marianne Akian and Stéphane Gaubert and Alexander E. Guterman},
  title = {{Tropical Polyhedra are Equivalent to mean Payoff Games}},
  journal = {Int. J. Algebra Comput.},
  year = {2012},
  url = {https://openreview.net/forum?id=EeJDM3brEr},
}
Figure