{"id":"e2d85249-0729-4cd7-8a1d-cb6fe0c7c24f","arxiv_id":"1908.01859","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The uniformed-patroller game, where the attacker sees the patroller at her chosen node and chooses a waiting delay, is solved for star, line, circle, and star-in-circle networks.","lead":"This paper models a security game where an attacker watches a patroller's movements and waits for the right moment to strike a chosen target. It computes optimal patrol and attack strategies for several simple network shapes, including stars, lines, and circles, when the patroller is visibly identifiable.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Section 2 restricts the Attacker to (i,d) strategies using free information about the age of the current absence run; absent a proof that all adapted stopping rules reduce to (i,d), every reported value is an upper bound on the true interception probability.","rationale":"I agree with the reader that the weakest point is the informal reduction of Attacker strategies to (i,d). The paper's own text in Section 2 flags the issue (\"The reader might as well think...\") and then gives the free-information argument; that argument changes the information structure. In the actual game the Attacker observes the binary process only from her arrival, so the total length of the current absence run is hidden. Consequently the restriction to pure pairs (i,d) is not established. Because Proposition 1 and the numerical sections compute interception probabilities only for (i,d), a failure of the reduction would make all reported values upper bounds (Patroller-favorable), not the true maxmin values. I would not change the CONDITIONAL verdict: the star algebra is internally consistent and the numerical claims are clearly approximate, but the model-equivalence gap should be closed before the results are described as solving the game. The proposed dynamic-programming check on S_n with m=2 gives a decisive, finite test: if it reproduces (7), the reduction is validated in the most important case; if it finds a lower value, the paper's central claim fails.","tokens_in":23788,"tokens_out":17401,"duration_ms":207445,"concrete_test":"For S_3 and S_4 with the Proposition 1 patrol and m=2, solve the Attacker's optimal stopping problem by belief-state dynamic programming over the simplex of beliefs on Patroller position, observing only whether the chosen end is occupied, with D=15 and D=100, stopping only when the end is unoccupied. Compare the minimal interception probability with Eq. (7); a value strictly below V disproves the (i,d) reduction, while equality supports it in the headline case.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The most load-bearing assumption is the Section 2 restriction of Attacker strategies to (i,d) pairs. The paper's justification (\"we could tell the Attacker, for free, the total number of 0's at node i since the last 1\") supplies information the game does not give her. In the actual game the Attacker observes the presence/absence process only from her arrival, so the age of the current absence run is hidden. A strategy that stops after d observed absences without first waiting for a visit is therefore not a pure (i,d) strategy, and the paper never proves that every adapted stopping rule can be represented as a (possibly mixed) strategy over (i,d). If such a rule achieves a lower interception probability than min_d q_d, then all computed values, including Proposition 1 and equations (5)-(7), are upper bounds on the true game value, i.e., they overestimate the Patroller's interception probability. This is not a cosmetic gap: the optimal stopping time could in principle be chosen to minimize the posterior probability that the Patroller is at the center at the moment the attack starts, and the paper compares only the deterministic (i,d) family.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":23941,"tokens_out":6896,"duration_ms":67471,"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":[{"comment":"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":"Section 2 (formal model), applied in all later sections"},{"comment":"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.","section":"Section 3.2, Proposition 2 (equation (8))"},{"comment":"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.","section":"Sections 4-5 and 6.2, Tables 3, 5, 7, 8, 9"}],"minor_comments":[{"comment":"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":"Section 3.2"},{"comment":"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":"Section 3.5, Proposition 3"},{"comment":"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":"Section 4.1"},{"comment":"The text says 'as seen in Figure 13' after presenting Figure 16; the cross-reference should be to Figure 16.","section":"Section 5.2"},{"comment":"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.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The Section 2 reduction of Attacker strategies is the main correctness risk; I would not accept the paper without either a proof of that reduction or a clear restatement of the model in which (i,d) strategies are definitionally the Attacker's strategy set. The numerical sections also need either more rigorous verification or a softened claim about being 'solved'. The analytic star results are attractive and may be publishable once the surrounding claims are adjusted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThe two things you should know: the star-network results are the real contribution, and the line/circle/star-in-circle sections are numerical explorations for small n and m, not solutions. The abstract says the game is 'solved' for those networks, which overstates what is in the paper.\n\nThe Section 2 restriction of attacker strategies to (i,d) pairs is informal but ultimately correct. The stress-test worry about the hidden age of an absence run does not land. For any fixed Markovian patroller strategy, the attacker can always wait for the next visit to her chosen node and then count d consecutive absences, achieving exactly the payoff q_d. Any strategy that attacks after observing t absences without waiting for a visit is a convex combination of q_d values for d at least t, so it cannot beat the best pure d. Thus the computed values are not just upper bounds; the restriction does not change the value. The paper's own justification (telling the attacker the total number of zeros since the last visit) is too free, but the conclusion is right.\n\nWhat the paper does well: the analytic star sections are clean and checkable. Proposition 1 gives a closed form for m=2; Proposition 2 gives an elegant result for odd m; the asymptotic analysis for m=4 is a nice addition. The model itself is a genuine new variant in the patrolling literature.\n\nSoft spots, in order of importance. First, the numerical sections fix D=15 and rely on visual/qualitative checks for larger D; no code, no grid resolution, no error analysis. That makes the tables hard to treat as rigorous game values. Second, the m=5 and m=6 payoff formulas for L4 and L5 are omitted, so those numbers cannot be independently reproduced. Third, the optimal-attack-node check is done only under the numerically optimal patrol; that is the right check for the Stackelberg value, but it is not an optimality proof over all patrols. Fourth, a minor typo in Proposition 3: s is about 0.217, not 0.136. None of this undermines the star sections.\n\nI largely agree with the conditional verdict, but I would drop the stress-test concern. The paper deserves a serious referee. I would send it out, expecting the authors to fix the abstract and either ship code or relabel the numerical parts as computational case studies. The star results alone justify publication at a good applied-math journal.","headline":"A useful new attacker-information model with clean star-network results, but the abstract oversells the numerical sections.","tokens_in":24520,"tokens_out":8967,"would_cite":true,"duration_ms":92022,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["91A05","91A43","90B40"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["two-person game","constant-sum game","patrolling game","uniformed patroller","star network","line network","circle network","waiting time"],"falsifier":"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.","tokens_in":23521,"feed_emoji":"🚔","tokens_out":10709,"duration_ms":94207,"temperature":0.7,"pith_summary":"This paper introduces a variant of network patrolling in which the Attacker can see the Patroller when he is at the node she plans to attack, because he wears a uniform, and can postpone her attack until he has been absent for $d$ consecutive periods. The paper's goal is to solve the resulting zero-sum game, and it claims full solutions for star, line, circle, and star-in-circle networks. On the star $S_n$ with two-period attacks, the solution is closed form: the Patroller should reflect at the end nodes and stay at the center with probability $\\sqrt{n(n-1)}-(n-1)$, the Attacker should attack a random end after a delay of two periods, and the interception probability is $(2n-1)-2\\sqrt{n(n-1)}$. For odd attack durations on the star, an ordinary random walk is uniquely optimal. If these results are right, uniformed patrols have a rational design that differs sharply from invisible-patrol strategies, and the paper provides exact benchmarks for that design.","feed_headline":"Star-network patrol: stay at center, attacker waits two beats","feed_subtitle":"Closed form: reflect at the ends, linger near the center about half the time, and the attacker waits two periods.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Defines the original invisible-patroller game with attack intervals, the Hamiltonian-cycle value $m/n$, and the zero-sum format that the uniformed model modifies.","marker":"Alpern, Morton and Papadaki (2011)"},{"why":"Supplies the border-patrol line-network setting and the 'diametrical strategy' baseline for end-node attacks that the line-network sections re-examine under a visible patroller.","marker":"Papadaki et al. (2016)"},{"why":"Provides the patrolling-security-game formulation with a single patroller and intruder that the paper's Stackelberg approach builds on.","marker":"Basilico, Gatti and Amigoni (2012)"}],"fun_headline_variants":["Patroller in uniform: attacker waits, then strikes","Observing patroller changes optimal patrol strategy","Star network: attacker waits two beats, patroller reflects","Uniformed patroller: attacker gains edge by waiting","Delay gives attacker power in network patrol game"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Patroller in uniform: attacker waits, then strikes","Observing patroller changes optimal patrol strategy","Star network: attacker waits two beats, patroller reflects","Uniformed patroller: attacker gains edge by waiting","Delay gives attacker power in network patrol game"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00082,"raw_usage":{"total_tokens":3630,"prompt_tokens":1029,"completion_tokens":2601,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":645,"completion_tokens_details":{"reasoning_tokens":2528}},"tokens_in":645,"tokens_out":2601,"duration_ms":16956,"temperature":1.0,"reasoning_tokens":2528,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T15:01:29.177779+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}