Reducing Stochastic Games to Semidefinite Programming
Research output: Contribution to book/Conference proceedings/Anthology/Report › Conference contribution › Contributed › peer-review
Contributors
Abstract
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.
Details
| Original language | English |
|---|---|
| Title of host publication | 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025 |
| Editors | Keren Censor-Hillel, Fabrizio Grandoni, Joel Ouaknine, Gabriele Puppis |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing |
| Number of pages | 15 |
| ISBN (electronic) | 9783959773720 |
| Publication status | Published - 30 Jun 2025 |
| Peer-reviewed | Yes |
Publication series
| Series | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 334 |
| ISSN | 1868-8969 |
Conference
| Title | 52nd EATCS International Colloquium on Automata, Languages, and Programming |
|---|---|
| Abbreviated title | ICALP 2025 |
| Conference number | 52 |
| Duration | 8 - 11 July 2025 |
| Website | |
| Location | Aarhus University |
| City | Aarhus |
| Country | Denmark |
External IDs
| ORCID | /0000-0001-8228-3611/work/208071917 |
|---|
Keywords
ASJC Scopus subject areas
Keywords
- max-atom problem, max-average constraints, Mean-payoff games, semidefinite programming, stochastic games