@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{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},
  note = {\href{https://api.newton.ac.uk/website/v0/events/preprints/NI06019}{Isaac Newton Institute preprint NI06019-LAA}}
}

@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}}
}


@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},
 note={\href{https://doi.org/10.1142/S0218196711006674}{DOI: \nolinkurl{10.1142/S0218196711006674}}}
}

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