2026-07-20T14:44:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23522 2025-10-02T12:57:41Z ddc:004 open_access

Reducing Stochastic Games to Semidefinite Programming Bodirsky, Manuel Loho, Georg Skomra, Mateusz Mean-payoff games stochastic games semidefinite programming max-average constraints max-atom problem We present a polynomial-time reduction from max-average constraints to the feasibility problem for semidefinite programs. This shows that Condon’s simple stochastic games, stochastic mean payoff games, and in particular mean payoff games and parity games can all be reduced to semidefinite programming. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Georg Loho and Mateusz Skomra 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.145 urn:nbn:de:0030-drops-235224 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.145 eng https://creativecommons.org/licenses/by/4.0/legalcode