Skip to Main content Skip to Navigation
Journal articles

Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games

Carlo Comin 1, 2 Romeo Rizzi 3
1 LIGM - Laboratoire d'Informatique Gaspard-Monge
2 Department of mathematics/Dipartimento di Matematica [Univ. Trento]
3 UNIVR | DI - Department of Computer Science [Verona]
Abstract : In this work we offer an O(|V|² |E| W) pseudo-polynomial time deterministic algorithm for solving the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. This improves by a factor log(|V| W) the best previously known pseudo-polynomial time upper bound due to Brim et al. The improvement hinges on a suitable characterization of values, and a description of optimal positional strategies, in terms of reweighted Energy Games and Small Energy-Progress Measures.
Keywords : mean payoff games value problem optimal strategy synthesis energy games small energy-progress measures pseudo-polynomial Time
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
https://hal-upec-upem.archives-ouvertes.fr/hal-01577457
Contributor : Admin Upem Connect in order to contact the contributor
Submitted on : Friday, August 25, 2017 - 5:38:23 PM
Last modification on : Tuesday, May 25, 2021 - 11:46:03 AM

File

Vignette du document
1503.04426.pdf
Files produced by the author(s)

Identifiers

Collections

UPEC-UPEM | ENPC | PARISTECH | LIGM | LIGM_MOA | CNRS | ESIEE-PARIS

Citation

Carlo Comin, Romeo Rizzi. Improved Pseudo-polynomial Bound for the Value Problem and Optimal Strategy Synthesis in Mean Payoff Games. Algorithmica, Springer Verlag, 2017, 77 (4), pp.995-1021. ⟨10.1007/s00453-016-0123-1⟩. ⟨hal-01577457⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

257

Files downloads

370