Pith. sign in

REVIEW 3 major objections 5 minor 25 references

The Uniformed Patroller Game

T0 review · 3 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Uniformed observers are easier to ambush: the optimal wait is exactly two periods.

desk verdict A clean solution of a well-defined restricted patrolling game, with the central d=2/s=1 and factor-of-four results sound inside that class; the unqualified optimality claims overreach because the Markovian symmetric restriction is never shown to be without loss. read the letter →

arxiv 1908.07366 v2 pith:5OGFCLYC submitted 2019-08-14 cs.CR cs.GT

Steve Alpern , Paul Chleboun , Stamatios Katsikas This is my paper · ORCID
classification cs.CRcs.GT MSC 91A8090B40
keywords two-persongameconstant-sumpatrollingstarnetworkuniformedpatrollerattackdurationdelayMarkovchain
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper introduces the Uniformed Patroller Game, in which an attacker watches a chosen location, sees when the patroller is present, and chooses how many periods $d$ to wait after she leaves before striking. It claims that for every number $n$ of defended locations and every attack duration $m\ge 2$, the attacker's optimal waiting time is $d=2$ and the patroller's optimal response is never to visit the same location in consecutive periods ($s=1$). This matters because it turns the attacker's timing problem into a single fixed rule, and because it quantifies the price of being observable: for short attacks on many locations, wearing a uniform reduces the chance of interception by a factor of four.

What carries the argument

The load-bearing object is the reduction of the symmetric game to a three-state birth-death chain $\{E,C,A\}$, where $A$ is the attacked end, $E$ lumps all other ends, and $C$ is the center. A Markov coupling compares a patrol path $(p,s)$ with the path obtained by deleting consecutive visits to $E$, which shows that reflection $s=1$ dominates any $s<1$ (strictly for $m\ge 3$). The attacker's delay is analyzed through the function $f(c)=(c r+(1-c))/(1-cp)$, the probability that the Patroller is at $C$ given that she has not returned to $A$; since $f$ decreases in $c$ and $c=1$ immediately after leaving $A$, the minimum occurs at $d=2$. Fill's passage-distribution theorem supplies the probability generating function of the hitting time of $A$, which yields the explicit interception formula, and a companion recursion on $m$ gives the same formula.

What would settle it

Compute the value of the full zero-sum game for a small instance, say $n=3$ and $m=4$, allowing the Patroller any finite-state or history-dependent strategy; if the resulting interception probability exceeds the maximum of the paper's formula over $p$, then the claimed optimality of $(d=2,s=1)$ fails.

Watch

Extended reading notes

Core claim

On a star network $S_n$ with center $C$ and $n$ end locations, the Patroller is assumed Markovian: from the center she moves to each end with probability $p$, stays with probability $r=1-np$, and from an end reflects with probability $s$. The Attacker, after observing the Patroller leave his chosen location $A$, waits $d$ consecutive observed absences before attacking. The paper proves (Theorem 1) that for every $m\ge 2$ and every $n$, $d=2$ and $s=1$ form an optimal strategy pair; moreover $d=2$ is uniquely optimal exactly when $m$ is even, and $s=1$ is uniquely optimal exactly when $m\ge 3$. The interception probability has closed forms: $V=(2n-1)-2\sqrt{n(n-1)}$ for $m=2$, $V=1-((n-1)/n)^{(m-1)/2}$ for odd $m$, and an explicit expression for $m=4$, with even $m\ge 6$ reducing to a one-dimensional optimization over $p$. Against a non-uniformed Patroller, the uniform imposes a loss: a factor of four for $m=2$ and large $n$, and a relative loss of $1/m$ for odd $m$.

Load-bearing premise

The argument rests on the unproved assumption that the Patroller can be restricted to a memoryless, symmetric two-parameter strategy, so a history-dependent or location-dependent patroller might do better than the paper's value.

Editorial extensions

If this is right

  • Attackers can standardize their timing: no matter $n$ or $m$, starting an attack on the second consecutive period of absence is an optimal response, and for even $m$ it is the only optimal delay.
  • Patrollers can standardize their movement: reflecting from every end location ($s=1$) is optimal for all $m\ge 2$, and uniquely so for $m\ge 3$; combined with the optimal $p$, this defines a one-parameter family of value-maximizing walks.
  • For odd $m$, the optimal patrol is the zero-holding random walk $p=1/n$, $s=1$, and the value is $1-((n-1)/n)^{(m-1)/2}$.
  • For even $m\ge 6$, no closed-form optimum for $p$ is given, but the explicit formula reduces the Patroller's search to maximizing a degree-$m$ polynomial in $p$; numerical optimization is one-dimensional.
  • The cost of observability is quantifiable: for $m=2$ and large $n$, the uniformed interception probability is one quarter of the non-uniformed one, and for odd $m$ the relative loss tends to $1/m$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension the paper leaves open is a history-dependent Patroller: if a small finite-state patrol schedule outperforms the best $(p,s)$ pair on a small star, the Markov restriction is binding and the factor-of-four comparison would need revisiting.
  • The $d=2$ rule is a behavioural prediction: with informed attackers, attack start times should cluster on the second period after a patroller leaves a sensitive location, which is testable on patrol logs.
  • The interception loss assumes attacks are certain; if the uniform also deters some attacks, as the paper suggests as a motivation, the net effect on security could still be positive, but that trade-off is not part of the solved game.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper analyzes a zero-sum patrolling game on a star network with n locations. The Attacker observes the Patroller's presence or absence at his chosen location and chooses a delay d; the attack begins after d consecutive periods of absence from that location and is intercepted if the Patroller visits the location during the m-period attack. The Patroller is restricted to a Markovian, location-symmetric strategy parameterized by p (the probability of moving from the center to a given end) and s (the reflection probability at the ends). The authors derive explicit values for m=2 (Proposition 1), odd m (Proposition 2), m=4 (Section 2.3), a general closed-form interception probability for d=2 and s=1 (Proposition 3), asymptotic results for m=4 (Section 2.4), and asymptotic cost-of-uniform comparisons (Propositions 4 and 5). Theorem 1 claims that d=2 and s=1 are optimal for all m and n, with uniqueness conditions. The paper's final formula (16) and the main special-case values are reproducible and internally consistent once the stated indexing slips are corrected.

Significance. If the results hold as stated, the paper gives a clean and nontrivial answer to a natural variant of patrolling games: observing the uniformed Patroller can reduce interception by a factor of four asymptotically for short attacks, and the optimal delay is d=2. The strengths are the explicit closed forms, the transparent derivations, and the elegant coupling argument for s=1 in Lemma 1. The main caveat is substantive: all value and optimality claims are proved only inside the two-parameter Markovian strategy family introduced at the start of Section 2, and the paper never shows this restriction is without loss of generality. If history-dependent Patroller strategies can do better, then V is only a lower bound and Propositions 4 and 5 overstate the cost of the uniform. The internal contradictions in Lemma 3 and equation (17) are localized and fixable, but they need correction before the paper can be accepted.

major comments (3)
  1. [Section 2 (first paragraph); Theorem 1] The analysis restricts the Patroller to a memoryless, location-symmetric two-parameter family (p,s), and all subsequent results—including the value formulas in Propositions 1–3 and the optimality claims in Theorem 1—are proved only within this family. No argument is given that the restriction is without loss of generality in the full game, where the Patroller could use history-dependent strategies. For example, a Patroller with memory could condition her future moves on the length of the current absence from the attacked node, and the paper does not rule out that such a strategy achieves an interception probability strictly greater than V. If so, V is a lower bound rather than the value of the game, and the factor-of-four claim in Proposition 4 overstates the cost of the uniform. Please either prove that the restriction is without loss of generality, or define the game as the restricted Markovian game and qualify Theorem 1 and the value statements accordingly.
  2. [Lemma 3; Theorem 1] The 'furthermore' clause of Lemma 3 states that for odd m the delay d=2 is the Attacker's unique optimal response. This contradicts Proposition 2, which states that for odd m any delay is optimal, and it contradicts Theorem 1, which states that d=2 is uniquely optimal if and only if m is even. The proof of Lemma 3 establishes only optimality of d=2, not uniqueness; the uniqueness claim for even m must instead be derived from Lemma 2 or proved separately. The erroneous 'furthermore' clause should be removed or corrected, and the proof of Theorem 1, which cites the 'furthermore' parts of Lemmas 1 and 3, should be revised accordingly.
  3. [Section 2.6, equation (17)] The displayed identity Q = Pr(TC < d+m−1 | TC≥d) = 1 − Pr(TC≥d+m−1)/Pr(TC≥d) is off by one. With the paper's convention that the Patroller starts at C in the first period of absence and the attack begins on the d-th consecutive absence period, an attack of duration m is intercepted if TC ≤ d+m−1, equivalently if TC < d+m. Therefore the correct conditional identity is Q = 1 − Pr(TC≥d+m)/Pr(TC≥d+1); for d=2 this is Q = 1 − Pr(TC≥m+2)/Pr(TC≥3), not 1 − Pr(TC≥m+1)/Pr(TC≥2). The final formula (16) is nevertheless correct, as confirmed by the recursion proof later in Section 2.6, but the hitting-time derivation needs to be repaired.
minor comments (5)
  1. [Throughout] The manuscript contains numerous typographical slips, including 'The the Uniformed Patroller Game', 'with probabilitys', 'Furthemored', and inconsistent use of 'Uniformed' versus 'uniformed'.
  2. [Propositions 1 and 3] The notation using ∑ where a square root is intended (for example in the formula for p-hat in Proposition 1 and in the definition of u) is nonstandard and confusing; please use \sqrt{} consistently.
  3. [Section 2.6, Proposition 3] The displayed formula for Q in Proposition 3 is missing parentheses and is ambiguous as typeset; the intended expression is Q = 1 - [(A+u)w_2^m - (A-u)w_1^m] / [2(1-p)u], and this should be written explicitly.
  4. [Introduction and Section 1] The paper says it determines solutions for arbitrary m and n, but for even m ≥ 6 the value is only obtained numerically after fixing d=2 and s=1; the introductory sentence should be qualified to match the actual content.
  5. [Section 2.6] The paper's Theorem 1 and the quoted 'Theorem 1.2' from Fill (2009) are both numbered '1', which is confusing; the external result should be labeled differently.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the star-network value and the d=2, s=1 optimality claims are proved from the stated Markov transition probabilities by best-response and coupling arguments, and the uniform-cost factor-four result is measured against an independently computed non-uniformed value.

full rationale

I find no circular step. The two strategy parameters p and s are decision variables, not fitted constants: the interception probability Q is written as a function of the transition probabilities (e.g., Eq. (5), Eq. (8), Eq. (16)) and then maximized over p and s. The d=2 result is derived as a best response via the monotonicity of f(c) in Eq. (15) and Lemma 2, not assumed as an input. The s=1 result is obtained from a Markov-coupling argument in Lemma 1, not from a self-citation. External citations (Fill 2009 for hitting-time generating functions, Brousseau 1971 for linear recurrences) provide standard tools and are not load-bearing self-citations. The cost-of-uniform comparison in Proposition 4 uses the independent non-uniformed value \ tilde V = 1/n for m=2, so the factor-four claim is a comparison rather than a renamed input. The paper is transparent that the analysis is restricted to a Markovian, symmetric two-parameter strategy family (Section 2, first paragraph), and it never proves that this restriction is without loss of generality; that is a scope limitation and a potential correctness gap, but it is not circular. Two textual slips also belong in the correctness category, not circularity: Lemma 3's 'furthermore' statement that d=2 is uniquely optimal for odd m contradicts Proposition 2 and Theorem 1, and Eq. (17) conditions on TC≥d where the attack-beginning event requires being away for d consecutive periods, i.e., TC>d.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The paper adds no invented entities or fitted constants. Its contribution rests entirely on the specification of a two-parameter Markovian patroller and the resulting game-theoretic analysis.

assumptions (5)
  • domain assumption The Patroller is Markovian and does not remember her previous sequence of locations.
    Quoted from Section 1 and Section 2. This restricts the strategy space and is not proven to be without loss of generality.
  • domain assumption The Patroller's strategy is symmetric across the n end nodes: from the center she chooses each end with equal probability p.
    Assumed in Section 2; symmetry reduction is natural but not proven as a general equilibrium property.
  • domain assumption The attacker chooses a single location A and attacks only the end nodes, never the center, because m≥2 makes center attacks always intercepted.
    The center-attack exclusion is argued from s=1 reflecting behavior; it is a restricted-model assumption.
  • standard math Fill's theorem on birth-death chain hitting-time generating functions is applied to the three-state chain.
    Used in the first proof of Proposition 3; cited from Fill (2009).
  • standard math The zero-sum game value equals the Nash equilibrium payoff of the constructed pair of strategies.
    Standard game theory; used in Theorem 1 proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The Uniformed Patroller Game." pith.science (2026). https://pith.science/paper/5OGFCLYC

@misc{pith2026190807366,
  author       = {Pith},
  title        = {Pith review of: The Uniformed Patroller Game},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5OGFCLYC}},
  note         = {Machine review of arXiv:1908.07366}
}
read the original abstract

Patrolling Games were introduced by Alpern, Morton and Papadaki (2011) to model the adversarial problem where a mobile Patroller can thwart an attack at some location only by visiting it during the attack period, which has a prescribed integer duration m. Here, we modify the problem by allowing the Attacker to go to his planned attack location early and observe the presence or the absence there of the Patroller (who wears a uniform). To avoid being too predictable, the Patroller may sometimes remain at her base when she could have been visiting a possible attack location. The Attacker can then choose to delay attacking for some number of periods d after the Patroller leaves his planned attack location. As shown here, this extra information for the Attacker can reduce thwarted attacks by as much as a factor of four in specific models. Our main finding, is that the attack should begin in the second period the Patroller is away (d = 2) and that the Patroller should never attack the same location in consecutive periods.

Figures

Figures reproduced from arXiv: 1908.07366 by the authors.

Figure 1
Figure 1. Left: The Star network Sn. Right: By symmetry, once the attacker has chosen a node A, we can reduce the Patroller Markov strategy to a three state birth-death chain on {E, C, A}. The holding probabilities are shown for clarity on the right, where r = 1 − np. Let A denote the end node the Attacker has chosen for the attack, and let E denote the set of all other end nodes (with a slight abuse of notation E will someti… view at source ↗
Figure 2
Figure 2. Plots of Q, for n = 10, m = 2, . . . , 10, p ≤ 1 n . pˆ are shown by red dots. 14 [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. pˆ (left) and rˆ (right) for even m, n = 5, 10, 15, 20 . 2.7 The Cost of Wearing a Uniform In the above analysis, the Attacker uses his information about the presence and absence of the Patroller at his location in optimizing the timing of his attack. So it would seem intuitive that forcing the Patroller to wear a uniform reduces the optimal probability of intercepting the attack. However in a distant but related mu… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

  1. [1]

    Operations Research

    Alpern S, Morton A, Papadaki K (2011) Patrolling games. Operations Research. 59(5):1246-1257

    work page 2011

  2. [2]

    European Journal of Operational Research

    Alpern S, Lidbetter T, Papadaki K (2019) Optimizing Periodic Patrols against Short Attacks on the Line and Other Networks. European Journal of Operational Research. 273(3):1065-1073

    work page 2019

  3. [3]

    The Uniformed Patroller Game

    Alpern S, Katsikas S (2019) The Uniformed Patroller Game. arXiv preprint arXiv:1908.01859

    work page Pith review arXiv 2019

  4. [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

    work page 2012

  5. [5]

    Artificial Intelligence

    Basilico N, De Nittis G, Gatti N (2017) Adversarial patrolling with spatially uncertain alarm signals. Artificial Intelligence. 246:220-257

    work page 2017

  6. [6]

    Operations Research

    Baston V, Kikuta K (2004) An ambush game with an unknown number of infiltrators. Operations Research. 52(4):597-605

    work page 2004

  7. [7]

    Operations Research

    Baston V, Kikuta K (2009) Technical Note-An Ambush Game with a Fat Infiltrator. Operations Research. 57(2):514-519

    work page 2009

  8. [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

    work page 2014

Show all 25 references
  1. [9]

    Brousseau A (1971) Linear recursion and Fibonacci sequences (Fibonacci Association)

    1971

  2. [10]

    Optimal patrolling of fragmented boundaries

    Collins A, Czyzowicz J, Gasieniec L, Kosowski A, Kranakis E, Krizanc D, Martin R, 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

  3. [11]

    Journal of Theoretical Probability

    Fill J A (2009) The passage distribution for a birth-and-death chain: Strong stationary duality gives a first stochastic proof. Journal of Theoretical Probability. 22(3):543-557

    2009

  4. [12]

    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

  5. [13]

    European Journal of Operational Research

    Garrec T (2019) Continuous Patrolling and Hiding Games. European Journal of Operational Research. 277(1):42-51

    2019

  6. [14]

    Networks

    Hochbaum D S, Lyu C, Ordóñez F (2014) Security routing games with multivehicle Chinese postman problem. Networks. 64(3):181-191

    2014

  7. [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

  8. [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

  9. [17]

    arXiv preprint arXiv:1905.03600

    Lin K Y (2019) Optimal Patrol on a Perimeter. arXiv preprint arXiv:1905.03600

    2019 arXiv

  10. [18]

    Morse P M, Kimball G E (1951) Methods of Operations Research (MIT Press and Wiley, New York)

    1951

  11. [19]

    Norris J R (1998) Markov Chains (Cambridge university press)

    1998

  12. [20]

    Operations Research

    Papadaki K, Alpern S, Lidbetter T, Morton A (2016) Patrolling a border. Operations Research. 64(6):1256-1269

    2016

  13. [21]

    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, Western C, Paruchuri P, 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 confe...

    2008

  14. [22]

    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

  15. [23]

    Naval Research Logistics Quarterly

    Washburn A R (1982) On patrolling a channel. Naval Research Logistics Quarterly. 29(4):609-615

    1982

  16. [24]

    Military Operations Research

    Washburn A (2010) Barrier games. Military Operations Research. 15(3):31-41

    2010

  17. [25]

    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

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.