Polytopal Stochastic Games
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916629731868672 |
|---|---|
| author | Castro, Pablo F. D'Argenio, Pedro |
| author_facet | Castro, Pablo F. D'Argenio, Pedro |
| contents | In this paper we introduce polytopal stochastic games, an extension of two-player, zero-sum, turn-based stochastic games, in which we may have uncertainty over the transition probabilities. In these games the uncertainty over the probabilities distributions is captured via linear (in)equalities whose space of solutions forms a polytope. We give a formal definition of these games and prove their basic properties: determinacy and existence of optimal memoryless and deterministic strategies. We do this for reachability and different types of reward objectives and show that the solution exists in a finite representation of the game. We also state that the corresponding decision problems are in the intersection of NP and coNP. We motivate the use of polytopal stochastic games via a simple example. Finally, we report some experiments we performed with a prototype tool. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16208 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polytopal Stochastic Games Castro, Pablo F. D'Argenio, Pedro Logic in Computer Science Computer Science and Game Theory In this paper we introduce polytopal stochastic games, an extension of two-player, zero-sum, turn-based stochastic games, in which we may have uncertainty over the transition probabilities. In these games the uncertainty over the probabilities distributions is captured via linear (in)equalities whose space of solutions forms a polytope. We give a formal definition of these games and prove their basic properties: determinacy and existence of optimal memoryless and deterministic strategies. We do this for reachability and different types of reward objectives and show that the solution exists in a finite representation of the game. We also state that the corresponding decision problems are in the intersection of NP and coNP. We motivate the use of polytopal stochastic games via a simple example. Finally, we report some experiments we performed with a prototype tool. |
| title | Polytopal Stochastic Games |
| topic | Logic in Computer Science Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.16208 |