Skip to Main content Skip to Navigation
Conference papers

Tropicalizing Semialgebraic Pivoting Rules, Or How to Solve Mean Payoff Games in Polynomial Time on Average

Xavier Allamigeon 1, 2 Pascal Benchimol 1, 2 Stephane Gaubert 1, 2
1 MAXPLUS - Max-plus algebras and mathematics of decision
CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique, Inria Saclay - Ile de France
2 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique
Abstract : 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. The proof relies on the observation that certain semi-algebraic pivoting rules can be tropicalized.
Document type :
Conference papers
Complete list of metadata
https://hal.inria.fr/hal-01263357
Contributor : Marianne Akian <>
Submitted on : Wednesday, January 27, 2016 - 4:38:44 PM
Last modification on : Friday, April 30, 2021 - 9:57:58 AM

Identifiers

  • HAL Id : hal-01263357, version 1

Collections

CNRS | X | INSMI | X-CMAP | CMAP | INRIA | TDS-MACS | X-DEP-MATHA | GS-COMPUTER-SCIENCE

Citation

Xavier Allamigeon, Pascal Benchimol, Stephane Gaubert. Tropicalizing Semialgebraic Pivoting Rules, Or How to Solve Mean Payoff Games in Polynomial Time on Average. SIAM Conference on Control and its Applications (SIAM CT’15), Jul 2015, Paris, France. ⟨hal-01263357⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

491

 

Contact                    Legal Notice                    Personal Data