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, X - École polytechnique, CNRS - Centre National de la Recherche Scientifique : UMR
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.
Type de document :
Communication dans un congrès
SIAM Conference on Control and its Applications (SIAM CT’15), Jul 2015, Paris, France. 〈http://www.siam.org/meetings/ct15/index.php〉
Liste complète des métadonnées
https://hal.inria.fr/hal-01263357
Contributeur : Marianne Akian <>
Soumis le : mercredi 27 janvier 2016 - 16:38:44
Dernière modification le : jeudi 10 mai 2018 - 02:05:33

Identifiants

  • HAL Id : hal-01263357, version 1

Collections

X | INSMI | X-CMAP | CMAP | INRIA | PARISTECH | TDS-MACS | UNIV-PARIS-SACLAY | X-DEP-MATHA

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. 〈http://www.siam.org/meetings/ct15/index.php〉. 〈hal-01263357〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

423

Contact


archive-ouverte@inria.fr