Two-Player Zero-Sum Differential Games with One-Sided Information
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916613451677696 |
|---|---|
| author | Ghimire, Mukesh Xu, Zhe Ren, Yi |
| author_facet | Ghimire, Mukesh Xu, Zhe Ren, Yi |
| contents | Unlike Poker where the action space $\mathcal{A}$ is discrete, differential games in the physical world often have continuous action spaces not amenable to discrete abstraction, rendering no-regret algorithms with $\mathcal{O}(|\mathcal{A}|)$ complexity not scalable. To address this challenge within the scope of two-player zero-sum (2p0s) games with one-sided information, we show that (1) a computational complexity independent of $|\mathcal{A}|$ can be achieved by exploiting the convexification property of incomplete-information games and the Isaacs' condition that commonly holds for dynamical systems, and that (2) the computation of the two equilibrium strategies can be decoupled under one-sidedness of information. Leveraging these insights, we develop an algorithm that successfully approximates the optimal strategy in a homing game. Code available in https://github.com/ghimiremukesh/cams/tree/workshop |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_05314 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Two-Player Zero-Sum Differential Games with One-Sided Information Ghimire, Mukesh Xu, Zhe Ren, Yi Computer Science and Game Theory Unlike Poker where the action space $\mathcal{A}$ is discrete, differential games in the physical world often have continuous action spaces not amenable to discrete abstraction, rendering no-regret algorithms with $\mathcal{O}(|\mathcal{A}|)$ complexity not scalable. To address this challenge within the scope of two-player zero-sum (2p0s) games with one-sided information, we show that (1) a computational complexity independent of $|\mathcal{A}|$ can be achieved by exploiting the convexification property of incomplete-information games and the Isaacs' condition that commonly holds for dynamical systems, and that (2) the computation of the two equilibrium strategies can be decoupled under one-sidedness of information. Leveraging these insights, we develop an algorithm that successfully approximates the optimal strategy in a homing game. Code available in https://github.com/ghimiremukesh/cams/tree/workshop |
| title | Two-Player Zero-Sum Differential Games with One-Sided Information |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2502.05314 |