A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908396646563840 |
|---|---|
| author | Berthon, Raphaël Katoen, Joost-Pieter Zhou, Zihan |
| author_facet | Berthon, Raphaël Katoen, Joost-Pieter Zhou, Zihan |
| contents | Significant progress has been recently achieved in developing efficient solutions for simple stochastic games (SSGs), focusing on reachability objectives. While reductions from stochastic parity games (SPGs) to SSGs have been presented in the literature through the use of multiple intermediate game models, a direct and simple reduction has been notably absent. This paper introduces a novel and direct polynomial-time reduction from quantitative SPGs to quantitative SSGs. By leveraging a gadget-based transformation that effectively removes the priority function, we construct an SSG that simulates the behavior of a given SPG. We formally establish the correctness of our direct reduction. Furthermore, we demonstrate that under binary encoding this reduction is polynomial, thereby directly corroborating the known $\textbf{NP}\,\mathbf{\cap}\,\textbf{coNP}$ complexity of SPGs and providing new understanding in the relationship between parity and reachability objectives in turn-based stochastic games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_06223 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games Berthon, Raphaël Katoen, Joost-Pieter Zhou, Zihan Computer Science and Game Theory Significant progress has been recently achieved in developing efficient solutions for simple stochastic games (SSGs), focusing on reachability objectives. While reductions from stochastic parity games (SPGs) to SSGs have been presented in the literature through the use of multiple intermediate game models, a direct and simple reduction has been notably absent. This paper introduces a novel and direct polynomial-time reduction from quantitative SPGs to quantitative SSGs. By leveraging a gadget-based transformation that effectively removes the priority function, we construct an SSG that simulates the behavior of a given SPG. We formally establish the correctness of our direct reduction. Furthermore, we demonstrate that under binary encoding this reduction is polynomial, thereby directly corroborating the known $\textbf{NP}\,\mathbf{\cap}\,\textbf{coNP}$ complexity of SPGs and providing new understanding in the relationship between parity and reachability objectives in turn-based stochastic games. |
| title | A Direct Reduction from Stochastic Parity Games to Simple Stochastic Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.06223 |