REVIEW 3 major objections 5 minor 1 cited by
The Uniformed Patroller Game
T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read This paper solves the uniformed-patroller game on star, line, circle, and star-in-circle networks, where the attacker sees the patroller at her node and waits a delay $d$ after he leaves before attacking.
desk verdict A useful new attacker-information model with clean star-network results, but the abstract oversells the numerical sections. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The central object is the away distribution $x^{(t)}$: the Patroller's position distribution conditional on his not having returned to the attack node for $t$ consecutive periods. The Attacker's delay $d$ determines which vector $x^{(d)}$ is used to start an attack, and each interception probability $\pi_m(p,q,\ldots,d)$ is a linear function of $x^{(d)}$ obtained by summing the Patroller's possible future paths of length $m$. On the star the machinery reduces to a one-parameter recursion for $q$, the probability that the Patroller is at the center given that he is away from the attacked end; minimizing $q$ in $t$ fixes $d=2$ and gives the closed forms (5)--(7). The same $x^{(t)}$ iteration, with symmetry-restricted Markovian walks, is what the numerical line, circle, and star-in-circle solutions are built on.
What would settle it
A concrete check: on the star $S_3$ with $m=2$, the paper's value is $5-2\sqrt{6}\approx 0.1010$; solve a dynamic program in which the Attacker's action at each period may depend on the full past history of the Patroller's presence at the chosen end node, and compute the minmax interception probability, and if any such history-dependent strategy achieves an interception probability below $5-2\sqrt{6}$, then the restriction to strategies $(i,d)$ fails and all claimed game values are upper bounds rather than exact values.
Extended reading notes
Core claim
The paper's central discovery is that once the Attacker can observe the Patroller's presence at her chosen node, the game changes character: instead of attacking at a random time, she waits out a delay $d$, and the Patroller's optimal response is to bias his walk so that the conditional probability of being at certain nodes is low when the delay expires. On the star $S_n$ with attack difficulty $m=2$, the optimal Markovian Patroller reflects from every end node and, from the center, moves to each end with probability $(1-\sqrt{n(n-1)})/n$ and stays at the center with probability $\sqrt{n(n-1)}-(n-1)$. The best Attacker reply is to pick an end node uniformly and attack in the second period after the Patroller leaves it, giving interception probability $(2n-1)-2\sqrt{n(n-1)}$. For odd $m$ the paper proves that the random walk is uniquely optimal with value $1-((n-1)/n)^{(m-1)/2}$; for $m=4$ it gives an exact formula and the asymptotics $1.0944/n$. For $L_4$, $L_5$, $C_4$, $C_5$, and $E_4$ it reports numerical solutions, and two model extensions (one-step memory for the Patroller, direction-of-departure vision for the Attacker) quantify how much each information change shifts the value.
Load-bearing premise
The load-bearing premise is that the Attacker loses nothing by restricting to strategies of the form $(i,d)$---choose a node, wait until the Patroller visits it, then attack after $d$ consecutive absences---and if any richer history-dependent timing did better, every claimed value would be only an upper bound.
Editorial extensions
If this is right
- On a star with two-period attacks, the Patroller should never chase the previous attack but should spend a fraction tending to $1/2$ of his time at the center; for large $n$ the interception probability decays like $1/(4n)$.
- For odd attack durations on a star, Proposition 2 shows that a memoryless random walk is uniquely optimal and that the Attacker's delay choice is irrelevant.
- On all the solved line and circle networks, the Patroller optimally reflects at the endpoints, and for odd attack durations the optimal patrol is a random walk; attacks at end nodes dominate interior-node attacks.
- Giving the Patroller one step of memory on $S_3$ raises the interception probability from about $0.101$ to about $0.136$, while giving the Attacker vision of the departure direction on $E_4$ lowers it from $0.1695$ to about $0.1667$; information alone moves the value in the direction one would expect.
- The remark after Proposition 1 notes that the optimal Attacker strategy does not require knowing the Patroller's strategy, so the computed pair is a Nash equilibrium, not just a Stackelberg solution.
Reading between the lines
- Extending beyond the paper, the same away-distribution machinery should solve any network whose symmetry group makes the Patroller's walk a small-parameter family; a natural next test is a complete bipartite graph or a lollipop graph.
- The sharp contrast with the earlier Hamiltonian-cycle value $m/n$ suggests a design principle: visible patrols should randomize and deliberately create unpredictable return times, since predictable tours invite immediate post-departure attacks.
- Because the value on a large star decays like $1/(4n)$, even optimal uniformed patrols intercept very rarely, so deterrence, not interception, may be the real benefit of visible patrols; the paper itself flags this as an open direction.
- A testable extension is to allow the Attacker's delay to be randomized and check on $S_n$ with $m=2$ whether mixing over $d=1$ and $d=2$ can beat the $d=2$ value; the paper's claimed Nash property predicts it cannot.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces a variant of network patrolling games in which the Attacker can observe the Patroller's presence or absence at her chosen node and may wait for d consecutive absence periods before launching an attack of duration m. The Patroller is restricted to ergodic Markovian strategies that respect the symmetries of the network. The main analytic result is for the star network S_n with attack difficulty m=2: the optimal Patroller strategy reflects at end nodes and stays at the center with probability sqrt(n(n-1))-(n-1), the optimal Attacker strategy is to attack a random end node with delay d=2, and the interception probability is (2n-1)-2*sqrt(n(n-1)) (Proposition 1, equations (5)-(7)). For odd m on stars, the random walk is claimed optimal with value 1-((n-1)/n)^((m-1)/2) (Proposition 2). For line, circle, and star-in-circle networks, values are obtained numerically for maximum delay D=15 and attack durations m=2,...,6. Two extensions are also considered: a Patroller with one-step memory on the star S_3, and an Attacker with slightly greater vision on the star-in-circle E_4.
Significance. If the results are correct, the paper makes a useful contribution by introducing asymmetric information into network patrolling games and by providing clean closed-form values for the star network. The analytic sections are derived by explicit optimization of payoff expressions, with no fitted constants; Proposition 1 and its equations are crisp and falsifiable, and Section 3.5 gives an instructive exact analysis of the one-step-memory case. The numerical sections offer initial evidence for line, circle, and star-in-circle networks. However, the correctness of all reported values hinges on an unproved reduction of Attacker strategies to pairs (i,d), and the numerical claims are not verified to the same standard as the analytic star results. The paper is likely to stimulate follow-up work if these gaps are closed.
major comments (3)
- [Section 2 (formal model), applied in all later sections] The restriction of the Attacker to strategies (i,d) is not proved. The justification in Section 2 tells the Attacker, for free, the total number of 0's at node i since the last 1, which is information not available in the game as described: the Attacker arrives at the node and observes the presence/absence process only from that moment onward. A strategy that attacks after d observed absences without first waiting for a visit is not a pure (i,d) strategy, and the paper does not show that every adapted stopping rule can be represented as a (possibly mixed) strategy over (i,d). Since all computed game values are obtained by minimizing over the restricted family (i,d), without this reduction every value in Proposition 1 and equations (5)-(7) is only an upper bound on the Patroller's true interception probability, not the game value. This is a load-bearing gap in the paper's central claim.
- [Section 3.2, Proposition 2 (equation (8))] The proof does not establish optimality of the random walk for odd m. The 'Similarly' paragraph analyzes the interception probability under the random walk only; it shows that against this particular Patroller strategy every attack has interception probability at most the claimed value, which is an upper bound for the Patroller restricted to the random walk, not for arbitrary feasible Markovian symmetric strategies. To prove that V is the value of the game, one must show that for every feasible Patroller strategy there exists an attack with interception probability at most V, and this is not provided. The uniqueness claim of Proposition 2 is therefore unsupported.
- [Sections 4-5 and 6.2, Tables 3, 5, 7, 8, 9] The claimed solutions for line, circle, and star-in-circle networks are numerical and not fully verified. The delay bound is fixed at D=15, and the check for larger delays is qualitative (Figures 9, 12, 15, 16). The explicit payoff formulas for m=5 and m=6 are omitted in Sections 4.1 and 4.2, and the optimization over Patroller parameters is described as grid-based numerical work, so the reader cannot verify that the reported maxima are global. Moreover, the comparison of attack nodes in Tables 4 and 6 is carried out under the patrol optimized for an attack at node 1; this verifies only that, for that particular patrol, an end-node attack is better than attacks at nodes 2 and 3, not that the Attacker could not force a lower interception probability by attacking a different node against a different patrol. The abstract's claim that these networks are 'solved' is therefore stronger than the evidence presented.
minor comments (5)
- [Section 3.2] In the displayed inequality following 'the probability that the Attacker's node is among them is', the right-hand side should be 1 - ((n-1)/n)^j; the '1 -' is missing on the right-hand side.
- [Section 3.5, Proposition 3] The proposition states that the Patroller chooses p and s with probabilities approximately 0.305 and 0.136, but the preceding paragraph gives s approximately 0.217 and the value V approximately 0.136; the proposition should be corrected. The stated 'increase of approximately 36%' also conflicts with the earlier '34%' figure.
- [Section 4.1] In the paragraph before Figure 10, the optimal patrol for m=6 is given as (0.4947, 0.4267, 1), while Table 3 reports (0.4974, 0.4267, 1); these numbers should be reconciled.
- [Section 5.2] The text says 'as seen in Figure 13' after presenting Figure 16; the cross-reference should be to Figure 16.
- [General] There are several minor wording issues, including 'scenaria' for 'scenarios' in the introduction, and the notation pi_m(..., infinity) used in Tables 3, 5, 7, and 8 should be explicitly defined as the limit as d tends to infinity.
Circularity Check
No significant circularity: game values are obtained by explicit optimization of payoff expressions, and earlier results are cited only as background.
full rationale
The paper defines a new game in which Attacker pure strategies are pairs (i,d) and Patroller strategies are ergodic Markovian walks, then computes interception probabilities from explicit transition dynamics and optimizes them. For example, in the star case, equations (1)-(4) derive the conditional probability of the Patroller being at the center given continued absence, and equations (5)-(7) follow by straightforward first-order optimization of the resulting interception probability; no fitted constant is renamed as a prediction and no target value is inserted as an input. The line, circle, and star-in-circle sections similarly derive payoff expressions from the relevant Markov chains and optimize them numerically or algebraically. Citations to Alpern, Morton and Papadaki (2011) are used for background comparison and for an extension of a non-uniformed game theorem, but the uniformed-game values are not imported from those citations. The only notable modeling step is the Section 2 restriction of Attacker strategies to (i,d), justified by an informal argument in which the Attacker is told for free the age of the current absence run. Even if that reduction is incomplete and should be assessed as a correctness risk, it is a modeling assumption about the strategy space rather than a circular derivation: the game value is defined within the (i,d) strategy space and computed independently from that definition. No circular step can be exhibited in the derivation chain.
Assumptions & free parameters
free parameters (2)
- D =
15
- Numerical grid/optimization resolution
assumptions (5)
- domain assumption Attacker strategies reduce to pairs (i,d): attack node i after the Patroller has been away for d consecutive periods following a visit.
- domain assumption Patroller is restricted to ergodic Markovian strategies that respect network symmetries.
- domain assumption Stackelberg play: the Patroller announces his Markovian strategy and the Attacker observes it before choosing (i,d).
- domain assumption D=15 is large enough to capture the Attacker's best delay for line, circle, and star-in-circle networks.
- domain assumption Numerical parameter searches in Sections 4-6 locate global optima.
Cite this review
Pith. "Pith review of The Uniformed Patroller Game." pith.science (2026). https://pith.science/paper/IHHTHPY7
@misc{pith2026190801859,
author = {Pith},
title = {Pith review of: The Uniformed Patroller Game},
year = {2026},
howpublished = {\url{https://pith.science/paper/IHHTHPY7}},
note = {Machine review of arXiv:1908.01859}
}
read the original abstract
In the recently introduced network patrolling game, an Attacker carries out an attack on a node of her choice, for a given number m of consecutive periods. The parameter m indicates the difficulty of the attack at a given node. To thwart such an attack, the Patroller adopts a walk on the network, hoping to be at the attacked node during one of the m periods. If this occurs, the attack is interrupted and the Patroller wins; otherwise the Attacker wins. In the original setting, the Attacker has no knowledge of the Patroller's location at any time. Here, to model the important alternative where the Patroller can be identified when he is at the Attacker's node (e.g. the Patroller wears a uniform), we allow the Attacker to initiate her attack after waiting for a chosen number d of consecutive periods in which the Patroller has been away. We solve this version of the game for various networks: star, line, circle and a mixture. We restrict the Patroller to Markovian strategies, which cover the whole network.
Figures
Figures from the paper (13 more)
Forward citations
Cited by 1 Pith paper
-
The Uniformed Patroller Game
In the observable-patroller star game, the optimal attack delay is two periods and the optimal patroller never spends consecutive periods at a location.
Reference graph
Works this paper leans on
-
[1]
SIAM Journal on Control and Optimization
Alpern S (1995) The rendezvous search problem. SIAM Journal on Control and Optimization. 33(3):673-683
work page 1995
-
[2]
Operations Research
Alpern S, Morton A, Papadaki K (2011) Patrolling games. Operations Research. 59(5):1246-1257
2011
-
[3]
European Journal of Operational Research
Alpern S, Lidbetter T, Papadaki K (2018) Optimizing Periodic Patrols against Short Attacks on the Line and Other Networks. European Journal of Operational Research
work page 2018
-
[4]
Artificial Intelligence
Basilico N, Gatti N, Amigoni F (2012) Patrolling security games: Definition and algorithms for solving large instances with single patroller and single intruder. Artificial Intelligence. 184:78-123
2012
-
[5]
Adversarial patrolling with spatially uncertain alarm signals
Basilico N, De Nittis G, Gatti N (2015) Adversarial patrolling with spatially uncertain alarm signals. arXiv preprint arXiv:1506.02850
work page Pith review arXiv 2015
-
[6]
Operations Research
Baston V, Kikuta K (2004) An ambush game with an unknown number of infiltrators. Operations Research. 52(4):597-605
2004
-
[7]
Operations Research
Baston V, Kikuta K (2009) Technical Note-An Ambush Game with a Fat Infiltrator. Operations Research. 57(2):514-519
2009
-
[8]
European Journal of Operational Research
Baykal-G\" u rsoy M, Duan Z, Poor H V, Garnaev A (2014) Infrastructure security games. European Journal of Operational Research. 239(2):469-478
2014
Show all 23 references
-
[9]
In 8th International Conference on Fun with Algorithms, FUN 2016 (Vol
Cohen N, Hilaire M, Martins N, Nisse N, Pérennes S (2016) Spy-Game on graphs. In 8th International Conference on Fun with Algorithms, FUN 2016 (Vol. 49). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
2016
-
[10]
Optimal patrolling of fragmented boundaries
Collins A, Czyzowicz J, Gasieniec L, Kosowski A, Kranakis E, Krizanc D, ..., Morales Ponce O (2013, July). Optimal patrolling of fragmented boundaries. In Proceedings of the twenty-fifth annual ACM symposium on Parallelism in algorithms and architectures (pp. 241-250). ACM
2013
-
[11]
In Handbook of Computational Approaches to Counterterrorism (pp
Fokkink R, Lindelauf R (2013) The Application of Search Games to Counter Terrorism Studies. In Handbook of Computational Approaches to Counterterrorism (pp. 543-557). Springer New York
2013
-
[12]
In International Conference on Foundations of Software Science and Computation Structures (pp
Ho H M, Ouaknine J (2015, April) The cyclic-routing UAV problem is PSPACE-complete. In International Conference on Foundations of Software Science and Computation Structures (pp. 328-342). Springer Berlin Heidelberg
2015
-
[13]
Networks
Hochbaum D S, Lyu C, Ordóñez F (2014) Security routing games with multivehicle Chinese postman problem. Networks. 64(3):181-191
2014
-
[14]
In System Sciences, 1989
Holte R, Mok A, Rosier L, Tulchinsky I, Varvel D (1989, January) The pinwheel: A real-time scheduling problem. In System Sciences, 1989. Vol. II: Software Track, Proceedings of the Twenty-Second Annual Hawaii International Conference on (Vol. 2, pp. 693-702). IEEE
1989
-
[15]
Operations Research
Lin K Y, Atkinson M P, Chung T H, Glazebrook K D (2013) A graph patrol problem with random attack times. Operations Research. 61(3):694-710
2013
-
[16]
Naval Research Logistics (NRL)
Lin K Y, Atkinson M P, Glazebrook K D (2014) Optimal patrol to uncover threats in time when detection is imperfect. Naval Research Logistics (NRL). 61(8):557-576
2014
-
[17]
Morse P M, Kimball G E (1951) Methods of Operations Research (MIT Press and Wiley, New York)
1951
-
[18]
Operations Research
Papadaki K, Alpern S, Lidbetter T, Morton A (2016) Patrolling a border. Operations Research. 64(6):1256-1269
2016
-
[19]
In Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems: industrial track (pp
Pita J, Jain M, Marecki J, Ordóñez F, Portway C, Tambe M, ..., Kraus S (2008, May) Deployed ARMOR protection: the application of a game theoretic model for security at the Los Angeles International Airport. In Proceedings of the 7th international joint conference on Autonomous...
2008
-
[20]
Naval Research Logistics (NRL)
Szechtman R, Kress M, Lin K, Cfir D (2008) Models of sensor operations for border surveillance. Naval Research Logistics (NRL). 55(1):27-41
2008
-
[21]
Naval Research Logistics Quarterly
Washburn A R (1982) On patrolling a channel. Naval Research Logistics Quarterly. 29(4):609-615
1982
-
[22]
Military Operations Research
Washburn A (2010) Barrier games. Military Operations Research. 15(3):31-41
2010
-
[23]
European Journal of Operational Research
Zoroa N, Fern\' a ndez-S\' a ez M J, Zoroa P (2012) Patrolling a perimeter. European Journal of Operational Research. 222(3):571-582
2012
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.