Paper deep dive
Feedback Dominance Analysis for Pursuit-Evasion Games on Graphs
Yue Guan, Daigo Shishika, Dipankar Maity, Michael Dorothy, Panagiotis Tsiotras
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/6/2026, 10:01:37 AM
Summary
This paper introduces a set-based dynamic programming approach to analyze discrete, simultaneous-move pursuit-evasion games on graphs. It defines necessary and sufficient conditions for the Pursuer's winning (dominance) and losing regions, addressing limitations of previous geometric methods that relied on open-loop strategies. For states where neither player can guarantee a win (the 'gray zone'), the authors propose an instantaneous matrix-game formulation to establish bounds on the Pursuer's winning probability. The framework allows for the synthesis of feedback strategies that adapt to real-time positions.
Entities (8)
Relation Signals (6)
Pursuer → playsagainst → Evader
confidence 98% · discrete, simultaneous-move pursuit-evasion games
Set-based Dynamic Programming → characterizes → Dominance Region
confidence 95% · we develop a set-based dynamic programming approach to characterize the pursuer's winning and losing regions
Set-based Dynamic Programming → characterizes → Losing Region
confidence 95% · we develop a set-based dynamic programming approach to characterize the pursuer's winning and losing regions
Dominance Region → enables → Feedback Strategy
confidence 92% · allowing translation of dominance sets to feedback strategies that adapt to the players' positions in real time
Matrix-game → analyzes → Gray Zone
confidence 90% · For states where neither player can guarantee victory, we introduce an instantaneous matrix-game formulation
Matrix-game → establishesboundson → Winning Probability
confidence 90% · establish upper and lower bounds on the pursuer's winning probability
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This work identifies the dominance regions for discrete, simultaneous-move pursuit-evasion games on graphs. Existing geometric approaches provide efficient characterizations of winning regions, but typically provide only sufficient conditions and rely on open-loop strategies. To address these challenges, we develop a set-based dynamic programming approach to characterize the pursuer's winning and losing regions, providing necessary and sufficient winning conditions under worst-case behavior. The reachability analysis admits a set-chasing interpretation, allowing translation of dominance sets to feedback strategies that adapt to the players' positions in real time. For states where neither player can guarantee victory, we introduce an instantaneous matrix-game formulation and establish upper and lower bounds on the pursuer's winning probability. Simulation results validate the correctness of the dominance-region characterization and the proposed bounds.
Tags
Links
- Source: https://arxiv.org/abs/2610.06186v1
- Canonical: https://arxiv.org/abs/2610.06186v1
Trouble viewing inline? Open PDF directly →
Full Text
45,318 characters extracted from source content.
Expand or collapse full text
Feedback Dominance Analysis for Pursuit–Evasion Games on Graphs Yue Guan Daigo Shishika Dipankar Maity Michael Dorothy Panagiotis Tsiotras †thanks: The views expressed in this paper are those of the authors and do not reflect the official policy or position of the United States Army, Department of Defense, or the United States Government. Affiliation: Yue Guan and Panagiotis Tsiotras are with the School of Aerospace Engineering, Georgia Institute of Technology, Atlanta, GA, USA. \yguan44, tsiotras\@gatech.edu Affiliation: Daigo Shishika is with the College of Engineering and Computing, George Mason University, Fairfax, VA, USA. dshishik@gmu.edu Affiliation: Dipankar Maity is with the Department of Electrical and Computer Engineering, University of North Carolina at Charlotte, Charlotte, NC, USA. dmaity@charlotte.edu Affiliation: Michael Dorothy is with DEVCOM Army Research Laboratory, Adelphi, MD, USA. michael.r.dorothy.civ@army.mil Abstract This work identifies the dominance regions for discrete, simultaneous-move pursuit-evasion games on graphs. Existing geometric approaches provide efficient characterizations of winning regions, but typically provide only sufficient conditions and rely on open-loop strategies. To address these challenges, we develop a set-based dynamic programming approach to characterize the Pursuer’s winning and losing regions, providing necessary and sufficient winning conditions under worst-case behavior. The reachability analysis admits a set-chasing interpretation, allowing translation of dominance sets to feedback strategies that adapt to the players’ positions in real time. For states where neither player can guarantee victory, we introduce an instantaneous matrix-game formulation and establish upper and lower bounds on the Pursuer’s winning probability. Simulation results validate the correctness of the dominance-region characterization and the proposed bounds. I Introduction Pursuit–evasion games (PEGs) have been studied extensively due to their fundamental role in defense [1], security [2], and multi-robot systems [3]. In its basic form, a PEG, also known as the cops-and-robbers game [4], considers an Evader attempting to avoid capture by a Pursuer. Many important variants extend this formulation, including reach-avoid games [5] with added evasion states, perimeter-defense games [3] with Pursuers restricted to a region’s perimeter, target-defense [6] games with turrets aiming at Evaders, etc. A standard approach to solving PEGs is through a game-of-degree formulation, where agents optimize performance metrics such as time-to-capture or time-to-escape. In continuous domains, such problems can be formulated as differential games and solved via Hamilton–Jacobi–Isaacs (HJI) equations [7], yielding optimal feedback strategies. In discrete settings, PEGs can be modeled as stochastic games, where Nash equilibria can be computed using value iteration [8]. While these approaches are general and provide guarantees, they do not exploit the underlying geometric structure and are therefore computationally expensive, if not intractable. An alternative line of work leverages geometric structure to obtain efficient solutions for PEGs. In continuous obstacle-free environments, reachability-based constructions such as the Apollonius circle (AC) [9, 10] characterize the set of points that each agent can reach first. This leads to the notion of dominance regions, where, roughly speaking, if the Evader can reach an evasion state strictly earlier than the Pursuer, then successful evasion is guaranteed. Such approaches are computationally efficient and admit closed-form solutions [11]. However, they provide only sufficient conditions and typically yield open-loop strategies based on shortest-path comparisons. This limitation becomes critical in environments with obstacles. Even when the Pursuer can reach all evasion states faster than the Evader, it may still fail to guarantee capture due to dilemmas, where committing to protect one evasion state allows the Evader to escape through others. In such cases, geometric shortest-path comparisons become overly conservative and fail to fully capture the strategic interaction. Fig. 1: Dilemma faced by the (blue) Pursuer, exploited by the (red) Evader. Black cells denote obstacles, and green squares mark evasion states. To illustrate this limitation, consider the scenario in Fig. 1. Although the Pursuer is strictly closer to both evasion states, it must commit immediately to a specific direction due to the obstacle, while the Evader can delay its decision until it reaches point A. As a result, the Evader can employ a feedback strategy that guarantees successful evasion by conditioning on the Pursuer’s position when the Evader reaches point A. This behavior cannot be captured by existing open-loop geometric analyses, thus motivating the feedback-based dominance analysis proposed in this work. To address these challenges, prior works have introduced additional structural assumptions, such as sequential actions or restricted motion models [12, 13, 14]. More recent work [15] considers simultaneous-move formulations, but remains limited to grid environments without obstacles. Contributions: In this work, we develop a reachability-based framework for simultaneous-move PEGs on general graphs with arbitrary capture regions. We propose a set-based dynamic programming approach to characterize the winning and losing regions of the Pursuer, providing necessary and sufficient conditions under worst-case encounters. This characterization admits a natural set-chasing interpretation [16], leading to closed-loop strategies that adapt to the agents’ actions. Furthermore, for states where neither player can guarantee victory, we introduce an instantaneous matrix-game formulation to analyze the resulting gray zone, and derive upper and lower bounds on the Pursuer’s winning probability. Overall, the proposed framework bridges geometric dominance analysis and feedback-based methods, while remaining computationally tractable and applicable to general graph environments. The effectiveness of the proposed approach is validated through numerical simulations. I Problem Formulation We study a discrete-time, two-agent pursuit–evasion game (PEG) with discrete state and action spaces. The Pursuer and the Evader move on a shared discrete environment S. Their states at time t are denoted by xt∈x_t and yt∈y_t , respectively, and their actions by ut∈(xt)u_t (x_t) and vt∈(yt)v_t (y_t), where (xt)U(x_t) and (yt)V(y_t) are nonempty, state-dependent action sets. We assume deterministic, separable dynamics: xt+1=f(xt,ut),yt+1=g(yt,vt).x_t+1=f(x_t,u_t), y_t+1=g(y_t,v_t). The Pursuer’s capture region is given by Capt(xt)⊆Capt(x_t) , and the set of evasion states is ⊆T . Capture occurs when yt∈Capt(xt)y_t (x_t), whereas successful evasion occurs when yt∈∖Capt(xt)y_t (x_t). The game terminates at the first occurrence of either event. At each nonterminal time step, both players observe the current joint state (xt,yt)(x_t,y_t) and select their actions simultaneously. Let Π denote the set of admissible Pursuer strategies π:×→((⋅))π:S\!×\!S\!→\!P(U(·)), where π(u|x,y)π(u|x,y) denotes the probability of selecting action u at joint state (x,y)(x,y). The Evader’s strategy σ and admissible strategy set Σ are defined analogously. We consider a game of kind: the Pursuer wins if capture occurs or if the game continues indefinitely without successful evasion; the Evader wins if successful evasion occurs. We say that a Pursuer strategy π guarantees a win from a given initial joint state if it achieves the winning condition with probability one against every admissible Evader strategy. In summary, the game is described by the tuple PEG=⟨,,,f,g,Capt,⟩, PEG= ,U,V,f,g,Capt,T , (1) and we pursue the following research objectives: Objective 1: Characterize the dominance region from which the Pursuer can guarantee a win, as well as the region from which the Evader can guarantee finite-time evasion. Objective 2: Construct feedback strategies that guarantee the Pursuer’s victory from its dominance region. Objective 3: For states outside both dominance regions, derive bounds on Pursuer’s optimal worst-case win rate. I Pursuer Dominance Region We begin by defining the Pursuer’s dominance region. Definition 1. The k-step Pursuer’s Dominance Region (DR), denoted by (y,k)Q(y,k), is the set of Pursuer states such that, given the Evader’s current state y, the Pursuer can guarantee (with probability one) that the Evader does not successfully evade within k time steps. To characterize the set (y,k)Q(y,k), we adopt a reachability-based analysis similar in spirit to the Apollonius circle construction [11] in continuous pursuit–evasion. We first define the one-step reachable sets, which contain all states an agent can reach in the next time step from its current state: ℛx(xt) _x(x_t) =xt+1∣∃u∈(xt) s.t. xt+1=f(xt,u), =\x_t+1 ∃ u (x_t) s.t. x_t+1=f(x_t,u)\, (2) ℛy(yt) _y(y_t) =yt+1∣∃v∈(yt) s.t. yt+1=g(yt,v). =\y_t+1 ∃ v (y_t) s.t. y_t+1=g(y_t,v)\. Given a set of Pursuer states X, we define the inverse reachability operator which returns the set of states that can reach X in one time step: ℛx−1() 0.7$-1$_x(X) =x∣∃u∈(x) such that f(x,u)∈, =\x ∃ u (x) such that f(x,u) \, (3) For notational simplicity, we further define the next-step potential capture region and the inverse capture region as ℛcap(xt)=⋃xt+1∈ℛx(xt)Capt(xt+1), _cap(x_t)= _x_t+1 _x(x_t)Capt(x_t+1), Capt−1(yt)=xt∣yt∈Capt(xt). 0.7$-1$(y_t)=\x_t y_t (x_t)\. I-A Current-step Failure Similar to other dynamic programming approaches, we begin with the terminal condition for the DR, which consists of all states xtx_t, given the current Evader state yty_t, that do not result in an immediate Pursuer defeat. (yt,0)=xt∣yt∈Capt(xt)∪c,Q(y_t,0)=\x_t y_t (x_t) ^c\, (4) where c=∖T^c=S denotes the complement of the set of evasion states. In words, a state pair (xt,yt)(x_t,y_t) does not constitute a Pursuer’s defeat if either the Evader is captured by the Pursuer (i.e., yt∈Capt(xt)y_t (x_t)), or the Evader has not reached an evasion state (i.e., yt∈cy_t ^c). Since (yt,0)Q(y_t,0) dictates the fundamental requirement for the Pursuer to survive the current step, any k-step dominance guarantee must recursively satisfy this baseline. For this reason, we denote req(yt)≜(yt,0)P_req(y_t) (y_t,0) and refer to it as the required set, serving as the foundational building block for constructing the k-step DR in the sequel. Fig. 2: An illustrative example of the sequence of Q-sets and Z-sets in a 10×1010× 10 grid environment. The red dot indicates the current Evader position yty_t for which the Q-sets and Z-sets are visualized. The Pursuer has 8-way mobility and a ×33\!×\!3 capture region, whereas the Evader has 4-way mobility. I-B Single-step DR Now, we examine the conditions under which the Pursuer avoids immediate defeat at the next time step. Proposition 1. Given the current states xtx_t and yty_t, the Pursuer can guarantee that it does not lose the game at time t+1t+1 if and only if xt∈(yt,1)x_t (y_t,1), where: (yt,1)= (y_t,1)= Capt−1(yt) \;Capt 0.7$-1$(y_t) (5) ∪(req(yt)∩ℛx−1(∩yt+1∈ℛy(yt)(yt+1,0)⏟+(yt,1))). 1.8$∪$ (P_req(y_t) 1.8$∩$ 0.7$-1$_x ( 1.8$∩$ _ y_t+1 _y(y_t)Q(y_t+1,0)_Q^+(y_t,1) ) ). Proof Sketch. There are two cases where the Pursuer can deterministically prevent its defeat at t+1t+1: (i) the Pursuer captures the Evader at the current time step, i.e., xt∈Capt−1(yt)x_t 0.7$-1$(y_t); (i) the Pursuer survives both stages t and stage t+1t+1. For the second case, survival at time t requires xt∈req(yt)x_t _req(y_t). To further ensure survival at time t+1t+1, the Pursuer must reach a state xt+1x_t+1 such that, for all possible states yt+1∈ℛy(yt)y_t+1 _y(y_t) chosen by the Evader, the pair (xt+1,yt+1)(x_t+1,y_t+1) does not result in Pursuer’s defeat, i.e., xt+1∈(yt+1,0)x_t+1 (y_t+1,0). This yields the condition xt+1∈+(yt,1)x_t+1\!∈\!Q^+(y_t,1) in (5), where +(yt,1)Q^+(y_t,1) is the set of desirable next Pursuer states. To reach one of these desirable states, the Pursuer must satisfy xt∈ℛx−1(+)x_t\!∈\!R 0.7$-1$_x(Q^+). ∎ I-C k-step DR Building upon the analysis for 11-step DR, we can generalize the dominance region to arbitrary time horizons using a recursive set-based dynamic programming approach [17]. Theorem 2. Let xtx_t and yty_t be the current states. The Pursuer can guarantee that it does not lose the game within k time steps if and only if xt∈(yt,k)x_t (y_t,k), which satisfies: (yt,k) (y_t,k) =Capt−1(yt) =Capt 0.7$-1$(y_t) (6) ∪(req(yt)∩ℛx−1(∩yt+1∈ℛy(yt)(yt+1,k−1))). -7.22743pt 1.8$∪$ (P_req(y_t) 1.8$∩$ 0.7$-1$_x ( 1.8$∩$ _ y_t+1 _y(y_t)Q(y_t+1,k-1) ) ). Proof. We proceed by induction on k. Base Case: Proposition 1 shows that xt∈(yt,1)x_t\!∈\!Q(y_t,1) is necessary and sufficient for Pursuer to avoid losing at time t+1t+1. Inductive Step: Suppose the statement holds for k−1k-1, we show that it holds for k. Sufficiency: If xt∈(yt,k)x_t\!∈\!\!Q(y_t,k), then either (i) xt∈Capt−1(yt)x_t\!∈\!\!Capt 0.7$-1$\!(y_t), which ensures immediate capture, or (i) xt∈req(yt)∩ℛx−1(∩yt+1∈ℛy(yt)(yt+1,k−1))x_t _req(y_t) 0.7$-1$_x ( _ y_t+1 _y(y_t)Q(y_t+1,k-1) ). For case (i), xt∈req(yt)x_t\!∈\!P_req(y_t) guarantees the Pursuer’s survival at the current time step. Moreover, xt∈ℛx−1(∩yt+1∈ℛy(yt)(yt+1,k−1))x_t 0.7$-1$_x ( _ y_t+1 _y(y_t)Q(y_t+1,k-1) ) ensures that the Pursuer can select a reachable state xt+1x_t+1 such that for all yt+1∈ℛy(yt)y_t+1 _y(y_t), we have xt+1∈(yt+1,k−1)x_t+1 (y_t+1,k-1). By the inductive hypothesis, this ensures that the Pursuer can deterministically avoid defeat for the remaining k−1k-1 steps, completing the proof of sufficiency. Necessity: Suppose xt∉(yt,k)x_t (y_t,k). Then xt∉Capt−1(yt)x_t 0.7$-1$(y_t), so capture does not occur at time t, and furthermore xt∉req(yt)∩ℛx−1(∩yt+1∈ℛy(yt)(yt+1,k−1)).x_t _req(y_t) 1.8$∩$ 0.7$-1$_x\! ( 1.8$∩$ _ y_t+1 _y(y_t) -10.84006ptQ(y_t+1,k-1) ). This implies either: (i) xt∉req(yt)x_t _req(y_t), leading to immediate loss at time t; or (i) for every xt+1∈ℛx(xt)x_t+1 _x(x_t), there exists some yt+1∈ℛy(yt)y_t+1 _y(y_t) such that xt+1∉(yt+1,k−1)x_t+1 (y_t+1,k-1). By the inductive hypothesis, being in (yt+1,k−1)Q(y_t+1,k-1) is necessary to avoid losing over the next k−1k-1 steps. Hence, starting from xt∉(yt,k)x_t (y_t,k), the Pursuer cannot deterministically avoid defeat within k steps, therefore establishing necessity. ∎ Since k-step dominance necessarily implies ℓ -step dominance for all ℓ≤k ≤ k, we have the following remark. Remark 1. The sequence of DRs forms a non-increasing sequence of sets. Formally, for all y∈y , (y,0)⊇(y,1)⊇(y,2)⊇⋯.Q(y,0) (y,1) (y,2) ·s. Theorem 3. If the state space is finite, i.e., ||<∞|S|<∞, then the DR iteration (6) converges in a finite number of steps. Proof. This follows directly from the finiteness of the Q-sets and the fact that they form a non-increasing sequence. ∎ I-D Indefinite DR As Theorem 3 ensures finite-step convergence of the Q-sets, we denote the converged Q-sets as ∞(y)Q_∞(y), which leads to the following corollary on indefinite survival. Corollary 4. Given the current states xtx_t and yty_t, the Pursuer can guarantee a win if and only if xt∈∞(yt)x_t _∞(y_t). Proof. The limiting sets satisfy the fixed-point relation: ∞(y)=Capt−1(y)∪(req(y)∩ℛx−1(∩y′∈ℛy(y)∞(y′))). -7.22743ptQ_∞(y)=Capt 0.7$-1$(y) 1.8$∪$ (P_req(y) 1.8$∩$ 0.7$-1$_x ( -3.61371pt 1.8$∩$ _ y _y(y) -3.61371ptQ_∞(y ) ) ). Thus, if xt∈∞(yt)x_t _∞(y_t), the Pursuer can either capture immediately or move to xt+1∈∞(yt+1)x_t+1 _∞(y_t+1) for all possible yt+1∈ℛy(yt)y_t+1 _y(y_t). Since ∞(yt)⊆(yt,k)Q_∞(y_t) (y_t,k) for any k≥1k≥ 1, the Pursuer can survive for k steps starting at xt∈∞(yt)x_t _∞(y_t). Transitioning to xt+1∈∞(yt+1)⊆(yt+1,k)x_t+1 _∞(y_t+1) (y_t+1,k) again guarantees Pursuer’s survival for another k steps. Repeating this selection guarantees either capture or indefinite prevention of evasion, both of which constitute a Pursuer win. Conversely, if xt∉∞(yt)x_t _∞(y_t), then xt∉(yt,K)x_t (y_t,K) for some finite K. By Theorem 2, the Pursuer cannot guarantee avoidance of defeat within K steps and therefore cannot guarantee a win over the infinite horizon. ∎ Fig. 2 presents a sequence of the DR (Q-sets) generated for a specific Evader state marked with the red dot. States within the DR are shown in blue. IV Pursuer’s Losing Set and Gray Zone Conversely, we also characterize the states from which the Pursuer is guaranteed to lose (i.e., the Evader reaches an evasion state without being captured) regardless of the Pursuer’s strategy. Theorem 5. The Pursuer is guaranteed to lose within k time steps if and only if its current state xt∈(yt,k)x_t (y_t,k), where the Z-sets are defined through recursion: (yt,0)=xt∣yt∈∖Capt(xt) (y_t,0)= \x_t y_t (x_t) \ (7a) (yt,k)=(yt,0)∪((∖Capt−1(yt))∩CLOSE (y_t,k)=Z(y_t,0) 1.8$∪$ ((S 0.7$-1$(y_t))\;∩ (7b) OPEN∪yt+1∈ℛy(yt)xt∣ℛx(xt)⊆(yt+1,k−1)). 36.135pt 1.8$∪$ _ y_t+1 _y(y_t) -10.84006pt\\,x_t _x(x_t) (y_t+1,k-1)\ ). Proof Sketch. The high-level inductive argument is similar to that of Theorem 2. For k=0k=0, (7a) characterizes all Pursuer states such that the given Evader state yty_t lies in the evasion region T without being captured, which results in an immediate loss for the Pursuer. For the inductive step, the Evader can guarantee the Pursuer’s defeat within k steps if and only if either the Pursuer has already lost at the current step (i.e., xt∈(yt,0)x_t (y_t,0)), or capture has not occurred and there exists an admissible Evader move yt+1y_t+1 such that every reachable Pursuer state lies in the corresponding (k−1)(k-1)-step losing set (i.e., ℛx(xt)⊆(yt+1,k−1)R_x(x_t) (y_t+1,k-1)). Taking the union over all admissible Evader next states, while excluding current capture states, yields (7b). ∎ Since losing within k steps necessarily implies losing within ℓ steps for all ℓ≥k ≥ k, we have the following remark. Remark 2. The sequence of Pursuer losing sets forms a non-decreasing sequence of sets. Formally, for all y∈y , (y,0)⊆(y,1)⊆(y,2)⊆⋯.Z(y,0) (y,1) (y,2) ·s. Similar to the DR sets, we also have the following convergence result for the losing sets. Theorem 6. If ||<∞|S|<∞, then the losing set iteration (7b) converges in a finite number of steps. Remark 3. We have (y,k)∩(y,k)=∅Q(y,k) (y,k)= for all y∈y and k∈ℤ≥0k _≥ 0, due to the necessity and sufficiency of the Q-sets and Z-sets. An example sequence of Z-sets is also presented in Fig. 2. IV-A Gray Zone The dominance region (y,k)Q(y,k) and the losing set (y,k)Z(y,k) rigorously characterize the states from which the Pursuer can either guarantee not losing or is certain to fail. However, due to the simultaneous-move structure of the discrete pursuit–evasion game, there often exist states from which neither victory nor defeat can be guaranteed with certainty. We formally define this probabilistic “gray zone” as the complement of the two k-step guaranteed sets: (yt,k)=∖((yt,k)∪(yt,k)).G(y_t,k)=S (Q(y_t,k) (y_t,k) ). (8) If xt∈(yt,k)x_t (y_t,k), the Pursuer cannot guarantee that it avoids defeat over the next k steps, while the Evader cannot guarantee successful evasion within the k steps. The infinite-horizon gray zone is defined as ∞(y)=∖(∞(y)∪∞(y)).G_∞(y)=S\! \! (Q_∞(y) _∞(y) ). Specifically, when the Pursuer is in the gray zone, both agents face a dilemma either currently or at a future time step. Consider the gray region in Fig. 2 with k=11k=11 and a scenario illustrated in Fig. 3. At the current time step, the Pursuer lies in the gray zone. Over the next two steps, the Evader and Pursuer move toward points A and B, respectively, and the corresponding Q/Z-sets and gray region are shown. The Evader has two possible escape options: the bottom-left or bottom-right evasion state. To intercept successfully, the Pursuer must exploit its diagonal motion and follow a shortest path. However, the L-shaped obstacle forces the Pursuer to commit to a direction. Since the capture timing is tight, once committed, the Pursuer cannot adjust if the Evader selects the other escape route. Similarly, the Evader cannot switch without being captured. Consequently, the outcome is determined almost entirely by this single decision: if both agents choose the same evasion state, the Pursuer wins; otherwise, the Evader succeeds. Since a competitive game is being played, the agents may naturally randomize their decisions, which leads to probabilistic outcomes. Fig. 3: An illustration of the dilemma the Pursuer faces in the gray zone. V Feedback Policies From the Dominance Sets In this section, we construct feedback policies based on the Q-sets and Z-sets. Given the current state pair (xt,yt)(x_t,y_t), three cases arise: (a) Pursuer dominance: xt∈∞(yt)x_t _∞(y_t); the Pursuer can capture or indefinitely prevent evasion; (b) Evader dominance: xt∈(yt,k)x_t (y_t,k) for some k; the Evader is guaranteed to evade within k steps; (c) Gray zone: xt∈∞(yt)x_t _∞(y_t); the outcome is undetermined/probabilistic. We first examine the first two cases, which admit deterministic outcomes. V-A Pursuer Dominance Region Under case (a), the Pursuer is guaranteed to win by capture or by preventing evasion indefinitely. Given the current state pair (xt,yt)(x_t,y_t), the Pursuer should simply select its next state xt+1∈ℛx(xt)∩yt+1∈ℛy(yt)∞(yt+1),x_t+1 _x(x_t)∩ 1.8$∩$ _ y_t+1 _y(y_t)Q_∞(y_t+1), (9) so that the next Pursuer state lies in the corresponding Q-set, regardless of the action taken by the Evader. Such a state xt+1x_t+1 is always reachable from xtx_t due to the reachability construction, in particular the use of the ℛx−1R 0.7$-1$_x operator in (6). The resulting feedback strategy can be interpreted as “set chasing”, where the Pursuer continually chases a set of desirable next states given the observed Evader state yty_t. Note that the above feedback strategy does not prioritize capturing the Evader, even when capture can be guaranteed. To encode a preference for capture over indefinite evasion prevention, one may select xt+1x_t+1 in (9) so as to reduce the distance to the current state yty_t. Since we consider a game-of-kind formulation, both capture and no evasion constitute equivalent losing outcomes for the Evader. Therefore, under case (a), the Evader is guaranteed to lose regardless of its strategy. In practice, the Evader may adopt heuristic strategies such as moving towards the nearest evasion state, or towards a state in the Z-set, or simply maintaining distance from the Pursuer. V-B Evader Dominance Region Case (b) guarantees that the Evader evades within k steps. To minimize the time to evasion, the Evader first computes kmin=mink∣xt∈(yt,k).k_min= \k x_t (y_t,k)\. To make progress, the Evader targets the (kmin−1)(k_min\!-\!1)-step Z-set and selects its next state from the set +(yt,kmin)=y′∈ℛy(yt)|ℛx(xt)⊆(y′,kmin−1).Z^+(y_t,k_min)\!=\!\y \!∈\!R_y(y_t)|R_x(x_t)\! \!Z(y ,k_min\!-\!1)\. (10) By choosing any yt+1∈+(yt,kmin)y_t+1 ^+(y_t,k_min), the Evader ensures that all possible Pursuer responses lie in (yt+1,kmin−1)Z(y_t+1,k_min-1), guaranteeing evasion within kmin−1k_min-1 steps. Although the Pursuer is destined to lose within kmink_min steps, it can attempt to delay this outcome. In particular, the Pursuer should avoid transitions to xt+1∈(yt+1,kmin−2)x_t+1 (y_t+1,k_min-2), which would reduce the remaining survival time by two steps rather than just one. Since the Pursuer does not know the Evader’s choice of yt+1y_t+1, it should select xt+1x_t+1 to minimize the number of yt+1∈+(yt,kmin)y_t+1 ^+(y_t,k_min) for which xt+1∈(yt+1,kmin−2)x_t+1 (y_t+1,k_min-2). Fig. 4: Game trajectories and the corresponding dominance sets at each Evader state. The blue Pursuer remains within the Q-set and captures the Evader. V-C Gray Zone When xt∈∞(yt)x_t _∞(y_t), neither the Pursuer nor the Evader can guarantee their victory. This arises because some future joint states favor the Pursuer, while others favor the Evader, as shown in Fig. 3. Since the next state is jointly determined by both agents, the outcome becomes inherently uncertain. In this case, we adopt a zero-sum matrix game formulation and allow both agents to randomize. Let the Pursuer’s feasible next states be indexed by i, where xt+1(i)∈ℛx(xt)x^(i)_t+1 _x(x_t), and the Evader’s next states be indexed by j, where yt+1(j)∈ℛy(yt)y^(j)_t+1 _y(y_t). We construct a payoff matrix M, where each entry MijM_ij evaluates the outcome of the next joint state (xt+1(i),yt+1(j))(x^(i)_t+1,y^(j)_t+1). Since states in the Q-set yield a winning probability of one for the Pursuer, while states in the Z-set yield zero, we define the payoff matrix as Mij=1if xt+1(i)∈∞(yt+1(j)),0if xt+1(i)∈(yt+1(j),k)for some k,rotherwise,M_ij= cases1&if x^(i)_t+1 _∞ (y^(j)_t+1 ),\\ 0&if x^(i)_t+1 (y^(j)_t+1,k )\ for some k,\\ r&otherwise, cases (11) where r∈0,0.5,1r∈\0,0.5,1\ reflects different levels of optimism, as discussed below. • Optimistic: r=1r=1, where the Pursuer assumes that transitioning into the gray zone will always result in its victory; • Pessimistic: r=0r=0, where the Pursuer assumes that entering the gray zone will always result in its defeat; • Neutral: r=0.5r=0.5, where the Pursuer assumes a 50/50 chance in the gray zone. We assume that the Pursuer maximizes the payoff while the Evader minimizes it, which leads to the following max-min optimization problem: maxπ∈Δ|ℛx(xt)|minσ∈Δ|ℛy(yt)|⊤M, _π∈ _|R_x(x_t)| _σ∈ _|R_y(y_t)| π M σ, (12) where Δn _n denotes the n-dimensional simplex. The above max-min problem can be solved via the following linear program [8]: max,v _ π,v~~ v ~~v (13) subject to ∑i[]iMij≥v, _i[ π]_iM_ij≥ v, ∀j with yt+1(j)∈ℛy(yt), ∀\,j with y^(j)_t+1 _y(y_t), ⊤=1,≥0. 1 π=1,~~ π≥ 0. The optimal solution ∗ π^* is a probability distribution over the Pursuer’s reachable set ℛx(xt)R_x(x_t), and its element [∗]i[ π^*]_i gives the probability of selecting xt+1(i)x^(i)_t+1 as the next Pursuer state. The Evader’s optimal strategy can be obtained from the dual variables of (13). V-D Bounds on Gray-Zone Winning Probability To properly bound the winning probability in the gray zone, we restrict our attention to dominance-rational strategies, where agents act optimally within the dominance sets. Definition 2. A Pursuer strategy is dominance-rational if it guarantees a win whenever xt∈∞(yt)x_t _∞(y_t). Similarly, an Evader strategy is dominance-rational if it guarantees the Pursuer’s defeat whenever xt∈(yt,k)x_t (y_t,k) for some k. Dominance rationality can be viewed as a necessary condition for optimal or equilibrium strategies. Note that the entries of matrix M capture the estimated winning probability of the Pursuer at each possible next state. The optimal value v∗v^* from (13) therefore corresponds to the equilibrium winning probability of the Pursuer, assuming that the estimates in M are accurate. While the entries 11 and 00, corresponding to the Q-sets and Z-sets, are exact under dominance-rational strategies, the entries involving r approximate the outcome in the gray zone. Nevertheless, the true winning probability always lies in [0,1][0,1]. Let MtrueM_true denote the accurate estimate under an arbitrary pair of dominance-rational strategies. We have the following element-wise inequality Mpess≤Mtrue≤Moptsm,M_pess≤ M_true≤ M_optsm, where MpessM_pess corresponds to the pessimistic case with r=0r=0 and MoptsmM_optsm corresponds to the optimistic case with r=1r=1. Lemma 7. Let vpess∗v^*_pess, vtrue∗v^*_true, and voptsm∗v^*_optsm be the optimal values of (13) corresponding to MpessM_pess, MtrueM_true, and MoptsmM_optsm, respectively. Then, we have vpess∗≤vtrue∗≤voptsm∗.v^*_pess≤ v^*_true≤ v^*_optsm. Proof. We show that if A,B∈ℝn×mA,B\!∈\!R^n× m satisfy A≥BA\!≥\!B elementwise, then we have vA∗≥vB∗v^*_A≥ v^*_B, where vA∗=maxπ∈Δnminσ∈Δmπ⊤Aσ,vB∗=maxπ∈Δnminσ∈Δmπ⊤Bσ.v^*_A= _π∈ _n _σ∈ _mπ Aσ, v^*_B= _π∈ _n _σ∈ _mπ Bσ. Since A≥BA≥ B elementwise and π,σ≥0π,σ≥ 0 are probability vectors, we have π⊤Aσ≥π⊤Bσπ Aσ≥π Bσ for all (π,σ)∈Δn×Δm(π,σ)∈ _n× _m. Let πB∗∈Δn _B^*∈ _n be an optimal row policy for game B, so that minσ∈Δm(πB∗)⊤Bσ=vB∗. _σ∈ _m( _B^*) Bσ=v_B^*. Since vA∗v_A^* is the maximum worst-case payoff over all π∈Δnπ∈ _n, evaluating game A at the specific policy πB∗ _B^* yields vA∗ v_A^* =maxπ∈Δnminσ∈Δmπ⊤Aσ≥minσ∈Δm(πB∗)⊤Aσ = _π∈ _n _σ∈ _mπ Aσ≥ _σ∈ _m( _B^*) Aσ ≥minσ∈Δm(πB∗)⊤Bσ=vB∗. ≥ _σ∈ _m( _B^*) Bσ=v_B^*. Therefore, vA∗≥vB∗v_A^*≥ v_B^*. ∎ Define the Pursuer’s optimal worst-case winning probability as V(xt,yt)=supπ∈Πinfσ∈Σℙπ,σ(Pursuer wins∣xt,yt).V(x_t,y_t)= _π∈ _σ∈ P_π,σ (Pursuer wins x_t,y_t ). Since the winning probability in the gray zone lies in [0,1][0,1], which corresponds to the MpessM_pess and MoptsmM_optsm matrices, we have the following bounds. Corollary 8. The pessimistic and optimistic matrix games provide lower and upper bounds on V(xt,yt)V(x_t,y_t), respectively. Specifically, at any joint state (xt,yt)(x_t,y_t) in the gray zone, vpess∗≤V(xt,yt)≤voptsm∗.v_pess ≤ V(x_t,y_t)≤ v_optsm . VI Numerical Experiments For clarity of exposition, we present results on the grid environment shown in Fig. 2. The Pursuer has 8-way mobility and a ×33\!×\!3 capture region, whereas the Evader has 4-way mobility. The proposed dominance set analysis and the set-based dynamic program, however, apply to arbitrary graphs and irregular Pursuer capture regions. All results are evaluated with 1,000 trials with a maximum horizon of 5050 steps; if the Evader fails to reach an evasion state within this horizon, the Pursuer is declared the winner. VI-A Dominance Regions We first revisit the dilemma example introduced earlier in Fig. 1. Fig. 5a shows the corresponding Q-set and Z-set, illustrating that the proposed set-based dynamic programming approach correctly identifies the given Pursuer state (blue point) as a losing state. Fig. 5: (a) Visualization of Q/Z-sets for the dilemma example. (b) Pursuer states used for performance evaluations. (c) Game trajectory with the Pursuer starting from Z-set. Fig. 4 illustrates the trajectories of the Pursuer and the Evader, with the Pursuer initially located in the Q-set (its dominance region), where its victory is guaranteed. In this scenario, we let the Evader follow a shortest path toward the bottom-right evasion state. The corresponding dominance sets at each Evader state are shown, illustrating that the Pursuer “chases” the Q-sets, remains within the Q-sets at each time step, and ultimately captures the Evader. Next, we compare the proposed policies derived from the dominance sets with Nash equilibrium (NE) policies. The NE policies are computed by treating the pursuit-evasion game as a stochastic game with a reward structure that assigns 11 for capture, −1-1 for successful evasion, and 00 otherwise. Under this zero-sum formulation, the Pursuer maximizes this reward while the Evader minimizes it, and we compute an NE via value iteration [18]. Importantly, NE policies are dominance-rational, i.e., whenever a winning opportunity exists, the agents exploit it optimally. As such, they provide a strong benchmark, acting optimally within the dominance regions and achieving the best performance against a fully rational opponent under worst-case assumptions11 1 The NE solution concept is inherently a game-of-degree formulation and thus differs from our game-of-kind formulation; nevertheless, it remains a natural and strong candidate for benchmarking. . This makes NE particularly suitable for validating the dominance-region analysis and for estimating the true winning probabilities in the gray zone. We evaluate the performance of different strategies at eight initial Pursuer states, while the Evader is fixed at the red dot as shown in Fig. 5b. Specifically, states Q1Q1–Q4Q4 lie in the Q-set, where an optimal Pursuer is expected to achieve a 100%100\% win rate. Similarly, states Z1Z1–Z4Z4 lie in the Z-set, where the Evader is guaranteed to evade. TABLE I: Simulated Pursuer Win Rate in Dominance Regions Q States Z States State Pursuer Win Rate State Pursuer Win Rate Q1Q1 1.01.0 Z1Z1 0.00.0 Q2Q2 1.01.0 Z2Z2 0.00.0 Q3Q3 1.01.0 Z3Z3 0.00.0 Q4Q4 1.01.0 Z4Z4 0.00.0 Table I reports the Pursuer winning probabilities for the Q- and Z-states. For Q-states, we evaluate the Q-set-based Pursuer strategy against a Nash Evader strategy to avoid bias toward a specific opponent. Similarly, we evaluate the Z-set-based Evader strategy against a Nash Pursuer strategy for the Z-states. The simulation results are fully consistent with the dominance-region analysis. In particular, xt∈∞(yt)x_t _∞(y_t) guarantees the Pursuer’s victory, whereas xt∈(yt,k)x_t (y_t,k) guarantees evasion and thus the Pursuer’s loss. Next, we examine the Pursuer state Z1Z1 marked in Fig. 5b. The k=8k\!=\!8 panel of Fig. 2 shows that Z1∈(yt,8)Z1 (y_t,8), implying guaranteed evasion within eight steps. To validate this, we plot a sample trajectory of a Nash Pursuer against a Z-set-based Evader in Fig. 5c. Consistent with the theory, the Evader successfully evades within 8 steps, even against the optimal Nash Pursuer. VI-B Gray Zone For the gray zone, we examine the scenario in Fig. 3 and analyze the LP solution from (13). There are 8 feasible Pursuer next states and 5 feasible Evader next states, as illustrated in Fig. 6. Based on (11), the resulting payoff matrix is M⊤=[r0000000000000r0r100000001r1].M = 0.85$ [ array[]cr&0&0&0&0&0&0&0\\ 0&0&0&0&0&0&r&0\\ r&r&r&r&r&r&r&1\\ 0&0&0&0&0&0&0&1\\ r&r&r&r&r&r&r&1\\ array ]$. For the optimistic case (r=1r=1), the LP in (13) yields voptsm∗=13v^*_optsm\!=\! 13, providing an upper bound on the Pursuer’s winning probability. The resulting optimal Pursuer policy is [13,0,0,0,0,0,13,13][ 13,0,0,0,0,0, 13, 13], so that the Pursuer randomizes uniformly among three actions: staying at its current position x(0)x^(0), moving to x(6)x^(6), and moving to x(7)x^(7). The Evader randomization is given by [13,13,0,13,0][ 13, 13,0, 13,0], that is, the Evader uniformly randomizes among staying at its current position y(0)y^(0), moving leftward to y(1)y^(1) and rightward to y(3)y^(3). In contrast, for the pessimistic case (r=0r=0), we obtain vpess∗=0v^*_pess\!=\!0, and an optimal solution is for both agents to remain at their current positions. This highlights that the optimistic Pursuer adopts a more proactive strategy to chase the Evader, whereas the pessimistic Pursuer remains conservative. Finally, we simulate 1,000 trajectories using the Nash policies and obtain a Pursuer win rate of 0.102∈[0,13]=[vpess∗,voptsm∗]0.102∈[0, 0.72229pt 13]=[v^*_pess,v^*_optsm], consistent with the bounds established in Corollary 8. Fig. 6: Illustrative example of LP construction in the gray zone. VII Conclusion In this work, we developed a reachability-based framework for analyzing dominance regions in simultaneous-move pursuit–evasion games on general graphs. Using a set-based dynamic programming approach, we characterized the Pursuer’s winning and losing regions, which lead to closed-loop feedback strategies that overcome limitations of existing open-loop analysis of dominance regions. For gray-zone states, where neither player can guarantee victory, we introduced a matrix-game formulation that provides bounds on the Pursuer’s winning probability. We demonstrate the correctness of the dominance-region characterization and the validity of the proposed gray-zone bounds through numerical simulations. Future work includes extending the framework to multi-agent settings and tightening gray-zone bounds. VIII Acknowledgment This work has been supported in part by ARL under DCIST CRA W911NF-17-2-0181 and by ONR award N00014-23-1-2308. References [1] R. Isaacs (1999) Differential games: a mathematical theory with applications to warfare and pursuit, control and optimization. Courier Corporation. Cited by: §I. [2] T. H. Chung, G. A. Hollinger, and V. Isler (2011) Search and pursuit-evasion in mobile robotics: a survey. Autonomous Robots 31 (4), p. 299–316. Cited by: §I. [3] D. Shishika and V. Kumar (2020) A review of multi agent perimeter defense games. In International Conference on Decision and Game Theory for Security, p. 472–485. Cited by: §I. [4] R. Nowakowski and P. Winkler (1983) Vertex-to-vertex pursuit in a graph. Discrete Mathematics 43 (2-3), p. 235–239. Cited by: §I. [5] M. Chen, S. Bansal, and C. J. Tomlin (2017) Reach-avoid games with time-varying dynamics, targets and constraints. IEEE Transactions on Automatic Control 62 (4), p. 1615–1630. Cited by: §I. [6] A. Von Moll, M. Pachter, D. Shishika, and Z. Fuchs (2022) Circular target defense differential games. IEEE Transactions on Automatic Control 68 (7), p. 4065–4078. Cited by: §I. [7] T. Basar and G. J. Olsder (1999) Dynamic noncooperative game theory. SIAM. Cited by: §I. [8] G. Owen (2013) Game theory. Emerald Group Publishing. Cited by: §I, §V-C. [9] M. V. Ramana and M. Kothari (2017) Pursuit-evasion games of high speed evader. Journal of Intelligent & Robotic Systems 85 (2), p. 293–306. Cited by: §I. [10] M. Pachter, A. Von Moll, E. Garcia, D. W. Casbeer, and D. Milutinović (2019) Two-on-one pursuit. Journal of Guidance, Control, and Dynamics 42 (7), p. 1638–1644. Cited by: §I. [11] M. Dorothy, D. Maity, D. Shishika, and A. Von Moll (2024) One apollonius circle is enough for many pursuit-evasion games. Automatica 163, p. 111587. Cited by: §I, §I. [12] F. Amigoni and N. Basilico (2012) A game theoretical approach to finding optimal strategies for pursuit evasion in grid environments. In 2012 IEEE International Conference on Robotics and Automation, p. 2155–2162. Cited by: §I. [13] F. V. Fomin, P. A. Golovach, and D. Lokshtanov (2011) Guard games on graphs: keep the intruder out!. Theoretical Computer Science 412 (46), p. 6484–6497. Cited by: §I. [14] H. Nagamochi (2011) Cop–robber guarding game with cycle robber-region. Theoretical Computer Science 412 (4-5), p. 383–390. Cited by: §I. [15] J. Berneburg, D. Shishika, and M. Dorothy (2025) Reach-avoid games on graphs: analysis and strategies. IEEE Control Systems Letters. Cited by: §I. [16] Y. Guan, L. Pan, D. Shishika, and P. Tsiotras (2023) On the adversarial convex body chasing problem. In 2023 American Control Conference (ACC), p. 435–440. Cited by: §I. [17] D. Shishika, Y. Guan, J. R. Marden, M. Dorothy, P. Tsiotras, and V. Kumar (2023) Dynamic adversarial resource allocation: the dDAB game. arXiv preprint arXiv:2304.02172. Cited by: §I-C. [18] Y. Guan, M. Afshari, Q. Zhang, and P. Tsiotras (2022) Hierarchical decompositions of stochastic pursuit-evasion games. In 2022 IEEE 61st Conference on Decision and Control (CDC), p. 5062–5067. Cited by: §VI-A.