{"id":"d93d62fd-a607-46f2-a460-5070c6f84d22","arxiv_id":"2506.07162","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For delegated choice with inspection cost and free delegation, a maximal mechanism combining a single threshold-based inspected proposal with the best no-inspection option is a tight 3-approximation.","lead":"A boss can hire an expert to pick a solution, but the expert may lie and checking the answer costs money. This paper models that tradeoff and proves a simple strategy that, when delegation is free, guarantees at least a third of the best possible value even against a worst-case expert.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 3-approximation for costless delegation depends on the favorable tie-breaking convention: under pessimistic tie-breaking, the SPMI component can be sabotaged and the max-E fallback is insufficient, breaking the ratio. The Theorem 4.12 algebra error is real but secondary.","rationale":"The central claim (Theorem 4.8) rests on Lemma 4.6, whose lower bound for the SPMI is only established under the Section 3.2 convention that indifferent agents favor the principal. This is not a mere technicality: when all Y_i are zero, every proposal (including an ineligible one) is a best response, and a pessimistic agent can force the principal to pay inspection costs on rejected proposals. The example with cheap high-value type-A boxes and an expensive zero-value type-B box gives a feasible no-delegation policy with utility about 90 while the proposed maximal mechanism obtains only 1, a ratio far above 3. Thus the headline guarantee is contingent on the tie-breaking refinement. I agree with the reader's assessment; the costly-delegation algebra error in Theorem 4.12 is also real and should be fixed, but it does not affect Theorem 4.8. The reader's CONDITIONAL verdict is appropriate; our concern reinforces the need for the authors to justify or weaken the tie-breaking assumption and correct the 4.12 bound.","tokens_in":20998,"tokens_out":36850,"duration_ms":395097,"concrete_test":"Run the SPMI of Lemma 4.6 on the instance (1000 type-A: X=100 w.p. 0.01 else 0, c=0.1; one type-B: X=0, c=1000; all Y_i=0, threshold tau=50) with pessimistic tie-breaking: compute the principal's expected utility; if it is negative while the friendly utility is about 99.9 and the no-delegation inspection policy achieves about 90, then Theorem 4.8's guarantee fails under the standard worst-case refinement. Also re-derive Theorem 4.12's second case with c_Del = M - 2E[Mec_P] to confirm the ratio is 3, not 2-epsilon.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Lemma 4.6 and hence Theorem 4.8 rely on Section 3.2's convention that an indifferent agent favors the principal. In the SPMI of Lemma 4.6, if no proposal is eligible, the agent is indifferent between the null signal (utility 0, principal pays nothing) and proposing an ineligible alternative (utility 0, principal pays the inspection cost). The claimed 1/2 E[max_i(X_i-c_i)^+] bound is therefore a consequence of the convention, not of incentive compatibility. The convention is not innocuous: consider 1000 type-A boxes with X=100 w.p. 0.01 (else 0), c_A=0.1, plus one type-B box with X=0, c_B=1000, and all Y_i=0. With threshold tau=50, the SPMI's friendly expected utility is about 99.9(1-0.99^1000) ~ 99.9, but a pessimistic agent proposes the type-B box whenever it exists, giving utility about -1000. The maximal mechanism then uses the max-E fallback, value 1. A feasible no-delegation policy inspects type-A boxes until the first success, yielding about 100(1-0.99^1000) - 0.1*(1-0.99^1000)/0.01 ~ 90. Thus E[Opt] >= 90 and the mechanism's ratio is at least 90, not 3. The stated 3-approximation is contingent on the tie-breaking convention; if the convention is rejected, Theorem 4.8 is false. Separately, Theorem 4.12's second branch uses c_Del >= M - E[Mec_P] in place of the stated c_Del >= M - 2E[Mec_P]; recomputing gives a 3-approximation, not 2-epsilon.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Delegated Choice with Inspection Cost (DCIC), a principal–agent model in which the agent may misreport the utility of a proposed alternative and the principal can inspect alternatives at an exogenous cost, with an additional fixed delegation cost c_Del. It observes that DCIC generalizes Pandora's box with nonobligatory inspection (PNOI), implies NP-hardness, and shows that neither pure inspection nor a single-proposal mechanism with inspection (SPMI) alone can be constant-factor approximable. Its main positive result is a 3-approximation for costless delegation: a maximal mechanism that takes the better of (i) an SPMI with a single threshold (capturing half of E[max_i (X_i - c_i)^+]) and (ii) the no-inspection choice of the alternative with largest E[X_i]. The 3 bound is shown tight for this mechanism and the analysis extends to monotone combinatorial costs, with an improved 2-approximation for equal inspection costs. For the costly-delegation setting, Theorem 4.12 claims constant-factor approximations in two regimes of c_Del. The paper also gives several impossibility and tightness examples.","tokens_in":74,"tokens_out":17097,"duration_ms":198394,"significance":"If the main theorem holds, the paper makes a useful conceptual connection between delegated choice and nonobligatory-inspection Pandora's box, and the overinspection-based upper bound (Lemmas 4.4 and 4.5) is an elegant technique that could be reused. The proofs for the costless case are carefully derived, the mechanism is simple, and the tightness example for the proposed mechanism is instructive. However, the significance is substantially tempered by two issues: the 3-approximation depends on a favorable tie-breaking convention that the paper calls 'innocuous', and the costly-delegation theorem contains a mismatch between statement and proof plus an algebra error that turns the claimed 2 - epsilon into 2 + epsilon. These concerns must be fixed before the results can be relied upon.","major_comments":[{"comment":"The proof of Lemma 4.6 relies on the assumption that when no eligible solution exists, the agent sends the null signal because he is indifferent and behaves in favor of the principal. This assumption is not innocuous: if ties are broken adversarially, the agent can propose an ineligible alternative, the principal inspects it and pays its cost, and the claimed lower bound 1/2 E[max_i (X_i - c_i)^+] fails. For example, take 1000 alternatives with X_i = 100 w.p. 0.01 (else 0) and c_i = 0.1, plus one alternative with X = 0 and c = 1000, and all Y_i = 0. With threshold tau = 50, favorable tie-breaking gives SPMI utility about 99.9, while a pessimistic tie-breaking agent proposes the high-cost box whenever it exists, giving utility about -1000. The maximal mechanism then falls back to the no-inspection rule (utility 1), while a feasible inspection policy obtains about 90, so the approximation ratio is at least 90 rather than 3. Thus Theorem 4.8 is contingent on the tie-breaking convention; the authors should either adopt it as an explicit modeling assumption or modify the mechanism and analysis to be robust to pessimistic tie-breaking.","section":"3.2, Lemma 4.6"},{"comment":"The statement of Theorem 4.12 requires c_Del >= E[max_i (X_i - c_i)^+] - 2 E[Mec_P], but the proof (line 'Now consider the second case where c_Del >= E[max] - E[Mec_P]') uses the strictly stronger condition c_Del >= E[max] - E[Mec_P]. Since 2 E[Mec_P] >= E[Mec_P], the stated condition does not imply the proof's condition, so the theorem as stated is unproved. The condition in the theorem should be corrected, or the proof should be modified to work under the weaker stated assumption.","section":"Theorem 4.12"},{"comment":"Even under the proof's corrected condition, the displayed chain gives E[Opt] <= (1 + 1/(1 - epsilon)) E[Mec] = (2 - epsilon)/(1 - epsilon) E[Mec], which is greater than 2 for every epsilon in (0,1). The conclusion '2 - epsilon-approximation for any epsilon' is therefore false; the argument yields a 2 + epsilon-approximation. This quantitative claim appears in the abstract and in Section 2.4 and should be corrected accordingly.","section":"Theorem 4.12, second branch"}],"minor_comments":[{"comment":"The example gives a ratio of (3 - 3 epsilon + epsilon^2)/1, which is below 3 for all epsilon in (0,1); this does not support the statement that the mechanism 'cannot have approximation factor better than 3+epsilon'. The intended tightness claim should be rephrased, e.g., as a family of instances whose approximation ratio approaches 3.","section":"Theorem 4.11"},{"comment":"The 'rich class of instances' is only the union of the two closed-form regimes for c_Del; the paper should state explicitly that intermediate delegation costs are left open.","section":"Section 2.4 and Theorem 4.12"},{"comment":"In the proof, the sentence 'If for any signal sigma, inspection policy Sig(sigma) selects a solution i without inspecting any solution...' appears to require that the agent's best response indeed sends such a signal; the argument would benefit from making the worst-case agent explicit.","section":"Proposition 4.10"}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious contribution to mechanism design with delegation and costly verification, but the main costless-delegation theorem is explicitly conditional on a tie-breaking convention that the authors dismiss as 'minor'. This is a substantive modeling assumption in a worst-case framework and should be prominently stated or removed. The costly-delegation theorem also contains a condition gap and a quantitative error that changes the stated bound from 2 - epsilon to 2 + epsilon. Both issues are fixable within the manuscript's scope, but they need attention before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read. The DCIC model is a legitimate extension of both delegated choice and PNOI, and the overinspection decomposition (Lemmas 4.4-4.5) is a genuine new technique. NP-hardness via PNOI is clean. The 3-approximation for costless delegation is proved carefully, and Theorem 4.11 shows tightness for that mechanism. The combinatorial-cost extension and identical-cost 2-approximation are nice bonuses. I checked the key steps; Lemmas 4.4-4.7 hold up under the paper's stated assumptions.\n\nThe soft spot is the tie-breaking convention in Section 3.2. The paper calls it 'innocuous' and leans on reputation, but it is doing real work in Lemma 4.6. When no eligible solution exists, the agent is indifferent between the null signal and proposing an ineligible alternative; the proof assumes he sends null. An agent who breaks ties adversarially (e.g., all Y_i = 0) can force an expensive inspection and destroy the SPMI's guarantee. The stress-test's example makes this concrete: with 1000 boxes that pay 100 w.p. 0.01 (cost 0.1) and one box with cost 1000, favorable tie-breaking gives the claimed SPMI utility, while pessimistic tie-breaking leaves the mechanism with the max-expected-value fallback, and the ratio to the optimal inspection policy becomes unbounded. This doesn't contradict the theorem as stated — the model includes the convention — but it means the guarantee is contingent on that convention, and the paper's 'innocuous' characterization is misleading. The authors should either prove a robust version or openly frame the result as conditional on favorable tie-breaking.\n\nThe second issue is in Theorem 4.12. The theorem's second branch states a (2−ε) approximation when c_Del ≥ M − 2E[Mec_P], but the proof uses the stronger condition c_Del ≥ M − E[Mec_P]. Recomputing with the stated assumption gives roughly a 3-approximation, so the proof doesn't establish the claim. This is secondary to the main costless result, but it needs fixing.\n\nWho is this for? People working on delegated choice, Pandora's box, and optimal stopping with verification. It deserves a serious referee. The model is new, the technique is non-obvious, and the paper is honest about what it doesn't get. I'd recommend conditional acceptance: patch Theorem 4.12 and address the tie-breaking head-on, either by strengthening the mechanism or by clearly labeling the result as being under a specific tie-breaking rule.","headline":"Solid new model and a clever 3-approx for costless delegation, but the guarantee rests on a tie-breaking convention that the paper understates, and Theorem 4.12 has a real proof gap.","tokens_in":21932,"tokens_out":7404,"would_cite":true,"duration_ms":70021,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","91B03"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that when delegation is free, the better of an inspected single proposal and the highest expected-value alternative approximates the optimal delegated-choice mechanism within a factor of 3, and that this factor is tight…","keywords":["delegated choice","inspection cost","Pandora's box with nonobligatory inspection","approximation mechanism","principal-agent problem","NP-hardness","strategic misreporting","single-proposal mechanism"],"falsifier":"Drop the assumption that an indifferent agent sends the principal-favorable signal. Take 10 alternatives with $X_i=1$ with probability $0.01$ and $0$ otherwise, and inspection cost $0$, plus a decoy alternative with $X=0$ and inspection cost $0.2$, where the agent's utility makes him propose the decoy whenever no alternative clears the threshold. The Theorem 4.8 mechanism then earns the maximum of $0.01$ and a negative single-proposal term, i.e., $0.01$, whereas the PNOI policy that inspects the 10 cheap alternatives and otherwise selects an uninspected one earns about $0.1046$; the ratio exceeds 10, so the claimed 3-approximation guarantee does not survive adversarial tie-breaking.","tokens_in":20799,"feed_emoji":"🔍","tokens_out":16647,"duration_ms":155582,"temperature":0.7,"pith_summary":"Delegated choice with inspection cost (DCIC) is a principal-agent problem in which the agent may lie about the value of the alternative he proposes, and the principal can verify by paying an inspection cost. The paper's main result is that, when delegation itself is free, a simple maximal mechanism—run the better of a single-proposal mechanism that inspects the proposed alternative and the no-inspection rule that picks the alternative with the largest expected value—approximates the optimal mechanism within a factor of 3. The factor is tight for this mechanism. The same ratio holds when inspection costs are given by any monotone set function, and it improves to 2 when all inspection costs are equal. These are the first constant-factor guarantees for this problem, and they show that a single inspection is enough to make delegation substantially robust to strategic misreporting.","feed_headline":"One inspected proposal plus the best guess is a 3-approximation","feed_subtitle":"Mixing a verified single proposal with the top expected-value option keeps the principal within a factor of 3 of the optimal mechanism.","key_machinery":"The load-bearing device is the notion of a solution accepted without overinspection: alternative $i$ is selected without inspecting any alternative whose inspection cost is at least $c_i$. The paper proves that, for the worst-case agent under favorable tie-breaking, the event that $i$ is accepted without overinspection is independent of $X_i$, because the agent's signal depends on his own utility ranking rather than on the principal's utility. This independence bounds the expected utility from such selections by $\\max_i \\mathbb{E}[X_i]$, producing the upper bound on the optimal mechanism. On the lower side, the key working identity is Lemma 4.6: a shifted single-proposal mechanism with inspection recovers $\\tfrac{1}{2}\\mathbb{E}[\\max_i (X_i-c_i)^+]$ by accepting a proposed alternative exactly when its net value $X_i-c_i$ clears a threshold. The maximal mechanism that chooses the better of these two components is the 3-approximation.","core_discovery":"The paper shows that the optimal mechanism's value is governed by two quantities: the largest ex-ante expected alternative value, $\\max_i \\mathbb{E}[X_i]$, and the expected surplus of the best inspected alternative, $\\mathbb{E}[\\max_i (X_i-c_i)^+]$. For any mechanism, the principal's utility is at most the sum of these two quantities. On the constructive side, the better of two simple mechanisms—a single-proposal mechanism that inspects the proposed alternative and accepts it only when $X_i-c_i$ passes a threshold, and the no-inspection choice of the maximum expected value—attains the maximum of $\\max_i \\mathbb{E}[X_i]$ and $\\tfrac{1}{2}\\mathbb{E}[\\max_i (X_i-c_i)^+]$. Comparing the two bounds yields the 3-approximation, and a matching lower-bound instance shows the factor is tight for this mechanism. The paper thus establishes that combining one round of inspection with a fallback on ex-ante expected values is sufficient to counteract strategic misreporting up to a constant factor.","pith_inferences":["The half-factor in Lemma 4.6 mirrors the classical threshold-mechanism half-guarantee for delegated search and prophet inequalities, which suggests that any improvement beyond 3 would need a richer signal structure than a single inspected proposal rather than a better threshold.","The overinspection-independence argument looks portable: any principal-agent search problem where the agent's signal is the only source of information and the principal can verify at a cost should admit a similar bound in terms of the best ex-ante value plus the best expected net surplus.","A testable extension is to randomize between the single-proposal mechanism with inspection and the PNOI policy when the delegation cost is moderate; the paper notes that randomization changes the agent's best-response and leaves this open, but the two-regime theorem suggests the failure region is exactly where neither component alone dominates.","If the favorable tie-breaking assumption is dropped, the SPMI's null-signal guarantee fails, so robustness to adversarial tie-breaking is the natural next stress test for any delegation mechanism."],"forward_implications":["With costless delegation, one inspection suffices to make delegation robust to misreporting up to a constant factor, so the principal need not pre-commit to blind trust or exhaustive inspection.","The same 3-approximation holds when inspection costs are given by an arbitrary monotone set function, extending the result to settings where inspecting a group costs more or less than the sum of its parts.","If every alternative has the same inspection cost, the approximation improves to 2.","When delegation itself is costly, a constant-factor approximation survives in two regimes—$c_{\\mathrm{Del}} < \\tfrac12\\mathbb{E}[\\max_i (X_i-c_i)^+]$ or $c_{\\mathrm{Del}} \\ge \\mathbb{E}[\\max_i (X_i-c_i)^+] - 2\\mathbb{E}[\\mathrm{Mec}_P]$—leaving the intermediate regime open.","Since the problem generalizes Pandora's box with nonobligatory inspection, a known NP-hard problem, no exact polynomial-time optimal mechanism is expected unless P = NP."],"supporting_citations":[{"why":"Defines the delegated choice problem and supplies the threshold single-proposal mechanism whose half-of-first-best guarantee Lemma 4.6 reuses after shifting values.","marker":"Kleinberg and Kleinberg (2018)"},{"why":"Defines Pandora's box with nonobligatory inspection, which DCIC generalizes.","marker":"Doval (2018)"},{"why":"Proves PNOI is NP-hard and gives a PTAS; the hardness transfers to DCIC by a delegation-cost reduction and the PTAS is used in the costly-delegation theorem.","marker":"Fu et al. (2023)"},{"why":"Provides the committing-policy and cap-based upper-bound approach for PNOI that the paper contrasts with the uninspected-information phenomenon in DCIC.","marker":"Beyhaghi and Kleinberg (2019)"},{"why":"Introduces Pandora's problem with combinatorial monotone set-function costs, the model to which the paper's 3-approximation extends.","marker":"Berger et al. (2023)"},{"why":"Supplies an alternative PTAS for PNOI that supports the costly-delegation constant-factor mechanism.","marker":"Beyhaghi and Cai (2023)"},{"why":"Defines Pandora's box and the cap identity $c_i = \\mathbb{E}[(X_i-\\sigma_i)^+]$ that underlies the paper's surplus upper bounds.","marker":"Weitzman (1978)"},{"why":"Formulates the delegated project choice model that DCIC builds on.","marker":"Armstrong and Vickers (2010)"}],"fun_headline_variants":["Inspect one, guess the rest: 3-approx for delegation","One inspection plus expected best: 3-approximation","Strategic agent? Inspect one option and settle for 3x optimal","Costly inspection counteracts lying: 3-approximation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument relies on the agent sending the principal-favorable signal whenever he is indifferent, especially the null signal when no proposed alternative clears the threshold; if indifference is resolved adversarially, the wasted inspection can break the half-surplus guarantee and the ratio 3.","fun_headline_variants_meta":{"raw":{"variants":["Inspect one, guess the rest: 3-approx for delegation","One inspection plus expected best: 3-approximation","Strategic agent? Inspect one option and settle for 3x optimal","Costly inspection counteracts lying: 3-approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001227,"raw_usage":{"total_tokens":5103,"prompt_tokens":1065,"completion_tokens":4038,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":681,"completion_tokens_details":{"reasoning_tokens":3964}},"tokens_in":681,"tokens_out":4038,"duration_ms":28168,"temperature":1.0,"reasoning_tokens":3964,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T05:44:42.993476+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Drop the assumption that an indifferent agent sends the principal-favorable signal. Take 10 alternatives with $X_i=1$ with probability $0.01$ and $0$ otherwise, and inspection cost $0$, plus a decoy alternative with $X=0$ and inspection cost $0.2$, where the agent's utility makes him propose the decoy whenever no alternative clears the threshold. The Theorem 4.8 mechanism then earns the maximum of $0.01$ and a negative single-proposal term, i.e., $0.01$, whereas the PNOI policy that inspects the 10 cheap alternatives and otherwise selects an uninspected one earns about $0.1046$; the ratio exceeds 10, so the claimed 3-approximation guarantee does not survive adversarial tie-breaking.","supporting_citations":[{"cited_title":"Delegated search approximates efficient search","cited_arxiv_id":null,"evidence_quote":"Defines the delegated choice problem and supplies the threshold single-proposal mechanism whose half-of-first-best guarantee Lemma 4.6 reuses after shifting values."},{"cited_title":"Whether or not to open pandora's box","cited_arxiv_id":null,"evidence_quote":"Defines Pandora's box with nonobligatory inspection, which DCIC generalizes."},{"cited_title":"Pandora's problem with nonobligatory inspection","cited_arxiv_id":null,"evidence_quote":"Provides the committing-policy and cap-based upper-bound approach for PNOI that the paper contrasts with the uninspected-information phenomenon in DCIC."},{"cited_title":"Pandora's problem with combinatorial cost","cited_arxiv_id":null,"evidence_quote":"Introduces Pandora's problem with combinatorial monotone set-function costs, the model to which the paper's 3-approximation extends."},{"cited_title":"Pandora’s problem with nonobligatory inspection: Optimal structure and a ptas","cited_arxiv_id":null,"evidence_quote":"Supplies an alternative PTAS for PNOI that supports the costly-delegation constant-factor mechanism."},{"cited_title":"Optimal search for the best alternative, volume 78","cited_arxiv_id":null,"evidence_quote":"Defines Pandora's box and the cap identity $c_i = \\mathbb{E}[(X_i-\\sigma_i)^+]$ that underlies the paper's surplus upper bounds."},{"cited_title":"A model of delegated project choice","cited_arxiv_id":null,"evidence_quote":"Formulates the delegated project choice model that DCIC builds on."}],"review_version":1}