{"id":"9cb86ded-565b-4d0e-bb5e-6a141697bf6f","arxiv_id":"1908.07366","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"In the observable-patroller star game, the optimal attack delay is two periods and the optimal patroller never spends consecutive periods at a location.","lead":"A game theory paper analyzes what happens to patrolling games when an attacker can watch for a patroller before attacking. The optimal attacker waits exactly two periods after the patroller leaves a location, and the optimal patroller never stays at a location two periods in a row.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central value and optimality claims are proved only inside the explicitly restricted two-parameter Markovian patroller family; the paper never shows history-dependent strategies are without loss of generality, so V and the factor-of-four cost may understate the unrestricted game's value.","rationale":"I re-derived the paper's core formulas and they hold within the stated class: p̂=(n−√(n(n−1)))/n and V=ĉp̂=(2n−1)−2√(n(n−1))≈1/(4n) for m=2; (16) matches Proposition 1 at m=2 and gives 1−((n−1)/n)^{(m−1)/2} at p=1/n for m=3; the recursion (22)-(24) agrees with (16). Section 2.4's asymptotics check out (poly(r)=1+r−3r²+2r³−r⁴, maximizer ≈0.20196). For the uniform cost, Ṽ=1/n is right because a walk on a star visits at most one leaf in any two consecutive periods, so the factor-of-four comparison is internally consistent. The load-bearing gap is the unproven without-loss-of-generality status of the Markovian/symmetric restriction stated in Section 2's first paragraph: the theorem statements, value formulas, and Proposition 4 are unqualified, but are proved only over the two parameters (p,s); any improvement from history-dependent play would lower the claimed cost of the uniform. This is the same weakest assumption the reader identified. The other reader-flagged issues are genuine: Lemma 3's odd-m uniqueness statement contradicts Theorem 1 and Proposition 2, and the display at (17) is off by one relative to (16). Since none of these corrupt the restricted-class mathematics and all are addressable by a WLOG argument or scoping language plus two small corrections, the CONDITIONAL verdict stands; my read does not change it.","tokens_in":16250,"tokens_out":54347,"duration_ms":503206,"concrete_test":"For m=2 and n=10, solve the finite zero-sum game in which the Patroller may use arbitrary behavioral strategies with full memory of her own walk (subject only to the star's edge constraint and location symmetry), while the Attacker observes only the presence/absence process at his chosen node and chooses an optimal stopping time; compute the value by linear programming or dynamic programming over the finite game tree (the attack-relevant horizon is about six periods). If the value exceeds V=(2n−1)−2√(n(n−1))≈0.0263, the Markovian restriction is binding, so the paper's value and the factor-of-four claim are not those of the unrestricted game; if the value equals V, the restriction has direct support in the headline m=2 case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 2's opening paragraph restricts the Patroller to a memoryless, location-symmetric two-parameter family: from the center she reaches each end node with probability p and stays with probability r=1−np; from an end she reflects with probability s. The paper is transparent that this is a restriction, but the unqualified conclusions — Theorem 1 that d=2 and s=1 'are optimal strategies', the closed-form value formulas (Propositions 1–3), and the factor-of-four uniform cost (Proposition 4) — are established only within this family. No argument shows the restriction is without loss of generality. A history-dependent Patroller could use her private walk history to shape the conditional distribution of her location at the attacker's trigger time (e.g., the absence-run-length distribution at the attacked node), which the two-parameter family cannot express; the cited literature does not establish sufficiency of memoryless strategies for a one-sided-information timing game of this kind. If such strategies raise interception above V, then V is a lower bound rather than the value, and Proposition 4 overstates the cost of the uniform. Two secondary textual slips, also flagged by the reader, are real but not load-bearing: Lemma 3's 'furthermore' (odd m implies d=2 uniquely optimal) contradicts Proposition 2 and Theorem 1, and the displayed reduction at equation (17), Q=1−Pr(TC≥m+1)/Pr(TC≥2), is off by one (the correct identity is Q=1−Pr(TC≥m+2)/Pr(TC≥3)); I verified formula (16) is nevertheless correct, reproducing Proposition 1 for m=2 and Proposition 2's value for m=3.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16545,"tokens_out":16944,"duration_ms":159798,"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":[{"comment":"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.","section":"Section 2 (first paragraph); Theorem 1"},{"comment":"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.","section":"Lemma 3; Theorem 1"},{"comment":"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.","section":"Section 2.6, equation (17)"}],"minor_comments":[{"comment":"The manuscript contains numerous typographical slips, including 'The the Uniformed Patroller Game', 'with probabilitys', 'Furthemored', and inconsistent use of 'Uniformed' versus 'uniformed'.","section":"Throughout"},{"comment":"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.","section":"Propositions 1 and 3"},{"comment":"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.","section":"Section 2.6, Proposition 3"},{"comment":"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.","section":"Introduction and Section 1"},{"comment":"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.","section":"Section 2.6"}],"recommendation":"major_revision","confidential_remarks":"The main risk is the scope of the strategic restriction. If the journal views the Markovian formulation as part of the model definition, the paper is close to acceptable after fixing Lemma 3 and equation (17). If not, the unqualified value-of-the-game claims and Theorem 1 overreach, and the authors should either provide a sufficiency argument or restrict the claims. I would ask the editor to require an explicit statement in the abstract and theorem that the results concern the restricted Markovian game unless the authors can prove otherwise."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead this as a solution to a specific model, not to the full strategic problem the title promises. Within the class of stationary, symmetric, two-parameter Markovian patroller strategies on a star, the paper is sound and genuinely useful. The new modeling twist—the attacker sees absences and can choose a delay d—is natural, and the main results are surprising enough to matter: d=2 is optimal and reflection probability s=1 is optimal, with a clean coupling argument; for short attacks m=2 and large n, the uniformed patroller catches only a quarter as much as the non-uniformed one. I checked the main formulas; they reproduce the stated values. This is a real extension of Alpern-Morton-Papadaki.\n\nThe soft spot is scope, and it is not manufactured. Section 2 says \"We restrict our analysis to a Markovian Patroller\" and never argues this is without loss of generality. History-dependent patrolling could in principle shape the conditional distribution of the patroller's location when the attacker's waiting clock expires, and the two-parameter memoryless family cannot express that. So Theorem 1's \"optimal strategies\" and Proposition 4's factor-of-four should be read as optimal within the restricted family and as a bound on the unrestricted game; the paper states them as unconditional. That is the main referee issue.\n\nThere are also two textual slips. Lemma 3's \"furthermore\" says d=2 is uniquely optimal for odd m, which contradicts Proposition 2 and Theorem 1; it should say \"even.\" Equation (17) has an index off-by-one even though the final formula (16) is correct. Both are presentation bugs, not cracks in the main calculation. The citation pattern looks normal; the self-citation to the companion paper is appropriate.\n\nWho gets value from this? Anyone working on patrolling or security games: the closed-form value formulas and the coupling technique are citable. A serious referee should engage with it. I would send it out and ask for a revision that qualifies the scope and fixes the slips.","headline":"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.","tokens_in":17115,"tokens_out":5579,"would_cite":true,"duration_ms":55758,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A80","90B40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Uniformed observers are easier to ambush: the optimal wait is exactly two periods.","keywords":["two-person game","constant-sum game","patrolling game","star network","uniformed patroller","attack duration","attack delay","Markov chain"],"falsifier":"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.","tokens_in":16019,"feed_emoji":"🚔","tokens_out":10327,"duration_ms":99174,"temperature":0.7,"pith_summary":"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.","feed_headline":"Uniformed patrollers are ambushable: wait two periods","feed_subtitle":"In a star-network patrol game, striking on the second period a guard is away is optimal for every attack length and every number of…","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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$."],"supporting_citations":[{"why":"Defines the baseline patrolling game without a uniform, which the paper extends and uses for the uniform-cost comparison.","marker":"Alpern, Morton and Papadaki (2011)"},{"why":"Cited as the standard justification for restricting the Patroller to a Markovian strategy.","marker":"Basilico, Gatti and Amigoni (2012)"},{"why":"Supplies the passage-distribution theorem for birth-death chains used to derive the closed-form interception probability.","marker":"Fill (2009)"},{"why":"Provides the linear-recursion solution used in the second proof of the interception formula.","marker":"Brousseau (1971)"},{"why":"Provides the contrasting fixed-path multi-patroller model in which uniforms cost nothing, motivating the uniform-loss comparison.","marker":"Lin (2019)"},{"why":"Shows that on some graphs the optimal delay is not $d=2$, delimiting the star-network scope of Theorem 1.","marker":"Alpern and Katsikas (2019)"},{"why":"Used in Proposition 1 to justify convergence of the center-occupancy probability for the aperiodic Markov chain.","marker":"Norris (1998)"}],"fun_headline_variants":["Wait two periods: optimal ambush in uniformed patrol game","Uniformed patrols: attackers gain by waiting two periods","Strike on second absence: best in patrol game with uniform","Delay attack by two: key to beating uniformed patroller","Patrol game: wait d=2 for optimal interception"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Wait two periods: optimal ambush in uniformed patrol game","Uniformed patrols: attackers gain by waiting two periods","Strike on second absence: best in patrol game with uniform","Delay attack by two: key to beating uniformed patroller","Patrol game: wait d=2 for optimal interception"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000744,"raw_usage":{"total_tokens":3347,"prompt_tokens":1006,"completion_tokens":2341,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":622,"completion_tokens_details":{"reasoning_tokens":2257}},"tokens_in":622,"tokens_out":2341,"duration_ms":18081,"temperature":1.0,"reasoning_tokens":2257,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:22:04.058576+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Operations Research","cited_arxiv_id":null,"evidence_quote":"Defines the baseline patrolling game without a uniform, which the paper extends and uses for the uniform-cost comparison."},{"cited_title":"Artificial Intelligence","cited_arxiv_id":null,"evidence_quote":"Cited as the standard justification for restricting the Patroller to a Markovian strategy."},{"cited_title":"Journal of Theoretical Probability","cited_arxiv_id":null,"evidence_quote":"Supplies the passage-distribution theorem for birth-death chains used to derive the closed-form interception probability."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the linear-recursion solution used in the second proof of the interception formula."},{"cited_title":"Optimal Patrol of a Perimeter","cited_arxiv_id":"1905.03600","evidence_quote":"Provides the contrasting fixed-path multi-patroller model in which uniforms cost nothing, motivating the uniform-loss comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Used in Proposition 1 to justify convergence of the center-occupancy probability for the aperiodic Markov chain."}],"review_version":1}