Reducing Stochastic Games to Semidefinite Programming

Manuel Bodirsky; Georg Loho; Mateusz Skomra

doi:10.48550/arXiv.2411.09646

Reducing Stochastic Games to Semidefinite Programming

Manuel Bodirsky, Georg Loho, Mateusz Skomra

Mathematics of Operations Research

Research output: Working paper › Preprint › Academic

8 Downloads (Pure)

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.

Original language	English
Publisher	ArXiv.org
Number of pages	15
DOIs	https://doi.org/10.48550/arXiv.2411.09646
Publication status	Published - 14 Nov 2024

Keywords

math.OC
cs.CC
cs.GT
90C22, 91A15, 14T90

Access to Document

10.48550/arXiv.2411.09646

2411.09646v1Final published version, 426 KB

Cite this

@techreport{2535b582d5dd4698a3d1c8f05fc8e7cc,

title = "Reducing Stochastic Games to Semidefinite Programming",

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. ",

keywords = "math.OC, cs.CC, cs.GT, 90C22, 91A15, 14T90",

author = "Manuel Bodirsky and Georg Loho and Mateusz Skomra",

note = "15 pages, 1 figure",

year = "2024",

month = nov,

day = "14",

doi = "10.48550/arXiv.2411.09646",

language = "English",

publisher = "ArXiv.org",

type = "WorkingPaper",

institution = "ArXiv.org",

}

TY - UNPB

T1 - Reducing Stochastic Games to Semidefinite Programming

AU - Bodirsky, Manuel

AU - Loho, Georg

AU - Skomra, Mateusz

N1 - 15 pages, 1 figure

PY - 2024/11/14

Y1 - 2024/11/14

N2 - 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.

AB - 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.

KW - math.OC

KW - cs.CC

KW - cs.GT

KW - 90C22, 91A15, 14T90

U2 - 10.48550/arXiv.2411.09646

DO - 10.48550/arXiv.2411.09646

M3 - Preprint

BT - Reducing Stochastic Games to Semidefinite Programming

PB - ArXiv.org

ER -

Reducing Stochastic Games to Semidefinite Programming

Abstract

Keywords

Access to Document

Fingerprint

Cite this