{"id":"63204cb1-d01e-442a-9ece-2fcc331464d4","arxiv_id":"1908.02132","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"For search games on general networks, the paper proves the deterministic expanding-search competitive ratio is achieved by a waterfilling strategy and gives constant-factor approximations to the randomized competitive ratio.","lead":"This paper designs search strategies for finding a hidden point in a network, balancing how quickly the target is found against how far away it could be. It shows a simple 'waterfilling' strategy is optimal for deterministic expanding search, and gives randomized strategies that get within a small constant factor of the best possible for both expanding and pathwise search.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 8 as stated and proved contains a false inequality, and the main 5/4-approximation proof depends on it; a one-line correction appears to repair the argument.","rationale":"The reader's weakest assumption was that Lemma 14 incorrectly applies a connected-set lower bound to the potentially disconnected sets Q_j. That is a real presentational issue with the proof as written. However, the more load-bearing defect is upstream: Theorem 8's proof claims T(S,u_A) >= d(A)+lambda(A)/2, which is false even for a connected ball in a two-ray star. This false inequality is what the text cites when proving Lemma 14, so the derivation of Theorem 16 is formally invalid as submitted. The good news is that the intended lower bound is almost certainly rho >= lambda(A)/(2d(A)), obtained from T(S,u_A) >= lambda(A)/2, and that corrected bound is sufficient for Lemma 14 by a short calculation. Moreover, the lambda(A)/2 inequality is purely measure-theoretic and does not need connectedness, so the reader's connectivity concern is resolved once the theorem is corrected. I therefore do not move the verdict: the paper remains CONDITIONAL, with the condition being that the authors repair Theorem 8 and its proof to state and prove rho >= lambda(A)/(2d(A)) rather than the printed d(A)+lambda(A)/2 version.","tokens_in":15511,"tokens_out":15565,"duration_ms":175094,"concrete_test":"Re-derive Lemma 14 using the corrected inequality T(S,u_A) >= lambda(A)/2 instead of the printed d(A)+lambda(A)/2, and then verify the algebra: from rho >= lambda(Q_j)/(2 d(Q_j)) one gets lambda(Q_j) <= 2 d(Q_j) rho, so (1 - d(Q_j)/2^j) lambda(Q_j) <= 2 d(Q_j)(1 - d(Q_j)/2^j) rho <= 2^{j-1} rho. If this derivation goes through, the main theorem survives as a typo-level flaw; if it does not, the 5/4 approximation is unsupported. As an additional check, compute T(S*,u_A) for the two-ray star and A=Q[1] to confirm the printed bound 3/2 is violated by the actual value 1.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 4.2, Theorem 8 asserts that the Hider strategy h_A with dh_A(x) proportional to d(x) du_A(x) gives rho >= (d(A)+lambda(A)/2)/d(A). The proof relies on the claim T(S,u_A) >= d(A)+lambda(A)/2 for every expanding search S. This claim is false. For a two-ray star rooted at O and A = Q[1], the ball of radius 1, we have lambda(A)=2 and d(A)=1/2. The waterfilling search S*(t)=Q[t/2] finds a point at distance r on either ray at time 2r, so T(S*,u_A)=1. The asserted lower bound is 3/2, which is larger than the actual value. The correct universal lower bound is T(S,u_A) >= lambda(A)/2, obtained by writing T as the integral of the survival probability and using lambda(S(t) intersect A) <= t. This yields rho >= lambda(A)/(2d(A)), which is exactly the form used in Lemma 10 and in the proof of Lemma 14. Since Lemma 14 is the technical engine of Theorem 16, the printed proof of the central 5/4-approximation is formally invalid: it cites a theorem whose stated lower bound is false. The fix is a one-line replacement in Theorem 8 and its proof. With that correction, the connectedness worry about the sets Q_j in Lemma 14 also disappears, because the lambda(A)/2 bound is a measure-theoretic fact that does not require A to be connected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies deterministic and randomized search games on a connected network, with a root O, under a competitive-ratio objective. For expanding search, it proposes the waterfilling strategy S*(t)=Q[g_Q(t)] and proves that it achieves the optimal deterministic competitive ratio sigma = sup_{r>0} f_Q(r)/r. For randomized expanding search, it gives the bound sigma/2 <= rho <= sigma, a Hider-strategy lower-bound tool, and a randomized doubling strategy that is claimed to be a 5/4-approximation of the randomized competitive ratio; it also analyzes exact optimal strategies on a three-arc Y-network. For pathwise search, it adapts the doubling strategy to obtain a claimed 5-approximation of the randomized competitive ratio, improving on the earlier 3+2*sqrt(2) factor.","tokens_in":15817,"tokens_out":14195,"duration_ms":182606,"significance":"The waterfilling optimality theorem and the sigma/2 <= rho <= sigma bounds are clean and correct, and the randomized doubling framework is a genuinely new approach to general, possibly unbounded networks. If the central approximation theorems were fully correct, the paper would make a solid contribution to the competitive-search literature: it gives the first constant-factor randomized approximation for expanding search on general networks and improves pathwise search. However, the proof of the main 5/4-approximation rests on Theorem 8, whose stated inequality is false, and the Y-network section contains algebraic and probabilistic errors. The identified correction to Theorem 8 appears to repair the main doubling argument, so the paper's core idea is defensible, but the manuscript as written does not establish its headline claims.","major_comments":[{"comment":"The lower bound T(S,u_A) >= d(A) + lambda(A)/2 asserted in the proof of Theorem 8 is false. For the two-ray star with unit arcs and A=Q[1], we have lambda(A)=2 and d(A)=1/2, while the waterfilling search S*(t)=Q[t/2] gives T(S*,u_A)=1, so the claimed bound 3/2 is violated. The correct universal bound is T(S,u_A) >= lambda(A)/2, obtained by writing T(S,u_A) as the integral of the survival probability and using lambda(S(t) intersect A) <= t. The theorem should therefore state rho >= lambda(A)/(2 d(A)). This corrected form is exactly what Lemma 10 and Lemma 14 use, and being measure-theoretic it also removes the need for the sets Q_j in Lemma 14 to be connected. As printed, the proof of Lemma 10 already applies the corrected form rather than the stated theorem, so the manuscript is internally inconsistent.","section":"Section 4.2, Theorem 8"},{"comment":"The lower-bound calculation for the Y-network is algebraically wrong. Substituting d(A)=1+(x^2+y^2)/(2(x+y)) and lambda(A)=x+y into (d(A)+lambda(A)/2)/d(A) yields 1+(x+y)^2/(2(x+y)+x^2+y^2), not the displayed 1+2xy/(x(x+2)+y(y+2)); the manuscript's numerator 1+(x+y)/2 omits the (x^2+y^2)/(2(x+y)) part of d(A). In addition, Table 1 assigns a negative probability to strategy B whenever M^2 > L^2+2L, for example L=1 and M=10 gives numerator 1+2-100=-97, so the proposed mixture is not a valid randomized strategy. Consequently the claimed exact value V and the statement that optimal randomized strategies are complex even on three-arc networks are not established as written.","section":"Section 4.3, Eq. (5) and Table 1"},{"comment":"The abstract and the introduction describe the randomized doubling strategy as a 5/4-approximation of the randomized competitive ratio, but Theorem 16 proves only rho_s <= (5/4)rho + 1/2. For a network with small rho, such as a single ray where rho=1, the bound gives 1.75, not 1.25. If the intended approximation notion permits an additive constant, that notion should be defined and stated precisely; as written, the claim 'within a factor at most 5/4' is stronger than what is proved.","section":"Abstract and Theorem 16"}],"minor_comments":[{"comment":"There is a typo: 'we will refer to an expanding search as a search search strategy' should read 'as a search strategy.'","section":"Definition 1"},{"comment":"The notation d(A) is used both for the distance from O to A and for the average distance from O to points in A; these should be denoted by different symbols throughout.","section":"Section 4.2, first paragraph"},{"comment":"The expression S(t1) intersect S(ts) should be S(t1) intersect S(t2).","section":"Lemma 13, proof"},{"comment":"The probabilities and search descriptions use M in rows A, B, and D even though M' = max{M, sqrt(L(L+2))} was defined for the strategy; the table should be restated consistently in terms of M'.","section":"Table 1"},{"comment":"The derivation of the Y-network lower bound would benefit from a displayed formula for d(A) in terms of x and y; the current omission appears to be the source of the algebraic error in Eq. (5).","section":"Section 4.3"},{"comment":"The reference 'Angelopoulos, S., , Arsénio, D., Dürr, C., & López-Ortiz, A.' contains a stray comma after the first author's name and should be cleaned up.","section":"References"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know up front. First, the main results are real: the deterministic waterfilling optimality is clean, and the randomized doubling strategy gives the first constant-factor approximation for the randomized expanding-search ratio on general continuous networks, plus a pathwise 5-approximation that beats the standing 3+2√2 ≈ 5.828 bound. Second, the paper has two honest warts: the abstract claims a strict 5/4 approximation when Theorem 16 proves ρ_s ≤ (5/4)ρ + 1/2, and the Y-network optimality table in Section 4.3 contains a negative probability (e.g., L=1, M=2 gives -1/11 for strategy B) and doesn't always sum to 1. Those are fixable, but the printed version is wrong.\n\nThe stress-test note about Theorem 8 does not survive contact with the paper. It claims the lower bound T(S,u_A) ≥ d(A)+λ(A)/2 is false, using a two-ray star and setting d(A)=1/2. That misreads the notation. In the paper, d(A) in that inequality is the minimum distance from the root to A, which is 0 for the ball Q[1]; the average distance is a different quantity, though the text confusingly uses the same symbol for both. With minimum d, the inequality follows from a simple survival-probability integral, and it does not require A to be connected. So the connectedness worry about Lemma 14 also disappears — the bound is measure-theoretic.\n\nWhat's good: Theorem 6's proof is short and correct; Lemma 10's degree bound and the concavity corollary are neat; the random-levels RDFS construction is genuinely inventive and, apart from the additive constant, the 5/4 analysis holds together. The pathwise adaptation in Theorem 19 is a real improvement and imports the expanding-search lower-bound technology in a natural way.\n\nWho should read it: people working in search games, competitive analysis of online algorithms, and those interested in the expanding-search paradigm. It is not a blockbuster outside the subfield, but inside it, it answers open questions from the authors' own earlier work.\n\nVerdict: the paper deserves a serious referee. The flaws are local — an abstract overstatement and a mistaken probability table — and both are repairable without touching the core arguments. I would send it to peer review and ask for a revision on those two points.","headline":"Core results are solid; abstract oversells the 5/4 factor, the Y-network table has a sign error, and the stress-test's Theorem 8 counterexample is a misreading.","tokens_in":16345,"tokens_out":14745,"would_cite":true,"duration_ms":129546,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B40","91A05","68W27"],"pacs":[],"model":"deepseek-v4-flash","headline":"Waterfilling search is optimal; random doubling hits 5/4","keywords":["search games","expanding search","pathwise search","competitive ratio","randomized search strategies","network search","waterfilling search","approximation algorithms"],"falsifier":"Take a rooted tree with two long branches and compute the worst-case expected normalized discovery time of the randomized doubling strategy for points just inside $2^k$; if the disconnected structure of $Q_k$ causes the quantity $E(L_J)/(d(x)\\rho)$ from Theorem 16's proof to exceed $5/4$, the claimed bound $\\rho_s\\le 5\\rho/4+1/2$ is false. This can be checked by dynamic programming over the tree or by direct simulation of the strategy.","tokens_in":15287,"feed_emoji":"🔍","tokens_out":13102,"duration_ms":118236,"temperature":0.7,"pith_summary":"The paper asks how efficiently a Searcher can locate a hidden point in a network when the score is the competitive ratio, the worst-case ratio of discovery time to the Hider's true distance from the root, and it covers both bounded and unbounded networks. For expanding search, where movement over already explored territory is free, it proves that the optimal deterministic strategy is a pure waterfilling search that sweeps outward in distance layers from the root, with competitive ratio $\\sup_{r>0} f_Q(r)/r$ where $f_Q(r)$ is the length of the network within distance $r$. The main new result is a randomized doubling strategy, formed by running randomized depth-first searches over randomly chosen distance bands, that approximates the randomized competitive ratio of every network within a factor of $5/4$, and a sibling strategy giving a $5$-approximation for the classical pathwise model. The paper also shows the deterministic-to-randomized gap can be as large as a factor of $2$, and that exact randomized optimal strategies are already intricate on a three-arc Y-shaped network.","feed_headline":"Waterfilling search is optimal; random doubling hits 5/4","feed_subtitle":"Flooding a network outward is exactly optimal; randomizing the search levels guarantees a 5/4 approximation.","key_machinery":"The load-bearing object is the family of distance discs $Q[r]=\\{x:d(x)\\le r\\}$ and its measure $f_Q(r)$; the inverse $g_Q$ turns the discs into the waterfilling strategy $S^*(t)=Q[g_Q(t)]$, and the optimality proof is simply that any search must spend at least $f_Q(r)$ time before it can cover $Q[r]$. For the randomized results, the supporting machinery is a Hider strategy that hides with density proportional to distance on a connected set $A$, forcing $\\rho\\ge(\\bar d(A)+\\lambda(A)/2)/\\bar d(A)$, and the randomized doubling strategy: partition a shortest-path tree into random bands $R_j$ with boundaries chosen uniformly in $[2^{j-1},2^j]$, then on each band run a randomized depth-first search, an equiprobable mixture of a DFS and its reverse. Lemma 13 bounds the expected discovery time inside a band, Lemma 14 converts the Hider lower bound into the band-measure inequality used in Theorem 16's calculation, and Lemma 15 computes the expected overlap between a band and its random boundary; the $5/4$ constant emerges from optimizing the resulting three-term expression in $d(x)/2^k$.","core_discovery":"On its own terms, the paper's central claim is that the competitive ratio of expanding search is governed by the function $f_Q(r)$, the total measure of all points at distance at most $r$ from the root. The waterfilling search $S^*(t)=Q[g_Q(t)]$, which at time $t$ has explored exactly the set of points within distance $g_Q(t)$, is optimal among deterministic expanding searches, so the deterministic ratio is exactly $\\sigma=\\sup_{r>0} f_Q(r)/r$. Randomization changes the picture: the paper constructs Hider strategies that force $\\rho\\ge\\sigma/2$, gives networks where this bound is tight, proves that for concave $f_Q$ the deterministic and randomized ratios coincide with the root degree, and exhibits a three-arc network whose optimal randomized strategy is a complicated mixture of four search orders. To escape that complexity, it proves that the randomized doubling strategy satisfies $\\rho_s\\le(5/4)\\rho+1/2$, and that the same level-doubling construction yields a $5$-approximation for pathwise search, improving the previous $3+2\\sqrt2\\approx5.828$ approximation.","pith_inferences":["The $5/4$ constant is likely not the last word: for the line and the star, the structure of known optimal randomized strategies suggests the true worst-case benefit of randomization is milder, and the band-partition analysis could be sharpened on those restricted domains.","A concrete test of the proof's weakest point is to run the doubling strategy on a rooted tree with several long branches and check whether the disconnected distance bands $Q_j$ require a larger approximation constant than $5/4$; if the constant survives, the proof can likely be repaired by componentwise bookkeeping.","In practical terms, the implementation section implies the strategy's oracle cost is logarithmic in the Hider's distance, so on road-network-like inputs with approximately concave $f_Q$ the waterfilling strategy may already be near-optimal and need no randomization at all."],"forward_implications":["The deterministic expanding competitive ratio of any network is exactly computable as $\\sup_{r>0} f_Q(r)/r$, so evaluating a network for search reduces to knowing its distance-measure function.","For networks whose distance-measure function $f_Q$ is concave (dense near the root, thinning outward), randomization buys nothing: $\\sigma=\\rho=\\deg_Q(O)$ and waterfilling is optimal in both senses.","The randomized competitive ratio can be as small as half the deterministic one, so forbidding randomization can cost a factor of $2$ in guaranteed worst-case discovery time.","Any exact optimal randomized expanding strategy must, on some three-arc networks, mix between qualitatively different orders of searching the branches, so simple fixed-rule strategies cannot be exactly optimal in general.","The same random-band construction yields the first constant-factor approximation for randomized pathwise search on general networks, with factor $5$, improving the previous $3+2\\sqrt2\\approx5.828$."],"supporting_citations":[{"why":"Introduces expanding search, defines the search time, and supplies the compactness and semicontinuity facts behind the game value.","marker":"(Alpern & Lidbetter, 2013)"},{"why":"Supplies the minimax theorem that identifies the randomized competitive ratio with the value of the search game.","marker":"(Alpern & Gal, 1988)"},{"why":"Provides the discrete-tree 5/4-approximation strategy and the open questions that this paper's randomized doubling strategy answers in the continuous setting.","marker":"(Angelopoulos et al., 2019)"},{"why":"Gives the fixed-graph pathwise framework and the $3+2\\sqrt2$ approximation that the pathwise $5$-approximation improves.","marker":"(Koutsoupias et al., 1996)"},{"why":"Supplies the pathwise randomized depth-first-search bound used as Lemma 18 in the $5$-approximation proof.","marker":"(Alpern & Gal, 2003)"},{"why":"Provides the infinitesimal-tour device for unbounded domains used in the implementation of the doubling strategies.","marker":"(Gal, 1974)"}],"fun_headline_variants":["Waterfilling wins deterministic; doubling hits 5/4","Flood network to search optimally; randomize for 5/4","Optimal search = waterfill; random approx = 5/4","Search games: waterfilling exact, random 5/4","Network search: waterfill optimal, doubling 5/4"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing technical premise is that the lower-bound argument may treat each distance band $Q_j=\\{x:2^{j-1}\\le d(x)<2^j\\}$ as one connected region when applying the Hider-strategy bound of Theorem 8, even though on a multi-branch tree the band is a disjoint union of intervals; if componentwise summation is not justified, the $5/4$ and pathwise $5$ constants lose their proof.","fun_headline_variants_meta":{"raw":{"variants":["Waterfilling wins deterministic; doubling hits 5/4","Flood network to search optimally; randomize for 5/4","Optimal search = waterfill; random approx = 5/4","Search games: waterfilling exact, random 5/4","Network search: waterfill optimal, doubling 5/4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000338,"raw_usage":{"total_tokens":1924,"prompt_tokens":1060,"completion_tokens":864,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":676,"completion_tokens_details":{"reasoning_tokens":773}},"tokens_in":676,"tokens_out":864,"duration_ms":8834,"temperature":1.0,"reasoning_tokens":773,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:55:16.132853+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a rooted tree with two long branches and compute the worst-case expected normalized discovery time of the randomized doubling strategy for points just inside $2^k$; if the disconnected structure of $Q_k$ causes the quantity $E(L_J)/(d(x)\\rho)$ from Theorem 16's proof to exceed $5/4$, the claimed bound $\\rho_s\\le 5\\rho/4+1/2$ is false. This can be checked by dynamic programming over the tree or by direct simulation of the strategy.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces expanding search, defines the search time, and supplies the compactness and semicontinuity facts behind the game value."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the minimax theorem that identifies the randomized competitive ratio with the value of the search game."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the discrete-tree 5/4-approximation strategy and the open questions that this paper's randomized doubling strategy answers in the continuous setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the fixed-graph pathwise framework and the $3+2\\sqrt2$ approximation that the pathwise $5$-approximation improves."},{"cited_title":"(2003).The theory of search games and rendezvous","cited_arxiv_id":null,"evidence_quote":"Supplies the pathwise randomized depth-first-search bound used as Lemma 18 in the $5$-approximation proof."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the infinitesimal-tour device for unbounded domains used in the implementation of the doubling strategies."}],"review_version":1}