Reducing Stochastic Games to Semidefinite Program Feasibility
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866915647408046080 |
|---|---|
| author | Bodirsky, Manuel Loho, Georg Skomra, Mateusz |
| author_facet | Bodirsky, Manuel Loho, Georg Skomra, Mateusz |
| contents | We present a polynomial-time reduction from max-plus-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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_09646 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reducing Stochastic Games to Semidefinite Program Feasibility Bodirsky, Manuel Loho, Georg Skomra, Mateusz Optimization and Control Computational Complexity Computer Science and Game Theory 90C22, 91A15, 14T90 We present a polynomial-time reduction from max-plus-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. |
| title | Reducing Stochastic Games to Semidefinite Program Feasibility |
| topic | Optimization and Control Computational Complexity Computer Science and Game Theory 90C22, 91A15, 14T90 |
| url | https://arxiv.org/abs/2411.09646 |