💻 computer science

Strategies in Sabotage Games: Temporal and Epistemic Perspectives

This paper proposes a framework for analyzing sabotage games by integrating temporal and epistemic perspectives through Alternating Time Temporal Logic (ATL $^\ast$ ) and its extensions to reason about winning strategies and player uncertainty in dynamic graphs.

Original authors: Nina Gierasimczuk, Katrine B. P. Thoft

Published 2026-04-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nina Gierasimczuk, Katrine B. P. Thoft

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A Game of Cat and Mouse on a Map

Imagine you are playing a video game where you control a character (the Runner) trying to get from Point A to Point B. But there's a catch: an invisible enemy (the Demon) is watching you. Every time you take a step, the Demon gets to delete a road on your map.

The paper asks a simple but deep question: Can the Runner always win, no matter how the Demon plays?

Traditionally, scientists used a specific type of logic (called Sabotage Modal Logic) to answer this. But the authors of this paper argue that this old logic is like looking at a single photograph of the game. It tells you if you can win, but it doesn't tell you how the game unfolds over time or what the players know about each other.

To fix this, the authors introduce a new, more powerful way of thinking using Time (Temporal Logic) and Knowledge (Epistemic Logic).

1. The Two Types of Games: "The Race" vs. "The Survival"

The paper looks at two different ways to play this game:

The Race (Reachability): The goal is to reach the finish line. If the Demon cuts all the roads before you get there, you lose.
- Analogy: It's like trying to drive to the airport. If the Demon closes every highway on-ramp before you get on, you miss your flight.
The Survival (Liveness): The goal isn't necessarily to reach a finish line; it's just to keep moving. You win if you can survive for $X$ $X$ number of turns without getting stuck.
- Analogy: It's like a game of "Red Light, Green Light" where the Demon is the traffic cop. You win if you can keep walking for 10 minutes without getting blocked.

The Discovery: The authors found that in the "Race" version, if the Demon plays perfectly, the Runner almost never wins (unless they start right next to the goal). The Demon can always cut the one specific road the Runner needs. However, in the "Survival" version, the Runner has a better chance because they just need to keep moving, not necessarily reach a specific spot.

2. The New Rulebook: Time and Strategy (ATL*)

The authors use a fancy logic system called ATL* (Alternating-time Temporal Logic). Think of this as upgrading from a black-and-white photo to a live-action movie with a strategy guide.

The Old Way (SML): "Is there a road left?" (Yes/No).
The New Way (ATL):* "Can the Runner force a path to the goal over time, even if the Demon tries to block it?"

This new system allows them to analyze Concurrent Games. In the old version, players took turns (Runner moves, then Demon moves). In the new version, they move simultaneously.

Analogy: Imagine playing chess, but both you and your opponent move a piece at the exact same time. If you both try to move to the same square, nothing happens! This adds a layer of chaos and strategy that the old logic couldn't handle.

3. The "Dynamic Cut" Problem

In math, there is a famous problem called the "Minimum Cut." Imagine a dam holding back water. You want to find the smallest number of rocks to remove to stop the water from flowing from the top to the bottom.

The authors realized that in their game, the "Minimum Cut" isn't static. It changes as the Runner moves!

Analogy: Imagine a maze. The "static" minimum cut is the fewest walls you need to knock down to stop someone from entering. But in this game, the Runner is running while you are knocking down walls.
If you knock down the "obvious" wall, the Runner might have already run past it to a new section of the maze. The Demon has to be smarter, predicting where the Runner will be, not just where they are. The authors use their new logic to calculate this "Dynamic Minimum Cut."

4. The "Blind" Game (Epistemic Logic)

The final part of the paper adds a twist: What if the players can't see everything?

This is called Epistemic Logic (the logic of knowledge).

Perfect Information: Both players see the whole map and know exactly where the other is.
Imperfect Information: The Demon might know the Runner is in a "forest," but doesn't know if they are at the North entrance or the South entrance.

The Big Surprise:
The authors show that a player can have a winning strategy (a plan that guarantees a win) but not know that they have it.

Analogy: Imagine you are playing a video game on "Hard Mode" with a blindfold. You might accidentally stumble into a winning move. You won, but you didn't know you were going to win until it happened.
In the paper's example, the Runner might have a path to victory, but because they can't see the whole map, they don't know which path to take. Conversely, the Demon might have a way to block the Runner, but because the Demon can't see where the Runner is, they can't execute the block.

Summary: Why Does This Matter?

This paper isn't just about abstract games; it's about real-world systems that change over time and where information is incomplete.

Traffic Networks: Can you get to the airport if a terrorist (Demon) keeps closing roads?
Computer Security: Can a hacker break into a system if the network keeps changing?
Robotics: Can a robot navigate a collapsing building?

By using this new "Time + Knowledge" logic, the authors provide a better toolkit for engineers and scientists to design systems that are robust, secure, and capable of handling uncertainty. They moved the conversation from "Can we win?" to "How do we win over time, even when we don't know everything?"

1. Problem Statement

Sabotage games model scenarios where an agent (the runner) attempts to navigate a graph to reach a goal or survive, while an adversary (the demon or blocker) dynamically removes edges to obstruct the runner. Traditionally, these games have been analyzed using Sabotage Modal Logic (SML). While SML is effective for expressing static properties and winning conditions in strictly turn-based settings, it has significant limitations:

It lacks native temporal reasoning capabilities to handle complex sequences of moves and dynamic graph evolution over time.
It struggles with concurrent moves (where agents act simultaneously).
It does not naturally accommodate epistemic reasoning (uncertainty about the game state or other agents' knowledge).
It treats "reachability" and "liveness" as static properties rather than temporal ones.

The paper aims to reconstruct sabotage games within the framework of Alternating-time Temporal Logic (ATL and ATL*) to provide a unified logical framework that integrates strategic temporal reasoning with adversarial structural changes, including extensions for imperfect information.

2. Methodology

The authors employ a formal logical approach, reconstructing sabotage games as game structures compatible with ATL*.

Game Structures: They define three types of sabotage game structures based on a graph $G=(V,E)$ $G = (V, E)$ :
1. Turn-based (tb): Agents move strictly in turns (Runner, then Demon).
2. Concurrent (con): Agents move simultaneously. Conflicting choices (e.g., runner moving on an edge demon deletes) result in cancellation.
3. General (gen): A flexible structure allowing agents to choose to move or skip, simulating any order of play (strict turns, concurrency, or mixed).
Logic Framework: The authors utilize ATL*, a multi-agent extension of CTL*. This allows for:
- Strategic Operators: $\langle\langle C \rangle\rangle \phi$ , meaning "coalition $C$ has a strategy to enforce $\phi$ ."
- Temporal Operators: $X$ (next), $G$ (globally), $U$ (until), and a parametrized until operator ( $U_i$ ) borrowed from metric temporal logic to handle specific time bounds.
Epistemic Extension: The framework is extended to Alternating-time Temporal Epistemic Logic (ATEL) by introducing accessibility relations ( $\sim_i$ ) to model agents' uncertainty regarding the current game state (edges remaining and runner's position).
Modeling: Game states are defined as pairs $(E', v)$ , representing the set of remaining edges and the runner's current vertex. Labeling functions map these states to propositions regarding the runner's position and available edges.

3. Key Contributions

A. Formalization of Sabotage Games in ATL*

The paper provides a rigorous reconstruction of sabotage games as ATL* models. This allows for the direct expression of winning strategies using temporal logic rather than inductively defined modal formulas.

Reachability Sabotage Games (RSG): The existence of a winning strategy for the runner is expressed as $\langle\langle \{r\} \rangle\rangle F g$ (runner can enforce reaching the goal $g$ ).
Liveness Sabotage Games (LSG): A new variant is introduced where the runner's goal is to survive for at least $b$ moves. This is expressed using the parametrized until operator: $\langle\langle \{r\} \rangle\rangle \top U_{2b} (X\top)$ .

B. Analysis of Game Variants and Incentives

The authors analyze different incentive structures (eager vs. unwilling runner, helpful vs. unhelpful demon) and compare SML formulas with their ATL equivalents.

Turn-based vs. Concurrent: They demonstrate that while turn-based games allow for specific winning conditions, concurrent games introduce new dynamics. For instance, in concurrent games, a runner can be "stuck" if the demon chooses the same edge, preventing any movement.
Impossibility Results: A key finding is that in simple graphs (without multi-edges), a runner in a turn-based RSG can almost never win if the goal is not immediately reachable. The demon can always delete the specific edge leading to the goal on their turn. This explains why sabotage games are often studied on multi-graphs.

C. Dynamic Minimum $s-t$ Cut

The paper bridges game theory and graph theory by relating sabotage strategies to the Minimum Cut problem.

Static vs. Dynamic: The authors distinguish between the static minimum $s-t$ cut (edges to remove to disconnect $s$ and $t$ ) and the dynamic minimum $s-t$ cut.
Dynamic Cut Definition: The dynamic cut is defined as the minimum number of rounds the demon needs to play to prevent the runner from reaching the goal, accounting for the runner's ability to move between edge deletions.
Logical Characterization: They express the dynamic cut size $k$ using ATL*: $k$ is the smallest integer such that $\langle\langle \{d\} \rangle\rangle (\top U_k (\langle\langle \emptyset \rangle\rangle G \neg g))$ holds. This connects logical strategy existence to algorithmic graph problems.

D. Angelic Sabotage Games

The framework is extended to Angelic Sabotage Games, introducing a third agent (the "builder") who can add edges. This allows for infinite games and the expression of complex properties like "visiting the goal infinitely often" ( $\langle\langle C \rangle\rangle G F g$ ), which requires the full power of ATL* (nested temporal operators) rather than simple ATL.

E. Epistemic Reasoning (ATEL)

The paper addresses the problem of imperfect information.

Knowledge vs. Strategy: It highlights the distinction between having a winning strategy and knowing one has a winning strategy.
Examples:
- A runner may have a winning strategy but, due to limited observation (e.g., only seeing the number of outgoing edges), cannot distinguish between a winning and losing position.
- A demon may have a winning strategy in a perfect information setting but fail to apply it in an imperfect information setting because they cannot distinguish the runner's current location.
Semantics Adjustment: The authors note that standard ATEL semantics may counterintuitively attribute knowledge of a strategy to an agent who cannot execute it due to uncertainty. They suggest adjusting semantics to account for "belief states" (as proposed in [21]) to correctly model strategies under imperfect information.

4. Results

Expressiveness: ATL* successfully captures winning conditions for both reachability and liveness sabotage games, including variants with different player incentives and cooperative/competitive dynamics.
Concurrent Dynamics: The analysis reveals that concurrent sabotage games are more restrictive for the runner than turn-based games due to the possibility of action cancellation.
Graph Theory Connection: The paper establishes a formal link between the "time to win" in sabotage games and the dynamic minimum cut problem, offering a logical perspective on dynamic graph algorithms.
Epistemic Limitations: The study confirms that in sabotage games with imperfect information, the existence of a strategy does not imply the agent's knowledge of that strategy, necessitating careful semantic definitions in ATEL.

5. Significance

This work is significant for several reasons:

Unification: It unifies the study of sabotage games under the robust framework of Alternating-time Temporal Logic, moving beyond the limitations of Sabotage Modal Logic.
Temporal Dynamics: It treats sabotage not just as a static graph modification but as a temporal process, allowing for the analysis of "liveness" and dynamic connectivity.
Interdisciplinary Bridge: It connects formal logic, game theory, and algorithmic graph theory (specifically dynamic min-cut problems), suggesting new directions for research in dynamic graph algorithms.
Epistemic Depth: By incorporating epistemic logic, it addresses real-world scenarios where agents operate with incomplete information, a crucial aspect for applications in multi-agent systems, network security, and formal learning.
Future Directions: The paper opens avenues for studying infinite games, distributed goals, multiple runners, and the interplay between positional and memory-based strategies in dynamic environments.