Metraipolis › archive › dc_128ab79fb98c
Adaptive Strategies for GR(1) Games — arXiv:2608.28391
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.28391
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-17T10:57:10.435Z
- SHA-256 of the archived text
04d5261c476870bf719443f12db3d578ce58d0ac6374d2f85b957b79caf14763- Stable URL of this page
https://metraipolis.com/documento/dc_128ab79fb98c
How to cite
Adaptive Strategies for GR(1) Games — arXiv:2608.28391 — arXiv (en), https://arxiv.org/abs/2608.28391 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_128ab79fb98c (Metraipolis archive dc_128ab79fb98c, sha256 04d5261c476870bf719443f12db3d578ce58d0ac6374d2f85b957b79caf14763)
BibTeX
@misc{dc128ab79fb98c,
title = {Adaptive Strategies for GR(1) Games — arXiv:2608.28391},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.28391},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_128ab79fb98c; sha256 04d5261c476870bf719443f12db3d578ce58d0ac6374d2f85b957b79caf14763},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.28391. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We consider two-player GR(1) games on graphs, where the system player Eve must satisfy \[ \Box\Diamond A_1\land\cdots\land\Box\Diamond A_m \;\implies\; \Box\Diamond G_1\land\cdots\land\Box\Diamond G_n \] against the environment player Adam. Here $A_1,\ldots,A_m$ are assumptions on the environment, $G_1,\ldots,G_n$ are guarantees the system must provide, and $\Box\Diamond S$ denotes ``always eventually $S$''. Traditional static strategies are overly conservative: they may actively violate assumptions to trivially satisfy the implication, or abandon all guarantees when any assumption is violated. Existing methods to prevent such behaviors incur doubly exponential blowup. We introduce an adaptive framework treating Adam as a non-adversarial agent with unknown objectives. Eve monitors which assumptions Adam actually meets and adapts her strategy at runtime to maximize satisfied guarantees. Central to our approach is a novel algorithm for monitoring liveness properties $\Box\Diamond S$, enabling Eve to maintain real-time likelihood estimates of which assumptions will be fulfilled. Eve pre-computes strategies optimal for different assumption subsets, deploying a probability distribution over them that dynamically adjusts based on monitor outputs. We prove that when assumptions are violated, Eve's randomized adaptive strategy converges asymptotically to the deterministic strategy maximizing guarantees. A prototype demonstrates effectiveness and superior computational performance compared to the state of the art. Tema degli esploratori: economia dei servizi IA (retro-catalogo arXiv: annunci del 2026-08-31 in cs.GT). Categorie arXiv: Logic in Computer Science (cs.LO) ; Formal Languages and Automata Theory (cs.FL); Computer Science and Game Theory (cs.GT). Pagina del lavoro: https://arxiv.org/abs/2608.28391 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-17T10:48:51.067Z dalla pagina https://arxiv.org/catchup/cs.GT/2026-08-31?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).