{"id":"5ea1ae30-b39a-4447-9aee-0ce19d3b55b0","arxiv_id":"2502.03574","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Pandora's box, replacing true distributions by estimates within Kolmogorov distance epsilon reduces optimal expected utility by at most O(n epsilon).","lead":"This paper studies how small errors in the estimated probability distributions affect the optimal strategy in Pandora's box, a classic search-and-stop problem. It proves that using a slightly wrong distribution costs at most a linear loss in the number of boxes times the estimation error, a clean robustness guarantee for decision algorithms.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5's key integral identity is false for the implicit independent coupling, so the proof of the O(nε) bound is incomplete; likely repairable via Wasserstein/quantile coupling.","rationale":"The reader's verdict is CONDITIONAL, and my stress-test does not move it. The core claim—that using reserves computed from Kolmogorov-ε-inaccurate priors loses O(nε) utility—is likely correct, since Lemma 4 establishes that the value function is 1-Lipschitz in each coordinate and Wasserstein distance on [0,1] is bounded by Kolmogorov distance. However, the proof of Lemma 5 as written contains a false integral identity: E|g(X)-g(X')| is not determined by the marginal survival functions alone. This is a genuine gap in the submitted manuscript, and it is exactly the step that carries the sensitivity bound. The reader's formal weakest_assumption points to equation (2) in Lemma 4, which I find plausible; the actual flaw is the later identity in Lemma 5, also flagged in the reader's rationale. A standard Wasserstein/quantile-coupling argument should repair the proof, making the result correct but the exposition incomplete. Thus the appropriate verdict remains CONDITIONAL, with no change from the reader's recommendation.","tokens_in":5713,"tokens_out":9933,"duration_ms":92718,"concrete_test":"Compute both sides of the displayed equality in Lemma 5 for D_i=D'_i=Uniform[0,1], g(x)=x, and independent X,X'; the equality fails (left 1/3, right 0), confirming the proof gap. Then re-derive Lemma 5 using the quantile coupling X'=F_{D'_i}^{-1}(F_{D_i}(X)) and the 1-Lipschitz property of g; if the per-coordinate O(ε) bound follows, the central claim is correct but the submitted proof requires revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central sensitivity bound rests on Lemma 5. After equation (6), the proof asserts E[|g(X)-g(X')|] = ∫_0^∞ |Pr[g(X)≥t]-Pr[g(X')≥t]| dt. This identity is not valid for arbitrary couplings of X~D_i and X'~D'_i. For example, if D_i=D'_i=Uniform[0,1], g(x)=x, and X,X' are independent, the left side is 1/3 while the right side is 0. The equality would require an optimal Wasserstein coupling, but the proof never specifies one and the marginals alone do not determine E|g(X)-g(X')|. Since this equality is the only step converting the Kolmogorov ε into a utility loss, Theorem 2 is not substantiated as written. The gap is nonetheless repairable: because g is 1-Lipschitz, one can take the quantile coupling X'=F_{D'_i}^{-1}(F_{D_i}(X)), obtaining E|X-X'| = W1(D_i,D'_i) ≤ ε and hence E|g(X)-g(X')| ≤ ε. However, this argument is absent from the manuscript. I do not see a comparable failure in Lemma 4's equation (2); the cost-shifting argument there checks out. The load-bearing concern is the false integral identity in Lemma 5.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the sensitivity of Weitzman's optimal algorithm for Pandora's box to inaccuracies in the prior distributions. It assumes each true distribution D_i and estimated distribution D'_i are within ε in Kolmogorov distance and are supported on [0,1]. Theorem 2 claims |W_σ(D) - W_σ(D')| ≤ O(nε), where σ is the vector of reserve prices for D; Corollary 3 then concludes that using reserve prices computed from the inaccurate distributions loses at most O(nε) in expected utility. The proof proceeds coordinate by coordinate: Lemma 4 shows that the value function is 1-Lipschitz in the value of a single box, and Lemma 5 bounds the per-coordinate loss by O(ε). The main issue is that the proof of Lemma 5 relies on an integral identity for E[|g(X)-g(X')|] that is not valid for the coupling implicitly used in the argument.","tokens_in":5956,"tokens_out":16588,"duration_ms":143844,"significance":"If the result holds, this is a clean and natural robustness statement for a classical optimal-stopping problem, paralleling the inaccurate-priors analysis of Dütting and Kesselheim for prophet inequalities. The O(nε) bound is explicit, the statement is falsifiable, and the high-level strategy is appropriate: decompose the total error into per-coordinate changes and exploit the Lipschitz property of the value function. The cost-shifting argument in Lemma 4 is a genuine technical contribution and, as far as I checked, correct. However, because the key identity in Lemma 5 is not justified as written, the proof of the main theorem is incomplete. The gap appears repairable by a standard quantile-coupling argument, but it is load-bearing for the central claim.","major_comments":[{"comment":"The identity E[|g(X)-g(X')|] = ∫_0^∞ |Pr[g(X) ≥ t] - Pr[g(X') ≥ t]| dt is not valid for an arbitrary coupling of X ~ D_i and X' ~ D'_i. The proof says only 'Sample the random variables X_i and X'_i from D_i and D'_i respectively', which does not specify the joint distribution. For the default independent coupling, the identity fails: if D_i = D'_i = Uniform[0,1] and g(x)=x, the left side is 1/3 while the right side is 0. The equality holds only under the quantile/comonotone coupling, or equivalently the right side is the W1 distance between the laws of g(X) and g(X'), which is a lower bound on E[|g(X)-g(X')|] for an arbitrary coupling. Since this is the only step converting the Kolmogorov error ε into the O(ε) utility loss, Theorem 2 is not established as written. The gap is repairable: choose the quantile coupling X' = F_{D'_i}^{-1}(F_{D_i}(X)); because g is 1-Lipschitz by Lemma 4, E[|g(X)-g(X')|] ≤ E[|X-X'|] = W1(D_i,D'_i) = ∫_0^1 |F_{D_i}(t)-F_{D'_i}(t)| dt ≤ ε, where the last inequality uses the fact that both distributions are supported on [0,1] and are within ε in Kolmogorov distance. This argument should be added to the proof.","section":"Section 3, proof of Lemma 5, display after Eq. (6)"}],"minor_comments":[{"comment":"The statement 'The expected utility of any algorithm for the Pandora's box problem is E[max_i κ_i]' is imprecise; it should say the optimal expected utility is E[max_i κ_i], or that the following algorithm achieves this bound. As written, the sentence is false for suboptimal algorithms.","section":"Section 2, Lemma 1"},{"comment":"The sentence 'Therefore, box i is accepted' appears to contain a typo and should refer to box i′ (the first box whose value exceeds its reserve price). As written, this sentence is confusing because the index i was fixed at the start of the lemma.","section":"Section 3, proof of Lemma 4"},{"comment":"The definition of g(x) as W_σ(x_1, ..., X_{i-1}, x, D_{i+1}, ..., D_n) uses the random variable X_{i-1} where the proof has fixed the values x_1, ..., x_{i-1}; this should be x_{i-1}.","section":"Section 3, proof of Lemma 5"},{"comment":"There are several typographical errors: 'thie problem' and 'different settings including different settings' in Section 1, 'expected ulity' in Section 3, and inconsistent dashes in the abstract. A careful proofread is recommended.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The flaw in Lemma 5 is localized and has a standard, short repair via quantile coupling, so I view this as a major revision rather than a rejection. My main concern is that the proof as currently written does not establish the central theorem; with the coupling argument added and the minor issues fixed, I would be satisfied."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the thing to know: this is the first treatment of inaccurate priors for Pandora's box, and it gives a clean O(nε) sensitivity bound for Kolmogorov error. That is a real result, and the per-coordinate Lipschitz argument is a good idea that will likely transfer to other search/stopping problems. I agree with the reader that Corollary 3 is the load-bearing statement, and that the cost-shifting argument in Lemma 4 checks out; the inclusion of acceptance-time charges there is handled correctly.\n\nNow the soft spot. Lemma 5 is not proven as written. The proof asserts E|g(X)-g(X')| = ∫ |Pr[g(X)≥t] - Pr[g(X')≥t]| dt after sampling X~D_i and X'~D'_i. That identity is only true for the Wasserstein-optimal coupling, and the proof never specifies a coupling. For independent uniforms with g(x)=x, the left side is 1/3 and the right side is 0. So the central per-coordinate bound is not substantiated.\n\nThat said, this is a repairable gap, not a fatal one. Since g is 1-Lipschitz, take the quantile coupling X' = F_{D'_i}^{-1}(F_{D_i}(X)). Then E|X-X'| = W1(D_i,D'_i) ≤ ε on [0,1], so E|g(X)-g(X')| ≤ ε. That gives the same O(ε) per-coordinate bound without the false identity. I checked that the rest of the proof, including the telescoping over coordinates, goes through.\n\nWho gets value: anyone working on robustness in Bayesian decision problems, prophet inequalities, or Pandora's-box variants. The paper is short and mostly clean; the main fix is a one-paragraph replacement in Lemma 5. The citation pattern is fine, with appropriate credit to Weitzman and Dütting-Kesselheim.\n\nRecommendation: send it to review. It deserves a serious referee. The referee should ask for the coupling fix before acceptance, but the result and the technique are solid enough that this is a conditional accept rather than a reject.","headline":"First robustness result for Pandora's box under inaccurate priors, with a clean O(nε) bound and a real but easily repairable gap in the key lemma.","tokens_in":6514,"tokens_out":3025,"would_cite":true,"duration_ms":25489,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W27","68W40"],"pacs":[],"model":"deepseek-v4-flash","headline":"Treating estimated distributions within Kolmogorov distance ε as true priors costs the optimal Pandora's-box policy at most O(nε) in expected utility.","keywords":["Pandora's box problem","inaccurate priors","Kolmogorov distance","reserve price","expected utility","stability","threshold algorithms","prophet inequalities"],"falsifier":"Take a sequence of instances with continuous distributions on $[0,1]$ and $d_K(D_i,D'_i)\\le\\varepsilon$, compute the exact loss $W_\\sigma(D)-W_{\\sigma'}(D)$, and watch $\\text{loss}/(n\\varepsilon)$ as $\\varepsilon\\to0$. If that ratio is unbounded over any sequence, the $O(n\\varepsilon)$ bound is false; the paper's proof predicts it stays bounded by a universal constant.","tokens_in":5508,"feed_emoji":"📦","tokens_out":13955,"duration_ms":120301,"temperature":0.7,"pith_summary":"The paper asks how much damage is done by solving Pandora's box, the canonical costly-search problem, with slightly wrong beliefs about the boxes' value distributions. The main answer is a stability theorem: if every estimated distribution differs from the true one by at most $\\varepsilon$ in Kolmogorov distance — the largest vertical gap between the two cumulative distribution functions — then the optimal reserve-price algorithm computed from the wrong beliefs is at most $O(n\\varepsilon)$ worse in expected utility than the same algorithm run with perfect knowledge. Equivalently, small prior error per box translates into at most a constant loss per box, summed over boxes. This is relevant because in any real application the distributions on the boxes' labels are estimates, and the result says the classical policy degrades gracefully rather than collapsing.","feed_headline":"Slightly off priors lose at most O(nε) in Pandora's box","feed_subtitle":"A small Kolmogorov-distance error in every box's value distribution shrinks expected utility by at most a constant per box.","key_machinery":"The central object is the reserve price $\\sigma_i$, defined by $E[(X_i-\\sigma_i)^+]=c_i$, together with the expected-utility functional $W_\\sigma(D)$ of the algorithm that opens boxes in decreasing $\\sigma$ and stops when the running maximum exceeds the next reserve price. The load-bearing identity is, for an opened box $i$,\n$$W_\\$\\sigma$(x_1,\\ldots,x_{i-1},x,D_{i+1},\\ldots,D_n)=E\\left[\\max\\left\\{B(x),\\max_{j\\ge i+1}\\kappa_j\\right\\}\\right]-c_{\\le i},$$\nwhere $B(x)=\\max\\{x_1,\\ldots,x_{i-1},x\\}$ and $\\kappa_j=\\min\\{\\sigma_j,X_j\\}$. The identity is proved by shifting each future opening cost $c_j$ to an acceptance-time charge $[X_j-\\sigma_j]^+$, whose expectation equals $c_j$. It makes the per-coordinate utility function $g(x)$ increasing and 1-Lipschitz, and that 1-Lipschitz property is what converts a Kolmogorov-distance bound on CDFs into the $O(\\varepsilon)$ per-coordinate utility loss of Lemma 5.","core_discovery":"The paper proves two statements. Theorem 2: for any two distribution vectors within Kolmogorov distance $\\varepsilon$ coordinatewise, replacing the true distributions by the estimated ones changes the expected utility of the same reserve-price policy by at most $O(n\\varepsilon)$. Corollary 3: computing reserve prices from the wrong distributions and running the classical algorithm is at most $O(n\\varepsilon)$ worse than running the optimal algorithm with the true distributions. The proof decomposes the change coordinate by coordinate: Lemma 4 shows the utility viewed as a function of one revealed value is increasing and 1-Lipschitz, and Lemma 5 shows that replacing one coordinate's distribution by an $\\varepsilon$-close one changes the expectation by at most $O(\\varepsilon)$; summing over $n$ coordinates gives the theorem. The paper also frames itself as the first to study inaccurate priors for Pandora's box, following the analogous question for prophet inequalities.","pith_inferences":["A learning extension left implicit: if each D_i is replaced by an empirical distribution from m samples, standard concentration bounds put the empirical CDF within Kolmogorov distance O(1/√m) with high probability, so the plug-in policy should lose O(n/√m) expected utility; this is our inference, not a claim of the paper.","The additive analysis does not use cancellation across boxes; whether adversarial errors can force a loss of Ω(nε) or whether the true worst case is smaller is an open question the paper does not address.","The continuity assumption is used to guarantee exact reserve prices and a clean threshold-crossing argument; a discrete analogue with approximate reserve prices is a plausible extension, but nothing in the paper guarantees it."],"forward_implications":["Using reserve prices inferred from priors that are ε-close in Kolmogorov distance loses at most O(nε) in expected utility, so the classical policy is stable under small estimation error.","The per-coordinate proof makes the loss additive across boxes: the total shortfall is at most a constant per box, not exponential in n and not dependent on a margin condition.","The guarantee covers every continuous distribution on [0,1] and every nonnegative cost vector, with no regularity assumptions beyond continuity.","In the descending-price-search view of Pandora's box, substituting ε-accurate estimated distributions preserves near-optimality of the search rule."],"supporting_citations":[{"why":"Defines the classical optimal search solution and the reserve-price characterization used as Lemma 1.","marker":"[6]"},{"why":"Supplies the auction and descending-price interpretation of Pandora's box and an alternative proof of optimality for the policy being analyzed.","marker":"[5]"},{"why":"Introduces the inaccurate-priors model with Kolmogorov-distance error for prophet inequalities, the model this paper adapts to Pandora's box.","marker":"[3]"}],"fun_headline_variants":["Pandora's box: small prior errors cost O(nε) at most","Inaccurate priors? Pandora's box utility loss bounded by O(nε)","Small prior errors in Pandora's box: only O(nε) utility loss","Pandora's box: O(nε) loss from slightly off priors","Inaccurate priors in Pandora's box? Only O(nε) worse"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that when boxes are opened in reserve-price order, expected utility can be counted as the expected best value among all boxes minus the costs of opened boxes, with each opening cost shifted to a charge at acceptance time; if this accounting identity fails, the $O(n\\varepsilon)$ bound does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Pandora's box: small prior errors cost O(nε) at most","Inaccurate priors? Pandora's box utility loss bounded by O(nε)","Small prior errors in Pandora's box: only O(nε) utility loss","Pandora's box: O(nε) loss from slightly off priors","Inaccurate priors in Pandora's box? Only O(nε) worse"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000816,"raw_usage":{"total_tokens":3503,"prompt_tokens":799,"completion_tokens":2704,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":415,"completion_tokens_details":{"reasoning_tokens":2598}},"tokens_in":415,"tokens_out":2704,"duration_ms":19154,"temperature":1.0,"reasoning_tokens":2598,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T04:27:59.964181+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a sequence of instances with continuous distributions on $[0,1]$ and $d_K(D_i,D'_i)\\le\\varepsilon$, compute the exact loss $W_\\sigma(D)-W_{\\sigma'}(D)$, and watch $\\text{loss}/(n\\varepsilon)$ as $\\varepsilon\\to0$. If that ratio is unbounded over any sequence, the $O(n\\varepsilon)$ bound is false; the paper's proof predicts it stays bounded by a universal constant.","supporting_citations":[{"cited_title":"Weitzman","cited_arxiv_id":null,"evidence_quote":"Defines the classical optimal search solution and the reserve-price characterization used as Lemma 1."},{"cited_title":"Dütting and T","cited_arxiv_id":null,"evidence_quote":"Introduces the inaccurate-priors model with Kolmogorov-distance error for prophet inequalities, the model this paper adapts to Pandora's box."}],"review_version":1}