Strategies in Sabotage Games: Temporal and Epistemic Perspectives
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910103246995456 |
|---|---|
| author | Gierasimczuk, Nina Thoft, Katrine B. P. |
| author_facet | Gierasimczuk, Nina Thoft, Katrine B. P. |
| contents | Sabotage games are played on a dynamic graph, in which one agent, called a runner, attempts to reach a goal state, while being obstructed by a demon who at each round removes an edge from the graph. Sabotage modal logic was proposed to carry out reasoning about such games. Since its conception, it has undergone a thorough analysis (in terms of complexity, completeness, and various extensions) and has been applied to a variety of domains, e.g., to formal learning. In this paper, we propose examining the game from a temporal perspective using alternating time temporal logic (ATL$^\ast$), and address the players' uncertainty in its epistemic extensions. This framework supports reasoning about winning strategies for those games, and opens ways to address temporal properties of dynamic graphs in general. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03872 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Strategies in Sabotage Games: Temporal and Epistemic Perspectives Gierasimczuk, Nina Thoft, Katrine B. P. Logic in Computer Science Multiagent Systems Sabotage games are played on a dynamic graph, in which one agent, called a runner, attempts to reach a goal state, while being obstructed by a demon who at each round removes an edge from the graph. Sabotage modal logic was proposed to carry out reasoning about such games. Since its conception, it has undergone a thorough analysis (in terms of complexity, completeness, and various extensions) and has been applied to a variety of domains, e.g., to formal learning. In this paper, we propose examining the game from a temporal perspective using alternating time temporal logic (ATL$^\ast$), and address the players' uncertainty in its epistemic extensions. This framework supports reasoning about winning strategies for those games, and opens ways to address temporal properties of dynamic graphs in general. |
| title | Strategies in Sabotage Games: Temporal and Epistemic Perspectives |
| topic | Logic in Computer Science Multiagent Systems |
| url | https://arxiv.org/abs/2604.03872 |