Pith. sign in

REVIEW 3 major objections 4 minor 22 references

An Exact Solution of the Two-Ball Multi-Look Search Game with Three Boxes and Heterogeneous Costs

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

Pith's one-line read For every $a\ge b\ge c>0$, the two-ball, three-box multi-look search game has value exactly $\max\{V_1,V_2,V_3\}$, with optimal Hider distributions of product form in each of three regimes.

desk verdict A genuine exact solution for the heterogeneous three-box two-ball search game, with a real but auditable soft spot: the V2/V3 upper-bound certificates live in supplementary code rather than in the printed argument. read the letter →

arxiv 2608.05406 v1 pith:YKY43VSW submitted 2026-08-05 math.OC

classification math.OC MSC 91A2491A05
keywords searchgamesmulti-lookboxzero-sumheterogeneouscostsproduct-formdistributionsexactsymbolicverificationBernsteinpolynomials
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

This paper claims to settle the two-ball, three-box instance of the multi-look search-cost game, in which a Hider hides two identical balls among three boxes with costs $a\ge b\ge c>0$ and a Searcher pays a box's cost each time she opens it, stopping once both balls are found. The author establishes that the game's value is exactly $\max\{V_1,V_2,V_3\}$, where the three candidate values are explicit rational functions of the costs, and that in the three corresponding regimes the optimal Hider distribution has product form on a nested support of three, five, or all six placements. On the Searcher side, the proof reduces every non-wasteful deterministic policy to one of 72 elementary decision trees with only 42 distinct opening-cost profiles, so the adaptive game becomes a finite 6×42 matrix game. If correct, this is the first complete parametric solution of a heterogeneous multi-look search game beyond the two-box case, and it verifies the product-form equalizing conjecture for this instance. The proof is exact, with the computer-assisted parts reduced to rational Bernstein-form sign certificates.

What carries the argument

The load-bearing objects are the complete homogeneous polynomials $T_m=\sum_{x_1+x_2+x_3=m}a^{x_1}b^{x_2}c^{x_3}$ and the nested product-form Hider distributions $h_1,h_2,h_3$ that define the three candidate values $V_1,V_2,V_3$. Lemma 1 produces the Hider lower bounds by conditioning on the first box, and the matching Searcher upper bounds come from Proposition 1, the finite reduction showing that every non-wasteful deterministic Searcher policy is payoff-equivalent to one of 72 elementary decision trees that induce only 42 opening-count profiles. The remaining work is done by exact Searcher mixtures whose weights are proved nonnegative by rational Bernstein-form range certificates, turning the continuous parameter space into a finite set of sign conditions.

What would settle it

At $(a,b,c)=(4,3,2)$, the theorem predicts the value $114/11$ (since $V_3$ dominates); solving the explicit finite zero-sum game with six Hider placements and the 42 opening-count profiles, using exact rational arithmetic, and comparing the result with $114/11$ would settle the central claim, because any difference refutes Theorem 1.

Watch

Extended reading notes

Core claim

The central claim is Theorem 1: for all $a\ge b\ge c>0$, the value $V(a,b,c)$ of the two-ball, three-box multi-look search game equals $\max\{V_1,V_2,V_3\}$, where, with $T_m=\sum_{x_1+x_2+x_3=m} a^{x_1} b^{x_2} c^{x_3}$, $$V_1=a+\frac{T_2}{T_1},\quad V_2=\frac{2T_3-$c^{2}$(a+b+2c)}{T_2-$c^{2}$},\quad V_3=\frac{2T_3}{T_2}.$$ The optimal Hider distributions are the product-form probabilities $h_1,h_2,h_3$ on the nested placement sets $H_1\subset H_2\subset H_3$ (three, five, or all six placements). The Searcher side is reduced by Proposition 1 to a finite game: every non-wasteful deterministic policy is payoff-equivalent to one of 72 elementary decision trees that induce only 42 opening-count profiles, so randomized policies lie in the convex hull of 42 columns. The upper bound that matches the Hider lower bounds is analytic in the $V_1$ regime and is given by explicit exact Searcher mixtures in the $V_2$ and $V_3$ regimes.

Load-bearing premise

The lower-bound half of the proof assumes that the one-ball and two-box search problems solved in an earlier paper are solved correctly and that their values carry over to the subgames that arise after the Searcher's first opening; if that external result were wrong or misapplied, the claimed value formula could fail.

Editorial extensions

If this is right

  • For any $a\ge b\ge c>0$, the exact search cost is computed directly from $\max\{V_1,V_2,V_3\}$, with no need to run a search algorithm or solve a linear program.
  • The optimal Hider support expands with equalizing costs: three placements when the expensive box dominates, five when only the placement with both balls in the cheapest box is excluded, and all six when costs are balanced.
  • Because all non-wasteful Searcher strategies reduce to 42 opening-count profiles, randomized optimal play in this game is a mixture of a small, explicitly enumerated set of deterministic policies.
  • The equalizing-property conjecture for multi-look search games is confirmed for this first heterogeneous three-box case, and the paper points to three balls in three boxes and two balls in four boxes as the next cases to test.

Reading between the lines

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

  • A natural generalization is that in the $n$-box, $k$-ball game optimal Hider distributions remain product-form on a subset of placements that omits configurations concentrating balls in the cheapest boxes, with the omitted set shrinking as costs become balanced; the two-ball, four-box case is the immediate check.
  • The finite reduction suggests a general exact-solution recipe for box search games: enumerate non-wasteful policies, compress to opening-count profiles, solve the zero-sum matrix symbolically, and certify polynomial inequalities by Bernstein subdivision; this may make larger games tractable without floating-point LP solvers.
  • At the parameter point where all three candidate values tie, the regime boundaries meet, so numerical implementations cannot distinguish the regimes from local data; this point is a natural stress test for any algorithm built on the theorem.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper studies a zero-sum search game in which a Hider distributes two identical balls among three boxes with search costs a ≥ b ≥ c > 0, and a Searcher opens boxes adaptively until both balls are found, paying the box cost per opening. The main result, Theorem 1, gives the exact value as V(a,b,c) = max{V1,V2,V3}, where V1, V2, V3 are explicit rational functions (Eqs. (1)–(3)), and identifies optimal Hider strategies h1, h2, h3 as product-form distributions on nested supports of size 3, 5, and 6. The proof proceeds by a finite reduction to 42 opening-count profiles (Proposition 1), lower bounds from Hider strategies (Lemma 1, using external one-ball and two-box values), an analytic upper bound in the V1 regime (Section 5), and Searcher mixture upper bounds for the V2 and V3 regimes (Lemmas 2 and 3), whose exact weights are asserted to be in the supplement and certified by rational Bernstein subdivision (Section 8). The paper also reports independent implementations and a numerical LP audit.

Significance. If the result is correct, this is a complete exact solution to the smallest heterogeneous multi-look search game beyond the two-box case, with a clean nested-support description and an explicit finite profile reduction. The paper's strengths include a transparent reduction of the game to a 6-by-42 matrix, exact rational candidate values, and a strong reproducibility apparatus: the code regenerates all policies, checks all identities, and the Bernstein certificates are exact rational, not floating-point. The equalizing-product-form conjecture from [14] is verified for this first heterogeneous three-box instance, and the parameter regimes are neatly separated. However, the significance is conditional on the upper-bound certificates being correct and auditable; in the current manuscript these certificates are only described at a high level, with the actual weights and Bernstein data deferred to the supplement. This is a central concern for the proof's completeness.

major comments (3)
  1. [§6, Lemma 2 and §7, Lemma 3] The upper-bound half of Theorem 1 for the V2 and V3 regimes rests entirely on Lemma 2 and Lemma 3, yet the actual Searcher mixtures are not presented in the manuscript. The proofs state 'The exact rational weights are given in the supplement' and that symbolic substitution verifies equalization and nonnegativity, but the weights, the equalization equations, and the excluded-placement expressions (except one identity in Lemma 2) are not printed. A reader cannot verify that a claimed mixture has nonnegative weights summing to one or that it equalizes the required placements, so the theorem's proof is not self-contained. This is not a presentation quibble: if any weight is negative or any equality fails on a boundary, the upper bound V ≤ max{V1,V2,V3} could fail in a subregion. The authors must include the exact weights for all six mixtures (or at least one fully worked example per branch) and the resulting equalization identities, or otherwise make the certifying data part of the paper, not merely the supplemental code.
  2. [§8, Table 1 and 'Primary symbolic certificate'] The Bernstein subdivision procedure is described algorithmically, and Table 1 reports statistics (outside/certified boxes, splits, max depth), but the actual polynomial implications and the certificates themselves are not given. The paper says the program 'verifies all lower-bound identities, solves the six Searcher support systems exactly, and proves every remaining polynomial implication by rational Bernstein subdivision,' but no list of the polynomial implications, the subdivision trees, or the final certificates appears in the text. Since the correctness of the V2/V3 upper bounds depends on these finite but non-explicated checks, the manuscript should either include the certificates (e.g., as a table or an appendix) or clearly state that the proof is computer-assisted and provide the code in a form that the journal can verify. As written, the proof of Theorem 1 cannot be checked from the printed arguments, which is a load-bearing gap.
  3. [§4, Lemma 1] The lower-bound identities in Lemma 1 depend on the external values U3, U2, J, and E taken from [14] without proof. This dependency is acceptable if [14] is correct and the reductions to the conditional subgames are valid, but the paper does not spell out why, after the first opening and a success or failure, the residual game is exactly the one-ball or two-box game with the displayed costs. A short derivation or a statement of the relevant lemmas from [14] would close this gap and make the lower-bound half auditable. I do not consider this a fatal issue, but it is a completeness concern that the authors should address.
minor comments (4)
  1. [§2, Proposition 1] The proof of Proposition 1 is concise and plausible, but the duplicate removal from 72 to 42 is claimed by code rather than shown. Listing a few of the 42 opening-count profiles (or at least the 14 used in the certificates) in the paper would aid understanding; currently only the 14 certificate profiles are given in Appendix A.
  2. [§6, Lemma 2, display after 'the excluded placement satisfies'] The identity C(002) − V2 = −(a+b)(a²−ab−ac+b²−bc−c²)/(a²+ab+ac+b²+bc) is stated without derivation. A one-line explanation of how this follows from the mixture weights would improve readability, even if the full weights remain in the supplement.
  3. [§5, Eq. (4)–(5)] The factorizations (4) and (5) are central to the V1 upper bound; they are stated without proof. They are easily verified by expansion, but a sentence saying 'by direct expansion' would be helpful.
  4. [§8, paragraph on denominators] The argument that denominators do not vanish is carefully handled, but the sentence 'Except in the branch V2, Q2 ≤ 0, each residual factor d has a strictly positive Bernstein lower bound' is a claim that is not demonstrated in the text. Since it is a necessary part of the exactness of the normalization, a reference to the specific certificate output (or a short proof) is requested.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is a standard minimax certification with external prior results and independently checkable Searcher certificates, not a self-referential argument.

full rationale

The paper does not fit any of the circularity patterns. The value candidates V1, V2, V3 are explicit rational functions of the box costs, and the Hider lower bounds in Lemma 1 are derived by conditioning on the first opening and using previously published one-ball and two-box values U3, U2, J, E from Lidbetter and Lin [14]. Those external values are cited as published results from other authors, not introduced ad hoc here, and they are not the target theorem. The upper-bound half is carried by explicit Searcher mixtures with nonnegative weights that equalize the relevant Hider placements; the paper states the supports, records the exact identities for the excluded placement, and defers the detailed rational weights and Bernstein certificates to the supplement. Deferring the printed weights and certificates to ancillary code is a verifiability or completeness concern, not circularity: the proof obligations are stated explicitly, the verification is exact rational arithmetic, and the claimed value is not obtained by renaming a fitted parameter or by defining the answer into the inputs. There are no fitted parameters called predictions, no self-citations, no uniqueness theorem imported from the present authors, and no ansatz smuggled in via citation. The paper also reports independent numerical LP audits and a separate Bernstein-engine audit, which further support the claim that the certificates are not generated by the same code that states the theorem. Therefore no load-bearing step reduces, by construction or by self-reference, to the theorem being proved.

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

No constants are fitted: the value candidates, Hider distributions, and Searcher mixtures are explicit functions of the costs, with no data-fitting step. The proof rests on prior published one-ball and two-box values and on the exactness of the supplied Bernstein certificates. No new physical or mathematical entities are introduced.

assumptions (2)
  • domain assumption The one-ball and two-box search-game values U3, U2, J, E stated in Section 4 as standard consequences of Lidbetter and Lin [14] are correct.
    Lemma 1 uses these values to establish V>=max{V1,V2,V3}. The paper does not reprove them.
  • domain assumption The supplied Bernstein-basis verifier correctly implements exact rational range enclosure and subdivision, and the four sign cases in Lemma 3 are exhaustive.
    Section 8 and Lemma 3 rely on this computer-assisted step to certify nonnegativity of Searcher mixture weights over the normalized parameter square.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An Exact Solution of the Two-Ball Multi-Look Search Game with Three Boxes and Heterogeneous Costs." pith.science (2026). https://pith.science/paper/YKY43VSW

@misc{pith2026260805406,
  author       = {Pith},
  title        = {Pith review of: An Exact Solution of the Two-Ball Multi-Look Search Game with Three Boxes and Heterogeneous Costs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YKY43VSW}},
  note         = {Machine review of arXiv:2608.05406}
}
abstract

A Hider distributes two identical balls among three boxes whose search costs satisfy $a\ge b\ge c>0$. A Searcher opens boxes adaptively until both balls are found; every opening incurs the corresponding box cost and recovers at most one ball. We give an exact solution of this heterogeneous multi-look search-cost game. The value is the maximum of three explicit rational functions. In the three parameter regimes, an optimal Hider strategy is the product-form distribution restricted respectively to three, five, or all six placements. Every non-wasteful deterministic Searcher policy is payoff-equivalent to one of $72$ elementary decision trees, which induce only $42$ distinct opening-count profiles. An analytic argument settles the first regime. Two exact Searcher mixtures settle the second, and four settle the third. Feasibility of the parameterized mixtures over the full cost region is established by exact rational Bernstein-basis certificates. Independent implementations reproduce the policy set, the zero-sum linear-program values, and all $154$ dyadic nodes examined by the Bernstein verifier.

Figures

Figures reproduced from arXiv: 2608.05406 by the authors.

Figure 1
Figure 1. The dominant candidate value on the closure [0 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 16 canonical work pages

  1. [14]

    Lidbetter and K

    T. Lidbetter and K. Y. Lin, Searching for multiple objects in multiple locations,European Journal of Operational Research278(2) (2019), 709–720. doi:10.1016/j.ejor.2019.05.002

  2. [1]

    Gal,Search Games, Mathematics in Science and Engineering, vol

    S. Gal,Search Games, Mathematics in Science and Engineering, vol. 149, Academic Press, New York, 1980

  3. [2]

    Garnaev,Search Games and Other Applications of Game Theory, Lecture Notes in Economics and Mathematical Systems, vol

    A. Garnaev,Search Games and Other Applications of Game Theory, Lecture Notes in Economics and Mathematical Systems, vol. 485, Springer, Berlin, 2000. doi:10.1007/978-3- 642-57304-0

  4. [3]

    Alpern and S

    S. Alpern and S. Gal,The Theory of Search Games and Rendezvous, International Series in Operations Research & Management Science, vol. 55, Kluwer Academic Publishers, Boston,

  5. [4]

    Alpern, R

    S. Alpern, R. Fokkink, L. A. Gasieniec, R. Lindelauf, and V. S. Subrahmanian, eds.,Search Theory: A Game Theoretic Perspective, Springer, New York, 2013. doi:10.1007/978-1-4614- 6825-7

  6. [5]

    S. J. Benkoski, M. G. Monticino, and J. R. Weisinger, A survey of the search theory literature, Naval Research Logistics38(4) (1991), 469–494

  7. [6]

    Hohzaki, Search games: Literature and survey,Journal of the Operations Research Society of Japan59(1) (2016), 1–34

    R. Hohzaki, Search games: Literature and survey,Journal of the Operations Research Society of Japan59(1) (2016), 1–34. doi:10.15807/jorsj.59.1

  8. [7]

    A review of minimum cost box searching games

    T. Lidbetter, A review of minimum cost box searching games, arXiv:2502.10551v2, 2025. doi:10.48550/arXiv.2502.10551

Show all 22 references
  1. [8]

    D. M. Roberts and J. C. Gittins, The search for an intelligent evader: Strategies for searcher and evader in the two-region problem,Naval Research Logistics Quarterly25(1) (1978), 95–106

  2. [9]

    J. C. Gittins and D. M. Roberts, The search for an intelligent evader concealed in one of an arbitrary number of regions,Naval Research Logistics Quarterly26(4) (1979), 651–666

  3. [10]

    W. H. Ruckle, A discrete search game, in T. E. S. Raghavan, T. S. Ferguson, T. Parthasarathy, and O. J. Vrieze, eds.,Stochastic Games and Related Topics, Kluwer Academic Publishers, Boston, 1991, pp. 29–43

  4. [11]

    Sharlin, Optimal search for one of many objects hidden in two boxes,European Journal of Operational Research32(2) (1987), 251–259

    A. Sharlin, Optimal search for one of many objects hidden in two boxes,European Journal of Operational Research32(2) (1987), 251–259

  5. [12]

    Lidbetter, Search games with multiple hidden objects,SIAM Journal on Control and Optimization51(4) (2013), 3056–3074

    T. Lidbetter, Search games with multiple hidden objects,SIAM Journal on Control and Optimization51(4) (2013), 3056–3074. doi:10.1137/120893938

  6. [13]

    Alpern, R

    S. Alpern, R. Fokkink, T. Lidbetter, and N. S. Clayton, A search game model of the scatter hoarder’s problem,Journal of the Royal Society Interface9(70) (2012), 869–879. doi:10.1098/rsif.2011.0581

  7. [15]

    Yolmeh and M

    A. Yolmeh and M. Baykal-G¨ ursoy, Weighted network search games with multiple hidden objects and multiple search teams,European Journal of Operational Research289(1) (2021), 338–349. doi:10.1016/j.ejor.2020.06.046

  8. [16]

    Hellerstein, T

    L. Hellerstein, T. Lidbetter, and D. Pirutinsky, Solving zero-sum games using best-response oracles with applications to search games,Operations Research67(3) (2019), 731–743. doi:10.1287/opre.2019.1853

  9. [17]

    Clarkson, K

    J. Clarkson, K. Y. Lin, and K. D. Glazebrook, A classical search game in discrete locations, Mathematics of Operations Research48(2) (2023), 687–707. doi:10.1287/moor.2022.1279

  10. [18]

    T. Bui, T. Lidbetter, and K. Y. Lin, Optimal pure strategies for a discrete search game,Euro- pean Journal of Operational Research313(2) (2024), 767–775. doi:10.1016/j.ejor.2023.08.041

  11. [19]

    Clarkson and K

    J. Clarkson and K. Y. Lin, Computing optimal strategies for a search game in discrete locations, INFORMS Journal on Computing37(3) (2025), 666–683. doi:10.1287/ijoc.2023.0155

  12. [20]

    Garloff, Convergent bounds for the range of multivariate polynomials, in K

    J. Garloff, Convergent bounds for the range of multivariate polynomials, in K. Nickel, ed., Interval Mathematics 1985, Lecture Notes in Computer Science, vol. 212, Springer, Berlin, 1986, pp. 37–56. doi:10.1007/3-540-16437-5 5

  13. [21]

    R. T. Farouki, The Bernstein polynomial basis: A centennial retrospective,Computer Aided Geometric Design29(6) (2012), 379–419. doi:10.1016/j.cagd.2012.03.001. 10

  14. [2003]

    doi:10.1007/b100809. 9

Pith tools

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