@article{EhrenfeuchtMycielski1979,
  author = {Ehrenfeucht, Andrzej and Mycielski, Jan},
  title = {Positional strategies for mean payoff games},
  journal = {International Journal of Game Theory},
  volume = {8},
  number = {2},
  pages = {109--113},
  year = {1979},
  doi = {10.1007/BF01768705},
  url = {https://doi.org/10.1007/BF01768705},
  note = {\href{https://doi.org/10.1007/BF01768705}{DOI: \nolinkurl{10.1007/BF01768705}}}
}

@article{ZwickPaterson1996,
  author = {Zwick, Uri and Paterson, Mike},
  title = {The complexity of mean payoff games on graphs},
  journal = {Theoretical Computer Science},
  volume = {158},
  number = {1--2},
  pages = {343--359},
  year = {1996},
  doi = {10.1016/0304-3975(95)00188-3},
  url = {https://doi.org/10.1016/0304-3975(95)00188-3},
  note = {\href{https://doi.org/10.1016/0304-3975(95)00188-3}{DOI: \nolinkurl{10.1016/0304-3975(95)00188-3}}}
}

@article{Jurdzinski1998,
  author = {Jurdzi{\'n}ski, Marcin},
  title = {Deciding the Winner in Parity Games Is in {UP} $\cap$ {co-UP}},
  journal = {Information Processing Letters},
  volume = {68},
  number = {3},
  pages = {119--124},
  year = {1998},
  doi = {10.1016/S0020-0190(98)00150-1},
  url = {https://www.dcs.warwick.ac.uk/~mju/Papers/Jur98-IPL.pdf},
  note = {\href{https://doi.org/10.1016/S0020-0190(98)00150-1}{DOI: \nolinkurl{10.1016/S0020-0190(98)00150-1}}}
}

@article{BjorklundVorobyov2007,
  author = {Bj{\"o}rklund, Henrik and Vorobyov, Sergei},
  title = {A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games},
  journal = {Discrete Applied Mathematics},
  volume = {155},
  number = {2},
  pages = {210--229},
  year = {2007},
  doi = {10.1016/j.dam.2006.04.029},
  url = {https://doi.org/10.1016/j.dam.2006.04.029},
  note = {\href{https://doi.org/10.1016/j.dam.2006.04.029}{DOI: \nolinkurl{10.1016/j.dam.2006.04.029}}}
}

@inproceedings{Parys2019,
  author = {Parys, Pawe{\l}},
  title = {Parity Games: {Zielonka's} Algorithm in Quasi-Polynomial Time},
  booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
  editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {138},
  pages = {10:1--10:13},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  year = {2019},
  doi = {10.4230/LIPIcs.MFCS.2019.10},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.10},
  note = {\href{https://doi.org/10.4230/LIPIcs.MFCS.2019.10}{DOI: \nolinkurl{10.4230/LIPIcs.MFCS.2019.10}}}
}

@misc{Ohlmann2026,
  author = {Ohlmann, Pierre},
  title = {A symmetric recursive algorithm for mean-payoff games},
  year = {2026},
  eprint = {2603.07555},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  doi = {10.48550/arXiv.2603.07555},
  url = {https://arxiv.org/abs/2603.07555v1},
  howpublished = {arXiv:2603.07555v1},
  month = {8 March},
  note = {\href{https://doi.org/10.48550/arXiv.2603.07555}{DOI: \nolinkurl{10.48550/arXiv.2603.07555}}}
}

@article{GurvichKarzanovKhachiyan1988,
  author = {Gurvich, Vladimir A. and Karzanov, Alexander V. and Khachiyan, Leonid G.},
  title = {Cyclic games and an algorithm to find minimax cycle means in directed graphs},
  journal = {USSR Computational Mathematics and Mathematical Physics},
  volume = {28},
  number = {5},
  pages = {85--91},
  year = {1988},
  doi = {10.1016/0041-5553(88)90012-2},
  url = {https://doi.org/10.1016/0041-5553(88)90012-2},
  note = {\href{https://doi.org/10.1016/0041-5553(88)90012-2}{DOI: \nolinkurl{10.1016/0041-5553(88)90012-2}}}
}

@article{KarzanovLebedev1993,
  author = {Karzanov, Alexander V. and Lebedev, Vasilij N.},
  title = {Cyclical games with prohibitions},
  journal = {Mathematical Programming},
  volume = {60},
  pages = {277--293},
  year = {1993},
  doi = {10.1007/BF01580616},
  url = {https://alexander-karzanov.net/Publications/93_CYCLIC92_N.pdf},
  note = {\href{https://doi.org/10.1007/BF01580616}{DOI: \nolinkurl{10.1007/BF01580616}}}
}

@article{Pisaruk1999,
  author = {Pisaruk, N. N.},
  title = {Mean Cost Cyclical Games},
  journal = {Mathematics of Operations Research},
  volume = {24},
  number = {4},
  pages = {817--828},
  year = {1999},
  doi = {10.1287/moor.24.4.817},
  url = {https://doi.org/10.1287/moor.24.4.817},
  note = {\href{https://doi.org/10.1287/moor.24.4.817}{DOI: \nolinkurl{10.1287/moor.24.4.817}}}
}

@inproceedings{ChakrabartiEtAl2003,
  author = {Chakrabarti, Arindam and de Alfaro, Luca and Henzinger, Thomas A. and Stoelinga, Mari{\"e}lle},
  title = {Resource Interfaces},
  booktitle = {Embedded Software (EMSOFT 2003)},
  editor = {Alur, Rajeev and Lee, Insup},
  series = {Lecture Notes in Computer Science},
  volume = {2855},
  pages = {117--133},
  publisher = {Springer},
  year = {2003},
  doi = {10.1007/978-3-540-45212-6_9},
  url = {https://doi.org/10.1007/978-3-540-45212-6_9},
  note = {\href{https://doi.org/10.1007/978-3-540-45212-6_9}{DOI: \nolinkurl{10.1007/978-3-540-45212-6_9}}}
}

@inproceedings{BjorklundSandbergVorobyov2004,
  author = {Bj{\"o}rklund, Henrik and Sandberg, Sven and Vorobyov, Sergei},
  title = {A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games},
  booktitle = {Mathematical Foundations of Computer Science 2004},
  series = {Lecture Notes in Computer Science},
  volume = {3153},
  pages = {673--685},
  publisher = {Springer},
  year = {2004},
  doi = {10.1007/978-3-540-28629-5_52},
  url = {https://www.dbai.tuwien.ac.at/staff/vorobyov/mfcs04.pdf},
  note = {\href{https://doi.org/10.1007/978-3-540-28629-5_52}{DOI: \nolinkurl{10.1007/978-3-540-28629-5_52}}}
}

@techreport{AnderssonVorobyov2006,
  author = {Andersson, Daniel and Vorobyov, Sergei},
  title = {Fast Algorithms for Monotonic Discounted Linear Programs with Two Variables per Inequality},
  institution = {Isaac Newton Institute for Mathematical Sciences},
  number = {NI06019-LAA},
  year = {2006},
  month = may,
  url = {https://api.newton.ac.uk/website/v0/events/preprints/NI06019}
}

@article{LifshitsPavlov2007,
  author = {Lifshits, Yury M. and Pavlov, Dmitri S.},
  title = {Potential theory for mean payoff games},
  journal = {Journal of Mathematical Sciences},
  volume = {145},
  number = {3},
  pages = {4967--4974},
  year = {2007},
  doi = {10.1007/s10958-007-0331-y},
  url = {https://doi.org/10.1007/s10958-007-0331-y},
  note = {\href{https://doi.org/10.1007/s10958-007-0331-y}{DOI: \nolinkurl{10.1007/s10958-007-0331-y}}}
}

@inproceedings{BouyerEtAl2008,
  author = {Bouyer, Patricia and Fahrenberg, Uli and Larsen, Kim G. and Markey, Nicolas and Srba, Ji{\v{r}}{\'i}},
  title = {Infinite Runs in Weighted Timed Automata with Energy Constraints},
  booktitle = {Formal Modeling and Analysis of Timed Systems (FORMATS 2008)},
  editor = {Cassez, Franck and Jard, Claude},
  series = {Lecture Notes in Computer Science},
  volume = {5215},
  pages = {33--47},
  publisher = {Springer},
  year = {2008},
  doi = {10.1007/978-3-540-85778-5_4},
  url = {https://doi.org/10.1007/978-3-540-85778-5_4},
  note = {\href{https://doi.org/10.1007/978-3-540-85778-5_4}{DOI: \nolinkurl{10.1007/978-3-540-85778-5_4}}}
}

@article{BrimEtAl2011,
  author = {Brim, Lubo{\v{s}} and Chaloupka, Jakub and Doyen, Laurent and Gentilini, Raffaella and Raskin, Jean-Fran{\c{c}}ois},
  title = {Faster algorithms for mean-payoff games},
  journal = {Formal Methods in System Design},
  volume = {38},
  number = {2},
  pages = {97--118},
  year = {2011},
  doi = {10.1007/s10703-010-0105-x},
  url = {https://doi.org/10.1007/s10703-010-0105-x},
  note = {\href{https://doi.org/10.1007/s10703-010-0105-x}{DOI: \nolinkurl{10.1007/s10703-010-0105-x}}}
}

@article{CaludeJainKhoussainovLiStephan2022,
 author={Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank},
 title={Deciding Parity Games in Quasi-polynomial Time},
 journal={SIAM Journal on Computing}, volume={51}, number={2},
 pages={STOC17-152--STOC17-188}, year={2022},
 doi={10.1137/17M1145288}, url={https://doi.org/10.1137/17M1145288},
  note = {\href{https://doi.org/10.1137/17M1145288}{DOI: \nolinkurl{10.1137/17M1145288}}}
}

@article{LehtinenParysScheweWojtczak2022,
 author={Lehtinen, Karoliina and Parys, Pawe{\l} and Schewe, Sven and Wojtczak, Dominik},
 title={A Recursive Approach to Solving Parity Games in Quasipolynomial Time},
 journal={Logical Methods in Computer Science}, volume={18}, number={1},
 pages={8:1--8:18}, year={2022},
 doi={10.46298/LMCS-18(1:8)2022}, url={https://lmcs.episciences.org/8953},
  note = {\href{https://doi.org/10.46298/LMCS-18(1:8)2022}{DOI: \nolinkurl{10.46298/LMCS-18(1:8)2022}}}
}

@inproceedings{FijalkowGawrychowskiOhlmann2020,
 author={Fijalkow, Nathana{\"e}l and Gawrychowski, Pawe{\l} and Ohlmann, Pierre},
 title={Value Iteration Using Universal Graphs and the Complexity of Mean Payoff Games},
 booktitle={45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
 series={Leibniz International Proceedings in Informatics (LIPIcs)}, volume={170},
 pages={34:1--34:15}, year={2020},
 publisher={Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
 doi={10.4230/LIPIcs.MFCS.2020.34}, url={https://doi.org/10.4230/LIPIcs.MFCS.2020.34},
  note = {\href{https://doi.org/10.4230/LIPIcs.MFCS.2020.34}{DOI: \nolinkurl{10.4230/LIPIcs.MFCS.2020.34}}}
}

@article{ColcombetFijalkowGawrychowskiOhlmann2022,
 author={Colcombet, Thomas and Fijalkow, Nathana{\"e}l and Gawrychowski, Pawe{\l} and Ohlmann, Pierre},
 title={The Theory of Universal Graphs for Infinite Duration Games},
 journal={Logical Methods in Computer Science}, volume={18}, number={3},
 pages={29:1--29:47}, year={2022},
 doi={10.46298/LMCS-18(3:29)2022}, url={https://lmcs.episciences.org/10012},
  note = {\href{https://doi.org/10.46298/LMCS-18(3:29)2022}{DOI: \nolinkurl{10.46298/LMCS-18(3:29)2022}}}
}

@misc{Zwick2026,
 author={Zwick, Uri},
 title={Improved subexponential analysis of the {Random-Action-Removal} algorithm for 2-player turn-based games and non-binary {AUSOs}},
 year={2026},
 howpublished={arXiv:2607.06334v1},
 eprint={2607.06334}, archivePrefix={arXiv}, primaryClass={cs.DS},
 doi={10.48550/arXiv.2607.06334},
 url={https://arxiv.org/abs/2607.06334v1},
  note = {\href{https://doi.org/10.48550/arXiv.2607.06334}{DOI: \nolinkurl{10.48550/arXiv.2607.06334}}}
}

@inproceedings{DaviaudJurdzinskiLazic2018,
  author = {Daviaud, Laure and Jurdzi{\'n}ski, Marcin and Lazi{\'c}, Ranko},
  title = {A Pseudo-Quasi-Polynomial Algorithm for Mean-Payoff Parity Games},
  booktitle = {Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science},
  series = {LICS '18},
  year = {2018},
  pages = {325--334},
  publisher = {ACM},
  doi = {10.1145/3209108.3209162},
  url = {https://arxiv.org/abs/1803.04756},
  eprint = {1803.04756},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  note = {\href{https://doi.org/10.1145/3209108.3209162}{DOI: \nolinkurl{10.1145/3209108.3209162}}}
}

@inproceedings{LoffSkomra2024,
  author = {Loff, Bruno and Skomra, Mateusz},
  title = {Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games},
  booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {297},
  pages = {147:1--147:16},
  year = {2024},
  editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.ICALP.2024.147},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.147},
  eprint = {2402.03975},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  note = {\href{https://doi.org/10.4230/LIPIcs.ICALP.2024.147}{DOI: \nolinkurl{10.4230/LIPIcs.ICALP.2024.147}}}
}

@inproceedings{CadilhacCasaresOhlmann2025,
  author = {Cadilhac, Micha{\"e}l and Casares, Antonio and Ohlmann, Pierre},
  title = {Fast Value Iteration: A Uniform Approach to Efficient Algorithms for Energy Games},
  booktitle = {Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2025), Part II},
  editor = {Gurfinkel, Arie and Heule, Marijn},
  series = {Lecture Notes in Computer Science},
  volume = {15697},
  pages = {323--342},
  year = {2025},
  publisher = {Springer},
  doi = {10.1007/978-3-031-90653-4_16},
  url = {https://link.springer.com/chapter/10.1007/978-3-031-90653-4_16},
  eprint = {2110.07346},
  archivePrefix = {arXiv},
  primaryClass = {cs.GT},
  note = {\href{https://doi.org/10.1007/978-3-031-90653-4_16}{DOI: \nolinkurl{10.1007/978-3-031-90653-4_16}}}
}

@inproceedings{DorfmanKaplanZwick2026,
  author = {Dorfman, Dani and Kaplan, Haim and Zwick, Uri},
  title = {Improved Bounds for Strategy Improvement Algorithms for Energy Games},
  booktitle = {34th Annual European Symposium on Algorithms (ESA 2026)},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  volume = {388},
  pages = {140:1--140:18},
  year = {2026},
  editor = {Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  doi = {10.4230/LIPIcs.ESA.2026.140},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.140},
  note = {\href{https://doi.org/10.4230/LIPIcs.ESA.2026.140}{DOI: \nolinkurl{10.4230/LIPIcs.ESA.2026.140}}}
}

@misc{Truffet2026SubstitutionV4,
 author={Truffet, Laurent},
 title={Substitution for minimizing/maximizing a tropical linear (fractional) programming},
 year={2026}, howpublished={arXiv:2603.26423v4, August 29},
 doi={10.48550/arXiv.2603.26423}, url={https://arxiv.org/abs/2603.26423v4},
 note={\href{https://arxiv.org/abs/2603.26423v4}{arXiv:2603.26423v4}}
}

@misc{Truffet2025MaxAtoms,
 author={Truffet, Laurent},
 title={Looking For All Solutions of a Set of Max-Atoms Solves the Max Atom Problem in Strongly Polynomial Time},
 year={2025}, howpublished={Mod\'elisation des Syst\`emes R\'eactifs (MSR 2025)},
 url={https://hal.science/hal-05491586},
 note={\href{https://hal.science/hal-05491586}{HAL: hal-05491586}}
}

@inproceedings{ArnoldNiwinskiParys2021,
 author={Arnold, Andr{\'e} and Niwi{\'n}ski, Damian and Parys, Pawe{\l}},
 title={A Quasi-Polynomial Black-Box Algorithm for Fixed Point Evaluation},
 booktitle={29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
 series={Leibniz International Proceedings in Informatics (LIPIcs)},
 volume={183}, pages={9:1--9:23}, year={2021},
 publisher={Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
 doi={10.4230/LIPIcs.CSL.2021.9},
 url={https://doi.org/10.4230/LIPIcs.CSL.2021.9}
}
@misc{JurdzinskiMorvanOhlmannThejaswini2020,
 author={Jurdzi{\'n}ski, Marcin and Morvan, R{\'e}mi and Ohlmann, Pierre and Thejaswini, K. S.},
 title={A symmetric attractor-decomposition lifting algorithm for parity games},
 year={2020}, howpublished={arXiv:2010.08288v1},
 eprint={2010.08288}, archivePrefix={arXiv},
 url={https://arxiv.org/abs/2010.08288v1}
}
@inproceedings{DorfmanKaplanZwick2019,
 author={Dorfman, Dani and Kaplan, Haim and Zwick, Uri},
 title={A Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games},
 booktitle={46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
 series={Leibniz International Proceedings in Informatics (LIPIcs)},
 volume={132}, pages={114:1--114:14}, year={2019},
 publisher={Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
 doi={10.4230/LIPIcs.ICALP.2019.114},
 url={https://doi.org/10.4230/LIPIcs.ICALP.2019.114},
 note={An updated author version contains the weight-independent bound in Theorem~3.10: \url{https://danidorfman.com/publication/energy-games/energy-games.pdf}}
}
@inproceedings{Kozachinskiy2021,
 author={Kozachinskiy, Alexander},
 title={Polyhedral Value Iteration for Discounted Games and Energy Games},
 booktitle={Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)},
 editor={Marx, D{\'a}niel},
 pages={600--616}, year={2021}, publisher={SIAM},
 doi={10.1137/1.9781611976465.37},
 url={https://doi.org/10.1137/1.9781611976465.37},
 note={\href{https://doi.org/10.1137/1.9781611976465.37}{DOI: \nolinkurl{10.1137/1.9781611976465.37}}}
}
@article{AkianGaubertGuterman2012,
 author={Akian, Marianne and Gaubert, St{\'e}phane and Guterman, Alexander},
 title={Tropical polyhedra are equivalent to mean payoff games},
 journal={International Journal of Algebra and Computation},
 volume={22}, number={1}, pages={1250001}, year={2012},
 doi={10.1142/S0218196711006674},
 url={https://doi.org/10.1142/S0218196711006674}
}

@misc{OpenAI2026Randomized,
  author = {{OpenAI}},
  title = {{Randomized quasipolynomial-time mean-payoff games}},
  howpublished = {OpenAI Math Release preprint
                  \href{https://github.com/openai/math/blob/main/preprints/Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026/paper.pdf}{OAI:Randomized-quasipolynomial-time-mean-payoff-games-September-25-2026}},
  year = {2026}
}

@inproceedings{ThejaswiniOhlmannJurdzinski2022,
 author = {Thejaswini, K. S. and Ohlmann, Pierre and Jurdzi{\'n}ski, Marcin},
 title = {A Technique to Speed up Symmetric Attractor-Based Algorithms for Parity Games},
 booktitle = {42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
 editor = {Dawar, Anuj and Guruswami, Venkatesan},
 series = {Leibniz International Proceedings in Informatics (LIPIcs)},
 volume = {250}, pages = {44:1--44:20}, year = {2022},
 publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
 doi = {10.4230/LIPIcs.FSTTCS.2022.44},
 url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2022.44},
 note = {\href{https://doi.org/10.4230/LIPIcs.FSTTCS.2022.44}{DOI: \nolinkurl{10.4230/LIPIcs.FSTTCS.2022.44}}}
}

@misc{AustinDellErba2023,
  author = {Austin, Peter and Dell'Erba, Daniele},
  title = {Errata to: {``Faster Deterministic Exponential Time Algorithm for Energy Games and Mean Payoff Games''}},
  year = {2023},
  howpublished = {arXiv:2310.04130v1, October 6},
  eprint = {2310.04130},
  archivePrefix = {arXiv},
  primaryClass = {cs.DS},
  doi = {10.48550/arXiv.2310.04130},
  url = {https://arxiv.org/abs/2310.04130v1}
}