2014/01/01 by Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Computation #Key (lock) #Machine Learning and Algorithms #Optimization and Search Problems #Polynomial #Property (philosophy) #Semiring #Simplex algorithm #Stochastic game #Time complexity #cs.DS #cs.GT #math.OC
paper · pdf · doi:10.1007/978-3-662-43948-7_8
17 pages, 7 figures, appears in 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I
openalex publication_date 2014/01/01 · arxiv created 2014/09/11 · arxiv updated 2014/09/12 · openalex created_date 2016/06/24 · openalex updated_date 2026/08/05
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 (ℝ ∪ \-∞\, 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ücker relations.