{"id":"997b8602-1388-4881-9b03-d3b0c841c0fb","arxiv_id":"2506.03102","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Optimal AI delegation reduces to choosing which human categories the machine should retain, and this subset-selection problem is NP-hard in general yet polynomial in separable settings.","lead":"The paper formalizes how to design an AI agent that a human will hand tasks off to, when the human can only tell broad categories of situations apart. It shows the best such delegate can beat a standalone AI by an arbitrarily large margin, and that finding the optimal delegate is NP-hard in general but tractable in several structured cases.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4's proof has an algebraic error: the ratio (D^2)+/(D^2)- is (k-1)/(k+1), not its cube, so the contradiction does not follow; Theorem 4's proof is incomplete.","rationale":"The paper's central theoretical contribution is the subset characterization and the tractability results. Theorem 4 is a main positive result, and its proof relies on Lemma 4 to justify reducing weighted probabilities to an expanded uniform problem. The proof of Lemma 4 contains a concrete algebraic error: the variance-decomposition terms (D^2)+ and (D^2)- are miscomputed by polynomial factors, so the claimed ratio is wrong and the contradiction disappears. This makes the proof incomplete, though the lemma itself may be true. The reader's stated weakest assumption was the rationality of the human delegation decision, but their rationale separately flagged the Lemma 4 algebra as needing cleanup. I agree the rationality assumption is a limitation, but the proof error is more directly load-bearing for the correctness of a headline result: if Lemma 4 is false, the polynomial algorithm for separable settings could fail. This does not warrant rejecting the paper, because the theorem might still be correct and the proof repairable; conditional acceptance with a request to fix or verify Lemma 4 is appropriate, which matches the reader's verdict. I therefore leave the verdict unchanged but with a shifted emphasis toward the proof gap.","tokens_in":37587,"tokens_out":25272,"duration_ms":235721,"concrete_test":"Re-derive the algebra in Lemma 4 with Result 1, or run a brute-force search over all R ⊆ [T] for T ≤ 10 with random integer values and multiplicities to test whether the 'all copies or none' property holds. If a counterexample exists, Theorem 4's algorithm is unsound; if the property holds, the lemma can be repaired but the existing proof is still incorrect.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The polynomial-time algorithm for separable settings (Theorem 4) depends on Lemma 4, which asserts that an optimal subset of the expanded multiset S includes all copies of a value if it includes any. The proof of Lemma 4 is algebraically wrong. Using Result 1 (O'Neill) correctly, for R+ = R* ∪ {s_r'} and R- = R* \\ {s_r} (with s_r = s_r' = u), one obtains (D^2)+ = |R+|σ^2(R+) - |R*|σ^2(R*) = |R*|/(|R*|+1)(s_r' - μ(R*))^2 = |R*|(|R*|+1)(μ(R+)-μ(R*))^2, and (D^2)- = |R*|σ^2(R*) - |R-|σ^2(R-) = (|R*|-1)/|R*|(s_r - μ(R-))^2 = |R*|(|R*|-1)(μ(R*)-μ(R-))^2. The paper's expressions for (D^2)+ and (D^2)- omit factors of (|R*|+1) and |R*| respectively. The correct ratio is (D^2)+/(D^2)- = (k-1)/(k+1) < 1, which does not contradict the necessary inequality (D^2)- ≤ (D^2)+. Thus the proof does not establish Lemma 4. If Lemma 4 fails, the reduction of weighted probabilities to the uniform expanded problem is invalid, and the polynomial-time algorithm in Theorem 4 may return a suboptimal delegate. The theorem may still be true, but the current proof is incomplete.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the design of an algorithmic delegate when a human decides whether to hand off a decision to the machine, where both agents observe only subsets of binary features and therefore operate under human and machine categories. The main results are a reduction of optimal delegate design to a discrete subset-selection problem (Propositions 1 and 2), a complete analysis of the two-feature case, a polynomial-time algorithm for separable delegation settings (Theorem 4), a polynomial-time algorithm when one side observes a constant number of features (Theorem 5), and an NP-hardness result for the general problem (Theorem 7). The paper also reports computational experiments on an iterative design process that converges to locally optimal delegates.","tokens_in":37914,"tokens_out":25024,"duration_ms":250801,"significance":"If the technical claims hold, this is a valuable contribution to the human-AI collaboration literature. The clean reformulation of optimal delegation as a variance-minimizing subset problem is elegant, and the contrast between the oblivious machine and the optimal delegate (Fact 1) gives a sharp justification for designing machines that account for when they will actually be adopted. The paper is self-contained and analytic, with no fitted parameters or empirical constants in the main results. The two-feature phase diagram is a nice concrete illustration of how even the simplest setting yields non-convex and disconnected optimal-design regions. The authors are also appropriately careful about the limits of the rational-delegation assumption, noting in Section 6.2 that behavioral biases are not covered. The main concern is a proof error in a lemma that supports Theorem 4; although the lemma appears to be repairable, the proof as written is not valid.","major_comments":[{"comment":"The proof of Lemma 4 contains an algebraic error in the application of O'Neill's variance decomposition result. With R+ = R* ∪ {s_r'} and R- = R* \\ {s_r}, the correct identities are (D^2)+ = |R*|(|R*|+1)(μ(R+)-μ(R*))^2 and (D^2)- = |R*|(|R*|-1)(μ(R*)-μ(R-))^2. The paper instead defines (D^2)+ = |R*|/(|R*|+1)(μ(R+)-μ(R*))^2 and (D^2)- = (|R*|-1)/|R*|(μ(R*)-μ(R-))^2, omitting factors of (|R*|+1) and |R*|, respectively. With the corrected formulas the ratio (D^2)+/(D^2)- is (|R*|-1)/(|R*|+1), which is less than 1 and still contradicts the necessary inequality (D^2)- ≤ (D^2)+, so the lemma is likely salvageable. Nevertheless, the proof as written is invalid, and Theorem 4 depends on this lemma. The authors should rewrite the proof and re-verify the reduction from the weighted problem to the expanded uniform multiset.","section":"Appendix E.1, Lemma 4"}],"minor_comments":[{"comment":"In the proof of Lemma 4, the definition R- = R* \\ {s_r'} is a typo: since s_r' is assumed not to be in R*, removing it leaves R* unchanged. The intended set is R- = R* \\ {s_r}.","section":"Appendix E.1, Lemma 4"},{"comment":"There is a typo in the overview: 'Thich reveals' should be 'This reveals'.","section":"Section 1.1"},{"comment":"The problem name 'MaxRegularCliqe' is misspelled; it should be 'MaxRegularClique'. This appears both in the proof of Theorem 7 and in the problem definition.","section":"Appendix E.4"},{"comment":"The claim that the maximally adopted machine is worse than the oblivious machine alone 'for most settings' is established only for the two-feature family in Appendix A.1; the scope of this claim should be stated more precisely in the main text.","section":"Section 3.2"},{"comment":"The use of arrangements of ellipsoids and the bound O(h^m) on the number of regions would benefit from a brief explanation of why Chazelle et al. applies to this specific family of ellipsoids, since the reader must otherwise take the geometric claim largely on faith.","section":"Theorem 5 proof"}],"recommendation":"major_revision","confidential_remarks":"The algebraic error in Lemma 4 is localized and appears to be repairable: the corrected formulas still yield a contradiction. I do not think this warrants rejection, but because Theorem 4 is a central positive result, the revision should contain a corrected proof rather than a remark acknowledging the issue. The rest of the paper's proofs and experiments seem consistent with the stated claims."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the core model—designing an algorithmic delegate when humans delegate by category—is genuinely new, and the central characterization in Propositions 1 and 2 is clean and correct as far as I can tell: the optimal delegate is f^R_M for some retained subset R of human categories. Second, the proof of Theorem 4 has a real gap, not a typo. Lemma 4's algebra is wrong: using O'Neill's result directly, (D^2)+/(D^2)- = (k-1)/(k+1), not its cube, so the claimed contradiction does not follow. The reduction from weighted to uniform probabilities is therefore unproven, and with it the polynomial-time claim for separable settings.\n\nWhat the paper does well: the subset characterization reframes delegation design in a useful way; the two-feature landscape in Section 3 is instructive, with non-convex adoption regions that make the problem's combinatorial nature concrete; and the NP-hardness proof (Theorem 7) is complex but I did not find a similar break. Fact 1's unbounded gap between oblivious and optimal delegates is demonstrated by a simple family and is correct. The related-work placement is accurate—Bansal et al. optimize for usage but do not model delegation, Lai et al. and Vafa et al. study delegation but not optimal design.\n\nSoft spots, in proportion: the Lemma 4 issue is load-bearing for Theorem 4, since the reduction to the uniform expanded problem is the only route given. The theorem may still be true, but the current proof does not establish it. The experiments are described but code and data are not released, so the simulation claims are hard to reproduce. The rational-delegation assumption is explicitly acknowledged and is reasonable for a first formal model. I did not see issues with Propositions 1 and 2 or the two-feature calculations.\n\nBottom line: this paper deserves a serious referee. It advances the human-AI delegation literature, and the subset characterization plus the hardness results are worth keeping even if Theorem 4 needs repair. I would send it to peer review with a request for a correct proof of Lemma 4 or a different route to the separable-case result, plus release of the experiment code and data.","headline":"A genuinely new and mostly clean model of optimal delegation under human categorization, but the proof of the main polynomial-time result has a load-bearing algebraic error in Lemma 4 that needs fixing before the theorem can be trusted.","tokens_in":38455,"tokens_out":3699,"would_cite":true,"duration_ms":36972,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","90C27"],"pacs":[],"model":"deepseek-v4-flash","headline":"The optimal algorithmic delegate is not the most accurate standalone model; it is the one tuned to the categories of tasks that humans actually hand off, and finding it is NP-hard in general.","keywords":["human-AI delegation","algorithmic delegates","categorization","team performance","variance assignment","NP-hardness","human-AI handoff","delegation design"],"falsifier":"Use the two-feature family of Section 3.1 with ground-truth actions $(0,1,0,N)$ on the four states and equal probabilities. Compare the team loss of the optimal delegate that retains only the second human category with the team loss of the oblivious machine that averages within each machine category: the paper's Fact 1 predicts a gap growing like $N^2$, with the optimal delegate's loss constant in $N$. If the gap fails to grow or a standalone-optimized machine matches the tailored machine's team performance, the central separation claim would be refuted.","tokens_in":37375,"feed_emoji":"🤖","tokens_out":8993,"duration_ms":87286,"temperature":0.7,"pith_summary":"This paper argues that an AI agent that takes over a task from a human should not be designed to be the most accurate on its own; it should be designed to be the best teammate, anticipating that the human will delegate only in situations she can recognize. The authors model a human who sees coarse categories of task instances and hands off exactly when the machine's expected squared loss is lower than her own, and they prove that optimizing the machine for this handoff can yield arbitrarily large gains over optimizing it in isolation. The central discovery is that the optimal delegate is characterized by a subset of human categories to “retain”: the machine is tuned to do well only there, and the human adopts it exactly there. Choosing this subset is NP-hard in general but has polynomial algorithms when the optimal action and distribution separate across human and machine features, or when one side sees few features. A designer who iteratively re-trains on where the machine is adopted generally reaches only a local optimum, though experiments suggest it often performs near optimally.","feed_headline":"Optimal delegate can be arbitrarily better than standalone AI","feed_subtitle":"A delegate tuned for the categories where users hand off tasks can beat a generally accurate one.","key_machinery":"The central object is the retained set $R$ of human categories together with the induced machine policy $f^R_M(K) = \\mathbb{E}[f^* \\mid X(R) \\cap K]$, the conditional mean of the ground-truth action over the states that lie both in retained human categories and in machine category $K$. Proposition 1 shows that optimal delegation reduces to choosing $R$; Proposition 2 rewrites the team loss as the sum of the conditional variance of $f^*$ over each yielded human category plus the conditional variance over the retained states in each machine category. This variance decomposition is what makes the problem combinatorial: the designer is really selecting which categories' variance the machine will absorb. It is also the object through which the tractability results are obtained and through which the NP-hardness reduction, via a variance-assignment variant of the densest-subgraph problem, is proved.","core_discovery":"The paper's central claim is that the right design target for an algorithmic delegate is not standalone performance but team performance under delegation, and that this target has a clean but combinatorially hard form. In the model, a human category is a set of states with identical human-observable features; a machine category is a set of states with identical machine-observable features. Given the human's optimal action $f^*_H$, which is the mean of the ground-truth action $f^*$ within each human category, the human delegates in category $C$ exactly when the machine's squared loss in $C$ is smaller. The optimal delegate is any machine function minimizing the resulting team loss, and the paper proves in Propositions 1 and 2 that it can be found by choosing a subset $R$ of human categories to retain and setting the machine's action in each machine category to the mean of $f^*$ over the retained states in that category. The team loss decomposes into within-category variances: the human absorbs variance in the unretained categories, and the machine absorbs variance over the retained states in each machine category. The authors also show that the oblivious machine, which minimizes standalone loss, can be arbitrarily worse than this optimal delegate, that a delegate designed to maximize adoption can be arbitrarily worse than the optimal delegate, and that computing the optimal retained set is NP-hard in general, with efficient algorithms for separable settings and for settings where one side has a constant number of features.","pith_inferences":["The variance decomposition suggests a practical screening rule: leave to the human any category with small within-category variance, and keep for the machine categories that become low-variance once a few high-variance human categories are excluded.","If humans delegate noisily, say only when the machine's expected advantage exceeds a threshold, the retained-set characterization becomes approximate, so the exact hardness and tractability boundaries would need re-examination.","Since the hardness result holds even for a single isolated decision with no communication, longer-horizon agentic systems are unlikely to admit optimal delegation design without further structural assumptions.","A designer with approximately linear $f^*$ and near-independent features could use Theorem 4 as a screening tool to compute the optimal retained set exactly, and fall back on iterative retraining when nonlinearities dominate."],"forward_implications":["Team performance, not standalone accuracy, is the right objective when an AI is used as a delegate: the paper's Fact 1 shows the oblivious machine can be arbitrarily worse than the optimal delegate.","Designing an optimal delegate reduces to selecting a subset of human categories to retain; the machine should average the optimal action only over states in those categories within each machine category (Propositions 1 and 2).","For separable delegation settings, where the optimal action is additive in human and machine features and the distribution is independent with polynomial-precision probabilities, an optimal delegate can be found in polynomial time (Theorem 4).","If the human or the machine observes only a constant number of features beyond the shared ones, an optimal delegate can again be found in polynomial time (Theorem 5).","In general the problem is NP-hard (Theorem 7), and a designer who re-trains the machine on the categories where it is adopted converges to a local optimum that experiments show is often near-optimal (Section 5)."],"supporting_citations":[{"why":"Establishes the premise that the most accurate AI is not necessarily the best teammate, which motivates optimizing for the categories where the AI is actually used.","marker":"[Bansal et al., 2021]"},{"why":"Supplies the human generalization function that formalizes why humans treat indistinguishable instances as the same category.","marker":"[Vafa et al., 2024]"},{"why":"Provides the model of indistinguishable inputs that the paper uses for machine categories under limited information.","marker":"[Alur et al., 2024]"},{"why":"Provides the variance decomposition identity used in the proofs of the contiguous-subset lemma and the separable-case algorithm.","marker":"[O'Neill, 2014]"},{"why":"Gives the arrangement algorithm used to find optimal delegates when the human or machine observes a constant number of features.","marker":"[Chazelle et al., 1991]"},{"why":"Shows that finding a maximum clique in regular graphs is NP-hard, which is the starting point of the hardness reduction.","marker":"[Brandes et al., 2016]"},{"why":"Introduces the negative-weight densest subgraph problem that the hardness reduction builds on.","marker":"[Tsourakakis et al., 2019]"},{"why":"Suggests the contiguous-subset principle used to solve the minimum-variance subset problem in the separable case.","marker":"[YXD, 2013]"}],"fun_headline_variants":["Optimal delegate for human-AI handoff beats standalone AI by any margin","Tune AI for handoff, not solo: arbitrarily better team performance","Optimal delegate for handoff is NP-hard, but can beat solo AI","Design AI for delegation, not standalone: arbitrarily better","Handoff-aware AI can be arbitrarily better than solo AI"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the human decides to delegate by comparing exact expected squared losses and hands off exactly when the machine's loss in her category is lower; if humans misestimate machine quality, prefer to stay in control, or are biased against algorithms, the characterization of the optimal delegate does not carry over.","fun_headline_variants_meta":{"raw":{"variants":["Optimal delegate for human-AI handoff beats standalone AI by any margin","Tune AI for handoff, not solo: arbitrarily better team performance","Optimal delegate for handoff is NP-hard, but can beat solo AI","Design AI for delegation, not standalone: arbitrarily better","Handoff-aware AI can be arbitrarily better than solo AI"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000814,"raw_usage":{"total_tokens":3650,"prompt_tokens":1111,"completion_tokens":2539,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":727,"completion_tokens_details":{"reasoning_tokens":2448}},"tokens_in":727,"tokens_out":2539,"duration_ms":16929,"temperature":1.0,"reasoning_tokens":2448,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:08:55.445318+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Use the two-feature family of Section 3.1 with ground-truth actions $(0,1,0,N)$ on the four states and equal probabilities. Compare the team loss of the optimal delegate that retains only the second human category with the team loss of the oblivious machine that averages within each machine category: the paper's Fact 1 predicts a gap growing like $N^2$, with the optimal delegate's loss constant in $N$. If the gap fails to grow or a standalone-optimized machine matches the tailored machine's team performance, the central separation claim would be refuted.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the variance decomposition identity used in the proofs of the contiguous-subset lemma and the separable-case algorithm."}],"review_version":1}