The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average

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 $(\mathbb{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.

• Publication year

  2014

• Venue

  International Colloquium on Automata, Languages and Programming

• Publication date

  2014-06-20

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-662-43948-7_8arXiv 1406.5433
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Tropicalizing the Simplex Algorithm

  2013cited by this paper
• Combinatorial Simplex Algorithms Can Solve Mean Payoff Games

  2013cited by this paper
• Two conditions for reducing the maximal length of node-disjoint paths in hypercubes

  2012cited by this paper
• Faster algorithms for mean-payoff games

  2011cited by this paper
• On the equilibria of alternating move games

  2010cited by this paper
• An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it

  2009cited by this paper
• Tropical Polyhedra are Equivalent to mean Payoff Games

  2009cited by this paper
• A Field of Generalised Puiseux Series for Tropical Geometry

  2007cited by this paper
• A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games

  2007cited by this paper
• A deterministic subexponential algorithm for solving parity games

  2006cited by this paper
• Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time

  2001cited by this paper
• A Discrete Strategy Improvement Algorithm for Solving Parity Games

  2000cited by this paper
• Deciding the Winner in Parity Games is in UP \cap co-Up

  1998cited by this paper
• THE DUALITY THEOREM FOR MIN-MAX FUNCTIONS

  1997cited by this paper
• The Complexity of Mean Payoff Games on Graphs

  1996influential reference
• Discriminants, Resultants, and Multidimensional Determinants

  1994cited by this paper
• Cyclic games and an algorithm to find minimax cycle means in directed graphs

  1990cited by this paper
• Linear systems in (max, +) algebra

  1990cited by this paper
• The Simplex Method: A Probabilistic Analysis

  1986cited by this paper
• A Family of Simplex Variants Solving an m × d Linear Program in Expected Number of Pivot Steps Depending on d Only

  1986cited by this paper
• Positional strategies for mean payoff games

  1979cited by this paper

• Strategy Improvement, the Simplex Algorithm and Lopsidedness

  2025cites this paper
• Combinatorial Algorithm for Tropical Linearly Factorized Programming

  2025cites this paper
• Smoothed analysis of deterministic discounted and mean-payoff games

  2024cites this paper
• Scalable Energy Games Solvers on GPUs

  2021cites this paper
• Solving Mean-Payoff Games via Quasi Dominions

  2019cites this paper
• C C ] 1 5 A pr 2 01 7 Checking Dynamic Consistency of Conditional Hyper Temporal Networks via Mean Payoff Games Hardness and ( pseudo ) Singly-Exponential Time Algorithm

  2018cites this paper
• Spectraèdres tropicaux: application à la programmation semi-définie et aux jeux à paiement moyen. (Tropical spectrahedra: Application to semidefinite programming and mean payoff games)

  2018cites this paper
• Special and structured matrices in max-plus algebra

  2017cites this paper
• Complexity in Infinite Games on Graphs and Temporal Constraint Networks. (Complexité dans les Jeux Infinis sur les Graphes et les Réseaux de Contraintes Temporelles)

  2017cites this paper
• Checking Dynamic Consistency of Conditional Hyper Temporal Networks via Mean Payoff Games (Hardness and (pseudo) Singly-Exponential Time Algorithm)

  2016cites this paper
• Dynamic Consistency of Conditional Simple Temporal Networks via Mean Payoff Games: A Singly-Exponential Time DC-checking

  2015cites this paper
• Tropical aspects of linear programming

  2014cites this paper