AI 智能体何时应该提问？人类注意力有限条件下的澄清请求

# When Should AI Agents Ask?Clarification Requests Under Limited Human Attention
Source: [https://arxiv.org/html/2610.41129](https://arxiv.org/html/2610.41129)
Shengjie LiuZhengchao Wang

###### Abstract

AI agents increasingly carry out delegated tasks in parallel, with one person overseeing several of them at once\. In practice, an agent often lacks information its task requires, such as an unstated preference, constraint, or specification\. It can ask the human to clarify, or it can search for the information itself, for example in past records, which takes time and effort and may fail\. In this paper, we study how to coordinate these decisions across several agents that share one human with limited attention\. We build a stylized model in which each agent can search, ask, or continue the parts of its task that do not depend on the missing information, and we formulate the problem as a dynamic program\. We first show that whether an agent should ask depends on more than its own uncertainty: an agent with other work to do can be better off asking earlier, and which question the human should answer first depends on all waiting questions, so no ranking computed agent by agent is optimal\. We then propose the Pairwise Coordination Policy \(PCP\), which uses exact one\- and two\-task problems to estimate how pairs of tasks delay each other when they share the human\. Theoretically, PCP is exactly optimal when at most two requirements remain unresolved and costs at most twice the optimum when every unresolved requirement must be resolved by the human\. We evaluate PCP on 864 synthetic cases and in a case study with LLM agents\. On the synthetic benchmark, PCP’s mean gap to optimal cost is 0\.07%, and it reduces cost by an average of 18–31% relative to three standard rules for when to ask\. In the LLM case study, agents completed every task correctly, and PCP achieved the lowest mean cost in all tested settings\.

Keywords:AI agents, human–AI collaboration, clarification requests, shared attention, approximate dynamic programming\.

## 1Introduction

Organizations are increasingly delegating multistep work to AI agents\. In McKinsey’s 2026 survey, 40% of respondents from organizations reported scaling agents in at least one business function, up from 27% in the previous year\([McKinsey, 2026](https://arxiv.org/html/2610.41129#bib.bib1)\)\. Delegation is also changing how individuals organize their work\. Usage evidence from Codex shows users assigning tasks to several agents running concurrently, tracking their progress in separate threads, and stepping in when clarification, review, or correction is needed\([Johnston et al\., 2026](https://arxiv.org/html/2610.41129#bib.bib2)\)\. A single person may thus oversee several streams of agentic work at once and serve as the shared source of human input for all of them\.

This arrangement raises an operational question: when should an agent continue working autonomously, and when should it seek human input? In practice, this choice already depends on how much human capacity is available\. OpenTable’s customer\-service agents, for example, draw on knowledge resources and follow escalation rules whose thresholds can be adjusted when staffing is tight\([Salesforce, 2025](https://arxiv.org/html/2610.41129#bib.bib3)\)\. Similarly, an internal study at Anthropic describes employees managing competing requests from agents and developing tools to triage them\([Wilmers et al\., 2026](https://arxiv.org/html/2610.41129#bib.bib4)\)\. These examples motivate studying how agents’ autonomous effort and their requests for human intervention should be coordinated across tasks\.

This question becomes concrete when an agent lacks information it needs to complete a delegated task\. Instructions may leave preferences, constraints, or other details unstated\. Some gaps require the person who delegated the task to clarify what is needed, and others can be filled from material already available to the agent\. Consider a procurement manager whose agents each handle a different purchase\. A missing specification may be recoverable from records of previous orders, or it may require the manager’s clarification\. A developer coordinating several coding agents may face questions about intended behavior whose answers are already in the tests or issue history\. Likewise, someone who has delegated travel research, a purchase comparison, and event planning may be asked about preferences recorded in their emails, calendar, or notes\. Such a gap need not bring the task to a halt\. The agent may still be able to organize records, write code unaffected by the open question, or compare general alternatives while the missing information remains unresolved\.

Figure[1](https://arxiv.org/html/2610.41129#S1.F1)shows a simple instance in Codex\([Johnston et al\., 2026](https://arxiv.org/html/2610.41129#bib.bib2)\)\. Two coding agents working for the same person need input at the same time\. One is building a daily sales report and asks which time zone defines a business day\. The other is implementing a checkout and asks whether a coupon and a loyalty discount can be combined\. Both agents have paused, and their questions wait for the same person\.

How an agent should handle such a gap is not obvious\. Looking for the answer takes time and effort that could otherwise advance the task, and the search may come up empty\. When it succeeds, however, the human is spared an interruption and has more attention left for other agents\. Asking early has its own appeal: the human can answer while the agent continues with other parts of the task, reducing the time lost waiting\. Yet every question competes for the same person’s attention, and a question the agent could have answered itself may delay one that requires human input\. Asking also need not end the agent’s search: while waiting for a response, it can keep looking and withdraw the question if it finds the answer before the human takes it up\. The right choice for one agent therefore depends on the human’s availability and on what the other agents need\. We study how to make these decisions together: how agents should balance finding missing information, continuing their work, and seeking clarification, and which waiting question the human should answer whenever available\.

![Refer to caption](https://arxiv.org/html/2610.41129v1/images/codex_agent1.png)![Refer to caption](https://arxiv.org/html/2610.41129v1/images/codex_agent2.png)AGENT 1AGENT 2HumanFigure 1:Two Codex coding agents that need input from the same person at the same time\.We formulate this problem as a dynamic program\. Each task has its own agent, which in every period can search existing records for the missing requirement, advance work that does not depend on it, or submit a question to the shared human\. The human is available only intermittently and answers at most one question per period\. A question stays pending until it is answered, and the agent can keep searching and withdraw the question if a search succeeds\. We show that several actions can be removed without loss of optimality, which makes the problem a finite dynamic program, although its size grows exponentially with the number of tasks\.

We first study the single\-agent case and examine how different settings affect the optimal strategy\. We show that an agent whose independent work is complete and whose requirement remains unresolved has an optimal policy characterized by two thresholds on the number of failed searches, which determine whether it should search again or ask the human\. We also show that increasing the amount of independent work \(which requires no additional information from either the human or a search\) can encourage the agent to ask sooner and increase demand on the human\. Finally, we study how allowing an agent to withdraw a pending question affects demand on the human, highlighting withdrawal as an important decision option in this setting\.

We then consider portfolios with multiple tasks\. We first establish a negative result: no policy based solely on each task’s individual state is optimal\. We then propose the Pairwise Coordination Policy \(PCP\), which estimates future costs using exactly solvable one\- and two\-task problems\. Each pairwise term measures how much two tasks delay one another by sharing the human and we call this quantity the pairwise price of shared attention\. PCP is exactly optimal when at most two requirements remain unresolved and costs no more than twice the optimal cost once no search can succeed\.

Numerically, we first conduct a synthetic experiment in which PCP’s cost is, on average, within 0\.07% of the optimal cost across 864 portfolios of three or four tasks\. PCP also reduces costs by 18% to 31% on average compared with common rules for deciding when to ask\. A case study in which LLM agents carry out procurement tasks using Codex shows a similar advantage for PCP\.

The rest of the paper is organized as follows\. Section[2](https://arxiv.org/html/2610.41129#S2)reviews related work\. Section[3](https://arxiv.org/html/2610.41129#S3)presents the model, Section[4](https://arxiv.org/html/2610.41129#S4)analyzes a single task, Section[5](https://arxiv.org/html/2610.41129#S5)develops PCP and its guarantees, Section[6](https://arxiv.org/html/2610.41129#S6)reports the numerical study and the case study, and Section[7](https://arxiv.org/html/2610.41129#S7)concludes\.

## 2Literature Review

This study brings together four streams: human–agent delegation, clarification and sequential information acquisition, allocation of shared human attention, and structured dynamic optimization\. Specifically, we examine a setting in which several agents can search for missing requirements or advance independent work, while their clarification requests compete for a single human’s attention\.

### 2\.1Delegation and adjustable autonomy

Research on agentic information systems treats delegation as an evolving distribution of responsibility between humans and agents\.[Baird and Maruping \(2021\)](https://arxiv.org/html/2610.41129#bib.bib5)develop a conceptual framework for delegation to and from agentic systems, and[Zhang and Sun \(2026\)](https://arxiv.org/html/2610.41129#bib.bib23)set out a decision\-science agenda centered on the interaction structures through which humans and agents make decisions over time\. Behavioral evidence complements these frameworks:[Fügener et al\. \(2022\)](https://arxiv.org/html/2610.41129#bib.bib13)show that the performance of human–AI collaboration depends on the direction of delegation and on humans’ ability to assess their own capabilities\. Earlier work on mixed\-initiative interaction and adjustable autonomy treats asking for human input as a sequential decision\.[Horvitz \(1999\)](https://arxiv.org/html/2610.41129#bib.bib18)advocates decision\-theoretic reasoning about when to act and when to engage a user, while[Scerri et al\. \(2002\)](https://arxiv.org/html/2610.41129#bib.bib19)model revisable transfers of control that account for uncertain human response times and their effects on team performance\. We take a normative, operational approach\. Assuming fixed search and human\-answer reliability, we model each question as pending until it is answered or withdrawn after a successful search\. While the question is pending, the agent can continue working\. We account separately for notification, answering, and waiting costs, allowing each to shape a distinct decision\.

### 2\.2Clarification and sequential information acquisition

Choosing between further search and asking relates to the economics of sequential search, in which the value of further information governs both search order and stopping\([Weitzman, 1979](https://arxiv.org/html/2610.41129#bib.bib21)\)\. In our setting, repeated attempts target a single requirement, failed searches weakly lower the probability that the next attempt succeeds, and search consumes agent time that could advance independent work\. Recent clarification research treats questions as costly information acquisition\.[Dong et al\. \(2026\)](https://arxiv.org/html/2610.41129#bib.bib11)weigh the expected utility gain from asking against the cognitive cost to the user, and[Suri et al\. \(2026\)](https://arxiv.org/html/2610.41129#bib.bib20)apply the expected value of perfect information to structured tool parameters, distinguishing uncertainty about the user’s specification from uncertainty in model predictions\. Computational studies further show that how and when clarification enters execution matters:[Edwards and Schuster \(2026\)](https://arxiv.org/html/2610.41129#bib.bib12)separate detection of underspecified instructions from code execution in a multi\-agent scaffold, and[Gulati et al\. \(2026\)](https://arxiv.org/html/2610.41129#bib.bib16)find that the value of a clarification depends on the missing information and on the stage of execution at which it arrives\. Unlike these studies, we consider multiple distinct tasks that share a human\. Searching for missing information on one task preserves the human’s capacity to assist with others, while an agent can continue working as it awaits an answer\. This setting lets us determine when the presence of independent work makes immediate clarification more attractive and evaluate clarification requests by their impact on portfolio completion costs\.

### 2\.3Allocation of shared human attention

A related stream of research studies human supervision of multiple robots\.[Dahiya et al\. \(2022\)](https://arxiv.org/html/2610.41129#bib.bib9)formulate operator allocation among semiautonomous robots as a restless\-bandit problem and derive conditions for a Whittle\-index policy, building on[Whittle \(1988\)](https://arxiv.org/html/2610.41129#bib.bib22)\.[Cai et al\. \(2022\)](https://arxiv.org/html/2610.41129#bib.bib7)schedule robots that can complete tasks autonomously or faster with human assistance using a mixed\-integer formulation with known processing times\.[Costen et al\. \(2024\)](https://arxiv.org/html/2610.41129#bib.bib8)design a bidding mechanism for shared assistance that balances its direct benefit against learning about latent operator performance\. In our model, demand for assistance is endogenous: an agent can remove its own need for clarification by finding the information, even after asking\. Search competes with work for the agent’s time, whereas human service runs in parallel with work\. These features change how priorities should be set\. Our pairwise policy prices the cost of sharing the human using exactly solved two\-task problems\. Our setting also connects to scheduling\. When every remaining requirement must be supplied by the human, choosing which question to answer is a single\-server scheduling problem with unit processing times\. In the absence of independent work, serving questions in descending order of weight is optimal, as in Smith’s rule\([Smith, 1956](https://arxiv.org/html/2610.41129#bib.bib24)\)\.

### 2\.4Structured dynamic optimization

Our computational approach builds on approximate dynamic programming with factored value functions\. For multiagent planning in factored Markov decision processes,[Guestrin et al\. \(2002\)](https://arxiv.org/html/2610.41129#bib.bib14);[Guestrin et al\. \(2003\)](https://arxiv.org/html/2610.41129#bib.bib15)use local value functions and coordination graphs\.[de Farias and Van Roy \(2003\)](https://arxiv.org/html/2610.41129#bib.bib10)relate value approximation to control performance in linear\-programming approaches, while[Boehmer et al\. \(2020\)](https://arxiv.org/html/2610.41129#bib.bib6)approximate joint action values using individual utilities and pairwise payoffs\. The Pairwise Coordination Policy constructs its components from exactly solved reduced versions of our model\. For each pair of tasks, it subtracts the two singleton values from the joint value when both tasks share a human, isolating the cost of sharing that capacity\. Each component therefore has an operational interpretation\.

## 3Model

We model a finite batch of delegated tasks that share one human\. Throughout, we use the procurement setting of Section[1](https://arxiv.org/html/2610.41129#S1)as a running example to illustrate the setup: each agent handles one purchase for a manager, and the missing requirement is a specification, such as the maximum acceptable lead time, that may or may not be recorded in earlier orders\.

### 3\.1Tasks, agents, and the human

In this study, we assume that each task is delegated to its own agent, as when a person runs several agent threads at once\([Johnston et al\., 2026](https://arxiv.org/html/2610.41129#bib.bib2)\)\. Letnnbe the number of tasks\. A task is complete only when both conditions are met\. First, the agent must finish the task’s*independent work*: steps that do not depend on the missing requirement, such as extracting supplier prices and computing landed costs\. Second, the missing requirement must be*resolved*, either by the agent searching existing records or by the human answering a question\. Time is divided into periods, each long enough for one search attempt or one unit of independent work\. An agent can perform at most one of these activities in a period, so searching and working compete for the agent’s time\.

To ask, the agent submits a question, which remains*pending*until the human answers it\. The human is shared by all tasks and only intermittently available\. While its question is pending, an agent can continue its independent work, including in the period in which the human answers\. It can also keep searching, and if a search succeeds first, the question is*withdrawn*\. A central controller makes all decisions: which questions to submit, which pending question the human answers, and whether each agent searches, works, or waits\.

### 3\.2Search and information

We assume the agent does not know whether the needed requirement is in the records\. Taskii’s requirement is recoverable with probabilitypi∈\[0,1\)p\_\{i\}\\in\[0,1\)\. We excludepi=1p\_\{i\}=1so that repeated failures eventually make further search unattractive\. If the requirement is recoverable, each search attempt finds it independently with probabilityαi∈\(0,1\]\\alpha\_\{i\}\\in\(0,1\]; if it is not, every search fails\. Recoverability and search outcomes are independent across tasks, and a successful search resolves the requirement correctly and observably\. In the procurement example,pip\_\{i\}is the probability that the specification appears in earlier orders, andαi\\alpha\_\{i\}is the probability that one pass through those records finds it, given that it is there\. We assume that the agent system knows \(or has estimates of\) these parameters; addressing cases in which they are unknown is left for future research\.

By Bayes’ rule, a failed search weakly increases the probability that the requirement is not recoverable\. Afterkkfailed searches, the probability that the next search succeeds is

qi​\(k\)=pi​αi​\(1−αi\)k1−pi\+pi​\(1−αi\)k,q\_\{i\}\(k\)=\\frac\{p\_\{i\}\\alpha\_\{i\}\(1\-\\alpha\_\{i\}\)^\{k\}\}\{1\-p\_\{i\}\+p\_\{i\}\(1\-\\alpha\_\{i\}\)^\{k\}\},\(1\)which is weakly decreasing inkk\. Thus, the number of failures summarizes all the information the agent has learned from searching\.

### 3\.3State and timing

At each periodtt, letsi=\(xi,ki,zi\)s\_\{i\}=\(x\_\{i\},k\_\{i\},z\_\{i\}\)denote the observed state of taskii, suppressing the time index for notational convenience\. Here,xix\_\{i\}is the number of independent work units remaining,kik\_\{i\}is the number of failed searches, andzi∈\{U,P,R\}z\_\{i\}\\in\\\{U,P,R\\\}indicates whether the requirement is unresolved with no question submitted \(UU\), unresolved with a pending question \(PP\), or resolved \(RR\)\. Taskiistarts in statesi=\(bi,0,U\)s\_\{i\}=\(b\_\{i\},0,U\), wherebi≥0b\_\{i\}\\geq 0denotes its amount of independent work\. We also allow a question to be pending initially\. The task is complete whenxi=0x\_\{i\}=0andzi=Rz\_\{i\}=R\. Figure[2](https://arxiv.org/html/2610.41129#S3.F2)shows howziz\_\{i\}evolves\.

Unsubmittedzi=Uz\_\{i\}=UPendingzi=Pz\_\{i\}=PResolvedzi=Rz\_\{i\}=Rsubmitquestionsearchsucceedshuman answers,or search succeedsand withdrawssearch fails \(ki\+1k\_\{i\}\{\+\}1\)search fails \(ki\+1k\_\{i\}\{\+\}1\)Figure 2:Statusziz\_\{i\}of taskii’s requirement\. Each search succeeds with probabilityqi​\(ki\)q\_\{i\}\(k\_\{i\}\)\.In each period, the human is available with probabilitya∈\(0,1\]a\\in\(0,1\], independently across periods and of all search outcomes\. This is a reduced\-form description of a person who checks in on agents intermittently while attending to other duties\. Events within each period occur in the following order:

1. 1\.Before learning whether the human is available, the controller submits questions\. Each task’s question can be submitted at most once\.
2. 2\.Availability is revealed\. If the human is available, the controller selects at most one unanswered submitted question for service; this may include a question submitted in the current period\. Service need not follow a first\-come, first\-served order\.
3. 3\.Each agent searches, works, or waits, knowing whether the human is available and which question, if any, is being served\.
4. 4\.Outcomes take effect at the end of the period\. Work units are completed, and a served question resolves its requirement because answers are correct\. A successful search also resolves its requirement and withdraws any pending question at no cost\. Completed tasks leave the system\.

We assume that answers and successful searches are correct, separating timing and capacity from the reliability of retrieval; this assumption is consistent with behavioral research\([Fügener et al\., 2022](https://arxiv.org/html/2610.41129#bib.bib13)\)\.

### 3\.4Costs and objective

We assume there are four types of cost\. Each period in which taskiiis incomplete incurs a cost ofwi\>0w\_\{i\}\>0, which we call its*delay weight*\. A higher weight marks a more urgent task, such as a supplier decision that holds up a purchase\. Delay costs are charged at the beginning of each period\. Each search on taskiiincurs a cost ofci\>0c\_\{i\}\>0, reflecting compute and tool usage\. Each submitted question incurs a cost ofκi≥0\\kappa\_\{i\}\\geq 0, representing the interruption caused by notifying the human, and each answer incurs a cost ofη≥0\\eta\\geq 0, representing the human time required to respond\. Because submission and answering are charged separately, a question withdrawn before service incurs only the submission costκi\\kappa\_\{i\}\.

LetCiC\_\{i\}be the number of periods until taskiicompletes,NiSN\_\{i\}^\{S\}its number of searches,NiQN\_\{i\}^\{Q\}its number of submitted questions, andNHN^\{H\}the total number of human answers\. From the joint states=\(s1,…,sn\)s=\(s\_\{1\},\\ldots,s\_\{n\}\), the controller seeks

V∗​\(s\)=infπ𝔼sπ​\[∑iwi​Ci\+∑ici​NiS\+∑iκi​NiQ\+η​NH\],V^\{\*\}\(s\)=\\inf\_\{\\pi\}\\mathbb\{E\}\_\{s\}^\{\\pi\}\\\!\\left\[\\sum\_\{i\}w\_\{i\}C\_\{i\}\+\\sum\_\{i\}c\_\{i\}N\_\{i\}^\{S\}\+\\sum\_\{i\}\\kappa\_\{i\}N\_\{i\}^\{Q\}\+\\eta N^\{H\}\\right\],\(2\)where the infimum is over nonanticipative policiesπ\\pi, which may depend on the observed history\. For a continuation state,CiC\_\{i\}counts the periods remaining until taskiicompletes, and the objective excludes fees already incurred\.

### 3\.5Structural properties

We first identify restrictions on the controller’s decisions that preserve optimality\.

###### Lemma 1\(Structural properties\)\.

There exists an optimal policy with the following three properties simultaneously\.

1. \(i\)An agent never searches while its question is being answered, performs its remaining work without delay after resolution, and, before resolution, works whenever it does not search and work remains\.
2. \(ii\)At most one new question is submitted per period, and a newly submitted question is served if the human is available in that period\.
3. \(iii\)Taskiiis never searched afterMiM\_\{i\}failures, whereMi=min⁡\{k≥0:qi​\(k\)​Bmax≤ci\}M\_\{i\}=\\min\\\{k\\geq 0:q\_\{i\}\(k\)B\_\{\\max\}\\leq c\_\{i\}\\\}is finite andBmax=∑iwi​bi\+na​∑iwi\+∑iκi\+n​ηB\_\{\\max\}=\\sum\_\{i\}w\_\{i\}b\_\{i\}\+\\frac\{n\}\{a\}\\sum\_\{i\}w\_\{i\}\+\\sum\_\{i\}\\kappa\_\{i\}\+n\\etabounds the optimal remaining cost from any reachable state\.

With these reductions, the optimal value solves a finite dynamic program in which every state\-changing transition advances work, failures, submission, or resolution\.

Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)shows that the controller can restrict attention to a much smaller set of decisions without losing optimality: agents never sit idle when they have work, at most one new question is submitted per period, and each task has a finite search budget\. Section[5](https://arxiv.org/html/2610.41129#S5)uses these properties to define the candidate plans of our policy\. Appendix[A\.1](https://arxiv.org/html/2610.41129#A1.SS1)shows that these caps are sufficient and states the resulting dynamic program, and Appendix[B\.2](https://arxiv.org/html/2610.41129#A2.SS2)proves these properties\.

Even with these reductions, solving for the optimal policy exactly remains computationally challenging\. A single taskiihas at most3​\(bi\+1\)​\(Mi\+1\)3\(b\_\{i\}\+1\)\(M\_\{i\}\+1\)states, so the joint state space can contain as many as∏i=1n3​\(bi\+1\)​\(Mi\+1\)\\prod\_\{i=1\}^\{n\}3\(b\_\{i\}\+1\)\(M\_\{i\}\+1\)states\. We call the decisions made in one period a*period plan*\. A period plan specifies which question, if any, is submitted and, for each possible availability outcome, which question is served and whether each agent searches, works, or waits\. The number of period plans grows exponentially withnn, so exact dynamic programming is practical only for small portfolios\. The following sections develop additional structure in the problem and introduce PCP, an efficient algorithm for larger portfolios\.

## 4When should a single agent search, ask, or work?

We begin with a single task to understand how an agent should choose among searching, asking, and working\. In this setting, the optimal policy admits an explicit characterization that reveals how costs and timing shape the decision to ask\. The same forces govern each agent’s choices in a portfolio and help explain the behavior of the optimal policy and PCP in Sections[5](https://arxiv.org/html/2610.41129#S5)and[6](https://arxiv.org/html/2610.41129#S6)\. The single\-task value functions also serve as building blocks for PCP\. Because this section considers one task, we drop the indexii\.

### 4\.1When to stop searching and ask

We start with the simplest case: a task whose independent work is finished \(x=0x=0\)\. We call such a task*blocked*because only its requirement remains; its agent can therefore only search or wait for the human\. The question is how many failed searches the agent should tolerate before asking, and whether it should continue searching afterward\. The trade\-off is subtle because these costs arise at different times: the submission fee is paid when the question is submitted, the answer fee when the human responds, and delay costs accrue while the task waits\. The next theorem shows that an optimal policy can be characterized by two thresholds on the number of failed searches: one before asking and one after\.

###### Theorem 1\(Blocked\-task thresholds\)\.

For one task withx=0x=0, there exists an optimal policy with an asking thresholdkaskk\_\{\\rm ask\}: an unsubmitted task searches below this threshold and submits at or above it, where ties between searching and submitting are broken in the same direction at every failure count\. Conditional on a pending question and an unavailable human, search is strictly preferable to waiting if and only if

q​\(k\)​\(η\+wa\)\>c\.q\(k\)\\left\(\\eta\+\\frac\{w\}\{a\}\\right\)\>c\.\(3\)Thus pending search also stops at a failure\-count threshold\. The two thresholds have no universal ordering\.

Theorem[1](https://arxiv.org/html/2610.41129#Thmtheorem1)shows that a blocked agent needs to track only how many of its searches have failed\. Appendix[A\.2](https://arxiv.org/html/2610.41129#A1.SS2)gives the exact characterization ofkaskk\_\{\\rm ask\}, and Appendix[B\.3](https://arxiv.org/html/2610.41129#A2.SS3)proves the theorem\. Before asking, the agent searches untilkaskk\_\{\\rm ask\}failures and then submits its question\. After asking, it keeps searching in periods when the human is unavailable for as long as \([3](https://arxiv.org/html/2610.41129#S4.E3)\) holds\. Condition \([3](https://arxiv.org/html/2610.41129#S4.E3)\) compares the cost of one more search with its expected benefit: with probabilityq⁡\(k\)q\(k\), the search succeeds and avoids the answer feeη\\etaand an expected wait of1/a1/aperiods for the human, each of which costsww\. The submission fee is avoidable before asking and sunk afterward, so the two thresholds can fall in either order\. Whether the agent searches therefore depends on its current belief and on whether it has already asked\.

For example, letw=η=1w=\\eta=1,a=0\.5a=0\.5,c=0\.1c=0\.1,p=0\.6p=0\.6, andα=0\.5\\alpha=0\.5\. Condition \([3](https://arxiv.org/html/2610.41129#S4.E3)\) holds fork≤4k\\leq 4, so a pending agent keeps searching while the human is unavailable until five searches have failed, whatever the submission fee\. The asking threshold rises with the submission fee: the agent asks at once whenκ≤1\.5\\kappa\\leq 1\.5, after one failure whenκ=3\\kappa=3, after three failures whenκ=8\\kappa=8, and after six failures whenκ=60\\kappa=60\. With a small fee, the agent asks at once and keeps searching while it waits for the answer\. With a very large fee, it searches beyond the point at which a pending agent would stop, because one more success still saves the fee\.

### 4\.2The influence of independent work

Most tasks still have work left when an agent discovers that a requirement is missing\. In the procurement example, the agent may still need to compute landed costs when it finds that the acceptable lead time is unknown\. We now ask how such independent work changes the decision to ask\. One might expect that work makes asking less urgent, because the agent has something useful to do while it searches\. The next theorem shows that the opposite can hold\. To isolate the effect of work, it compares two tasks that are identical except that one has a unit of work left, and it setsα=1\\alpha=1, so that a single search reveals whether the requirement is in the records\.

###### Theorem 2\(Work overlap and human demand\)\.

Consider one task withα=1\\alpha=1,w,c,κ,η\>0w,c,\\kappa,\\eta\>0, anda∈\(0,1\]a\\in\(0,1\]\. Define

θ0=w\+a​cκ\+w\+a​η,θ1=w\+a​cκ\+\(1−a\)​w\+a​η\.\\theta\_\{0\}=\\frac\{w\+ac\}\{\\kappa\+w\+a\\eta\},\\qquad\\theta\_\{1\}=\\frac\{w\+ac\}\{\\kappa\+\(1\-a\)w\+a\\eta\}\.\(4\)If

max⁡\{c/η,θ0\}<p<min⁡\{1,θ1\},\\max\\\{c/\\eta,\\theta\_\{0\}\\\}<p<\\min\\\{1,\\theta\_\{1\}\\\},\(5\)the optimal initial actions differ between two otherwise identical tasks:

1. \(i\)With zero work units, search first and submit only after failure\.
2. \(ii\)With one work unit, submit immediately\. If the human is available, receive the answer while working\. Otherwise, search\.

Adding that work unit raises the probability of a human answer bya​papand reduces expected searches byaa\. The interval in \([5](https://arxiv.org/html/2610.41129#S4.E5)\) is nonempty exactly when

c<η,0<κ<w⁡\[ηc−\(1−a\)\]\.c<\\eta,\\qquad 0<\\kappa<w\\left\[\\frac\{\\eta\}\{c\}\-\(1\-a\)\\right\]\.\(6\)

Theorem[2](https://arxiv.org/html/2610.41129#Thmtheorem2)shows that giving an agent useful independent work can make it ask the human sooner and therefore increase human demand\. Within the interval \([5](https://arxiv.org/html/2610.41129#S4.E5)\), adding one work unit switches the optimal first move from searching to asking\. The two cutoffs have direct interpretations\. Aboveθ0\\theta\_\{0\}, a task without work prefers to search before asking\. Belowθ1\\theta\_\{1\}, a task with one work unit prefers to ask immediately\. The lower boundp\>c/ηp\>c/\\etaensures that searching remains worth its cost even when an answer is on its way\.

The intuition is that independent work changes the cost of waiting\. Without work, waiting for the human wastes the agent’s time, so an agent with a promising search first tries to resolve the requirement itself\. With work, waiting is productive: an answer received now overlaps work that must be done anyway, whereas a search displaces that work\. In the procurement example, an agent that still has to compute landed costs should ask the manager about the lead time right away and do the computation while it waits, whereas an agent with nothing left to do should check earlier orders first\. Numerically, forw=κ=η=1w=\\kappa=\\eta=1,c=0\.1c=0\.1, anda=0\.5a=0\.5, the interval is0\.42<p<0\.5250\.42<p<0\.525, and atp=0\.5p=0\.5the probability of a human answer rises from0\.50\.5to0\.750\.75\. Figure[3](https://arxiv.org/html/2610.41129#S4.F3)shows how the region varies withaa\. The proof is in Appendix[B\.4](https://arxiv.org/html/2610.41129#A2.SS4)\.

### 4\.3The influence of question withdrawal

In our model, an agent may continue searching after asking and withdraw its question if a search succeeds\. Some agent interfaces can disable this option\. In those cases, asking acts as a handoff: once the agent asks, it stops searching for the requirement and waits for the answer, although it may continue other work\. We now ask how much the option to withdraw is worth and how it affects demand on the human\. To isolate the effect of withdrawal, consider the*no\-withdrawal model*, which differs from ours only in that an agent cannot search after submitting a question\. Withdrawal adds an option and therefore cannot increase the optimal cost\. Because some questions may be withdrawn before service, one might also expect withdrawal to reduce demand on the human\. The next result shows that it can have the opposite effect\.

###### Proposition 1\(Withdrawable questions\)\.

Consider one task withα=1\\alpha=1, one work unit,w,c,κ,η\>0w,c,\\kappa,\\eta\>0, anda∈\(0,1\)a\\in\(0,1\)\. Withθ1\\theta\_\{1\}as in \([4](https://arxiv.org/html/2610.41129#S4.E4)\), define

θnw=a⁡\(w\+c\)a​κ\+a​η\+\(1−a\)​w\.\\theta\_\{\\rm nw\}=\\frac\{a\(w\+c\)\}\{a\\kappa\+a\\eta\+\(1\-a\)w\}\.\(7\)If

max⁡\{c/η,θnw\}<p<min⁡\{1,θ1\},\\max\\\{c/\\eta,\\theta\_\{\\rm nw\}\\\}<p<\\min\\\{1,\\theta\_\{1\}\\\},\(8\)the optimal initial actions differ between the two models:

1. \(i\)Without withdrawal, search first and submit only after failure\.
2. \(ii\)With withdrawal, submit immediately\. If the human is available, receive the answer while working\. Otherwise, search, and withdraw the question if the search succeeds\.

Allowing withdrawal lowers the optimal expected cost by

w\+a​c−p⁡\[κ\+\(1−a\)​w\+a​η\]\>0w\+ac\-p\\bigl\[\\kappa\+\(1\-a\)w\+a\\eta\\bigr\]\>0\(9\)and the expected completion time by1−\(1−a\)​p1\-\(1\-a\)p\. It raises the probability of a human answer bya​papand the probability of submission bypp, and it reduces expected searches byaa\. The interval in \([8](https://arxiv.org/html/2610.41129#S4.E8)\) is nonempty exactly when

c<η,κ<w⁡\[ηc−\(1−a\)\],\(2​a−1\)​w<a⁡\(κ\+η−c\)\.c<\\eta,\\qquad\\kappa<w\\left\[\\frac\{\\eta\}\{c\}\-\(1\-a\)\\right\],\\qquad\(2a\-1\)w<a\(\\kappa\+\\eta\-c\)\.\(10\)

Within the interval \([8](https://arxiv.org/html/2610.41129#S4.E8)\), withdrawal switches the optimal first move from searching to asking, lowering total cost while raising human demand\. The new cutoffθnw\\theta\_\{\\rm nw\}plays the role ofθ0\\theta\_\{0\}: above it, a task that cannot withdraw its question prefers to search before asking\. Unlike Theorem[2](https://arxiv.org/html/2610.41129#Thmtheorem2), the proposition requiresa<1a<1, because ata=1a=1the cutoffsθnw\\theta\_\{\\rm nw\}andθ1\\theta\_\{1\}coincide and the interval is empty\. Appendix[B\.5](https://arxiv.org/html/2610.41129#A2.SS5)gives the proof\.

Intuitively, without withdrawal, asking forfeits the chance to resolve the requirement autonomously, so an agent with a promising search postpones its question and delays its independent work while searching\. Withdrawal removes this forfeit and makes early questions cheaper\. For the parameters of the earlier illustration, the interval is0\.367<p<0\.5250\.367<p<0\.525\. Atp=0\.5p=0\.5, withdrawal lowers the optimal cost from3\.603\.60to3\.553\.55: faster completion saves0\.750\.75in delay costs and fewer searches save0\.050\.05, which outweighs the additional0\.500\.50in submission fees and0\.250\.25in answer fees, and the probability that the human answers rises from0\.500\.50to0\.750\.75\. The one\-work\-unit policy in Theorem[2](https://arxiv.org/html/2610.41129#Thmtheorem2)relies on withdrawal in exactly this way, and Figure[3](https://arxiv.org/html/2610.41129#S4.F3)shows that the two regions overlap substantially\.

000\.20\.20\.40\.40\.60\.60\.80\.811000\.20\.20\.40\.40\.60\.6θ1\\theta\_\{1\}θ0\\theta\_\{0\}max⁡\{c/η,θnw\}\\max\\\{c/\\eta,\\theta\_\{\\rm nw\}\\\}a=p=0\.5a=p=0\.5Human availabilityaaRecoverabilityppWork changes the decision \(Thm\.[2](https://arxiv.org/html/2610.41129#Thmtheorem2)\)Withdrawal changes the decision \(Prop\.[1](https://arxiv.org/html/2610.41129#Thmproposition1)\)Figure 3:Regions of Theorem[2](https://arxiv.org/html/2610.41129#Thmtheorem2)and Proposition[1](https://arxiv.org/html/2610.41129#Thmproposition1)forw=κ=η=1w=\\kappa=\\eta=1andc=0\.1c=0\.1\. In both, an agent with one work unit and withdrawable questions asks immediately, whereas the same agent without work \(aboveθ0\\theta\_\{0\}\) or without withdrawal \(aboveθnw\\theta\_\{\\rm nw\}\) would search first\. Both regions also requirep\>c/η=0\.1p\>c/\\eta=0\.1, which binds only for the withdrawal region whena<0\.1a<0\.1\. The withdrawal region closes ata=1a=1, whereθnw=θ1\\theta\_\{\\rm nw\}=\\theta\_\{1\}\.Together, the two results offer a management insight: we should not judge agents or interface designs solely by how rarely they ask questions\. Useful independent work can make the optimal agent ask sooner and the human answer more often, and the option to withdraw a question can do so while lowering total cost\. Both mechanisms persist beyond the single search attempt and single work unit assumed in the two results\. When search can be repeated, one more unit of work raises the optimal expected number of human answers in at least 88% of the settings we examine, and withdrawal lowers the optimal cost in every setting while raising the number of answers in 19% to 40% of them; both effects also appear when four tasks share one human \(more results can be found in Appendix[C\.6](https://arxiv.org/html/2610.41129#A3.SS6)\)\. Theorem[2](https://arxiv.org/html/2610.41129#Thmtheorem2)and Proposition[1](https://arxiv.org/html/2610.41129#Thmproposition1)describe each agent’s incentives in isolation\. In a portfolio, however, every question can delay other agents waiting for the human\. The next section shows how to account for this interaction\.

## 5Coordinating a portfolio: the Pairwise Coordination Policy

We now consider portfolios of tasks that share one human\. Each agent still faces the tradeoffs of Section[4](https://arxiv.org/html/2610.41129#S4), but its choices also affect the other agents: when the human answers one question, service for other waiting questions is delayed\. Exact dynamic programming captures these interactions but becomes intractable as the portfolio grows \(Section[3](https://arxiv.org/html/2610.41129#S3)\)\. We therefore seek a computationally efficient policy that accounts for this congestion\.

### 5\.1Task\-local priorities can fail

A simple way to coordinate the agents is to assign each waiting question a priority score based only on its task, such as its weight or the probability that a search will find the requirement, and have the human answer the question with the highest score\. Index policies of this kind are optimal \(or numerically perform well\) in many scheduling and bandit problems, including restless\-bandit models of shared assistance\([Dahiya et al\., 2022](https://arxiv.org/html/2610.41129#bib.bib9)\), and they are easy to implement\. However, the next proposition and example show that no such task\-local score is optimal in our setting: which question should be answered first depends on the other tasks in the portfolio\.

###### Proposition 2\(No optimal task\-local priority\)\.

There is no scorerr, computed from a task’s own parameters and current state together with the common parametersaaandη\\eta, such that in every portfolio each task with the largest score is an optimal choice for the next human service\.

###### Example 1\(Portfolio\-dependent priority\)\.

Leta=1a=1,xi=0x\_\{i\}=0,αi=1\\alpha\_\{i\}=1,ci=0\.01c\_\{i\}=0\.01,κi=0\.05\\kappa\_\{i\}=0\.05, andη=0\.05\\eta=0\.05\. TasksA,B,CA,B,Chave\(wi,pi\)=\(4,0\.75\),\(1,0\.10\),\(0\.5,0\)\(w\_\{i\},p\_\{i\}\)=\(4,0\.75\),\(1,0\.10\),\(0\.5,0\)\. Optimizing all remaining decisions conditional on first human service gives

Proposition[2](https://arxiv.org/html/2610.41129#Thmproposition2)implies that the human’s priorities must depend on the portfolio as a whole, and Example[1](https://arxiv.org/html/2610.41129#Thmexample1)shows it\. TasksAAandBBhave the same parameters and states in both portfolios\. In\{A,B\}\\\{A,B\\\}, servingAAis uniquely optimal, which requiresr⁡\(A\)\>r⁡\(B\)r\(A\)\>r\(B\)\. In\{A,B,C\}\\\{A,B,C\\\}, servingBBis uniquely optimal, which requiresr⁡\(B\)\>r⁡\(A\)r\(B\)\>r\(A\)\. The reversal has a simple explanation\. TaskAAis urgent and likely to be found in the records, taskBBis unlikely to be found, and taskCCcan only be resolved by the human\. In\{A,B\}\\\{A,B\\\}, the urgent task is served first whileBBsearches, becauseBB’s likely wait for a later answer costs little\. OnceCCis present, servingAAfirst would leave bothBBandCCwaiting for the human with high probability\. ServingBBfirst whileAAsearches is better, becauseAA’s search succeeds with probability0\.750\.75and then leaves the human free forCC\. Appendix[B\.6](https://arxiv.org/html/2610.41129#A2.SS6)gives the calculation of the example\. Although no task\-local priority is optimal in general, approximate indices, including priorities that respond to a system\-wide attention price, can still be useful, as numerical experiments in Appendix[C\.6](https://arxiv.org/html/2610.41129#A3.SS6)illustrate\. A good policy should nonetheless account for how tasks interact through the human\. The next subsection develops a pairwise approach\.

### 5\.2Pairwise prices of shared attention

To account for interactions without solving the full dynamic program, we estimate the portfolio’s future cost using smaller problems that can be solved exactly: each task on its own and each pair of tasks sharing one human\. LetVi​\(si\)V\_\{i\}\(s\_\{i\}\)be the optimal cost of taskiiwhen it has its own human, and letVi​j​\(si,sj\)V\_\{ij\}\(s\_\{i\},s\_\{j\}\)be the optimal cost of tasksiiandjjwhen they share one human\. Both problems use the same availability and cost parameters and the search caps from Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\. Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)describes how we compute these values using the reduced dynamic program \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\)\. Define

Δi​j​\(si,sj\)\\displaystyle\\Delta\_\{ij\}\(s\_\{i\},s\_\{j\}\)=Vi​j​\(si,sj\)−Vi​\(si\)−Vj​\(sj\),\\displaystyle=V\_\{ij\}\(s\_\{i\},s\_\{j\}\)\-V\_\{i\}\(s\_\{i\}\)\-V\_\{j\}\(s\_\{j\}\),\(11\)V^PCP​\(s\)\\displaystyle\\widehat\{V\}\_\{\\rm PCP\}\(s\)=∑iVi​\(si\)\+∑i<jΔi​j​\(si,sj\)\.\\displaystyle=\\sum\_\{i\}V\_\{i\}\(s\_\{i\}\)\+\\sum\_\{i<j\}\\Delta\_\{ij\}\(s\_\{i\},s\_\{j\}\)\.\(12\)We callV^PCP\\widehat\{V\}\_\{\\rm PCP\}the*pairwise approximation*andΔi​j\\Delta\_\{ij\}the*pairwise price of shared attention*: the additional expected cost that tasksiiandjjincur when they share one human, compared with each having a human of its own\. The price is nonnegative, because separate human capacity relaxes the pair’s shared\-capacity constraint \(Lemma[B\.4](https://arxiv.org/html/2610.41129#A2.Thmlemma4)\)\. Resolved tasks contribute only their deterministic remaining\-work cost and have zero prices with other tasks\. Setting every price to zero gives the*singleton approximation*∑iVi​\(si\)\\sum\_\{i\}V\_\{i\}\(s\_\{i\}\), which captures each task’s own tradeoffs but ignores congestion\. Before using the approximation, we identify cases in which it gives the optimal value\.

###### Proposition 3\(Optimal cases\)\.

The pairwise approximation \([12](https://arxiv.org/html/2610.41129#S5.E12)\) gives the optimal value when at most two requirements remain unresolved\. It also gives the optimal value for any number of unresolved tasks when no remaining search can succeed andxi=0x\_\{i\}=0for every unresolved task\. In the latter case,

Δi​j=min⁡\(wi,wj\)a,\\Delta\_\{ij\}=\\frac\{\\min\(w\_\{i\},w\_\{j\}\)\}\{a\},\(13\)and descending\-weight human service is optimal\.

Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3)shows that the pairwise approximation loses nothing in two situations\. The first is a consistency property of the construction: when at most two tasks still need their requirements, the approximation contains the exact value of that pair\. The second arises when every remaining requirement must come from the human and no work remains\. Serving in descending weight is then Smith’s rule for jobs of equal length\([Smith, 1956](https://arxiv.org/html/2610.41129#bib.bib24)\), and the price of attention takes a transparent form\. Appendix[B\.7](https://arxiv.org/html/2610.41129#A2.SS7)gives the proof, and Corollary[A\.1](https://arxiv.org/html/2610.41129#A1.Thmcorollary1)extends the second case to tasks with at most one unit of work\.

When neither task can avoid human service and neither has work left, the task served second waits an extra1/a1/aperiods in expectation\. Thus, the pairwise price equals the lower delay weight multiplied by this expected wait\. For example, if the manager is available with probability0\.50\.5and two blocked tasks have delay weights44and11, the task with weight11is served second and waits two extra periods on average, soΔi​j=2\\Delta\_\{ij\}=2\. For general portfolios,V^PCP\\widehat\{V\}\_\{\\rm PCP\}need not be either a lower or an upper bound onV∗V^\{\*\}\. Nevertheless, Section[5\.4](https://arxiv.org/html/2610.41129#S5.SS4)establishes guarantees for PCP based on its action\-selection rule\.

### 5\.3Pairwise Coordination Policy

Pairwise Coordination Policy \(PCP\) uses the pairwise approximation as an estimate of the cost to go\. In each period, it chooses the plan that minimizes the immediate cost plus the expected approximate cost of the next state\. Formally, letgd​\(s\)g\_\{d\}\(s\)be the expected immediate cost of a period plandd\(Section[3](https://arxiv.org/html/2610.41129#S3)\) andPdP\_\{d\}its transition law\. Let𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)contain the plans that satisfy the reductions of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)and change the state with positive probability\. Definition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmdefinition1)in Appendix[A\.1](https://arxiv.org/html/2610.41129#A1.SS1)defines this set formally, and Proposition[A\.2](https://arxiv.org/html/2610.41129#A1.Thmproposition2)shows that restricting attention to it preserves the optimum\. PCP selects

dPCP​\(s\)∈arg⁡mind∈𝒟\+​\(s\)​\{gd​\(s\)\+∑s′Pd​\(s,s′\)​V^PCP​\(s′\)\},d\_\{\\rm PCP\}\(s\)\\in\\arg\\min\_\{d\\in\\mathcal\{D\}\_\{\+\}\(s\)\}\\left\\\{g\_\{d\}\(s\)\+\\sum\_\{s^\{\\prime\}\}P\_\{d\}\(s,s^\{\\prime\}\)\\widehat\{V\}\_\{\\rm PCP\}\(s^\{\\prime\}\)\\right\\\},\(14\)executes the selected plan, observes the next state, and repeats\. By Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3), PCP is optimal from any state on the two exact boundaries when the minimization in \([14](https://arxiv.org/html/2610.41129#S5.E14)\) is exact\. The*singleton policy*makes the same choice with the singleton approximation in place ofV^PCP\\widehat\{V\}\_\{\\rm PCP\}\. Comparing the two policies isolates the value of pricing shared attention\. Each answer occupies the human for a period and delays the other tasks waiting for answers\. The pairwise prices charge this delay to the decision that causes it, whereas the singleton policy ignores it and therefore tends to ask too often and search too little\. Section[6](https://arxiv.org/html/2610.41129#S6)shows that this congestion effect is the main source of PCP’s advantage\. Algorithm[1](https://arxiv.org/html/2610.41129#alg1)summarizes PCP\.

When multiple plans attain the minimum in \([14](https://arxiv.org/html/2610.41129#S5.E14)\), PCP breaks ties lexicographically: it first prefers plans that serve a question, then plans that submit one, and finally plans that use fewer searches\. The discussion following Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)explains the rationale for this rule, and Section[5\.5](https://arxiv.org/html/2610.41129#S5.SS5)describes how PCP is computed\.

Algorithm 1Pairwise Coordination Policy \(PCP\)1:initial state

ss, parameters

aa,

η\\eta, and

\(wi,pi,αi,ci,κi\)i=1n\(w\_\{i\},p\_\{i\},\\alpha\_\{i\},c\_\{i\},\\kappa\_\{i\}\)\_\{i=1\}^\{n\}, caps

\(Mi\)i=1n\(M\_\{i\}\)\_\{i=1\}^\{n\}, and a tie\-breaking rule

2:a period plan

dPCP​\(s\)d\_\{\\rm PCP\}\(s\)in each period until all tasks complete

3:whilesome task is incompletedo

4:obtain

ViV\_\{i\}and

Vi​jV\_\{ij\}for unresolved tasks and pairs

5:

d←d\\leftarrowa minimizer of \([14](https://arxiv.org/html/2610.41129#S5.E14)\) over

𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)
6:submit

dd’s question, if any, and observe availability

7:execute

dd’s service and agent actions

8:observe the outcomes and update

ss
9:endwhile

### 5\.4Performance guarantees

Because PCP relies on an approximation, we want to know how far its cost can be above the optimum\. We consider two cases\. When no remaining search can succeed, every unresolved requirement must be resolved by the human, and the problem has enough structure for a worst\-case bound\. When search remains useful, we give a bound that can be checked for each instance\. For a policyπ\\pi, letJπ​\(s\)J^\{\\pi\}\(s\)denote its expected total cost from statess, so thatV∗​\(s\)=infπJπ​\(s\)V^\{\*\}\(s\)=\\inf\_\{\\pi\}J^\{\\pi\}\(s\)\. LetJPCP​\(s\)J^\{\\rm PCP\}\(s\)denote PCP’s expected total cost from statess\. SetH=V^PCPH=\\widehat\{V\}\_\{\\rm PCP\}, letω⁡\(s\)=∑i​incompletewi\\omega\(s\)=\\sum\_\{i\\text\{ incomplete\}\}w\_\{i\}denote the delay cost in the current period, and define the one\-period Bellman defect

ρ⁡\(s\)=mind∈𝒟\+​\(s\)⁡\{gd​\(s\)\+Pd​H​\(s\)\}−H⁡\(s\),\\rho\(s\)=\\min\_\{d\\in\\mathcal\{D\}\_\{\+\}\(s\)\}\\bigl\\\{g\_\{d\}\(s\)\+P\_\{d\}H\(s\)\\bigr\\\}\-H\(s\),\(15\)wherePd​H​\(s\)=∑s′Pd​\(s,s′\)​H​\(s′\)P\_\{d\}H\(s\)=\\sum\_\{s^\{\\prime\}\}P\_\{d\}\(s,s^\{\\prime\}\)H\(s^\{\\prime\}\), withH=ρ=0H=\\rho=0at terminal states\. The next theorem bounds PCP’s cost relative to the optimum, first when every unresolved requirement must be resolved by the human and then in the full model\.

###### Theorem 3\(PCP performance guarantees\)\.

Use exact singleton and pair values, the caps of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1), and exact minimization in \([14](https://arxiv.org/html/2610.41129#S5.E14)\)\.

1. \(i\)Human\-resolution regime\.Suppose no remaining search can succeed\. Let𝒜\\mathcal\{A\}contain the unresolved tasks and define K\\displaystyle K=∑i:zi=Rwixi\+∑i∈𝒜\(η\+κi𝟏\{zi=U\}\),\\displaystyle=\\sum\_\{i:z\_\{i\}=R\}w\_\{i\}x\_\{i\}\+\\sum\_\{i\\in\\mathcal\{A\}\}\(\\eta\+\\kappa\_\{i\}\\mathbf\{1\}\\\{z\_\{i\}=U\\\}\),B\\displaystyle B=∑i∈𝒜wi​max⁡\{xi,1\},w𝒜=∑i∈𝒜wi,\\displaystyle=\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}\\max\\\{x\_\{i\},1\\\},\\qquad w\_\{\\mathcal\{A\}\}=\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\},Q\\displaystyle Q=1a​\(w𝒜\+∑i<ji,j∈𝒜min⁡\(wi,wj\)\)\.\\displaystyle=\\frac\{1\}\{a\}\\left\(w\_\{\\mathcal\{A\}\}\+\\sum\_\{\\begin\{subarray\}\{c\}i<j\\\\ i,j\\in\\mathcal\{A\}\\end\{subarray\}\}\\min\(w\_\{i\},w\_\{j\}\)\\right\)\.For every tie\-breaking rule, JPCP​\(s\)≤K\+B\+Q−w𝒜≤2​V∗​\(s\)−K−w𝒜≤2​V∗​\(s\)\.J^\{\\rm PCP\}\(s\)\\leq K\+B\+Q\-w\_\{\\mathcal\{A\}\}\\leq 2V^\{\*\}\(s\)\-K\-w\_\{\\mathcal\{A\}\}\\leq 2V^\{\*\}\(s\)\.\(16\)If ties are broken toward plans that neither submit nor serve, there are instances in this regime withJPCP/V∗J^\{\\rm PCP\}/V^\{\*\}arbitrarily close toφ=\(1\+5\)/2≈1\.618\\varphi=\(1\+\\sqrt\{5\}\)/2\\approx 1\.618\.
2. \(ii\)Full search model\.On a set of capped states containing the initial state and closed under every positive\-probability successor of every plan in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\), suppose constantsϵ−≥0\\epsilon\_\{\-\}\\geq 0andϵ\+∈\[0,1\)\\epsilon\_\{\+\}\\in\[0,1\)satisfy −ϵ−​ω​\(s\)≤ρ⁡\(s\)≤ϵ\+​ω​\(s\)\-\\epsilon\_\{\-\}\\omega\(s\)\\leq\\rho\(s\)\\leq\\epsilon\_\{\+\}\\omega\(s\)\(17\)at every unfinished state\. Then JPCP​\(s\)≤H⁡\(s\)1−ϵ\+≤1\+ϵ−1−ϵ\+​V∗​\(s\)\.J^\{\\rm PCP\}\(s\)\\leq\\frac\{H\(s\)\}\{1\-\\epsilon\_\{\+\}\}\\leq\\frac\{1\+\\epsilon\_\{\-\}\}\{1\-\\epsilon\_\{\+\}\}V^\{\*\}\(s\)\.\(18\)

Part \(i\) shows that when no search can still succeed, PCP costs at most twice the optimum for any availability, weights, work, and fees, whichever way ties are broken\. The bound is computable from the current state alone, withoutV∗V^\{\*\}or an evaluation of PCP\. Appendix[A\.4](https://arxiv.org/html/2610.41129#A1.SS4)shows that it holds more generally, whenever the search caps of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)rule out further search\.

The guarantee relies on a property of PCP’s decisions \(Lemma[A\.3](https://arxiv.org/html/2610.41129#A1.Thmlemma3)in Appendix[A\.4](https://arxiv.org/html/2610.41129#A1.SS4)\): once a task has at most one unit of work remaining, PCP never serves a lower\-weight task ahead of it and never leaves an available human\-service opportunity unused while the task remains unresolved\. Each additional period of service delay can then be charged to a distinct pair, at a cost of at mostmin⁡\(wi,wj\)/a\\min\(w\_\{i\},w\_\{j\}\)/a—the pairwise price in Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3)\. The factor of two comes from comparing PCP’s cost with two lower bounds on the optimum: one based on remaining work and the other on the queue for human answers\.

Although the bound holds for every tie rule, ties affect PCP’s actual cost, which motivates the tie rule of Section[5\.3](https://arxiv.org/html/2610.41129#S5.SS3)\. When the human is always available and tasks still have ample work, a pairwise price can be zero even if the human cannot answer all the tasks in time, because any two of them can be answered before either needs its answer\. Answering a question now and answering it later then have the same approximate value, and a rule that postpones questions at such ties may wait until the prices turn positive, when the human can no longer keep up\. This is the source of the lower boundφ\\varphiin part \(i\), which Appendix[A\.5](https://arxiv.org/html/2610.41129#A1.SS5)derives for portfolios of identical tasks\. On the same portfolios, preferring plans that serve a question is optimal\. Appendix[B\.9](https://arxiv.org/html/2610.41129#A2.SS9)proves part \(i\)\.

Part \(ii\) covers portfolios in which search remains useful\. It gives an instance\-specific certificate: if the pairwise approximation nearly satisfies the Bellman equation, then PCP is nearly optimal\. The condition depends only on the singleton and pair tables and the one\-period plans, so it can be checked without computingV∗V^\{\*\}or evaluating PCP\. However, checking it at every state in the theorem’s set costs about as much as solving the exact dynamic program\. Thus, it is most useful for confirming PCP’s quality on instances that can still be analyzed exactly, as in Section[6\.1\.2](https://arxiv.org/html/2610.41129#S6.SS1.SSS2)\. Appendix[A\.6](https://arxiv.org/html/2610.41129#A1.SS6)expressesρ\\rhoin terms of disagreements between singleton and pair optimal decisions and extends the bound to inexact minimization, and Appendix[B\.11](https://arxiv.org/html/2610.41129#A2.SS11)gives the proof\.

Intuitively,ρ⁡\(s\)\\rho\(s\)measures the difference between the best one\-period look\-ahead value and the approximation itself\. If this difference is small relative to the delay cost incurred in each period, approximation errors cannot accumulate faster than that cost\. For example, ifϵ−=ϵ\+=0\.05\\epsilon\_\{\-\}=\\epsilon\_\{\+\}=0\.05, the ratio is at most1\.05/0\.95≈1\.1051\.05/0\.95\\approx 1\.105\. The guarantee in part \(ii\) is conditional: the model does not generally ensure that the residual bound in \([17](https://arxiv.org/html/2610.41129#S5.E17)\) holds\.

### 5\.5Computation

PCP requiresnnsingleton value tables andn⁡\(n−1\)/2n\(n\-1\)/2pair value tables\. Each pair table is computed by solving an exact two\-task dynamic program over the product of the two tasks’ state spaces; taskiihas at most3​\(bi\+1\)​\(Mi\+1\)3\(b\_\{i\}\+1\)\(M\_\{i\}\+1\)states\. Tables can be reused across decisions\. The pairwise approximation is a sum of singleton and pair terms, each depending on the search outcomes of at most two tasks, so evaluating one candidate plan requiresO⁡\(n2\)O\(n^\{2\}\)table lookups\. Because the number of plans grows exponentially withnn, our implementation uses coordinate search \(Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)\)\. For each of then\+1n\+1submission choices and each availability outcome, coordinate search starts from two plans and applies a fixed number of sweeps over the service choice and the agents’ search\-or\-work choices\. A decision therefore evaluatesO⁡\(n2\)O\(n^\{2\}\)candidate plans and requiresO⁡\(n4\)O\(n^\{4\}\)table lookups\. Coordinate search approximates the minimization in \([14](https://arxiv.org/html/2610.41129#S5.E14)\)\. In the setting of Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\), where no search choices remain, it evaluates every plan, and the factor\-two bound applies to it under a mild condition on its numerical tolerance that holds in all our experiments \(Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)\)\.

## 6Numerical study

We evaluate PCP in two settings\. Section[6\.1](https://arxiv.org/html/2610.41129#S6.SS1)uses synthetic portfolios in which search outcomes and the human’s availability are drawn from the model\. Section[6\.2](https://arxiv.org/html/2610.41129#S6.SS2)reports a case study in which LLM agents carry out the tasks themselves\. Appendix[C](https://arxiv.org/html/2610.41129#A3)describes the instances, the implementation, and the evaluation in detail\.

We compare PCP with four policies\. The singleton policy of Section[5](https://arxiv.org/html/2610.41129#S5)makes the same greedy choice as PCP using the singleton approximation, so the difference between the two isolates the value of pricing shared attention\. It breaks ties in the same way as PCP\. The other three policies are simple rules for when to ask\.*Always Ask*never searches\. Whenever no question is pending, it submits the question of the unresolved task with the largest weight, and the human answers whenever available\.*Random\-order Ask*does the same but chooses the next question at random\.*Search Once Then Ask*lets each agent work until it is blocked, search once, and ask only if that search fails\. For small portfolios, we also compute the optimal policy by dynamic programming\.

### 6\.1Synthetic experiments

Our main benchmark contains 864 portfolios of three or four tasks\. It crosses the amount of independent workb∈\{0,1,2,4\}b\\in\\\{0,1,2,4\\\}, the availabilitya∈\{0\.25,0\.5,1\}a\\in\\\{0\.25,0\.5,1\\\}, the recoverabilityp∈\{0\.3,0\.7\}p\\in\\\{0\.3,0\.7\\\}, the search success probabilityα∈\{0\.8,1\}\\alpha\\in\\\{0\.8,1\\\}, and the search costc∈\{0\.1,0\.5,1\.5\}c\\in\\\{0\.1,0\.5,1\.5\\\}, with three random draws of the task weights from\{0\.5,1,2,4\}\\\{0\.5,1,2,4\\\}for each combination\. The submission and answer fees areκi=0\.1\\kappa\_\{i\}=0\.1andη=0\.5\\eta=0\.5\. We evaluate every policy exactly and report its gap to the optimal cost and its saving relative to other policies, both averaged over portfolios\. Section[6\.1\.3](https://arxiv.org/html/2610.41129#S6.SS1.SSS3)turns to larger portfolios, which we evaluate by simulation, and Section[6\.1\.4](https://arxiv.org/html/2610.41129#S6.SS1.SSS4)to misestimated inputs\.

#### 6\.1\.1Performance against the optimal policy

Table[1](https://arxiv.org/html/2610.41129#S6.T1)reports the gap to the optimal cost on the benchmark\.

Table 1:Performance on 864 portfolios\. Mean, 95th percentile \(P95\), and largest \(Worst\) gap to the optimal cost,100​\(J−V∗\)/V∗100\(J\-V^\{\*\}\)/V^\{\*\}\(%\)\. Opt\. is the share of portfolios in which the policy’s cost equals the optimal cost up to a relative difference of10−810^\{\-8\}\(%\)\. Saving is PCP’s mean saving relative to the policy,100​\(J−JPCP\)/J100\(J\-J^\{\\rm PCP\}\)/J, averaged over portfolios \(%\)\.PCP is close to optimal throughout\. Its mean gap is 0\.07%, its 95th percentile is 0\.32%, and its largest gap is 1\.87%\. It is exactly optimal in 56% of portfolios\. Coordinate search loses almost nothing relative to exact minimization of \([14](https://arxiv.org/html/2610.41129#S5.E14)\) and attains the same cost in 853 of 864 portfolios\. The singleton policy has a mean gap of 1\.24% and a largest gap of 21\.0%\. The rules for when to ask are far from optimal: PCP saves 18\.2%, 30\.6%, and 28\.7% on average relative to Always Ask, Random\-order Ask, and Search Once Then Ask\. Always Ask comes closest when its two simplifications cost little: when the human is always available \(mean gap 6\.3%\), when long independent work hides the wait for an answer \(10\.5% forb=4b=4\), or when search rarely succeeds \(13\.2% forp=0\.3p=0\.3\)\. It is worst when the human is scarce \(60\.1% fora=0\.25a=0\.25\)\. Search Once Then Ask has the opposite weaknesses\. It pays for searches that are unlikely to succeed and delays questions that the human could answer at once, so its gap is largest forp=0\.3p=0\.3\(51\.9%\) and fora=1a=1\(55\.5%\)\.

The tie rule matters as well\. Breaking ties toward not submitting raises PCP’s largest gap from 1\.87% to 15\.2%\. PCP’s service\-preferring rule is never materially worse, and it saves up to 13\.2%\. Every portfolio in which it saves more than 1% has four units of work per task and an always\-available human, which is the synchronized\-work mechanism discussed after Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(Appendix[A\.5](https://arxiv.org/html/2610.41129#A1.SS5)\)\.

Relative to the singleton policy, PCP saves 1\.1% on average and up to 17\.4%, and Figure[4](https://arxiv.org/html/2610.41129#S6.F4)shows where these savings arise\. They are largest when search is costly and smallest when independent work is long\. With four tasks and no independent work, PCP saves 3\.9% on average when the search cost is1\.51\.5and almost nothing when it is0\.10\.1\. The explanation lies in the search decisions of the singleton policy\. When search is cheap, every agent searches regardless of the other tasks\. When search is costly, the singleton policy searches much less, because it credits a search only with the agent’s own benefit\. In these portfolios with a search cost of1\.51\.5, the singleton policy makes 1\.5 searches per portfolio on average, against 2\.7 for both PCP and the optimal policy\. A successful search also frees the human for the other tasks, and PCP accounts for this benefit through its pairwise prices\. With long work \(b=4b=4\), both policies can schedule questions around the work, and the savings shrink\. The availability of the human has a smaller and less regular effect \(panel b\)\.

![Refer to caption](https://arxiv.org/html/2610.41129v1/fig_regimes.png)Figure 4:Mean saving \(%\) of PCP relative to the singleton policy for portfolios of four tasks, by the amount of independent work and \(a\) the search cost or \(b\) the availability of the human\. Each cell averages 36 portfolios\.This explanation predicts how PCP changes the use of the human, and the data confirm it\. In 299 of the 317 portfolios in which PCP saves more than 0\.5% relative to the singleton policy, PCP uses fewer human answers and more searches\. On average, PCP’s expected number of answers per portfolio \(2\.53\) is close to that of the optimal policy \(2\.55\), whereas the singleton policy asks more \(2\.67\)\. This finding complements Section[4](https://arxiv.org/html/2610.41129#S4)\. The incentive to ask early when work can overlap an answer is private to each task, so the singleton policy already captures it\. The congestion that each question imposes on the other tasks is shared, and pricing it leads agents to resolve more requirements themselves\.

#### 6\.1\.2The guarantees in practice

We next examine how informative Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)is\. For part \(i\), we solve 180 portfolios of three to five tasks in which no search can succeed, with heterogeneous weights, up to six units of work, anda∈\{0\.5,1\}a\\in\\\{0\.5,1\\\}\. PCP is exactly optimal in 175 of them, and its largest ratio to the optimal cost is 1\.06\. The bound in \([16](https://arxiv.org/html/2610.41129#S5.E16)\) lies between the optimal cost and 1\.40 times the optimal cost, with a median of 1\.18\. The tie rule again matters\. With ties broken toward not submitting, PCP is optimal in only 135 portfolios, and its largest ratio is 1\.15\. In the homogeneous family of Appendix[A\.5](https://arxiv.org/html/2610.41129#A1.SS5), the worst ratio under that rule rises from 1\.24 with five tasks to 1\.54 with thirty, approachingφ\\varphi, whereas PCP’s service\-preferring rule is optimal throughout\.

For part \(ii\), we compute conservative values ofϵ\+\\epsilon\_\{\+\}andϵ−\\epsilon\_\{\-\}\(Appendix[C\.3](https://arxiv.org/html/2610.41129#A3.SS3)\) over all states reachable from the initial state under any plan, for 815 benchmark portfolios\. We omit 49 of the 54 four\-task portfolios withα=0\.8\\alpha=0\.8andb=4b=4, whose state spaces are the largest\. The conditionϵ\+<1\\epsilon\_\{\+\}<1holds in every one of them, withϵ\+\\epsilon\_\{\+\}at most 0\.71\. The certified ratio\(1\+ϵ−\)/\(1−ϵ\+\)\(1\+\\epsilon\_\{\-\}\)/\(1\-\\epsilon\_\{\+\}\)has a median of 1\.17, is at most1\.251\.25in 67% of portfolios, and is at most22in 96%\. PCP’s actual ratio never exceeds 1\.019, so the certificate is informative but conservative\.

#### 6\.1\.3Larger portfolios

For portfolios of up to 48 tasks, we compute PCP’s decisions from precomputed singleton and pair tables \(Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)\) and estimate expected costs by simulation\. The 56 instances cross the number of tasksn∈\{4,8,12,16,24,32,48\}n\\in\\\{4,8,12,16,24,32,48\\\}withb∈\{0,2\}b\\in\\\{0,2\\\},a∈\{0\.5,1\}a\\in\\\{0\.5,1\\\}, andp∈\{0\.3,0\.7\}p\\in\\\{0\.3,0\.7\\\}, withα=0\.8\\alpha=0\.8,c=0\.5c=0\.5, and random weights\. Every policy is simulated on the same 200 sample paths of availability and search outcomes, so that differences between policies are estimated precisely\.

Figure 5:Larger portfolios \(α=0\.8\\alpha=0\.8,c=0\.5c=0\.5, 200 common sample paths per instance\)\. \(a\) PCP’s mean saving relative to the singleton policy for each instance \(thin lines, colored by the amount of work\) and the mean over the eight instances of each size \(thick line\)\. \(b\) PCP’s saving relative to each policy, averaged over the instances of each size\.Figure[5](https://arxiv.org/html/2610.41129#S6.F5)shows that pricing shared attention becomes more valuable as the portfolio grows\. PCP’s saving relative to the singleton policy rises from 2\.3% with four tasks to 12\.1% with 48 tasks, and reaches 19\.9% in one instance\. More tasks compete for the human, so the congestion that the singleton policy ignores grows\. Consistent with Section[6\.1\.1](https://arxiv.org/html/2610.41129#S6.SS1.SSS1), PCP uses fewer answers than the singleton policy, by 0\.2 per portfolio with four tasks and 5\.1 with 48\. Its savings relative to Always Ask and Random\-order Ask also grow, to 59% and 74% with 48 tasks, and its saving relative to Search Once Then Ask stays between 25% and 30% at every size\.

PCP remains fast at this scale\. A decision takes about 1 ms for up to 12 tasks, 6 ms for 24 tasks, and 44 ms for 48 tasks on a personal computer with an Apple processor, after a one\-time construction of the tables that takes 1\.3 s for 48 tasks\.

#### 6\.1\.4Robustness to misestimated inputs

PCP uses the recoverabilitypp, the search success probabilityα\\alpha, and the availabilityaa, which a deployment would have to estimate\. To assess sensitivity, we build PCP and the singleton policy with wrong inputs and evaluate them exactly under the true parameters, for the 144 four\-task portfolios of the benchmark with the first weight draw\. With correct inputs, PCP’s mean gap on these portfolios is 0\.10%\. Halvingpp, multiplying it by1\.51\.5, multiplyingα\\alphaby0\.750\.75, or shiftingaaby±0\.2\\pm 0\.2raises PCP’s mean gap to at most 0\.74%, and its largest gap from 1\.76% to at most 10\.26%\. Across the same scenarios, the singleton policy’s mean gap ranges from 0\.53% to 4\.02%, and it is largest when recoverability is underestimated\. When availability is underestimated by 0\.2, the singleton policy does better than PCP, with a mean gap of 0\.53% against 0\.74% and a largest gap of 5\.79% against 10\.26%\. On average, PCP is robust to these estimation errors, but individual portfolios can lose up to 10\.3%\. Appendix[C\.7](https://arxiv.org/html/2610.41129#A3.SS7)reports every scenario\.

### 6\.2A case study with LLM agents

The experiments of Section[6\.1](https://arxiv.org/html/2610.41129#S6.SS1)simulate the outcomes of search and work\. Here, LLM agents carry out the tasks themselves\. The policies decide only when each agent searches, works, or asks, and which question the human answers\.

#### 6\.2\.1Design

Each task is a procurement decision\. The agent must choose the cheapest of four suppliers whose delivery time meets a maximum lead time that the person who delegated the task has not stated\. The task has two units of independent work, which do not need the missing requirement\. In the first, the agent extracts each supplier’s current approved quote from a list that also contains superseded quotes, drafts, and quotes for other purchases\. In the second, it computes each supplier’s landed cost\. A search gives the agent a packet of six documents about the purchase\. The packet contains the binding requirement only if the search succeeds, and its other documents are decoys, such as superseded revisions, drafts, supplier recommendations, and requirements of other purchases\. The agent must therefore judge whether the packet settles the requirement\. The human is scripted and returns the true requirement when it answers\. Once the requirement is known and the work is done, the agent chooses the supplier\. Every step of every agent is carried out bygpt\-6\.1\-sol, called through the Codex command\-line interface\. Each step is a separate call without tool use that receives only the data the step needs, including the agent’s own earlier outputs\.

We use portfolios of four tasks of weight one, two units of work per task,p=0\.3p=0\.3,α=0\.8\\alpha=0\.8,κi=0\.1\\kappa\_\{i\}=0\.1, andη=0\.5\\eta=0\.5, and cross the availabilitya∈\{0\.25,1\}a\\in\\\{0\.25,1\\\}with the search costc∈\{0\.1,1\.5\}c\\in\\\{0\.1,1\.5\\\}\. For each of the four settings, we draw ten portfolios and run PCP, the singleton policy, Always Ask, and Search Once Then Ask on each\. All policies face the same documents, the same outcome for each search attempt, and the same availability of the human in each period\. Appendix[C\.4](https://arxiv.org/html/2610.41129#A3.SS4)gives the documents, the prompt, and the execution protocol\.

#### 6\.2\.2Results

Table 2:Case study with LLM agents \(four tasks, ten portfolios per setting\)\. Mean cost, with the lowest in each setting in bold, and PCP’s mean saving \(%\) relative to each benchmark, with standard deviations across portfolios in parentheses\. Search Once denotes Search Once Then Ask\.The agents carried out every step correctly\. All 640 quote extractions, all 640 cost calculations, and all 640 supplier choices are correct, and the agents recognized all 91 successful searches and rejected all 276 packets without the binding requirement\. Because the agents always recognized whether a search had succeeded, the differences in cost between the policies come from coordination alone\. This follows from the design of the documents and does not test the assumption in general\.

Pricing shared attention matters only when the human is scarce and search is costly\. When the human is always available and search is costly, PCP, the singleton policy, and Always Ask ask every question without searching, one per period, so they cost the same in every portfolio\. When search is cheap, the singleton policy already searches often, and under the model PCP’s saving relative to the singleton policy averages 0\.0% per portfolio with an available human and 0\.6% with a scarce one\.

When the human is scarce and search is costly, PCP saves 11\.2% on average relative to the singleton policy, close to the average saving of 9\.4% that the model predicts \(Appendix[C\.4](https://arxiv.org/html/2610.41129#A3.SS4)\)\. The singleton policy never searches in this setting\. For a single agent, a search that costs1\.51\.5and succeeds with probability0\.240\.24is not worth its cost, so every agent waits for the human\. PCP searches 3\.6 times per portfolio and asks 3\.0 questions, against 4\.0 for the singleton policy, because a successful search also frees the human for the other agents\. This is the congestion effect of Section[6\.1\.1](https://arxiv.org/html/2610.41129#S6.SS1.SSS1), here with agents that must read the documents to learn whether a search has succeeded\.

The standard deviation of this saving is large \(27\.2%\), because the cost of a portfolio depends mainly on when the human happens to be available, and ten portfolios cover few of these histories\. Since the agents made no errors, every decision in the run can also be evaluated under the model\. In this setting, each decision of the singleton policy raises the expected cost by 1\.50 on average relative to the optimal decision, compared with 0\.011 for PCP\. Under the model, PCP’s advantage in this setting therefore does not hinge on the ten portfolios drawn\. Relative to the rules for when to ask, PCP saves 27\.2% and 23\.8% on average when the human is scarce and search is cheap\. Search Once Then Ask is the most expensive policy whenever the human is always available, because it delays questions that the human could answer at once\.

## 7Conclusion

As organizations delegate more work to AI agents, the attention of the people who oversee them becomes a shared and scarce resource\. We studied how agents should divide their effort between searching for missing information, continuing independent work, and asking a human whom they all share, and which waiting question the human should answer\.

Three insights emerge\. First, how often an agent asks is a poor measure of how well it uses human attention\. Useful independent work and withdrawable questions can both make optimal agents ask more, and withdrawal does so while lowering total cost\. Second, the value of a question depends on the whole portfolio\. Each answer delays the other tasks that wait for the human, and adding a task can reverse which of two others should be answered first\. Third, this congestion can be priced with small problems that are solved exactly\. PCP’s pairwise prices of attention lead agents to search more and ask less when the human is scarce\. On average, PCP is within a fraction of a percent of the optimal cost in small portfolios, and its saving relative to a policy that ignores congestion grows with the number of tasks\.

These insights bear directly on the design of agent systems\. Interfaces should let agents keep working and searching after they ask, and should let them withdraw questions that they resolve themselves\. Systems that run several agents for one person should coordinate their questions centrally and charge each question for the attention it consumes\. The case study shows that this coordination pays off when the person is rarely available and searching is costly, and matters little when the person answers at once\.

Our model has limitations that suggest directions for future work\. First, an agent never acts on a guessed requirement, and every answer and successful search is correct\. In practice, an agent can proceed on its best guess and redo work if the guess turns out wrong, and a record it retrieves can be outdated\. Adding an action that proceeds on a guess at the risk of rework, together with searches that can return a wrong requirement, would turn the decision to ask into a choice between preventing errors and repairing them\. Second, the human answers at most one question per period and is available independently over time\. People often check in for a session, answer several questions at once, and stay available for a while\. A model with sessions and persistent availability would make the timing of questions more strategic: questions should be ready when a session starts, and a human who has just become available is likely to remain so\. Third, PCP takes the recoverability, search success, and availability probabilities as known, and Section 6\.1\.4 shows that misestimating them, especially underestimating availability, can be costly in individual portfolios\. A controller that updates these estimates from observed searches and check\-ins would face a trade\-off between learning the parameters and acting on them\. On the theoretical side, an unconditional constant\-factor guarantee for portfolios in which search remains useful is still open\.

## References

- Baird and Maruping \(2021\)A\. Baird and L\. M\. MarupingThe next generation of research on IS use: a theoretical framework of delegation to and from agentic IS artifacts\.MIS Quarterly45\(1\),pp\. 315–341\.External Links:[Document](https://dx.doi.org/10.25300/MISQ/2021/15882),[Link](https://aisel.aisnet.org/misq/vol45/iss1/12/)Cited by:[§2\.1](https://arxiv.org/html/2610.41129#S2.SS1.p1.1)\.
- Boehmeret al\.\(2020\)W\. Boehmer, V\. Kurin, and S\. WhitesonDeep coordination graphs\.InProceedings of the 37th International Conference on Machine Learning,H\. Daumé and A\. Singh \(Eds\.\),Proceedings of Machine Learning Research, Vol\.119,pp\. 980–991\.External Links:[Link](https://proceedings.mlr.press/v119/boehmer20a.html)Cited by:[§2\.4](https://arxiv.org/html/2610.41129#S2.SS4.p1.1)\.
- Caiet al\.\(2022\)Y\. Cai, A\. Dahiya, N\. Wilde, and S\. L\. SmithScheduling operator assistance for shared autonomy in multi\-robot teams\.In2022 IEEE 61st Conference on Decision and Control \(CDC\),pp\. 3997–4003\.External Links:[Document](https://dx.doi.org/10.1109/CDC51059.2022.9993014),[Link](https://arxiv.org/abs/2209.03458)Cited by:[§2\.3](https://arxiv.org/html/2610.41129#S2.SS3.p1.1)\.
- Costenet al\.\(2024\)C\. Costen, A\. Gautier, N\. Hawes, and B\. LacerdaMulti\-robot allocation of assistance from a shared uncertain operator\.InProceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems,AAMAS ’24,pp\. 400–408\.External Links:[Link](https://www.ifaamas.org/Proceedings/aamas2024/pdfs/p400.pdf)Cited by:[§2\.3](https://arxiv.org/html/2610.41129#S2.SS3.p1.1)\.
- Dahiyaet al\.\(2022\)A\. Dahiya, N\. Akbarzadeh, A\. Mahajan, and S\. L\. SmithScalable operator allocation for multirobot assistance: a restless bandit approach\.IEEE Transactions on Control of Network Systems9\(3\),pp\. 1397–1408\.External Links:[Document](https://dx.doi.org/10.1109/TCNS.2022.3153872),[Link](https://cim.mcgill.ca/~adityam/projects/bandits/journal/multi-robot-assistance.pdf)Cited by:[§2\.3](https://arxiv.org/html/2610.41129#S2.SS3.p1.1),[§5\.1](https://arxiv.org/html/2610.41129#S5.SS1.p1.1)\.
- de Farias and Van Roy \(2003\)D\. P\. de Farias and B\. Van RoyThe linear programming approach to approximate dynamic programming\.Operations Research51\(6\),pp\. 850–865\.External Links:[Document](https://dx.doi.org/10.1287/opre.51.6.850.24925),[Link](https://pubsonline.informs.org/doi/10.1287/opre.51.6.850.24925)Cited by:[§2\.4](https://arxiv.org/html/2610.41129#S2.SS4.p1.1)\.
- Donget al\.\(2026\)Y\. R\. Dong, T\. Hu, Z\. Hui, C\. Zhang, I\. Vulić, A\. Bobu, and N\. CollierValue of information: a framework for human–agent communication\.InProceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 42879–42896\.External Links:[Link](https://aclanthology.org/2026.acl-long.1987/),[Document](https://dx.doi.org/10.18653/v1/2026.acl-long.1987),ISBN 979\-8\-89176\-390\-6Cited by:[§2\.2](https://arxiv.org/html/2610.41129#S2.SS2.p1.1)\.
- Edwards and Schuster \(2026\)N\. Edwards and S\. SchusterAsk or assume? uncertainty\-aware clarification\-seeking in coding agents\.Note:arXiv:2603\.26233, version 3, September 7, 2026; EMNLP 2026 camera\-ready versionExternal Links:2603\.26233,[Document](https://dx.doi.org/10.48550/arXiv.2603.26233),[Link](https://arxiv.org/abs/2603.26233v3)Cited by:[§2\.2](https://arxiv.org/html/2610.41129#S2.SS2.p1.1)\.
- Fügeneret al\.\(2022\)A\. Fügener, J\. Grahl, A\. Gupta, and W\. KetterCognitive challenges in human–artificial intelligence collaboration: investigating the path toward productive delegation\.Information Systems Research33\(2\),pp\. 678–696\.External Links:[Document](https://dx.doi.org/10.1287/isre.2021.1079),[Link](https://pubsonline.informs.org/doi/10.1287/isre.2021.1079)Cited by:[§2\.1](https://arxiv.org/html/2610.41129#S2.SS1.p1.1),[§3\.3](https://arxiv.org/html/2610.41129#S3.SS3.p2.2)\.
- Guestrinet al\.\(2003\)C\. Guestrin, D\. Koller, R\. Parr, and S\. VenkataramanEfficient solution algorithms for factored MDPs\.Journal of Artificial Intelligence Research19,pp\. 399–468\.External Links:[Document](https://dx.doi.org/10.1613/jair.1000),[Link](https://jair.org/index.php/jair/article/view/10341)Cited by:[§2\.4](https://arxiv.org/html/2610.41129#S2.SS4.p1.1)\.
- Guestrinet al\.\(2002\)C\. Guestrin, D\. Koller, and R\. ParrMultiagent planning with factored MDPs\.InAdvances in Neural Information Processing Systems,T\. G\. Dietterich, S\. Becker, and Z\. Ghahramani \(Eds\.\),Vol\.14,Cambridge, MA,pp\. 1523–1530\.Note:Proceedings of the 2001 conferenceExternal Links:[Link](https://proceedings.neurips.cc/paper/2001/hash/7af6266cc52234b5aa339b16695f7fc4-Abstract.html)Cited by:[§2\.4](https://arxiv.org/html/2610.41129#S2.SS4.p1.1)\.
- Gulatiet al\.\(2026\)A\. Gulati, H\. Gupta, E\. Lumer, S\. Sen, and V\. K\. SubbiahAsk early, ask late, ask right: when does clarification timing matter for long\-horizon agents?\.Note:arXiv preprint arXiv:2605\.07937, version 1, May 8, 2026External Links:2605\.07937,[Document](https://dx.doi.org/10.48550/arXiv.2605.07937),[Link](https://arxiv.org/abs/2605.07937v1)Cited by:[§2\.2](https://arxiv.org/html/2610.41129#S2.SS2.p1.1)\.
- Hansen \(2011\)E\. A\. HansenSuboptimality bounds for stochastic shortest path problems\.InProceedings of the 27th Conference on Uncertainty in Artificial Intelligence,F\. Cozman and A\. Pfeffer \(Eds\.\),pp\. 339–348\.External Links:[Link](https://proceedings.mlr.press/r9/hansen11a.html)Cited by:[§A\.6](https://arxiv.org/html/2610.41129#A1.SS6.SSS0.Px2.p2.1)\.
- Horvitz \(1999\)E\. HorvitzPrinciples of mixed\-initiative user interfaces\.InProceedings of the SIGCHI Conference on Human Factors in Computing Systems,CHI ’99,pp\. 159–166\.External Links:[Document](https://dx.doi.org/10.1145/302979.303030),[Link](https://doi.org/10.1145/302979.303030)Cited by:[§2\.1](https://arxiv.org/html/2610.41129#S2.SS1.p1.1)\.
- Johnstonet al\.\(2026\)D\. Johnston, D\. Holtz, A\. M\. Richmond, C\. Ong, P\. Tambe, and A\. ChatterjiThe shift to agentic AI: evidence from Codex\.Note:arXiv:2606\.26959, version 1, June 25External Links:[Document](https://dx.doi.org/10.48550/arXiv.2606.26959),[Link](https://arxiv.org/abs/2606.26959)Cited by:[§1](https://arxiv.org/html/2610.41129#S1.p1.1),[§1](https://arxiv.org/html/2610.41129#S1.p4.1),[§3\.1](https://arxiv.org/html/2610.41129#S3.SS1.p1.1)\.
- McKinsey \(2026\)McKinseyThe state of AI in 2026: on the road to ROI\.Note:Survey report, August 25\. Accessed October 22, 2026External Links:[Link](https://www.mckinsey.com/capabilities/quantumblack/our-insights/the-state-of-ai)Cited by:[§1](https://arxiv.org/html/2610.41129#S1.p1.1)\.
- Salesforce \(2025\)SalesforceDiscover OpenTable’s secret sauce to building AI agents that people actually want to use\.Note:Customer implementation account, August 6\. Accessed October 22, 2026External Links:[Link](https://www.salesforce.com/customer-stories/opentable-agentforce-implementation/)Cited by:[§1](https://arxiv.org/html/2610.41129#S1.p2.1)\.
- Scerriet al\.\(2002\)P\. Scerri, D\. V\. Pynadath, and M\. TambeTowards adjustable autonomy for the real world\.Journal of Artificial Intelligence Research17,pp\. 171–228\.External Links:[Document](https://dx.doi.org/10.1613/jair.1037),[Link](https://jair.org/index.php/jair/article/view/10312)Cited by:[§2\.1](https://arxiv.org/html/2610.41129#S2.SS1.p1.1)\.
- Smith \(1956\)W\. E\. SmithVarious optimizers for single\-stage production\.Naval Research Logistics Quarterly3\(1–2\),pp\. 59–66\.Cited by:[§2\.3](https://arxiv.org/html/2610.41129#S2.SS3.p1.1),[§5\.2](https://arxiv.org/html/2610.41129#S5.SS2.p2.1)\.
- Suriet al\.\(2026\)M\. Suri, P\. Mathur, N\. Lipka, F\. Dernoncourt, R\. A\. Rossi, and D\. ManochaStructured uncertainty guided clarification for LLM agents\.InFindings of the Association for Computational Linguistics: ACL 2026,M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),San Diego, California, United States,pp\. 40811–40838\.External Links:[Link](https://aclanthology.org/2026.findings-acl.2028/),[Document](https://dx.doi.org/10.18653/v1/2026.findings-acl.2028),ISBN 979\-8\-89176\-395\-1Cited by:[§2\.2](https://arxiv.org/html/2610.41129#S2.SS2.p1.1)\.
- Weitzman \(1979\)M\. L\. WeitzmanOptimal search for the best alternative\.Econometrica47\(3\),pp\. 641–654\.External Links:[Document](https://dx.doi.org/10.2307/1910412),[Link](https://www.jstor.org/stable/1910412)Cited by:[§2\.2](https://arxiv.org/html/2610.41129#S2.SS2.p1.1)\.
- Whittle \(1988\)P\. WhittleRestless bandits: activity allocation in a changing world\.Journal of Applied Probability25\(A\),pp\. 287–298\.External Links:[Document](https://dx.doi.org/10.2307/3214163),[Link](https://www.cambridge.org/core/journals/journal-of-applied-probability/article/abs/restless-bandits-activity-allocation-in-a-changing-world/DDEB5E22AFFEFF50AA97ADC96B71AE35)Cited by:[§2\.3](https://arxiv.org/html/2610.41129#S2.SS3.p1.1)\.
- Wilmerset al\.\(2026\)N\. Wilmers, R\. Catipon, M\. Massenkoff, and P\. McCroryHow employment is changing at Anthropic\.Note:Research report, October 16\. Accessed October 22, 2026External Links:[Link](https://www.anthropic.com/research/employment-at-anthropic)Cited by:[§1](https://arxiv.org/html/2610.41129#S1.p2.1)\.
- Zhang and Sun \(2026\)Y\. Zhang and T\. SunDecision science in the agentic era: research frontiers on agentic AI and human–agent collaboration\.Decision Sciences57\(5\),pp\. 391–405\.External Links:[Document](https://dx.doi.org/10.1111/deci.70037),[Link](https://onlinelibrary.wiley.com/doi/10.1111/deci.70037)Cited by:[§2\.1](https://arxiv.org/html/2610.41129#S2.SS1.p1.1)\.

## Appendix AAdditional Results and Discussion

This appendix collects results that complement the main text\. All proofs are in Appendix[B](https://arxiv.org/html/2610.41129#A2)\.

##### Conventions

All values are remaining costs from the displayed state, and fees paid earlier are sunk\. The delay cost of a period is charged to every task that is incomplete at its start, and work and resolution achieved during a period take effect at its end\. For a joint statess, let𝒜⁡\(s\)=\{i:zi≠R\}\\mathcal\{A\}\(s\)=\\\{i:z\_\{i\}\\neq R\\\}be the set of unresolved tasks,m=\|𝒜⁡\(s\)\|m=\|\\mathcal\{A\}\(s\)\|, andω⁡\(s\)=∑i​incompletewi\\omega\(s\)=\\sum\_\{i\\text\{ incomplete\}\}w\_\{i\}the delay cost incurred in the current period\. Unless stated otherwise, sums over pairsi<ji<jrun over unresolved tasks\. A state is terminal when every task is complete\.

### A\.1The reduced dynamic program

##### Beliefs

LetΛi​\(k\)=1−pi\+pi​\(1−αi\)k\\Lambda\_\{i\}\(k\)=1\-p\_\{i\}\+p\_\{i\}\(1\-\\alpha\_\{i\}\)^\{k\}be the probability that the firstkksearches of taskiifail, and let

βi​\(k\)=pi​\(1−αi\)kΛi​\(k\)\\beta\_\{i\}\(k\)=\\frac\{p\_\{i\}\(1\-\\alpha\_\{i\}\)^\{k\}\}\{\\Lambda\_\{i\}\(k\)\}\(A\.1\)be the posterior probability that its requirement is recoverable afterkkfailures\. The next\-search success probability \([1](https://arxiv.org/html/2610.41129#S3.E1)\) isqi​\(k\)=αi​βi​\(k\)q\_\{i\}\(k\)=\\alpha\_\{i\}\\beta\_\{i\}\(k\)\. Bothβi​\(k\)\\beta\_\{i\}\(k\)andqi​\(k\)q\_\{i\}\(k\)are nonincreasing inkk, andqi​\(k\)→0q\_\{i\}\(k\)\\to 0\(Lemma[B\.1](https://arxiv.org/html/2610.41129#A2.Thmlemma1)\)\. Because recoverability and search outcomes are independent across tasks, taskii’s future evolution depends on its history only through\(xi,ki,zi\)\(x\_\{i\},k\_\{i\},z\_\{i\}\), so the joint state is a sufficient statistic\.

##### Search caps

The next result shows that the caps of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(iii\) are sufficient\. Herebib\_\{i\}may be any upper bound on taskii’s remaining work, for example its initial amount\.

###### Proposition A\.1\(Sufficient search caps\)\.

For a portfolio ofnntasks with remaining work at mostbib\_\{i\}, let

Bmax=∑iwi​bi\+na​∑iwi\+∑iκi\+n​η,Mi=min⁡\{k≥0:qi​\(k\)​Bmax≤ci\}\.B\_\{\\max\}=\\sum\_\{i\}w\_\{i\}b\_\{i\}\+\\frac\{n\}\{a\}\\sum\_\{i\}w\_\{i\}\+\\sum\_\{i\}\\kappa\_\{i\}\+n\\eta,\\qquad M\_\{i\}=\\min\\\{k\\geq 0:q\_\{i\}\(k\)B\_\{\\max\}\\leq c\_\{i\}\\\}\.\(A\.2\)1. \(i\)EveryMiM\_\{i\}is finite, and0≤V∗​\(s\)≤Bmax0\\leq V^\{\*\}\(s\)\\leq B\_\{\\max\}at every state reachable from the initial state\.
2. \(ii\)Prohibiting every search of taskiiat failure countski≥Mik\_\{i\}\\geq M\_\{i\}, for allii, does not change the optimal value\. The same holds for any larger capsMi′≥MiM\_\{i\}^\{\\prime\}\\geq M\_\{i\}\.
3. \(iii\)For every subsetIIof tasks, the optimal value of the tasks inIIsharing one human, computed with the caps\(Mi\)i∈I\(M\_\{i\}\)\_\{i\\in I\}, equals its value without caps\.

Part \(iii\) is what allows PCP’s singleton and pair values to be computed with the caps of the full portfolio\. We call the model with the caps of Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)the*capped model*\. Its state space is finite:xi∈\{0,…,bi\}x\_\{i\}\\in\\\{0,\\ldots,b\_\{i\}\\\},ki∈\{0,…,Mi\}k\_\{i\}\\in\\\{0,\\ldots,M\_\{i\}\\\}, andzi∈\{U,P,R\}z\_\{i\}\\in\\\{U,P,R\\\}\.

##### Reduced plans

A period planddspecifies the question submitted at the start of the period, if any, and, for each availability outcome of positive probability, the question served, if any, and each agent’s action: search, work, or wait\. Letgd​\(s\)g\_\{d\}\(s\)be its expected immediate cost, which isω⁡\(s\)\\omega\(s\)plus the expected submission, search, and answer fees, and letPd​\(s,⋅\)P\_\{d\}\(s,\\cdot\)be its transition law\.

###### Definition A\.1\(Reduced plans\)\.

At an unfinished statessof the capped model,𝒟red​\(s\)\\mathcal\{D\}\_\{\\rm red\}\(s\)is the set of feasible plansddsuch that

1. \(a\)at most one new question is submitted, and a newly submitted question is served if the human is available;
2. \(b\)no agent searches while its question is being served;
3. \(c\)no task is searched at a failure countki≥Mik\_\{i\}\\geq M\_\{i\};
4. \(d\)in each availability outcome, every agent withxi\>0x\_\{i\}\>0performs one unit of work unless it searches\.

Let𝒟\+​\(s\)=\{d∈𝒟red​\(s\):Pd​\(s,s\)<1\}\\mathcal\{D\}\_\{\+\}\(s\)=\\\{d\\in\\mathcal\{D\}\_\{\\rm red\}\(s\):P\_\{d\}\(s,s\)<1\\\}\.

Rule \(d\) applies to every agent with work left: to agents whose question is being served, to agents with a pending or unsubmitted question, and to agents whose requirement is already resolved\. Human service is optional, and an agent without work may wait\. Rule \(a\) restricts new submissions, not the number of pending questions, because a question submitted in a period in which the human is unavailable remains pending\. The set𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)is nonempty at every unfinished state: if some task has work, every plan in𝒟red​\(s\)\\mathcal\{D\}\_\{\\rm red\}\(s\)changes the state\. Otherwise, submitting an unresolved task’s question, or serving it if it is already pending, changes the state with positive probability\.

##### The dynamic program

Define the integer rank

rk\(s\)=∑ixi\+∑i∈𝒜⁡\(s\)\[\(Mi−ki\)\+\+1\+𝟏\{zi=U\}\]\.\\mathrm\{rk\}\(s\)=\\sum\_\{i\}x\_\{i\}\+\\sum\_\{i\\in\\mathcal\{A\}\(s\)\}\\bigl\[\(M\_\{i\}\-k\_\{i\}\)^\{\+\}\+1\+\\mathbf\{1\}\\\{z\_\{i\}=U\\\}\\bigr\]\.\(A\.3\)
###### Proposition A\.2\(Ranked dynamic program\)\.

In the capped model, every transition that changes the state strictly decreasesrk\\mathrm\{rk\}\. The optimal value satisfiesV∗​\(s\)=0V^\{\*\}\(s\)=0at terminal states and, at every unfinished state,

V∗​\(s\)=mind∈𝒟\+​\(s\)⁡gd​\(s\)\+∑s′≠sPd​\(s,s′\)​V∗​\(s′\)1−Pd​\(s,s\)\.V^\{\*\}\(s\)=\\min\_\{d\\in\\mathcal\{D\}\_\{\+\}\(s\)\}\\frac\{g\_\{d\}\(s\)\+\\sum\_\{s^\{\\prime\}\\neq s\}P\_\{d\}\(s,s^\{\\prime\}\)V^\{\*\}\(s^\{\\prime\}\)\}\{1\-P\_\{d\}\(s,s\)\}\.\(A\.4\)This value equals the optimal value \([2](https://arxiv.org/html/2610.41129#S3.E2)\) of the original model, without caps and with unrestricted plans, and the recursion gives the same values if the minimum is taken over all feasible plans withPd​\(s,s\)<1P\_\{d\}\(s,s\)<1\. There is an optimal deterministic stationary policy that selects a plan of𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)at every unfinished state\. In particular, the three properties of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)hold simultaneously\.

Each ratio in \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\) is the expected cost of repeating plandduntil the state changes and then continuing optimally\. Because every distinct successor has lower rank, \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\) computesV∗V^\{\*\}by induction on rank, starting from terminal states\. From an initially unsubmitted portfolio, the induction has depthrk⁡\(s0\)=∑i\(bi\+Mi\+2\)\\mathrm\{rk\}\(s\_\{0\}\)=\\sum\_\{i\}\(b\_\{i\}\+M\_\{i\}\+2\)\.

##### The one\-period Bellman operator

For a functionLLon the capped state space, withL=0L=0at terminal states, define at unfinished states

\(𝒯​L\)​\(s\)=mind∈𝒟\+​\(s\)⁡\{gd​\(s\)\+Pd​L​\(s\)\},Pd​L​\(s\)=∑s′Pd​\(s,s′\)​L​\(s′\)\.\(\\mathcal\{T\}L\)\(s\)=\\min\_\{d\\in\\mathcal\{D\}\_\{\+\}\(s\)\}\\bigl\\\{g\_\{d\}\(s\)\+P\_\{d\}L\(s\)\\bigr\\\},\\qquad P\_\{d\}L\(s\)=\\sum\_\{s^\{\\prime\}\}P\_\{d\}\(s,s^\{\\prime\}\)L\(s^\{\\prime\}\)\.\(A\.5\)Unlike \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\), the operator𝒯\\mathcal\{T\}keeps the self\-transition\. It hasV∗V^\{\*\}as a fixed point, and PCP \([14](https://arxiv.org/html/2610.41129#S5.E14)\) and the Bellman defect \([15](https://arxiv.org/html/2610.41129#S5.E15)\) apply it to the pairwise approximation\.

### A\.2The complete policy for a blocked task

Consider one task with no work left and suppress its index\. LetVkUV^\{U\}\_\{k\}andVkPV^\{P\}\_\{k\}be the optimal values of the unsubmitted and pending states withkkfailures,\(0,k,U\)\(0,k,U\)and\(0,k,P\)\(0,k,P\), and letMMbe the cap of Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\. Define

W=η\+wa,Yk=c\+\(1−qk\)​Vk\+1P,ψk=w\+Yk−VkP−κ​qk,W=\\eta\+\\frac\{w\}\{a\},\\qquad Y\_\{k\}=c\+\(1\-q\_\{k\}\)V^\{P\}\_\{k\+1\},\\qquad\\psi\_\{k\}=w\+Y\_\{k\}\-V^\{P\}\_\{k\}\-\\kappa q\_\{k\},\(A\.6\)whereqk=q⁡\(k\)q\_\{k\}=q\(k\),VkP=WV^\{P\}\_\{k\}=Wfork≥Mk\\geq M, andYk=c\+\(1−qk\)​WY\_\{k\}=c\+\(1\-q\_\{k\}\)Wfork≥Mk\\geq M\. HereWWis the cost of waiting for the human without further search, because the expected wait is1/a1/aperiods\.YkY\_\{k\}is the cost of one more search from a pending state, including its continuation but excluding the current period’s delay cost, because a successful search completes a blocked task\. Finally,ψk\\psi\_\{k\}is the cost of searching once more and asking after a failure, minus the cost of asking now\.

###### Proposition A\.3\(Complete blocked\-task policy\)\.

For one task withx=0x=0:

1. \(i\)Pending values\.VkP=min⁡\{w\+Yk,w\+a​η\+\(1−a\)​Yk,W\}V^\{P\}\_\{k\}=\\min\\\{w\+Y\_\{k\},\\;w\+a\\eta\+\(1\-a\)Y\_\{k\},\\;W\\\}, and bothVkPV^\{P\}\_\{k\}andYkY\_\{k\}are nondecreasing inkk\.
2. \(ii\)Pending policy\.The following pending policy is optimal\. IfYk<ηY\_\{k\}<\\eta, search in both availability outcomes, declining available service\. Ifη≤Yk<W\\eta\\leq Y\_\{k\}<W, accept service when the human is available and search otherwise\. IfYk≥WY\_\{k\}\\geq W, accept service when available and wait otherwise\. The last regime holds exactly whenqk​W≤cq\_\{k\}W\\leq c\. At the boundaries, the adjacent plans tie\.
3. \(iii\)Asking threshold\.The sequenceψk\\psi\_\{k\}is nondecreasing on\{0,…,M\}\\\{0,\\ldots,M\\\}andψM≥w\>0\\psi\_\{M\}\\geq w\>0\. Withkask=min⁡\{k:ψk≥0\}≤Mk\_\{\\rm ask\}=\\min\\\{k:\\psi\_\{k\}\\geq 0\\\}\\leq M, the policy that searches while unsubmitted atk<kaskk<k\_\{\\rm ask\}and submits atk=kaskk=k\_\{\\rm ask\}is optimal\. Moreover,VkU=κ\+VkPV^\{U\}\_\{k\}=\\kappa\+V^\{P\}\_\{k\}fork≥kaskk\\geq k\_\{\\rm ask\}andVkU<κ\+VkPV^\{U\}\_\{k\}<\\kappa\+V^\{P\}\_\{k\}fork<kaskk<k\_\{\\rm ask\}\.
4. \(iv\)Ordering\.The pending policy does not depend onκ\\kappa, whereasψk\\psi\_\{k\}depends onκ\\kappaonly through−κ​qk\-\\kappa q\_\{k\}\. Ifp\>0p\>0and0<α<10<\\alpha<1, thenkask→∞k\_\{\\rm ask\}\\to\\inftyasκ→∞\\kappa\\to\\infty\. Conversely, there are parameters for whichkask=0k\_\{\\rm ask\}=0while a pending agent with no failures searches when the human is unavailable\.

Proposition[A\.3](https://arxiv.org/html/2610.41129#A1.Thmproposition3)completes Theorem[1](https://arxiv.org/html/2610.41129#Thmtheorem1)\. In the first regime of part \(ii\), a pending agent declines available service when one more search, together with its continuation, costs less than the answer fee\. BecauseYk≥cY\_\{k\}\\geq c, this requiresη\>c\\eta\>c\. BecauseYkY\_\{k\}is nondecreasing, a question that the agent is willing to have answered at one failure count remains so at every later count\. Under the submission rule of part \(iii\), therefore, declined service arises only for questions that are pending while search still looks promising, such as questions pending at the outset or questions submitted with a zero fee\.

The zero\-fee case also shows why Theorem[1](https://arxiv.org/html/2610.41129#Thmtheorem1)refers to a consistent choice at ties\. Ifκ=0\\kappa=0andYk<ηY\_\{k\}<\\eta, thenψk=0\\psi\_\{k\}=0, so submitting now and postponing submission are equally good, and the convention that resolves ties toward asking giveskask=0k\_\{\\rm ask\}=0\. The resulting policy submits a question and then declines its service, which violates Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(ii\)\. The alternative convention, which submits at the firstkkwithYk\>ηY\_\{k\}\>\\eta, is also optimal and satisfies Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(ii\)\. Both conventions are threshold policies\. Withκ\>0\\kappa\>0, submitting a question and then declining its available service in the same period is strictly dominated by postponing the submission\.

Part \(iii\) also giveskaskk\_\{\\rm ask\}explicitly as a function of the fee\. Wheneverqk\>0q\_\{k\}\>0,ψk≥0\\psi\_\{k\}\\geq 0is equivalent toκ≤tk\\kappa\\leq t\_\{k\}, wheretk=\(w\+Yk−VkP\)/qkt\_\{k\}=\(w\+Y\_\{k\}\-V^\{P\}\_\{k\}\)/q\_\{k\}does not depend onκ\\kappa\. Wheneverqk=0q\_\{k\}=0, which happens for everykkifp=0p=0and fork≥1k\\geq 1ifα=1\\alpha=1,ψk=w\+Yk−VkP≥0\\psi\_\{k\}=w\+Y\_\{k\}\-V^\{P\}\_\{k\}\\geq 0for every fee, becauseVkP≤w\+YkV^\{P\}\_\{k\}\\leq w\+Y\_\{k\}by part \(i\), and we settk=\+∞t\_\{k\}=\+\\infty\. With this convention,kask=min⁡\{k:κ≤tk\}k\_\{\\rm ask\}=\\min\\\{k:\\kappa\\leq t\_\{k\}\\\}\. For the example after Theorem[1](https://arxiv.org/html/2610.41129#Thmtheorem1), withw=η=1w=\\eta=1,a=0\.5a=0\.5,c=0\.1c=0\.1,p=0\.6p=0\.6, andα=0\.5\\alpha=0\.5, the recursion of part \(i\) gives\(t0,…,t6\)≈\(1\.60,3\.06,5\.96,11\.72,23\.00,46\.13,93\.07\)\(t\_\{0\},\\ldots,t\_\{6\}\)\\approx\(1\.60,\\,3\.06,\\,5\.96,\\,11\.72,\\,23\.00,\\,46\.13,\\,93\.07\), which reproduces the values ofkaskk\_\{\\rm ask\}reported there\. The pending threshold follows from part \(ii\):q4​W≈0\.129\>c\>q5​W≈0\.067q\_\{4\}W\\approx 0\.129\>c\>q\_\{5\}W\\approx 0\.067\.

Part \(iv\) is the formal version of the statement that the two thresholds have no universal ordering\. The example after Theorem[1](https://arxiv.org/html/2610.41129#Thmtheorem1)shows both orders: a large submission fee raiseskaskk\_\{\\rm ask\}above the pending search threshold, and a small one giveskask=0k\_\{\\rm ask\}=0while a pending agent keeps searching\. Appendix[B\.3](https://arxiv.org/html/2610.41129#A2.SS3)gives a second example of the latter order\.

### A\.3Implementing the Pairwise Coordination Policy

##### Value tables

PCP uses the valuesVi​\(si\)V\_\{i\}\(s\_\{i\}\)andVi​j​\(si,sj\)V\_\{ij\}\(s\_\{i\},s\_\{j\}\)of one\- and two\-task portfolios, computed by \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\) with the caps of the full portfolio\. By Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\(iii\), these caps preserve the optimum of each subproblem, so the tables are exact optimal values and carry no truncation error\. A resolved task hasVi​\(xi,ki,R\)=wi​xiV\_\{i\}\(x\_\{i\},k\_\{i\},R\)=w\_\{i\}x\_\{i\}, and its pair value with any other task is additive, because its remaining work uses only its own agent\. Hence, withCR​\(s\)=∑i∉𝒜⁡\(s\)wi​xiC\_\{R\}\(s\)=\\sum\_\{i\\notin\\mathcal\{A\}\(s\)\}w\_\{i\}x\_\{i\},

V^PCP​\(s\)=CR​\(s\)\+∑i∈𝒜⁡\(s\)Vi​\(si\)\+∑i<ji,j∈𝒜⁡\(s\)Δi​j​\(si,sj\),\\widehat\{V\}\_\{\\rm PCP\}\(s\)=C\_\{R\}\(s\)\+\\sum\_\{i\\in\\mathcal\{A\}\(s\)\}V\_\{i\}\(s\_\{i\}\)\+\\sum\_\{\\begin\{subarray\}\{c\}i<j\\\\ i,j\\in\\mathcal\{A\}\(s\)\\end\{subarray\}\}\\Delta\_\{ij\}\(s\_\{i\},s\_\{j\}\),\(A\.7\)and only pairs of unresolved tasks require tables\. The tables can be computed lazily at the states PCP visits and stored for reuse\. In each availability outcome, the next states of distinct tasks are conditionally independent, and each takes at most two values\. Evaluatinggd​\(s\)\+Pd​V^PCP​\(s\)g\_\{d\}\(s\)\+P\_\{d\}\\widehat\{V\}\_\{\\rm PCP\}\(s\)for one plan therefore needs only the marginal law of each task and of each pair, which takesO⁡\(n2\)O\(n^\{2\}\)table lookups\.

##### The progress guard

PCP restricts its minimization in \([14](https://arxiv.org/html/2610.41129#S5.E14)\) to𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\), which excludes plans that leave the state unchanged with probability one\. The next lemma shows that this restriction alone ensures that PCP, and any other selector that respects it, completes the portfolio in finite expected time\. Let

εa=\{min⁡\{a,1−a\},0<a<1,1,a=1\.\\varepsilon\_\{a\}=\\begin\{cases\}\\min\\\{a,1\-a\\\},&0<a<1,\\\\ 1,&a=1\.\\end\{cases\}\(A\.8\)
###### Lemma A\.1\(Progress guard\)\.

Every plan in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)changes the state with probability at leastεa\\varepsilon\_\{a\}\. Consequently, under any policy, possibly history dependent or randomized, that selects a plan in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)at every unfinished statess, the expected time until all tasks are complete is at mostrk⁡\(s\)/εa\\mathrm\{rk\}\(s\)/\\varepsilon\_\{a\}, and the expected total cost is finite\.

##### Coordinate search

The number of plans in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)grows exponentially innn, because each agent chooses between search and work in each availability outcome\. Given the submission decision, the objective in \([14](https://arxiv.org/html/2610.41129#S5.E14)\) is the probability\-weighted sum of two terms, one for each availability outcome, so the two outcomes can be optimized separately\. The progress guard couples them only through the requirement that at least one outcome change the state, which can be handled by retaining, for each outcome, the best candidate that changes the state and the best candidate that does not\. Our implementation enumerates the submission decision: no submission, or the question of one unsubmitted task\. For each submission decision and availability outcome, it optimizes the remaining choices by coordinate search from two deterministic starting plans, one in which no agent searches and one in which every eligible agent searches\. Each sweep optimizes the service choice over all eligible questions and then each agent’s search\-or\-work choice in turn\. The reference implementation uses two sweeps\. It then selects the best combination of the visited candidates that satisfies the guard\. Plans whose objectives exceed the minimummmby at most the absolute toleranceτ⁡\(s\)=10−12​max⁡\{1,\|m\|\}\\tau\(s\)=10^\{\-12\}\\max\\\{1,\|m\|\\\}are treated as tied\. Among tied plans, PCP prefers a plan that serves a question, then a plan that submits a question, then a plan with fewer searches, and finally the first plan in a fixed order of task indices\. We call this the*service\-preferring*rule\. The*no\-submission*rule, used for comparison, prefers no submission and then no service among tied plans\. Appendix[C](https://arxiv.org/html/2610.41129#A3)reports the settings used in each experiment\.

Coordinate search need not find a minimizer of \([14](https://arxiv.org/html/2610.41129#S5.E14)\), so results that assume exact minimization apply to it only where its candidates include a minimizer\. One case is important: in the human\-resolution regime of Appendix[A\.4](https://arxiv.org/html/2610.41129#A1.SS4), no search choices remain, and a sweep that tries every eligible service choice evaluates every plan in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)\. Because of the tolerance, the selected plan is then withinτ⁡\(s\)\\tau\(s\)of the minimum\. This does not affect Lemma[A\.3](https://arxiv.org/html/2610.41129#A1.Thmlemma3)or Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\) as long as, at every state visited,τ⁡\(s\)\\tau\(s\)is smaller than the weight of every unresolved task and every positive difference between the weights of two unresolved tasks, because the objective differences used in their proofs are at least that large \(Appendix[B\.9](https://arxiv.org/html/2610.41129#A2.SS9)\)\. The condition concerns the absolute toleranceτ⁡\(s\)\\tau\(s\), which grows with the objective, not the factor10−1210^\{\-12\}\. In our experiments every objective is below10510^\{5\}, soτ⁡\(s\)<10−7\\tau\(s\)<10^\{\-7\}, whereas every weight and every positive difference between two weights is at least0\.50\.5\. Appendix[A\.6](https://arxiv.org/html/2610.41129#A1.SS6)quantifies the effect of inexact minimization in general, and Appendix[A\.5](https://arxiv.org/html/2610.41129#A1.SS5)shows that the tie rule matters\.

### A\.4The price of attention when human service is unavoidable

We say that a statessis in the*human\-resolution regime*if no unresolved task has an admissible search, that is,ki≥Mik\_\{i\}\\geq M\_\{i\}for everyi∈𝒜⁡\(s\)i\\in\\mathcal\{A\}\(s\)\. Becauseqi​\(ki\)=0q\_\{i\}\(k\_\{i\}\)=0implieski≥Mik\_\{i\}\\geq M\_\{i\}, the regime contains every state at which no remaining search can succeed, which is the setting of Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\)\. The proof of the theorem uses only that no admissible search remains, so the theorem, like every result in this subsection, holds throughout the regime\. In this regime, every unresolved task needs exactly one human answer, every agent works until its work is finished, and the regime is invariant\. Throughout this subsection, writea¯=1−a\\bar\{a\}=1\-a, with the convention00=10^\{0\}=1whena=1a=1, letfi=η\+κi𝟏\{zi=U\}f\_\{i\}=\\eta\+\\kappa\_\{i\}\\mathbf\{1\}\\\{z\_\{i\}=U\\\}be taskii’s unpaid fees, and letGGbe a geometric random variable on\{1,2,…\}\\\{1,2,\\ldots\\\}with success probabilityaa\.

###### Lemma A\.2\(Singleton and pair values\)\.

In the human\-resolution regime, for unresolved tasksiiandjj,

Vi​\(si\)\\displaystyle V\_\{i\}\(s\_\{i\}\)=fi\+wi​\(xi\+a¯xia\),\\displaystyle=f\_\{i\}\+w\_\{i\}\\left\(x\_\{i\}\+\\frac\{\\bar\{a\}^\{x\_\{i\}\}\}\{a\}\\right\),\(A\.9\)Δi​j​\(si,sj\)\\displaystyle\\Delta\_\{ij\}\(s\_\{i\},s\_\{j\}\)=1a​𝔼​\[min⁡\{wi​a¯\(xi−G\)\+,wj​a¯\(xj−G\)\+\}\]\.\\displaystyle=\\frac\{1\}\{a\}\\,\\mathbb\{E\}\\\!\\left\[\\min\\Bigl\\\{w\_\{i\}\\bar\{a\}^\{\(x\_\{i\}\-G\)^\{\+\}\},\\;w\_\{j\}\\bar\{a\}^\{\(x\_\{j\}\-G\)^\{\+\}\}\\Bigr\\\}\\right\]\.\(A\.10\)The priceΔi​j\\Delta\_\{ij\}is nondecreasing in each task’s weight, nonincreasing in each task’s remaining work, and satisfies0≤Δi​j≤min⁡\(wi,wj\)/a0\\leq\\Delta\_\{ij\}\\leq\\min\(w\_\{i\},w\_\{j\}\)/a, with equality on the right whenxi,xj≤1x\_\{i\},x\_\{j\}\\leq 1\. Whena=1a=1,Δi​j=min⁡\(wi,wj\)​𝟏​\{xi≤1,xj≤1\}\\Delta\_\{ij\}=\\min\(w\_\{i\},w\_\{j\}\)\\mathbf\{1\}\\\{x\_\{i\}\\leq 1,\\ x\_\{j\}\\leq 1\\\}\.

The termwi​a¯\(xi−t\)\+/aw\_\{i\}\\bar\{a\}^\{\(x\_\{i\}\-t\)^\{\+\}\}/ain \([A\.10](https://arxiv.org/html/2610.41129#A1.E10)\) is the expected additional delay cost of taskiiif its answer is postponed from the first available periodttto the next one: postponement matters only if the next opportunity arrives after taskii’s work is finished, which happens with probabilitya¯\(xi−t\)\+\\bar\{a\}^\{\(x\_\{i\}\-t\)^\{\+\}\}\. The pairwise price of attention is the expected cost of postponing the cheaper of the two tasks\. Independent work therefore hides congestion: the more work both tasks have, the more likely the human can answer both before either task needs its answer\. Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3)’s pricemin⁡\(wi,wj\)/a\\min\(w\_\{i\},w\_\{j\}\)/ais the case in which neither task has more than one unit of work\. Appendix[A\.5](https://arxiv.org/html/2610.41129#A1.SS5)shows that, whena=1a=1, this can hide a bottleneck that only groups of three or more tasks create\.

The next lemma formalizes the property of PCP described after Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\.

###### Lemma A\.3\(PCP service priorities\)\.

Letssbe in the human\-resolution regime, and let PCP select an exact minimizer of \([14](https://arxiv.org/html/2610.41129#S5.E14)\) with any tie rule\. If some unresolved taskiihasxi≤1x\_\{i\}\\leq 1, then PCP serves a question whenever the human is available, and every taskjjit serves satisfieswj≥wiw\_\{j\}\\geq w\_\{i\}\.

The proof of Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\) also yields a sharper, interpolating form of the factor\-two bound\.

###### Corollary A\.1\(Interpolating bound and an exact boundary\)\.

In the human\-resolution regime, letKK,BB,QQ, andw𝒜w\_\{\\mathcal\{A\}\}be as in Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\), and let PCP select exact minimizers\. Then

JPCP​\(s\)V∗​\(s\)≤1\+min⁡\{B,Q\}−w𝒜K\+max⁡\{B,Q\}≤2\.\\frac\{J^\{\\rm PCP\}\(s\)\}\{V^\{\*\}\(s\)\}\\leq 1\+\\frac\{\\min\\\{B,Q\\\}\-w\_\{\\mathcal\{A\}\}\}\{K\+\\max\\\{B,Q\\\}\}\\leq 2\.\(A\.11\)If, in addition,xi≤1x\_\{i\}\\leq 1for every unresolved task, thenV^PCP​\(s\)=V∗​\(s\)=K\+Q\\widehat\{V\}\_\{\\rm PCP\}\(s\)=V^\{\*\}\(s\)=K\+Q, and PCP is optimal fromss\.

The ratio bound in \([A\.11](https://arxiv.org/html/2610.41129#A1.E11)\) is close to one when either independent work \(BB\) or congestion \(QQ\) dominates, and it can approach two only whenBBandQQare comparable and both are large relative toKKandw𝒜w\_\{\\mathcal\{A\}\}\. Hard instances for pairwise prices therefore balance work against congestion, as in the family of Appendix[A\.5](https://arxiv.org/html/2610.41129#A1.SS5)\. The second statement extends the exact boundary of Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3)from tasks without work to tasks with at most one unit of work, because an answer received in the next available period overlaps that unit\.

### A\.5Tie\-breaking and a golden\-ratio example

Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\) holds for every tie rule\. The next lemma shows that ties can nonetheless matter, because the pairwise approximation can assign the same value to serving a question now and serving it later\.

###### Lemma A\.4\(Homogeneous portfolios\)\.

Considern≥2n\\geq 2initially unsubmitted tasks withwi=1w\_\{i\}=1, common workbi=bb\_\{i\}=b, andpi=0p\_\{i\}=0, and leta=1a=1andκi=η=0\\kappa\_\{i\}=\\eta=0\. Let PCP use the no\-submission tie rule of Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)\. Then

V∗=∑j=1nmax⁡\{b,j\},JPCP=\{n⁡\(n\+1\)/2,b≤1,n​b\+\(n−1\)​\(n−2\)/2,b≥2\.V^\{\*\}=\\sum\_\{j=1\}^\{n\}\\max\\\{b,j\\\},\\qquad J^\{\\rm PCP\}=\\begin\{cases\}n\(n\+1\)/2,&b\\leq 1,\\\\ nb\+\(n\-1\)\(n\-2\)/2,&b\\geq 2\.\\end\{cases\}\(A\.12\)On this class,JPCP/V∗≤φ=\(1\+5\)/2J^\{\\rm PCP\}/V^\{\*\}\\leq\\varphi=\(1\+\\sqrt\{5\}\)/2, and the ratio tends toφ\\varphialongb=⌊n/φ⌋b=\\lfloor n/\\varphi\\rfloorasn→∞n\\to\\infty\. PCP with any tie rule that prefers, among tied plans, a plan that serves a question, including the service\-preferring rule, is optimal on this class\.

For example, withn=12n=12andb=9b=9, the optimal cost is114114, whereas PCP with the no\-submission rule costs163163, about 43% more\. Every pair of tasks can be answered within its remaining work, so every pairwise price at the next state is zero until two units of work remain, and serving a question early has the same value as waiting\. The no\-submission rule then postpones all questions until the prices turn positive, at which point the human can no longer keep up\. The bottleneck is visible only to groups of three or more tasks\. For the no\-submission rule, no factor smaller thanφ\\varphican therefore replace the factor two of Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\)\. We do not know whether the factor two is tight for the service\-preferring rule or for any other tie rule\.

### A\.6The pairwise Bellman defect

This subsection analyzes Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(ii\)\. Let𝒮\\mathcal\{S\}be a finite set of states of the capped model that contains the initial state and is*forward closed*: for every unfinisheds∈𝒮s\\in\\mathcal\{S\}and everyd∈𝒟\+​\(s\)d\\in\\mathcal\{D\}\_\{\+\}\(s\), everys′s^\{\\prime\}withPd​\(s,s′\)\>0P\_\{d\}\(s,s^\{\\prime\}\)\>0belongs to𝒮\\mathcal\{S\}\. The set of all capped states reachable from the initial state is forward closed\. WriteH=V^PCPH=\\widehat\{V\}\_\{\\rm PCP\}, withH=0H=0at terminal states, so thatρ=𝒯​H−H\\rho=\\mathcal\{T\}H\-Hby \([15](https://arxiv.org/html/2610.41129#S5.E15)\) and \([A\.5](https://arxiv.org/html/2610.41129#A1.E5)\)\. For a selectorπ\\pithat choosesπ​\(s\)∈𝒟\+​\(s\)\\pi\(s\)\\in\\mathcal\{D\}\_\{\+\}\(s\), for example coordinate search, define the selection error

eπ​\(s\)=gπ⁡\(s\)​\(s\)\+Pπ⁡\(s\)​H​\(s\)−\(𝒯​H\)​\(s\)≥0\.e\_\{\\pi\}\(s\)=g\_\{\\pi\(s\)\}\(s\)\+P\_\{\\pi\(s\)\}H\(s\)\-\(\\mathcal\{T\}H\)\(s\)\\geq 0\.\(A\.13\)Exact PCP haseπ≡0e\_\{\\pi\}\\equiv 0\.

##### Decomposition

Allocate a plan’s expected immediate cost to tasks by

gid​\(s\)=wi​𝟏​\{i​incomplete\}\+ci​Prd​\{i​searches\}\+κi​𝟏​\{i​submits\}\+η​Prd​\{i​is served\},g\_\{i\}^\{d\}\(s\)=w\_\{i\}\\mathbf\{1\}\\\{i\\text\{ incomplete\}\\\}\+c\_\{i\}\\Pr\_\{d\}\\\{i\\text\{ searches\}\\\}\+\\kappa\_\{i\}\\mathbf\{1\}\\\{i\\text\{ submits\}\\\}\+\\eta\\Pr\_\{d\}\\\{i\\text\{ is served\}\\\},so that∑igid=gd\\sum\_\{i\}g\_\{i\}^\{d\}=g\_\{d\}\. Define the singleton and pair regrets of plandd,

λid​\(s\)\\displaystyle\\lambda\_\{i\}^\{d\}\(s\)=gid​\(s\)\+𝔼d​\[Vi​\(Si′\)\]−Vi​\(si\),\\displaystyle=g\_\{i\}^\{d\}\(s\)\+\\mathbb\{E\}\_\{d\}\[V\_\{i\}\(S^\{\\prime\}\_\{i\}\)\]\-V\_\{i\}\(s\_\{i\}\),λi​jd​\(s\)\\displaystyle\\lambda\_\{ij\}^\{d\}\(s\)=gid​\(s\)\+gjd​\(s\)\+𝔼d​\[Vi​j​\(Si′,Sj′\)\]−Vi​j​\(si,sj\)\.\\displaystyle=g\_\{i\}^\{d\}\(s\)\+g\_\{j\}^\{d\}\(s\)\+\\mathbb\{E\}\_\{d\}\[V\_\{ij\}\(S^\{\\prime\}\_\{i\},S^\{\\prime\}\_\{j\}\)\]\-V\_\{ij\}\(s\_\{i\},s\_\{j\}\)\.
###### Lemma A\.5\(Pairwise decomposition of the Bellman defect\)\.

Everyλid\\lambda\_\{i\}^\{d\}andλi​jd\\lambda\_\{ij\}^\{d\}is nonnegative\. Withnnthe total number of tasks, including resolved ones,

gd\+Pd​H−H=∑i<jλi​jd−\(n−2\)​∑iλid,g\_\{d\}\+P\_\{d\}H\-H=\\sum\_\{i<j\}\\lambda\_\{ij\}^\{d\}\-\(n\-2\)\\sum\_\{i\}\\lambda\_\{i\}^\{d\},\(A\.14\)where the sums run over all tasks\. Equivalently, withm=\|𝒜⁡\(s\)\|m=\|\\mathcal\{A\}\(s\)\|,

ρ⁡\(s\)=mind∈𝒟\+​\(s\)⁡\{∑i<ji,j∈𝒜⁡\(s\)λi​jd​\(s\)−\(m−2\)​∑i∈𝒜⁡\(s\)λid​\(s\)\},\\rho\(s\)=\\min\_\{d\\in\\mathcal\{D\}\_\{\+\}\(s\)\}\\left\\\{\\sum\_\{\\begin\{subarray\}\{c\}i<j\\\\ i,j\\in\\mathcal\{A\}\(s\)\\end\{subarray\}\}\\lambda\_\{ij\}^\{d\}\(s\)\-\(m\-2\)\\sum\_\{i\\in\\mathcal\{A\}\(s\)\}\\lambda\_\{i\}^\{d\}\(s\)\\right\\\},\(A\.15\)where an empty sum is zero\.

The regretλid\\lambda\_\{i\}^\{d\}measures how much worse plandd, projected onto taskii, is than an optimal decision for taskiiif it had a human of its own, andλi​jd\\lambda\_\{ij\}^\{d\}is the analogous regret in the two\-task problem\. The defect is small when a single portfolio plan is nearly optimal for every pair problem at once, after the singleton regrets, each of which appears inm−1m\-1pair regrets, are netted out\. It is computed from the singleton and pair tables and one\-period plans only\. Whenm≤2m\\leq 2, the defect is zero\.

##### A guarantee with approximate selection

The next result extends Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(ii\) to selectors that only approximate the minimization in \([14](https://arxiv.org/html/2610.41129#S5.E14)\), and it separates the two halves of condition \([17](https://arxiv.org/html/2610.41129#S5.E17)\)\.

###### Proposition A\.4\(Defect guarantee with approximate selection\)\.

Letϵ\+,ϵ−,δ≥0\\epsilon\_\{\+\},\\epsilon\_\{\-\},\\delta\\geq 0withϵ\+\+δ<1\\epsilon\_\{\+\}\+\\delta<1\.

1. \(i\)Ifρ⁡\(s\)\+eπ​\(s\)≤\(ϵ\+\+δ\)​ω​\(s\)\\rho\(s\)\+e\_\{\\pi\}\(s\)\\leq\(\\epsilon\_\{\+\}\+\\delta\)\\,\\omega\(s\)at every unfinished state reachable froms0s\_\{0\}underπ\\pi, thenJπ​\(s0\)≤H⁡\(s0\)/\(1−ϵ\+−δ\)J^\{\\pi\}\(s\_\{0\}\)\\leq H\(s\_\{0\}\)/\(1\-\\epsilon\_\{\+\}\-\\delta\)\.
2. \(ii\)Ifρ⁡\(s\)≥−ϵ−​ω​\(s\)\\rho\(s\)\\geq\-\\epsilon\_\{\-\}\\,\\omega\(s\)at every unfinished state of a forward\-closed set𝒮\\mathcal\{S\}containings0s\_\{0\}, thenH⁡\(s0\)≤\(1\+ϵ−\)​V∗​\(s0\)H\(s\_\{0\}\)\\leq\(1\+\\epsilon\_\{\-\}\)V^\{\*\}\(s\_\{0\}\)\.

In particular, if−ϵ−​ω≤ρ≤ϵ\+​ω\-\\epsilon\_\{\-\}\\omega\\leq\\rho\\leq\\epsilon\_\{\+\}\\omegaandeπ≤δ​ωe\_\{\\pi\}\\leq\\delta\\omegaat every unfinished state of𝒮\\mathcal\{S\}, then

Jπ​\(s0\)≤H⁡\(s0\)1−ϵ\+−δ≤1\+ϵ−1−ϵ\+−δ​V∗​\(s0\)\.J^\{\\pi\}\(s\_\{0\}\)\\leq\\frac\{H\(s\_\{0\}\)\}\{1\-\\epsilon\_\{\+\}\-\\delta\}\\leq\\frac\{1\+\\epsilon\_\{\-\}\}\{1\-\\epsilon\_\{\+\}\-\\delta\}\\,V^\{\*\}\(s\_\{0\}\)\.\(A\.16\)Exact PCP hasδ=0\\delta=0, which gives Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(ii\)\.

Part \(i\) controls the policy\. Its condition involves no minimization, becauseρ\+eπ=gπ⁡\(s\)\+Pπ⁡\(s\)​H−H\\rho\+e\_\{\\pi\}=g\_\{\\pi\(s\)\}\+P\_\{\\pi\(s\)\}H\-H, and it needs to hold only at the states the selector reaches\. Part \(ii\) compares the approximation with the optimum\. An optimal policy may visit states that PCP never reaches, so part \(ii\) requires the lower condition on a forward\-closed set\. Checking it uses neitherV∗V^\{\*\}nor the cost of PCP, but it requiresρ⁡\(s\)\\rho\(s\)at every state of such a set, which costs about as much as exact dynamic programming\. Both conditions are sufficient, and the model does not guarantee them\. Bounds of this type, which control a greedy policy through the Bellman residual of its value approximation, are standard for stochastic shortest\-path problems\([Hansen, 2011](https://arxiv.org/html/2610.41129#bib.bib17), e\.g\.,\)\.

## Appendix BProofs

This appendix gives proofs for the main\-text results in order of appearance, together with proofs of the related results in Appendix[A](https://arxiv.org/html/2610.41129#A1)\. Appendix[B\.1](https://arxiv.org/html/2610.41129#A2.SS1)collects two facts about beliefs used in several proofs\. The conventions of Appendix[A](https://arxiv.org/html/2610.41129#A1)apply throughout\.

### B\.1Belief dynamics

###### Lemma B\.1\(Posterior beliefs\)\.

For a task withp<1p<1andα∈\(0,1\]\\alpha\\in\(0,1\],β⁡\(k\)\\beta\(k\)in \([A\.1](https://arxiv.org/html/2610.41129#A1.E1)\) is the posterior probability that the requirement is recoverable afterkkfailed searches, andq⁡\(k\)=α​β​\(k\)q\(k\)=\\alpha\\beta\(k\)is the success probability of the next search\. Moreover,

β⁡\(k\+1\)=β​\(k\)​\(1−α\)1−α​β​\(k\)≤β⁡\(k\),\\beta\(k\+1\)=\\frac\{\\beta\(k\)\(1\-\\alpha\)\}\{1\-\\alpha\\beta\(k\)\}\\leq\\beta\(k\),soβ⁡\(k\)\\beta\(k\)andq⁡\(k\)q\(k\)are nonincreasing inkk, andq⁡\(k\)→0q\(k\)\\to 0ask→∞k\\to\\infty\.

###### Proof\.

Letχ∈\{0,1\}\\chi\\in\\\{0,1\\\}indicate recoverability\. Conditional onχ=1\\chi=1, the firstkksearches fail with probability\(1−α\)k\(1\-\\alpha\)^\{k\}; conditional onχ=0\\chi=0, they fail with probability one\. Bayes’ rule givesβ⁡\(k\)=p​\(1−α\)k/Λ⁡\(k\)\\beta\(k\)=p\(1\-\\alpha\)^\{k\}/\\Lambda\(k\), and the next search succeeds with probabilityα​β​\(k\)\\alpha\\beta\(k\), which is \([1](https://arxiv.org/html/2610.41129#S3.E1)\)\. Applying Bayes’ rule to one more failure gives the displayed recursion\. Its denominator satisfies1−α​β​\(k\)≥1−β⁡\(k\)=\(1−p\)/Λ⁡\(k\)\>01\-\\alpha\\beta\(k\)\\geq 1\-\\beta\(k\)=\(1\-p\)/\\Lambda\(k\)\>0, and1−α≤1−α​β​\(k\)1\-\\alpha\\leq 1\-\\alpha\\beta\(k\)gives the inequality\. Finally,Λ⁡\(k\)≥1−p\>0\\Lambda\(k\)\\geq 1\-p\>0and\(1−α\)k→0\(1\-\\alpha\)^\{k\}\\to 0, soβ⁡\(k\)→0\\beta\(k\)\\to 0andq⁡\(k\)→0q\(k\)\\to 0\. ∎

Because search outcomes are conditionally independent given recoverability, a task withkkfailures evolves exactly like a fresh task with priorβ⁡\(k\)\\beta\(k\)and the sameα\\alpha\. The next lemma shows that a more optimistic belief cannot hurt\.

###### Lemma B\.2\(Optimism cannot hurt\)\.

Consider two portfolios that are identical except that taskii’s posterior recoverability probability isβ\+\\beta\_\{\+\}in the first andβ−≤β\+\\beta\_\{\-\}\\leq\\beta\_\{\+\}in the second\. Then the optimal value of the first portfolio is at most that of the second\. The same holds for the truncated problems of Appendix[B\.2](https://arxiv.org/html/2610.41129#A2.SS2)\. In particular, ifssands′s^\{\\prime\}differ only in that taskiihaskik\_\{i\}failures inssandki\+1k\_\{i\}\+1ins′s^\{\\prime\}, thenV∗​\(s\)≤V∗​\(s′\)V^\{\*\}\(s\)\\leq V^\{\*\}\(s^\{\\prime\}\)\.

###### Proof\.

Ifβ\+=0\\beta\_\{\+\}=0, thenβ−=0\\beta\_\{\-\}=0and the portfolios coincide\. Otherwise, letχ\\chibe taskii’s recoverability indicator in the first portfolio, soPr⁡\(χ=1\)=β\+\\Pr\(\\chi=1\)=\\beta\_\{\+\}, and letZZbe an independent Bernoulli random variable with success probabilityβ−/β\+\\beta\_\{\-\}/\\beta\_\{\+\}, drawn privately by the controller\. Define a*virtual*taskiithat is recoverable exactly whenχ​Z=1\\chi Z=1, and whosettth search succeeds exactly when the actualttth search succeeds andZ=1Z=1\. The virtual task is recoverable with probabilityβ−\\beta\_\{\-\}; conditional on recoverability its searches succeed independently with probabilityαi\\alpha\_\{i\}; and otherwise they all fail\. Its outcomes therefore have the law of taskiiin the second portfolio, and the outcomes of the other tasks and of availability are unaffected\.

Fix any policyπ\\pifor the second portfolio and run it on the virtual history, which consists of the actual history of the other tasks and the virtual history of taskii\. As long as the actual taskiiis unresolved, executeπ\\pi’s actions verbatim; then every virtual search success is also an actual one\. If the actual task is resolved by a search that the virtual history records as a failure, which requiresZ=0Z=0, continue to simulateπ\\pi: record every later virtual search of taskiias a failure without performing it, letting the agent wait instead; do not submit taskii’s question; and leave the human idle in any period in whichπ\\piserves taskii\. All other tasks receive the same actions and have the same outcomes\. Taskiiperforms the same work in the same periods and is resolved no later than in the virtual history, so it completes no later, and its search, submission, and answer fees are no greater\. Conditional onZZand on the randomization ofπ\\pi, the constructed policy is a deterministic nonanticipative policy for the first portfolio\. Its expected cost is therefore at least the optimal value of the first portfolio, and it is at most the cost ofπ\\piin the second\. Taking the infimum overπ\\piproves the claim\.

The truncated problems of Appendix[B\.2](https://arxiv.org/html/2610.41129#A2.SS2)require a fixed completion rule from periodTTonward\. The same construction applies, with the completion rule executed on the actual state; if the actual taskiiis already resolved,FFskips it, and becauseFFserves in a fixed index order, skipping a task can only move every other task’s answer earlier\. The last statement follows becauseβi​\(ki\+1\)≤βi​\(ki\)\\beta\_\{i\}\(k\_\{i\}\+1\)\\leq\\beta\_\{i\}\(k\_\{i\}\)by Lemma[B\.1](https://arxiv.org/html/2610.41129#A2.Thmlemma1)\. ∎

### B\.2Proofs of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)and Propositions[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)and[A\.2](https://arxiv.org/html/2610.41129#A1.Thmproposition2)

We first establish a dynamic\-programming principle for the capped model that holds for any restriction of the plans, then prove the caps, and then construct the reductions\.

###### Lemma B\.3\(Ranked recursion\)\.

In the capped model, every transition to a different state strictly decreases the rank \([A\.3](https://arxiv.org/html/2610.41129#A1.E3)\)\. Suppose that each unfinished statesshas a set𝒟⁡\(s\)\\mathcal\{D\}\(s\)of feasible plans containing at least one plan withPd​\(s,s\)<1P\_\{d\}\(s,s\)<1, and letV𝒟​\(s\)V\_\{\\mathcal\{D\}\}\(s\)be the infimum of the expected total cost fromssover policies, possibly history dependent and randomized, that select a plan in𝒟⁡\(St\)\\mathcal\{D\}\(S\_\{t\}\)in every period\. ThenV𝒟=0V\_\{\\mathcal\{D\}\}=0at terminal states and, at unfinished states,

V𝒟\(s\)=mind∈𝒟⁡\(s\):Pd​\(s,s\)<1gd​\(s\)\+∑s′≠sPd​\(s,s′\)​V𝒟​\(s′\)1−Pd​\(s,s\)\.V\_\{\\mathcal\{D\}\}\(s\)=\\min\_\{d\\in\\mathcal\{D\}\(s\):\\,P\_\{d\}\(s,s\)<1\}\\frac\{g\_\{d\}\(s\)\+\\sum\_\{s^\{\\prime\}\\neq s\}P\_\{d\}\(s,s^\{\\prime\}\)V\_\{\\mathcal\{D\}\}\(s^\{\\prime\}\)\}\{1\-P\_\{d\}\(s,s\)\}\.\(B\.1\)A deterministic stationary policy that selects a minimizer at every unfinished state attainsV𝒟V\_\{\\mathcal\{D\}\}\.

###### Proof\.

Consider a transition fromsstos′≠ss^\{\\prime\}\\neq s\. No agent completes more than one work unit in a period, so noxix\_\{i\}increases\. A failed search raiseskik\_\{i\}by one and is admissible only ifki<Mik\_\{i\}<M\_\{i\}, so it lowers\(Mi−ki\)\+\(M\_\{i\}\-k\_\{i\}\)^\{\+\}by one\. A submission changesziz\_\{i\}fromUUtoPPand lowers𝟏\{zi=U\}\\mathbf\{1\}\\\{z\_\{i\}=U\\\}by one\. A resolution removes taskiifrom𝒜\\mathcal\{A\}and lowers the rank by\(Mi−ki\)\+\+1\+𝟏\{zi=U\}≥1\(M\_\{i\}\-k\_\{i\}\)^\{\+\}\+1\+\\mathbf\{1\}\\\{z\_\{i\}=U\\\}\\geq 1\. No component of the rank increases, and at least one changes becauses′≠ss^\{\\prime\}\\neq s\. Hence the rank strictly decreases\. Rank zero consists of terminal states\.

We prove the recursion and its attainment by induction on rank\. Fix an unfinished statessand suppose the claims hold at every state of lower rank\. The minimum in \([B\.1](https://arxiv.org/html/2610.41129#A2.E1)\) is over a finite nonempty set; letr∗r^\{\*\}be its value andd∗d^\{\*\}a minimizer\. Repeatingd∗d^\{\*\}until the state changes and then following stationary optimal policies at the lower\-rank successors costs∑t≥0Pd∗​\(s,s\)t​\[gd∗​\(s\)\+∑s′≠sPd∗​\(s,s′\)​V𝒟​\(s′\)\]=r∗\\sum\_\{t\\geq 0\}P\_\{d^\{\*\}\}\(s,s\)^\{t\}\[g\_\{d^\{\*\}\}\(s\)\+\\sum\_\{s^\{\\prime\}\\neq s\}P\_\{d^\{\*\}\}\(s,s^\{\\prime\}\)V\_\{\\mathcal\{D\}\}\(s^\{\\prime\}\)\]=r^\{\*\}\.

Conversely, fix any admissible policy and letτ∈\{1,2,…,∞\}\\tau\\in\\\{1,2,\\ldots,\\infty\\\}be the number of periods it spends inssbefore the state first changes\. On the event\{τ\>t\}\\\{\\tau\>t\\\}, letdt∈𝒟⁡\(s\)d\_\{t\}\\in\\mathcal\{D\}\(s\)be the plan used in periodtt, which may depend on the history and on randomization\. Conditional on the history up to periodtt, that period costsgdt​\(s\)g\_\{d\_\{t\}\}\(s\)in expectation, and the next state iss′≠ss^\{\\prime\}\\neq swith probabilityPdt​\(s,s′\)P\_\{d\_\{t\}\}\(s,s^\{\\prime\}\)\. Because the state is a sufficient statistic, the cost from a states′s^\{\\prime\}onward is at leastV𝒟​\(s′\)V\_\{\\mathcal\{D\}\}\(s^\{\\prime\}\)whatever the past\. Hence the policy’s expected cost is at least

𝔼∑t≥0𝟏\{τ\>t\}\[gdt\(s\)\+∑s′≠sPdt\(s,s′\)V𝒟\(s′\)\]≥r∗𝔼∑t≥0𝟏\{τ\>t\}\(1−Pdt\(s,s\)\)=r∗Pr\(τ<∞\)\.\\mathbb\{E\}\\sum\_\{t\\geq 0\}\\mathbf\{1\}\\\{\\tau\>t\\\}\\Bigl\[g\_\{d\_\{t\}\}\(s\)\+\\sum\_\{s^\{\\prime\}\\neq s\}P\_\{d\_\{t\}\}\(s,s^\{\\prime\}\)V\_\{\\mathcal\{D\}\}\(s^\{\\prime\}\)\\Bigr\]\\geq r^\{\*\}\\,\\mathbb\{E\}\\sum\_\{t\\geq 0\}\\mathbf\{1\}\\\{\\tau\>t\\\}\\bigl\(1\-P\_\{d\_\{t\}\}\(s,s\)\\bigr\)=r^\{\*\}\\Pr\(\\tau<\\infty\)\.The inequality holds termwise: forPd​\(s,s\)<1P\_\{d\}\(s,s\)<1it is the definition ofr∗r^\{\*\}, and forPd​\(s,s\)=1P\_\{d\}\(s,s\)=1its right side is zero\. IfPr⁡\(τ=∞\)\>0\\Pr\(\\tau=\\infty\)\>0, the cost is infinite, because every period at an unfinished state costs at leastω⁡\(s\)\>0\\omega\(s\)\>0\. Otherwise the cost is at leastr∗r^\{\*\}\. HenceV𝒟​\(s\)=r∗V\_\{\\mathcal\{D\}\}\(s\)=r^\{\*\}, attained by the stationary policy above\. ∎

###### Proof of Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\.

*Step 1: a uniform bound\.*LetFFbe the following completion rule: submit every unsubmitted question, never search, let every agent with work perform it, and in every available period serve the pending question of the unresolved task with the smallest index\. From a state reachable from the initial state, at mostnnquestions remain, every task has at mostbib\_\{i\}units of work, and thennth available period arrives aftern/an/aperiods in expectation\. UnderFF, each task completes by the later of these two events, soFFcosts at most∑iwi​\(bi\+n/a\)\+∑iκi\+n​η=Bmax\\sum\_\{i\}w\_\{i\}\(b\_\{i\}\+n/a\)\+\\sum\_\{i\}\\kappa\_\{i\}\+n\\eta=B\_\{\\max\}\. Since costs are nonnegative,0≤V∗≤Bmax0\\leq V^\{\*\}\\leq B\_\{\\max\}at every reachable state\.

*Step 2: truncated problems\.*For a horizonT≥0T\\geq 0and0≤t≤T0\\leq t\\leq T, letVtT​\(s\)V^\{T\}\_\{t\}\(s\)be the optimal cost from statessat periodttwhen the controller must followFFfrom periodTTonward, without caps\. ThenVTT​\(s\)V^\{T\}\_\{T\}\(s\)is the cost ofFF, andVtT​\(s\)=mind⁡\{gd​\(s\)\+𝔼d​\[Vt\+1T​\(S′\)\]\}V^\{T\}\_\{t\}\(s\)=\\min\_\{d\}\\\{g\_\{d\}\(s\)\+\\mathbb\{E\}\_\{d\}\[V^\{T\}\_\{t\+1\}\(S^\{\\prime\}\)\]\\\}fort<Tt<T, where the minimum is over the finitely many feasible plans\. EachVtTV^\{T\}\_\{t\}lies in\[0,Bmax\]\[0,B\_\{\\max\}\], because followingFFimmediately is feasible, and by Lemma[B\.2](https://arxiv.org/html/2610.41129#A2.Thmlemma2)it is nonincreasing in each task’s posterior\.

Lett<Tt<Tand letddbe a plan that, in some availability outcome, searches taskiiat a failure countki≥Mik\_\{i\}\\geq M\_\{i\}\. Letd′d^\{\\prime\}be the plan that replaces this search by waiting\. If taskiiis being served in that outcome, the search cannot change the next state and only addscic\_\{i\}\. Otherwise, condition on the availability outcome and on the outcomes of all other searches, which are independent of taskii’s search\. LetsSs\_\{S\}andsFs\_\{F\}be the next states after a success and a failure of taskii’s search, andsNs\_\{N\}the next state without it;sNs\_\{N\}differs fromsFs\_\{F\}only in having one failure fewer\. Withq=qi​\(ki\)≤qi​\(Mi\)≤ci/Bmaxq=q\_\{i\}\(k\_\{i\}\)\\leq q\_\{i\}\(M\_\{i\}\)\\leq c\_\{i\}/B\_\{\\max\}, the conditional cost ofddminus that ofd′d^\{\\prime\}is

ci\+q​Vt\+1T​\(sS\)\+\(1−q\)​Vt\+1T​\(sF\)−Vt\+1T​\(sN\)≥ci−q⁡\[Vt\+1T​\(sF\)−Vt\+1T​\(sS\)\]≥ci−q​Bmax≥0,c\_\{i\}\+qV^\{T\}\_\{t\+1\}\(s\_\{S\}\)\+\(1\-q\)V^\{T\}\_\{t\+1\}\(s\_\{F\}\)\-V^\{T\}\_\{t\+1\}\(s\_\{N\}\)\\geq c\_\{i\}\-q\\bigl\[V^\{T\}\_\{t\+1\}\(s\_\{F\}\)\-V^\{T\}\_\{t\+1\}\(s\_\{S\}\)\\bigr\]\\geq c\_\{i\}\-qB\_\{\\max\}\\geq 0,usingVt\+1T​\(sN\)≤Vt\+1T​\(sF\)V^\{T\}\_\{t\+1\}\(s\_\{N\}\)\\leq V^\{T\}\_\{t\+1\}\(s\_\{F\}\)and0≤Vt\+1T≤Bmax0\\leq V^\{T\}\_\{t\+1\}\\leq B\_\{\\max\}\. Averaging preserves the inequality\. Replacing every such search in turn shows that the minimum definingVtTV^\{T\}\_\{t\}is attained by a plan that respects the caps\. BecauseFFnever searches, backward induction onttshows thatV0TV^\{T\}\_\{0\}equals the value of the truncated problem in which searches atki≥Mik\_\{i\}\\geq M\_\{i\}are prohibited\.

*Step 3: the limit\.*LetVcapV^\{\\rm cap\}be the optimal value of the capped model\. Every capped policy is a policy, and every capped truncated policy is a capped policy, soV∗≤Vcap≤V0TV^\{\*\}\\leq V^\{\\rm cap\}\\leq V^\{T\}\_\{0\}for everyTT\. Conversely, letπ\\pibe any policy with finite costJπJ^\{\\pi\}and letπT\\pi\_\{T\}followπ\\piforTTperiods andFFthereafter\. ThenV0T≤JπT≤Jπ\+Bmax​Prπ⁡\(τ\>T\)V^\{T\}\_\{0\}\\leq J^\{\\pi\_\{T\}\}\\leq J^\{\\pi\}\+B\_\{\\max\}\\Pr^\{\\pi\}\(\\tau\>T\), whereτ\\tauis the completion time of the portfolio\. Becausewi\>0w\_\{i\}\>0,𝔼π​τ≤Jπ/mini⁡wi<∞\\mathbb\{E\}^\{\\pi\}\\tau\\leq J^\{\\pi\}/\\min\_\{i\}w\_\{i\}<\\infty, soPrπ⁡\(τ\>T\)→0\\Pr^\{\\pi\}\(\\tau\>T\)\\to 0andlim supTV0T≤Jπ\\limsup\_\{T\}V^\{T\}\_\{0\}\\leq J^\{\\pi\}\. Taking the infimum overπ\\pigiveslimTV0T=V∗\\lim\_\{T\}V^\{T\}\_\{0\}=V^\{\*\}, henceVcap=V∗V^\{\\rm cap\}=V^\{\*\}\. By Lemma[B\.3](https://arxiv.org/html/2610.41129#A2.Thmlemma3)with all feasible capped plans,VcapV^\{\\rm cap\}is attained by a deterministic stationary policy, which is therefore optimal in the original model\.

*Step 4: the remaining claims\.*EachMiM\_\{i\}is finite becauseqi​\(k\)→0q\_\{i\}\(k\)\\to 0andci\>0c\_\{i\}\>0\. For capsMi′≥MiM\_\{i\}^\{\\prime\}\\geq M\_\{i\}, everyMM\-capped policy isM′M^\{\\prime\}\-capped, soV∗≤VM′≤VM=V∗V^\{\*\}\\leq V^\{M^\{\\prime\}\}\\leq V^\{M\}=V^\{\*\}\. For a subsetIIof tasks, the boundBmaxIB^\{I\}\_\{\\max\}defined by \([A\.2](https://arxiv.org/html/2610.41129#A1.E2)\) forIIalone is at mostBmaxB\_\{\\max\}, so the caps that the proposition assigns toIIare at mostMiM\_\{i\}\. Applying the previous sentence to the portfolioIIproves \(iii\)\. ∎

###### Proof of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(i\)\.

Letπ\\pibe any policy for the capped model\. Construct a policyπ1\\pi\_\{1\}as follows\. Maintain*virtual*work countsx~i\\tilde\{x\}\_\{i\}, initially equal toxix\_\{i\}, and let the virtual history be the actual history withxix\_\{i\}replaced byx~i\\tilde\{x\}\_\{i\}\. In each period,π1\\pi\_\{1\}computes the planddthatπ\\piselects at the virtual history and makes the same submission and service decisions\. In each availability outcome, agentiisearches ifddsearches taskiiand does not serve it; otherwise, the agent works ifxi\>0x\_\{i\}\>0and waits ifxi=0x\_\{i\}=0\. The virtual countx~i\\tilde\{x\}\_\{i\}decreases by one wheneverddlets agentiiwork andx~i\>0\\tilde\{x\}\_\{i\}\>0\.

The actual and virtual histories differ only in work counts\. A search thatπ\\piperforms on a task being served affects nothing, because the task is resolved at the end of the period either way; ifπ\\piconditions later decisions on the outcome of such a search,π1\\pi\_\{1\}feeds it an independently simulated outcome with the correct probability, soπ1\\pi\_\{1\}may be randomized\. The other searches and their outcomes are identical\. By induction,xi≤x~ix\_\{i\}\\leq\\tilde\{x\}\_\{i\}in every period: whenever the virtual count decreases, the actual count decreases as well unless it is already zero\. The virtual history is a function of the actual history, soπ1\\pi\_\{1\}is nonanticipative\. Every task is resolved at the same time in both histories and finishes its work no later in the actual one, so it completes no later; search fees do not increase, and submission and answer fees are unchanged\. HenceJπ1≤JπJ^\{\\pi\_\{1\}\}\\leq J^\{\\pi\}\. By construction,π1\\pi\_\{1\}never searches a task while its question is being served, and every agent with work left works unless it searches, both before and after resolution\. ∎

###### Proof of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(ii\)\.

Letπ1\\pi\_\{1\}be any policy for the capped model\. Construct a policyπ2\\pi\_\{2\}that followsπ1\\pi\_\{1\}on a virtual history in which some questions may be virtually submitted but actually unsubmitted\. At the start of each period, compute the planddthatπ1\\pi\_\{1\}selects at the virtual history, drawing any randomization now\. This determinesπ1\\pi\_\{1\}’s virtual submissions and the questionjjthatπ1\\pi\_\{1\}would serve if the human is available, if any\. Ifjjexists and is actually unsubmitted,π2\\pi\_\{2\}submitsjj; it submits no other question\. If the human is available,π2\\pi\_\{2\}servesjj\. In both availability outcomes,π2\\pi\_\{2\}usesdd’s agent actions, and the virtual history is updated according todd\.

The construction is feasible\. Binary availability is the only information revealed between submission and service, sojjis known at the start of the period\. Moreover,jjis virtually submitted and unresolved, so it is actually pending or newly submitted, and newly submitted questions are immediately eligible\. Search, work, and service are the same in both histories, so all completion times, search fees, and answer fees coincide\. Each actual submission of a question occurs at most once and only ifπ1\\pi\_\{1\}has virtually submitted that question, so submission fees do not increase\. HenceJπ2≤Jπ1J^\{\\pi\_\{2\}\}\\leq J^\{\\pi\_\{1\}\}\. The policyπ2\\pi\_\{2\}submits at most one question per period and serves it if the human is available\. Because it usesπ1\\pi\_\{1\}’s agent actions and serves the same questions, it inherits every property of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(i\) and the caps fromπ1\\pi\_\{1\}\. ∎

###### Proof of Proposition[A\.2](https://arxiv.org/html/2610.41129#A1.Thmproposition2)and of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\.

The rank claim is part of Lemma[B\.3](https://arxiv.org/html/2610.41129#A2.Thmlemma3)\. By Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1), the capped model has the optimal value of the original model, and by Lemma[B\.3](https://arxiv.org/html/2610.41129#A2.Thmlemma3)applied to all feasible capped plans, it has a deterministic stationary optimal policyπ∗\\pi^\{\*\}; this proves that \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\) with all feasible plans givesV∗V^\{\*\}\. Apply the construction in the proof of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(i\) toπ∗\\pi^\{\*\}and the construction in the proof of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(ii\) to the result\. The final policyπ2\\pi\_\{2\}has cost at mostV∗V^\{\*\}, so it is optimal, and in every period it selects a plan in𝒟red​\(St\)\\mathcal\{D\}\_\{\\rm red\}\(S\_\{t\}\)\. LetVredV\_\{\\rm red\}be the value of Lemma[B\.3](https://arxiv.org/html/2610.41129#A2.Thmlemma3)with𝒟=𝒟red\\mathcal\{D\}=\\mathcal\{D\}\_\{\\rm red\}; Appendix[A\.1](https://arxiv.org/html/2610.41129#A1.SS1)shows that𝒟red​\(s\)\\mathcal\{D\}\_\{\\rm red\}\(s\)contains a plan withPd​\(s,s\)<1P\_\{d\}\(s,s\)<1\. ThenV∗≤Vred≤Jπ2=V∗V^\{\*\}\\leq V\_\{\\rm red\}\\leq J^\{\\pi\_\{2\}\}=V^\{\*\}, soVred=V∗V\_\{\\rm red\}=V^\{\*\}\. This is \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\), because the minimum in \([B\.1](https://arxiv.org/html/2610.41129#A2.E1)\) is over𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)when𝒟=𝒟red\\mathcal\{D\}=\\mathcal\{D\}\_\{\\rm red\}\. The stationary policy that attains it selects plans in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)and therefore satisfies the three properties of Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)simultaneously; property \(iii\) holds with the caps of Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\. Finally, by the rank argument, every state\-changing transition advances work, failures, submission, or resolution\. ∎

### B\.3Proofs of Theorem[1](https://arxiv.org/html/2610.41129#Thmtheorem1)and Proposition[A\.3](https://arxiv.org/html/2610.41129#A1.Thmproposition3)

We use the notation \([A\.6](https://arxiv.org/html/2610.41129#A1.E6)\)\. A task withx=0x=0has no work, so rule \(d\) of Definition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmdefinition1)is vacuous\. LetΠ⁡\(Y\)=min⁡\{w\+Y,w\+a​η\+\(1−a\)​Y,W\}\\Pi\(Y\)=\\min\\\{w\+Y,\\;w\+a\\eta\+\(1\-a\)Y,\\;W\\\}\. Two facts aboutΠ\\Piare used repeatedly\. First,Π\\Piis nondecreasing\. Second,Π⁡\(Y\)=W\\Pi\(Y\)=WwheneverY≥WY\\geq W, because thenw\+Y\>Ww\+Y\>Wandw\+a​η\+\(1−a\)​Y≥w\+a​η\+\(1−a\)​W=Ww\+a\\eta\+\(1\-a\)Y\\geq w\+a\\eta\+\(1\-a\)W=W\.

###### Proof of Proposition[A\.3](https://arxiv.org/html/2610.41129#A1.Thmproposition3)\.

*Part \(i\)\.*At a pending state\(0,k,P\)\(0,k,P\)withk<Mk<M, the plans are described by the action in the available outcome \(serve, search, or wait\) and in the unavailable outcome \(search or wait\)\. By \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\), their ratios are as follows\. Searching in both outcomes givesw\+Ykw\+Y\_\{k\}\. Serving when available and searching otherwise givesw\+a​η\+\(1−a\)​Ykw\+a\\eta\+\(1\-a\)Y\_\{k\}\. Serving when available and waiting otherwise gives\(w\+a​η\)/a=W\(w\+a\\eta\)/a=W\. Searching when available and waiting otherwise gives\(w\+a​Yk\)/a≥w\+Yk\(w\+aY\_\{k\}\)/a\\geq w\+Y\_\{k\}, and, fora<1a<1, waiting when available and searching otherwise givesw/\(1−a\)\+Yk≥w\+Ykw/\(1\-a\)\+Y\_\{k\}\\geq w\+Y\_\{k\}\. Waiting in both outcomes leaves the state unchanged\. HenceVkP=Π⁡\(Yk\)V^\{P\}\_\{k\}=\\Pi\(Y\_\{k\}\)\. Fork≥Mk\\geq M, only the third plan is available andVkP=WV^\{P\}\_\{k\}=W; sinceYk=c\+\(1−qk\)​W≥WY\_\{k\}=c\+\(1\-q\_\{k\}\)W\\geq Wthere becauseqk​W≤qk​Bmax≤cq\_\{k\}W\\leq q\_\{k\}B\_\{\\max\}\\leq c, alsoVkP=Π⁡\(Yk\)V^\{P\}\_\{k\}=\\Pi\(Y\_\{k\}\)\. Whena=1a=1, the unavailable outcome has probability zero, and the same formulas hold\.

For monotonicity, note first thatVM−1P=Π⁡\(YM−1\)≤W=VMPV^\{P\}\_\{M\-1\}=\\Pi\(Y\_\{M\-1\}\)\\leq W=V^\{P\}\_\{M\}\. SupposeVk\+1P≤Vk\+2PV^\{P\}\_\{k\+1\}\\leq V^\{P\}\_\{k\+2\}\. Becauseqk≥qk\+1q\_\{k\}\\geq q\_\{k\+1\}and values are nonnegative,Yk=c\+\(1−qk\)​Vk\+1P≤c\+\(1−qk\+1\)​Vk\+2P=Yk\+1Y\_\{k\}=c\+\(1\-q\_\{k\}\)V^\{P\}\_\{k\+1\}\\leq c\+\(1\-q\_\{k\+1\}\)V^\{P\}\_\{k\+2\}=Y\_\{k\+1\}, and thereforeVkP=Π⁡\(Yk\)≤Π⁡\(Yk\+1\)=Vk\+1PV^\{P\}\_\{k\}=\\Pi\(Y\_\{k\}\)\\leq\\Pi\(Y\_\{k\+1\}\)=V^\{P\}\_\{k\+1\}\. Downward induction fromk=M−1k=M\-1proves that both sequences are nondecreasing on\{0,…,M\}\\\{0,\\ldots,M\\\}\. BeyondMM,VkP=WV^\{P\}\_\{k\}=Wis constant andYk=c\+\(1−qk\)​WY\_\{k\}=c\+\(1\-q\_\{k\}\)Wis nondecreasing becauseqkq\_\{k\}is nonincreasing\.

*Part \(ii\)\.*Comparing the three terms inΠ\\Pi:w\+Y≤w\+a​η\+\(1−a\)​Yw\+Y\\leq w\+a\\eta\+\(1\-a\)Yexactly whenY≤ηY\\leq\\eta; fora<1a<1,w\+a​η\+\(1−a\)​Y≤Ww\+a\\eta\+\(1\-a\)Y\\leq Wexactly whenY≤WY\\leq W, becauseW−w−a​η=\(1−a\)​WW\-w\-a\\eta=\(1\-a\)W; andY<ηY<\\etaimpliesw\+Y<w\+η≤Ww\+Y<w\+\\eta\\leq W\. These comparisons give the three regimes, with ties at the boundaries\. Fora=1a=1the second and third plans coincide, and the statement holds trivially\.

It remains to show thatYk≥WY\_\{k\}\\geq Wexactly whenqk​W≤cq\_\{k\}W\\leq c\. Ifqk​W\>cq\_\{k\}W\>c, thenYk≤c\+\(1−qk\)​W<WY\_\{k\}\\leq c\+\(1\-q\_\{k\}\)W<WbecauseVk\+1P≤WV^\{P\}\_\{k\+1\}\\leq W\. Ifqk​W≤cq\_\{k\}W\\leq c, thenqj​W≤cq\_\{j\}W\\leq cfor allj≥kj\\geq k\. For any suchjj,Vj\+1P=WV^\{P\}\_\{j\+1\}=WimpliesYj=c\+\(1−qj\)​W≥WY\_\{j\}=c\+\(1\-q\_\{j\}\)W\\geq Wand henceVjP=Π⁡\(Yj\)=WV^\{P\}\_\{j\}=\\Pi\(Y\_\{j\}\)=W\. Downward induction fromVMP=WV^\{P\}\_\{M\}=WgivesVk\+1P=WV^\{P\}\_\{k\+1\}=WandYk=c\+\(1−qk\)​W≥WY\_\{k\}=c\+\(1\-q\_\{k\}\)W\\geq W\.

*Part \(iii\)\.*At an unsubmitted state\(0,k,U\)\(0,k,U\)withk<Mk<M, waiting leaves the state unchanged, submitting givesκ\+VkP\\kappa\+V^\{P\}\_\{k\}, and searching without submitting givesw\+c\+\(1−qk\)​Vk\+1Uw\+c\+\(1\-q\_\{k\}\)V^\{U\}\_\{k\+1\}\. Hence

VkU=min⁡\{κ\+VkP,w\+c\+\(1−qk\)​Vk\+1U\},VMU=κ\+W\.V^\{U\}\_\{k\}=\\min\\bigl\\\{\\kappa\+V^\{P\}\_\{k\},\\;w\+c\+\(1\-q\_\{k\}\)V^\{U\}\_\{k\+1\}\\bigr\\\},\\qquad V^\{U\}\_\{M\}=\\kappa\+W\.\(B\.2\)Searching once and submitting after a failure costsw\+c\+\(1−qk\)​\(κ\+Vk\+1P\)=κ\+VkP\+ψkw\+c\+\(1\-q\_\{k\}\)\(\\kappa\+V^\{P\}\_\{k\+1\}\)=\\kappa\+V^\{P\}\_\{k\}\+\\psi\_\{k\}, which explains the definition ofψk\\psi\_\{k\}\. Because

w\+Y−Π⁡\(Y\)=max⁡\{0,a⁡\(Y−η\),w\+Y−W\}w\+Y\-\\Pi\(Y\)=\\max\\bigl\\\{0,\\;a\(Y\-\\eta\),\\;w\+Y\-W\\bigr\\\}is nondecreasing inYY,YkY\_\{k\}is nondecreasing, and−κ​qk\-\\kappa q\_\{k\}is nondecreasing,ψk\\psi\_\{k\}is nondecreasing on\{0,…,M\}\\\{0,\\ldots,M\\\}\. At the cap,ψM=w\+c−qM​\(W\+κ\)≥w\+c−qM​Bmax≥w\\psi\_\{M\}=w\+c\-q\_\{M\}\(W\+\\kappa\)\\geq w\+c\-q\_\{M\}B\_\{\\max\}\\geq w, becauseW\+κ≤BmaxW\+\\kappa\\leq B\_\{\\max\}\. Hencekask≤Mk\_\{\\rm ask\}\\leq M\.

Fork≥kaskk\\geq k\_\{\\rm ask\}, we showVkU=κ\+VkPV^\{U\}\_\{k\}=\\kappa\+V^\{P\}\_\{k\}by downward induction fromk=Mk=M\. IfVk\+1U=κ\+Vk\+1PV^\{U\}\_\{k\+1\}=\\kappa\+V^\{P\}\_\{k\+1\}, the search option in \([B\.2](https://arxiv.org/html/2610.41129#A2.E2)\) equalsκ\+VkP\+ψk≥κ\+VkP\\kappa\+V^\{P\}\_\{k\}\+\\psi\_\{k\}\\geq\\kappa\+V^\{P\}\_\{k\}, so submitting is optimal atkk\. Fork<kaskk<k\_\{\\rm ask\},ψk<0\\psi\_\{k\}<0, so searching once and submitting after a failure is strictly cheaper than submitting now; henceVkU<κ\+VkPV^\{U\}\_\{k\}<\\kappa\+V^\{P\}\_\{k\}, and searching is the unique optimal action\. Thus the policy that searches belowkaskk\_\{\\rm ask\}and submits atkaskk\_\{\\rm ask\}is optimal\.

*Part \(iv\)\.*By Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\(ii\), the pending values do not depend on which sufficient cap is used, and no submission fee is paid from a pending state, soVkPV^\{P\}\_\{k\},YkY\_\{k\}, and the pending policy do not depend onκ\\kappa\. Ifp\>0p\>0and0<α<10<\\alpha<1, thenqk\>0q\_\{k\}\>0for everykk, so for any fixedk¯\\bar\{k\}and all sufficiently largeκ\\kappawe haveψk<0\\psi\_\{k\}<0fork≤k¯k\\leq\\bar\{k\}, that is,kask\>k¯k\_\{\\rm ask\}\>\\bar\{k\}\.

For the converse example, letw=η=1w=\\eta=1,a=0\.5a=0\.5,c=0\.1c=0\.1,p=0\.2p=0\.2, andα=0\.5\\alpha=0\.5\. ThenW=3W=3,q0=0\.1q\_\{0\}=0\.1,q1=0\.05/0\.9<0\.1q\_\{1\}=0\.05/0\.9<0\.1, andq0​W=0\.3\>cq\_\{0\}W=0\.3\>c, so by part \(ii\) a pending agent with no failures searches when the human is unavailable\. Every pending period costs at leastww, soV2P≥1V^\{P\}\_\{2\}\\geq 1\. Hencew\+Y1≥1\+0\.1\+0\.9⋅1=2w\+Y\_\{1\}\\geq 1\+0\.1\+0\.9\\cdot 1=2,w\+a​η\+\(1−a\)​Y1≥1\.5w\+a\\eta\+\(1\-a\)Y\_\{1\}\\geq 1\.5, andW=3W=3, soV1P≥1\.5V^\{P\}\_\{1\}\\geq 1\.5andY0≥0\.1\+0\.9⋅1\.5=1\.45Y\_\{0\}\\geq 0\.1\+0\.9\\cdot 1\.5=1\.45\. The identity forw\+Y−Π⁡\(Y\)w\+Y\-\\Pi\(Y\)then givesψ0≥a⁡\(Y0−η\)−κ​q0≥0\.225−0\.1​κ\\psi\_\{0\}\\geq a\(Y\_\{0\}\-\\eta\)\-\\kappa q\_\{0\}\\geq 0\.225\-0\.1\\kappa, which is nonnegative forκ≤2\.25\\kappa\\leq 2\.25\. Hencekask=0k\_\{\\rm ask\}=0\. ∎

###### Proof of Theorem[1](https://arxiv.org/html/2610.41129#Thmtheorem1)\.

Part \(iii\) of Proposition[A\.3](https://arxiv.org/html/2610.41129#A1.Thmproposition3)gives the asking threshold; the zero\-fee discussion after Proposition[A\.3](https://arxiv.org/html/2610.41129#A1.Thmproposition3)gives the consistent choice at ties\. For the pending statement, leta<1a<1; fora=1a=1the unavailable outcome is unreachable\. After an unavailable realization, searching leads to the expected continuation costYkY\_\{k\}and waiting returns to the same state, with continuation costVkPV^\{P\}\_\{k\}\. Hence search is strictly preferable exactly whenYk<VkP=Π⁡\(Yk\)Y\_\{k\}<V^\{P\}\_\{k\}=\\Pi\(Y\_\{k\}\)\. BecauseY<w\+YY<w\+Yalways and, fora<1a<1,Y<w\+a​η\+\(1−a\)​YY<w\+a\\eta\+\(1\-a\)Yexactly whenY<WY<W, this holds exactly whenYk<WY\_\{k\}<W, that is, by part \(ii\), whenqk​\(η\+w/a\)\>cq\_\{k\}\(\\eta\+w/a\)\>c\. Becauseqkq\_\{k\}is nonincreasing, the set of suchkkis an initial segment, so pending search stops at a failure\-count threshold\. The absence of a universal ordering is part \(iv\)\. ∎

### B\.4Proof of Theorem[2](https://arxiv.org/html/2610.41129#Thmtheorem2)

Letα=1\\alpha=1\. The first search succeeds with probabilitypp, and after a failure the posterior is zero, so the task can be resolved only by the human\. Becausep​η\>cp\\eta\>cin the region \([5](https://arxiv.org/html/2610.41129#S4.E5)\) andBmax≥ηB\_\{\\max\}\\geq\\eta, we haveq⁡\(0\)​Bmax\>cq\(0\)B\_\{\\max\}\>candq⁡\(1\)=0q\(1\)=0, so the cap isM=1M=1: the model with one search attempt is the exactα=1\\alpha=1case, not a truncation\. Write

W=η\+wa,Y0=c\+\(1−p\)​W,Y1=c\+p​w\+\(1−p\)​W=Y0\+p​w\.W=\\eta\+\\frac\{w\}\{a\},\\qquad Y\_\{0\}=c\+\(1\-p\)W,\\qquad Y\_\{1\}=c\+pw\+\(1\-p\)W=Y\_\{0\}\+pw\.Once the search attempt has failed, a pending task with zero or one unit of work has valueWW: it paysη\\etaonce, and serving at the first available periodGGwhile working completes it atmax⁡\{x,G\}=G\\max\\\{x,G\\\}=G, with𝔼​G=1/a\\mathbb\{E\}G=1/a\. An unsubmitted task in the same situation has valueκ\+W\\kappa\+W, because submitting at once costsκ\+W\\kappa\+Wand working first costs at leastw\+κ\+Ww\+\\kappa\+W\.

##### Zero remaining work

Searching before submitting costs

S0=w\+c\+\(1−p\)​\(κ\+W\)\.S\_\{0\}=w\+c\+\(1\-p\)\(\\kappa\+W\)\.Becausep​η\>cp\\eta\>c, we haveY0<WY\_\{0\}<W, so by Proposition[A\.3](https://arxiv.org/html/2610.41129#A1.Thmproposition3)\(i\) the value of submitting immediately is

A0=κ\+min⁡\{w\+Y0,w\+a​η\+\(1−a\)​Y0\}\.A\_\{0\}=\\kappa\+\\min\\bigl\\\{w\+Y\_\{0\},\\;w\+a\\eta\+\(1\-a\)Y\_\{0\}\\bigr\\\}\.Direct subtraction gives

S0−\(κ\+w\+Y0\)=−p​κ<0,S0−\[κ\+w\+a​η\+\(1−a\)​Y0\]=w\+a​c−p⁡\(κ\+w\+a​η\)\.S\_\{0\}\-\(\\kappa\+w\+Y\_\{0\}\)=\-p\\kappa<0,\\qquad S\_\{0\}\-\\bigl\[\\kappa\+w\+a\\eta\+\(1\-a\)Y\_\{0\}\\bigr\]=w\+ac\-p\(\\kappa\+w\+a\\eta\)\.Hence, ifp\>θ0p\>\\theta\_\{0\}, searching first is strictly better than both ways of submitting immediately\. Waiting is dominated, and there is no work\. Thus search\-first is the unique optimal initial action, andV0U=S0V^\{U\}\_\{0\}=S\_\{0\}\.

##### One remaining work unit

Consider first the pending state\(1,0,P\)\(1,0,P\)\. In each availability outcome, compare the continuation costs of the agent’s options\. Searching leaves the work unit undone: on success, the work costsww, and on failure, the pending value isWW, so searching has continuation costY1Y\_\{1\}\. Working leads to\(0,0,P\)\(0,0,P\), whose value isV0P=min⁡\{w\+Y0,w\+a​η\+\(1−a\)​Y0,W\}V^\{P\}\_\{0\}=\\min\\\{w\+Y\_\{0\},\\;w\+a\\eta\+\(1\-a\)Y\_\{0\},\\;W\\\}\. IfY0<ηY\_\{0\}<\\eta, thenV0P−Y1=\(1−p\)​w\>0V^\{P\}\_\{0\}\-Y\_\{1\}=\(1\-p\)w\>0\. Ifη≤Y0<W\\eta\\leq Y\_\{0\}<W, thenV0P−Y1=w\+a​η−a​Y0−p​w=a⁡\(p​η−c\)\>0V^\{P\}\_\{0\}\-Y\_\{1\}=w\+a\\eta\-aY\_\{0\}\-pw=a\(p\\eta\-c\)\>0\. Hence searching is strictly better than working when the human is unavailable\. When the human is available, serving while working completes the task and has continuation costη\\eta, and

Y1−η=c\+wa−p⁡\(η\+\(1−a\)​wa\)\>0wheneverp<θ1,Y\_\{1\}\-\\eta=c\+\\frac\{w\}\{a\}\-p\\left\(\\eta\+\\frac\{\(1\-a\)w\}\{a\}\\right\)\>0\\quad\\text\{whenever\}\\quad p<\\theta\_\{1\},becauseθ1≤\(w\+a​c\)/\(a​η\+\(1−a\)​w\)\\theta\_\{1\}\\leq\(w\+ac\)/\(a\\eta\+\(1\-a\)w\)\. Hence serving is strictly best when available\. The value of submitting immediately is therefore

A1=κ\+w\+a​η\+\(1−a\)​Y1\.A\_\{1\}=\\kappa\+w\+a\\eta\+\(1\-a\)Y\_\{1\}\.Without an initial submission, waiting is dominated, and the remaining options are search and work\. Searching first costs

S1=w\+c\+p​w\+\(1−p\)​\(κ\+W\)=S0\+p​w,S\_\{1\}=w\+c\+pw\+\(1\-p\)\(\\kappa\+W\)=S\_\{0\}\+pw,and working first costsw\+V0U=w\+S0=S1\+\(1−p\)​w\>S1w\+V^\{U\}\_\{0\}=w\+S\_\{0\}=S\_\{1\}\+\(1\-p\)w\>S\_\{1\}\. Finally,

S1−A1=w\+a​c−p⁡\[κ\+\(1−a\)​w\+a​η\]\>0wheneverp<θ1\.S\_\{1\}\-A\_\{1\}=w\+ac\-p\\bigl\[\\kappa\+\(1\-a\)w\+a\\eta\\bigr\]\>0\\quad\\text\{whenever\}\\quad p<\\theta\_\{1\}\.This exhausts the initial decisions and proves the policy switch throughout the region \([5](https://arxiv.org/html/2610.41129#S4.E5)\)\.

##### Nonemptiness

Because0<θ0<θ10<\\theta\_\{0\}<\\theta\_\{1\}, the region is nonempty exactly whenc/η<1c/\\eta<1,θ0<1\\theta\_\{0\}<1, andc/η<θ1c/\\eta<\\theta\_\{1\}\. The first condition isc<ηc<\\eta, which implies the second becauseκ\>0\\kappa\>0\. The third is equivalent toc​κ\+c⁡\(1−a\)​w<η​wc\\kappa\+c\(1\-a\)w<\\eta w, that is,κ<w⁡\[η/c−\(1−a\)\]\\kappa<w\[\\eta/c\-\(1\-a\)\]\. Together withκ\>0\\kappa\>0, these give \([6](https://arxiv.org/html/2610.41129#S4.E6)\)\.

##### Resource use

Without work, the agent searches once, and a submission and a human answer occur only after a failure, with probability1−p1\-p\. With one work unit, a question is always submitted; a search occurs only if the human is initially unavailable, with probability1−a1\-a; and that search withdraws the question with probability\(1−a\)​p\(1\-a\)p\. The probability of a human answer is therefore1−\(1−a\)​p1\-\(1\-a\)p, which exceeds1−p1\-pbya​pap, and the expected number of searches falls from11to1−a1\-a\.

##### The numerical illustration

Forw=κ=η=1w=\\kappa=\\eta=1,c=0\.1c=0\.1, anda=0\.5a=0\.5,θ0=1\.05/2\.5=0\.42\\theta\_\{0\}=1\.05/2\.5=0\.42,θ1=1\.05/2=0\.525\\theta\_\{1\}=1\.05/2=0\.525, andc/η=0\.1c/\\eta=0\.1, so the region is0\.42<p<0\.5250\.42<p<0\.525\. Atp=0\.5p=0\.5, the probability of a human answer is1−p=0\.51\-p=0\.5without work and1−\(1−a\)​p=0\.751\-\(1\-a\)p=0\.75with one work unit\. ∎

### B\.5Proof of Proposition[1](https://arxiv.org/html/2610.41129#Thmproposition1)

As in Appendix[B\.4](https://arxiv.org/html/2610.41129#A2.SS4),α=1\\alpha=1makes the one\-attempt model exact in both models\. We useWW,Y0Y\_\{0\},Y1Y\_\{1\},S0S\_\{0\},S1S\_\{1\}, andA1A\_\{1\}from that proof\. When no further search is possible, either because the attempt has failed or because withdrawal is not allowed, a pending task withx∈\{0,1\}x\\in\\\{0,1\\\}has valueWWand an unsubmitted task has valueκ\+W\\kappa\+W, by the same argument as there\.

##### \(i\) Without withdrawal

At the initial state\(1,0,U\)\(1,0,U\), waiting returns the same state at costw\>0w\>0and is dominated\. Submitting now forfeits the search and has valueκ\+W\\kappa\+W\. Searching without submitting costsS1S\_\{1\}: on success, one work unit remains and costsww, and on failure, the value isκ\+W\\kappa\+W\. Working without submitting leads to\(0,0,U\)\(0,0,U\), whose value in this model ismin⁡\{κ\+W,S0\}\\min\\\{\\kappa\+W,S\_\{0\}\\\}; this option therefore costsmin⁡\{w\+κ\+W,S1\+\(1−p\)​w\}\>min⁡\{κ\+W,S1\}\\min\\\{w\+\\kappa\+W,\\;S\_\{1\}\+\(1\-p\)w\\\}\>\\min\\\{\\kappa\+W,S\_\{1\}\\\}\. Finally,

S1−\(κ\+W\)=w\+c−p⁡\(κ\+η\+\(1−a\)​wa\)=a⁡\(w\+c\)−p⁡\[a​κ\+a​η\+\(1−a\)​w\]a,S\_\{1\}\-\(\\kappa\+W\)=w\+c\-p\\left\(\\kappa\+\\eta\+\\frac\{\(1\-a\)w\}\{a\}\\right\)=\\frac\{a\(w\+c\)\-p\\bigl\[a\\kappa\+a\\eta\+\(1\-a\)w\\bigr\]\}\{a\},which is negative exactly whenp\>θnwp\>\\theta\_\{\\rm nw\}\. Hence search\-first is uniquely optimal, with valueS1S\_\{1\}\.

##### \(ii\) With withdrawal

The one\-work\-unit part of Appendix[B\.4](https://arxiv.org/html/2610.41129#A2.SS4)uses onlyc/η<p<θ1c/\\eta<p<\\theta\_\{1\}to show that the best plan that submits immediately is the stated one, with valueA1A\_\{1\}, and thatS1\>A1S\_\{1\}\>A\_\{1\}\. That argument also compares working first with searching first usingV0U=S0V^\{U\}\_\{0\}=S\_\{0\}, which requiresp\>θ0p\>\\theta\_\{0\}\. We replace this step with a direct comparison\. Without a submission, working first costsw\+V0Uw\+V^\{U\}\_\{0\}, whereV0U=min⁡\{S0,κ\+V0P\}V^\{U\}\_\{0\}=\\min\\\{S\_\{0\},\\kappa\+V^\{P\}\_\{0\}\\\}\. First,w\+S0=S1\+\(1−p\)​w\>A1w\+S\_\{0\}=S\_\{1\}\+\(1\-p\)w\>A\_\{1\}\. Second,w\+κ\+V0P−A1=V0P−a​η−\(1−a\)​Y1w\+\\kappa\+V^\{P\}\_\{0\}\-A\_\{1\}=V^\{P\}\_\{0\}\-a\\eta\-\(1\-a\)Y\_\{1\}\. Sincep<θ1p<\\theta\_\{1\}givesY1\>ηY\_\{1\}\>\\eta, that is,Y0−η\>−p​wY\_\{0\}\-\\eta\>\-pw, each of the three candidates forV0PV^\{P\}\_\{0\}gives a positive difference:

w\+Y0−a​η−\(1−a\)​Y1\\displaystyle w\+Y\_\{0\}\-a\\eta\-\(1\-a\)Y\_\{1\}=w⁡\[1−\(1−a\)​p\]\+a⁡\(Y0−η\)\>\(1−p\)​w\>0,\\displaystyle=w\\bigl\[1\-\(1\-a\)p\\bigr\]\+a\(Y\_\{0\}\-\\eta\)\>\(1\-p\)w\>0,w\+a​η\+\(1−a\)​Y0−a​η−\(1−a\)​Y1\\displaystyle w\+a\\eta\+\(1\-a\)Y\_\{0\}\-a\\eta\-\(1\-a\)Y\_\{1\}=w⁡\[1−\(1−a\)​p\]\>0,\\displaystyle=w\\bigl\[1\-\(1\-a\)p\\bigr\]\>0,W−a​η−\(1−a\)​Y1\\displaystyle W\-a\\eta\-\(1\-a\)Y\_\{1\}=w\+\(1−a\)​\(p​η−c\)\+\(1−a\)2​p​wa\>0,\\displaystyle=w\+\(1\-a\)\(p\\eta\-c\)\+\\frac\{\(1\-a\)^\{2\}pw\}\{a\}\>0,where the last line usesp​η\>cp\\eta\>c\. Hence working first is strictly worse thanA1A\_\{1\}\. Waiting is dominated, so submitting immediately with the stated contingent actions is uniquely optimal, and the value with withdrawal isA1A\_\{1\}\.

##### \(iii\) Cost and resource use

The cost reduction isS1−A1=w\+a​c−p⁡\[κ\+\(1−a\)​w\+a​η\]S\_\{1\}\-A\_\{1\}=w\+ac\-p\[\\kappa\+\(1\-a\)w\+a\\eta\], which is \([9](https://arxiv.org/html/2610.41129#S4.E9)\) and positive becausep<θ1p<\\theta\_\{1\}\. Without withdrawal, the agent searches once\. With probabilityppit completes in period 2, and otherwise it submits in period 2 and completes after a further geometric wait for the human\. Its expected completion time is2​p\+\(1−p\)​\(1\+1/a\)2p\+\(1\-p\)\(1\+1/a\), and a submission and an answer each occur with probability1−p1\-p\. With withdrawal, a submission always occurs\. With probabilityaa, the task completes in period 1 after one answer\. Otherwise, the agent searches once; on success, the question is withdrawn and the task completes in period 2, and on failure, it completes after a further geometric wait and one answer\. Its expected completion time isa\+\(1−a\)​\[2​p\+\(1−p\)​\(1\+1/a\)\]a\+\(1\-a\)\[2p\+\(1\-p\)\(1\+1/a\)\], the answer probability isa\+\(1−a\)​\(1−p\)=1−\(1−a\)​pa\+\(1\-a\)\(1\-p\)=1\-\(1\-a\)p, and the expected number of searches is1−a1\-a\. Subtraction gives the stated changes: the expected completion time falls by1−\(1−a\)​p1\-\(1\-a\)p, the answer probability rises bya​pap, the submission probability rises bypp, and expected searches fall byaa\. As a check,w⁡\[1−\(1−a\)​p\]\+a​c−κ​p−η​a​pw\[1\-\(1\-a\)p\]\+ac\-\\kappa p\-\\eta apequals the cost reduction\. For the illustration in the main text,w=κ=η=1w=\\kappa=\\eta=1,c=0\.1c=0\.1,a=0\.5a=0\.5, andp=0\.5p=0\.5, soW=3W=3,Y1=2\.1Y\_\{1\}=2\.1,S1=3\.60S\_\{1\}=3\.60, andA1=3\.55A\_\{1\}=3\.55; the four terms of the check are0\.750\.75,0\.050\.05,−0\.5\-0\.5, and−0\.25\-0\.25\. Moreover,θnw=0\.55/1\.5≈0\.367\\theta\_\{\\rm nw\}=0\.55/1\.5\\approx 0\.367, so the region \([8](https://arxiv.org/html/2610.41129#S4.E8)\) is0\.367<p<0\.5250\.367<p<0\.525\.

##### Nonemptiness

Becauseθnw\\theta\_\{\\rm nw\}andθ1\\theta\_\{1\}are positive, the region \([8](https://arxiv.org/html/2610.41129#S4.E8)\) is nonempty exactly whenc/η<1c/\\eta<1,c/η<θ1c/\\eta<\\theta\_\{1\},θnw<1\\theta\_\{\\rm nw\}<1, andθnw<θ1\\theta\_\{\\rm nw\}<\\theta\_\{1\}\. The first isc<ηc<\\eta, and the second isκ<w⁡\[η/c−\(1−a\)\]\\kappa<w\[\\eta/c\-\(1\-a\)\], as in Appendix[B\.4](https://arxiv.org/html/2610.41129#A2.SS4)\. The third rearranges to\(2​a−1\)​w<a⁡\(κ\+η−c\)\(2a\-1\)w<a\(\\kappa\+\\eta\-c\)\. For the fourth, writeN1=w\+a​cN\_\{1\}=w\+acandD1=κ\+\(1−a\)​w\+a​ηD\_\{1\}=\\kappa\+\(1\-a\)w\+a\\eta, so thatθ1=N1/D1\\theta\_\{1\}=N\_\{1\}/D\_\{1\}andθnw=\[N1−\(1−a\)​w\]/\[D1−\(1−a\)​κ\]\\theta\_\{\\rm nw\}=\[N\_\{1\}\-\(1\-a\)w\]/\[D\_\{1\}\-\(1\-a\)\\kappa\]\. Cross\-multiplying positive denominators shows that, fora<1a<1,θnw<θ1\\theta\_\{\\rm nw\}<\\theta\_\{1\}is equivalent tow​D1\>κ​N1wD\_\{1\}\>\\kappa N\_\{1\}, that is,\(1−a\)​w2\+a⁡\(η​w−κ​c\)\>0\(1\-a\)w^\{2\}\+a\(\\eta w\-\\kappa c\)\>0\. The second condition givesκ​c<w⁡\[η−\(1−a\)​c\]\\kappa c<w\[\\eta\-\(1\-a\)c\], so the left side exceeds\(1−a\)​w2\+a⁡\(1−a\)​w​c\>0\(1\-a\)w^\{2\}\+a\(1\-a\)wc\>0\. Thus the fourth condition is implied by the second, which yields \([10](https://arxiv.org/html/2610.41129#S4.E10)\)\. ∎

### B\.6Proof of Proposition[2](https://arxiv.org/html/2610.41129#Thmproposition2)and verification of Example[1](https://arxiv.org/html/2610.41129#Thmexample1)

###### Proof of Proposition[2](https://arxiv.org/html/2610.41129#Thmproposition2)\.

Suppose such a scorerrexists\. In Example[1](https://arxiv.org/html/2610.41129#Thmexample1), tasksAAandBBhave the same parameters and states in both portfolios, andaaandη\\etaare common\. In\{A,B\}\\\{A,B\\\}, servingAAfirst is uniquely optimal, soBBcannot have the largest score, andr⁡\(A\)\>r⁡\(B\)r\(A\)\>r\(B\)\. In\{A,B,C\}\\\{A,B,C\\\}, servingBBfirst is uniquely optimal, sor⁡\(B\)\>r⁡\(A\)r\(B\)\>r\(A\)\. This is a contradiction\. The strict optimality claims are verified below\. ∎

##### Setup

All tasks are initially unsubmitted and have no work,αi=1\\alpha\_\{i\}=1,a=1a=1,ci=0\.01c\_\{i\}=0\.01,κi=0\.05\\kappa\_\{i\}=0\.05, andη=0\.05\\eta=0\.05; tasksAA,BB,CChave\(wi,pi\)=\(4,0\.75\)\(w\_\{i\},p\_\{i\}\)=\(4,0\.75\),\(1,0\.10\)\(1,0\.10\), and\(0\.5,0\)\(0\.5,0\)\. Every period is available\. Each task has at most one useful search, after whose failure it can be resolved only by the human, and searchingCCis useless becausepC=0p\_\{C\}=0\. Every task’s eventual answer costsfi=κi\+η=0\.1f\_\{i\}=\\kappa\_\{i\}\+\\eta=0\.1\. By Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1), we may restrict attention to plans that submit at most the question that is served, never search a served task, and change the state with positive probability\. This restriction preserves the optimal cost conditional on each choice of first service, because the constructions in Appendix[B\.2](https://arxiv.org/html/2610.41129#A2.SS2)serve the same questions in the same periods as the policy they modify\. LetVXhV^\{\\rm h\}\_\{X\}denote the optimal cost of a setXXof tasks that all require the human\. By Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3), these tasks are served in descending weight order, one per period, so

VAh=4\.1,VBh=1\.1,VCh=0\.6,VA​Bh=6\.2,VA​Ch=5\.2,VB​Ch=2\.2,VA​B​Ch=7\.8\.V^\{\\rm h\}\_\{A\}=4\.1,\\quad V^\{\\rm h\}\_\{B\}=1\.1,\\quad V^\{\\rm h\}\_\{C\}=0\.6,\\quad V^\{\\rm h\}\_\{AB\}=6\.2,\\quad V^\{\\rm h\}\_\{AC\}=5\.2,\\quad V^\{\\rm h\}\_\{BC\}=2\.2,\\quad V^\{\\rm h\}\_\{ABC\}=7\.8\.For example,VA​B​Ch=4⋅1\+1⋅2\+0\.5⋅3\+fA\+fB\+fC=7\.8V^\{\\rm h\}\_\{ABC\}=4\\cdot 1\+1\\cdot 2\+0\.5\\cdot 3\+f\_\{A\}\+f\_\{B\}\+f\_\{C\}=7\.8\.

##### Intermediate values

We need the values of states in which some tasks have searched without success and others have not yet searched; writeXuX^\{\\rm u\}for an unsearched task andXfX^\{\\rm f\}for a task whose search has failed\. A single unsearched task has valuesV⁡\(Au\)=min⁡\{4\.1,4\+0\.01\+0\.25​VAh\}=4\.1V\(A^\{\\rm u\}\)=\\min\\\{4\.1,\\;4\+0\.01\+0\.25V^\{\\rm h\}\_\{A\}\\\}=4\.1andV⁡\(Bu\)=min⁡\{1\.1,1\+0\.01\+0\.9​VBh\}=1\.1V\(B^\{\\rm u\}\)=\\min\\\{1\.1,\\;1\+0\.01\+0\.9V^\{\\rm h\}\_\{B\}\\\}=1\.1\. Enumerating the first\-period decisions in the same way gives

V⁡\(Au,Bu\)=6\.100,V⁡\(Af,Bu\)=6\.100,V⁡\(Au,Bf\)=6\.135,\\displaystyle V\(A^\{\\rm u\},B^\{\\rm u\}\)=6\.100,\\quad V\(A^\{\\rm f\},B^\{\\rm u\}\)=6\.100,\\quad V\(A^\{\\rm u\},B^\{\\rm f\}\)=6\.135,V⁡\(Au,C\)=5\.200,V⁡\(Bu,C\)=2\.200,\\displaystyle V\(A^\{\\rm u\},C\)=5\.200,\\quad V\(B^\{\\rm u\},C\)=2\.200,V⁡\(Af,Bu,C\)=7\.650,V⁡\(Au,Bf,C\)=7\.360\.V\(A^\{\\rm f\},B^\{\\rm u\},C\)=7\.650,\\qquad V\(A^\{\\rm u\},B^\{\\rm f\},C\)=7\.360\.Once a task is served, its search history no longer matters, so servingAAwhileBBsearches costs7\.6507\.650at\(Af,Bu,C\)\(A^\{\\rm f\},B^\{\\rm u\},C\), as in the corresponding entry of the table below\. The alternatives cost7\.87\.8\(servingAAwithout search\),10\.810\.8\(servingBB\),11\.611\.6\(servingCCwhileBBsearches\), and13\.0513\.05\(declining service whileBBsearches\)\. Similarly,V⁡\(Au,Bf,C\)V\(A^\{\\rm u\},B^\{\\rm f\},C\)is attained by servingBBwhileAAsearches, at7\.3607\.360, against7\.87\.8,7\.9857\.985, and9\.119\.11for servingAA, servingCCwhileAAsearches, and declining service whileAAsearches\. The remaining values follow in the same way\.

##### First\-period decisions

Each entry of the following table is the first period’s delay and fee cost plus the optimal continuation, for a given first service and set of concurrent searches\. A dash denotes a search of the served task, which is dominated\.

For example, in\{A,B\}\\\{A,B\\\}, servingAAwhileBBsearches costs5\+0\.1\+0\.01\+0\.9​VBh=6\.1005\+0\.1\+0\.01\+0\.9V^\{\\rm h\}\_\{B\}=6\.100, and servingBBwhileAAsearches costs5\+0\.1\+0\.01\+0\.25​VAh=6\.1355\+0\.1\+0\.01\+0\.25V^\{\\rm h\}\_\{A\}=6\.135\. In\{A,B,C\}\\\{A,B,C\\\}, servingAAwhileBBsearches costs5\.5\+0\.1\+0\.01\+0\.1​VCh\+0\.9​VB​Ch=7\.6505\.5\+0\.1\+0\.01\+0\.1V^\{\\rm h\}\_\{C\}\+0\.9V^\{\\rm h\}\_\{BC\}=7\.650; servingBBwhileAAsearches costs5\.5\+0\.1\+0\.01\+0\.75​VCh\+0\.25​VA​Ch=7\.3605\.5\+0\.1\+0\.01\+0\.75V^\{\\rm h\}\_\{C\}\+0\.25V^\{\\rm h\}\_\{AC\}=7\.360; servingCCwhileAAandBBsearch costs5\.5\+0\.1\+0\.02\+0\.225​VA​Bh\+0\.025​VAh\+0\.675​VBh=7\.8605\.5\+0\.1\+0\.02\+0\.225V^\{\\rm h\}\_\{AB\}\+0\.025V^\{\\rm h\}\_\{A\}\+0\.675V^\{\\rm h\}\_\{B\}=7\.860; and declining service while both search costs5\.5\+0\.02\+0\.225​VA​B​Ch\+0\.025​VA​Ch\+0\.675​VB​Ch\+0\.075​VCh=8\.9355\.5\+0\.02\+0\.225V^\{\\rm h\}\_\{ABC\}\+0\.025V^\{\\rm h\}\_\{AC\}\+0\.675V^\{\\rm h\}\_\{BC\}\+0\.075V^\{\\rm h\}\_\{C\}=8\.935\. Declining service while onlyAAsearches costs5\.51\+0\.75​V​\(Bu,C\)\+0\.25​V​\(Af,Bu,C\)=9\.07255\.51\+0\.75V\(B^\{\\rm u\},C\)\+0\.25V\(A^\{\\rm f\},B^\{\\rm u\},C\)=9\.0725\. Declining service without any search leaves the state unchanged and is dominated\. Taking the minimum of each row gives the table of Example[1](https://arxiv.org/html/2610.41129#Thmexample1)\. In\{A,B\}\\\{A,B\\\}, servingAAis uniquely optimal; in\{A,B,C\}\\\{A,B,C\\\}, servingBBis uniquely optimal\.

### B\.7Projection, nonnegative prices, and the proof of Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3)

###### Lemma B\.4\(Projection onto a task block\)\.

For any nonempty setIIof tasks, letVIV\_\{I\}be the optimal value of the tasks inIIwhen they share one human with the original availability process and the caps of Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\. For any feasible policyπ\\piof the full portfolio, letJiπ​\(s\)J\_\{i\}^\{\\pi\}\(s\)be the expected cost attributable to taskii, namely its delay cost and its own search, submission, and answer fees\. ThenVI​\(sI\)≤∑i∈IJiπ​\(s\)V\_\{I\}\(s\_\{I\}\)\\leq\\sum\_\{i\\in I\}J\_\{i\}^\{\\pi\}\(s\)\. In particular,Δi​j=Vi​j−Vi−Vj≥0\\Delta\_\{ij\}=V\_\{ij\}\-V\_\{i\}\-V\_\{j\}\\geq 0\.

###### Proof\.

Runπ\\piin the system that contains only the tasks inII, simulating the excluded tasks with independently drawn search outcomes and using the same availability process\. Wheneverπ\\piserves an excluded task, leave the human idle\. The tasks inIIreceive the same actions as in the full system\. Because the excluded tasks’ outcomes are independent of everything else and the state is a sufficient statistic, the simulated system has the same joint law as the full system, so the tasks inIIincur the same expected costs\. Conditional on the simulated outcomes, this is a feasible policy for the block\. It may search a task ofIIbeyond its cap ifπ\\pidoes, so it is feasible for the block without caps\. Its cost is therefore at least the block’s optimal value without caps, which equalsVI​\(sI\)V\_\{I\}\(s\_\{I\}\)by Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\(iii\)\. Applying the inequality to an optimal policy for the pair\{i,j\}\\\{i,j\\\}and the two singleton blocks givesVi\+Vj≤Vi​jV\_\{i\}\+V\_\{j\}\\leq V\_\{ij\}\. ∎

###### Proof of Proposition[3](https://arxiv.org/html/2610.41129#Thmproposition3)\.

A resolved task’s remaining cost is its deterministic work cost, which uses neither another agent nor the human, so its value is additive with any other block\. Hence the pairwise approximation equals \([A\.7](https://arxiv.org/html/2610.41129#A1.E7)\)\. With zero or one unresolved task, \([A\.7](https://arxiv.org/html/2610.41129#A1.E7)\) is the exact additive value\. With two unresolved tasksiiandjj, the singleton terms cancel inside the single pairwise price, leavingCR\+Vi​j=V∗C\_\{R\}\+V\_\{ij\}=V^\{\*\}\.

Now suppose that no remaining search can succeed and that every unresolved task hasxi=0x\_\{i\}=0\. Each unresolved task must be served once and paysfi=η\+κi𝟏\{zi=U\}f\_\{i\}=\\eta\+\\kappa\_\{i\}\\mathbf\{1\}\\\{z\_\{i\}=U\\\}\. Under any policy, theℓ\\ellth service among unresolved tasks occurs no earlier than theℓ\\ellth available periodTℓT\_\{\\ell\}, and a task completes when it is served\. By the rearrangement inequality, pathwise∑i∈𝒜wi​Ci≥∑ℓw\(ℓ\)​Tℓ\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}C\_\{i\}\\geq\\sum\_\{\\ell\}w\_\{\(\\ell\)\}T\_\{\\ell\}, wherew\(1\)≥w\(2\)≥⋯w\_\{\(1\)\}\\geq w\_\{\(2\)\}\\geq\\cdotsare the sorted weights\. Serving in descending weight order in every available period attains this bound\. Since𝔼​Tℓ=ℓ/a\\mathbb\{E\}T\_\{\\ell\}=\\ell/aand∑ℓℓ​w\(ℓ\)=∑iwi\+∑i<jmin⁡\(wi,wj\)\\sum\_\{\\ell\}\\ell w\_\{\(\\ell\)\}=\\sum\_\{i\}w\_\{i\}\+\\sum\_\{i<j\}\\min\(w\_\{i\},w\_\{j\}\),

V∗=CR\+∑i∈𝒜fi\+1a​\(∑i∈𝒜wi\+∑i<jmin⁡\(wi,wj\)\)\.V^\{\*\}=C\_\{R\}\+\\sum\_\{i\\in\\mathcal\{A\}\}f\_\{i\}\+\\frac\{1\}\{a\}\\Bigl\(\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}\+\\sum\_\{i<j\}\\min\(w\_\{i\},w\_\{j\}\)\\Bigr\)\.\(B\.3\)Applied to one and two tasks, \([B\.3](https://arxiv.org/html/2610.41129#A2.E3)\) givesVi=fi\+wi/aV\_\{i\}=f\_\{i\}\+w\_\{i\}/aandΔi​j=min⁡\(wi,wj\)/a\\Delta\_\{ij\}=\\min\(w\_\{i\},w\_\{j\}\)/a, which is \([13](https://arxiv.org/html/2610.41129#S5.E13)\)\. Substituting into \([A\.7](https://arxiv.org/html/2610.41129#A1.E7)\) shows that the pairwise approximation equals \([B\.3](https://arxiv.org/html/2610.41129#A2.E3)\)\.

Both boundaries are invariant: the number of unresolved tasks cannot increase, and in the second boundary resolved tasks leave𝒜\\mathcal\{A\}and the remaining ones keepxi=0x\_\{i\}=0and no useful search\. HenceV^PCP=V∗\\widehat\{V\}\_\{\\rm PCP\}=V^\{\*\}at every state of the boundary and at all its successors\. An exact minimizer of \([14](https://arxiv.org/html/2610.41129#S5.E14)\) then minimizesgd​\(s\)\+Pd​V∗​\(s\)g\_\{d\}\(s\)\+P\_\{d\}V^\{\*\}\(s\)over𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\), whose minimum isV∗​\(s\)V^\{\*\}\(s\)by Proposition[A\.2](https://arxiv.org/html/2610.41129#A1.Thmproposition2)\. A policy that attains this minimum at every state and satisfies the progress guard has costV∗V^\{\*\}, by telescopingV∗V^\{\*\}along its trajectory and Lemma[A\.1](https://arxiv.org/html/2610.41129#A1.Thmlemma1)\. This proves that PCP is optimal on both boundaries\. ∎

### B\.8Proofs for Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)

###### Proof of Lemma[A\.1](https://arxiv.org/html/2610.41129#A1.Thmlemma1)\.

Fix an availability outcome and a deterministic pland∈𝒟red​\(s\)d\\in\\mathcal\{D\}\_\{\\rm red\}\(s\)\. Ifddsubmits a question, serves a question, lets an agent search, or lets an agent work, the state changes with probability one: a search either resolves its requirement or raises its failure count, which is below the cap\. Otherwise, the state does not change\. A submission is made in both availability outcomes\. Hence the probability thatddchanges the state is one of00,aa,1−a1\-a, and11, and it is at leastεa\\varepsilon\_\{a\}ifd∈𝒟\+​\(s\)d\\in\\mathcal\{D\}\_\{\+\}\(s\); fora=1a=1only the available outcome has positive probability\. A randomized choice among such plans has the same lower bound\. Under the policy, the conditional probability that the state changes in a period, given the past, is therefore at leastεa\\varepsilon\_\{a\}\. By Lemma[B\.3](https://arxiv.org/html/2610.41129#A2.Thmlemma3), each change lowers the rank by at least one, so at mostrk⁡\(s\)\\mathrm\{rk\}\(s\)changes precede completion, and each takes at most1/εa1/\\varepsilon\_\{a\}periods in expectation\. Hence the expected completion time is at mostrk⁡\(s\)/εa\\mathrm\{rk\}\(s\)/\\varepsilon\_\{a\}\. Per\-period costs are bounded on the finite capped model, so the expected total cost is finite\. ∎

### B\.9Proofs for the human\-resolution regime

Throughout this subsection, the state is in the human\-resolution regime,a¯=1−a\\bar\{a\}=1\-a, andGGis geometric on\{1,2,…\}\\\{1,2,\\ldots\\\}with success probabilityaa\. For a task with workxx, leth⁡\(t\)=w​max⁡\{x,t\}h\(t\)=w\\max\\\{x,t\\\}be its delay cost if its question is answered in periodtt\. BecausePr⁡\(G\>t\)=a¯t\\Pr\(G\>t\)=\\bar\{a\}^\{t\},

𝔼⁡\[h⁡\(t\+G\)−h⁡\(t\)\]=w​𝔼​\[\(t\+G−x\)\+−\(t−x\)\+\]=wa​a¯\(x−t\)\+\\mathbb\{E\}\\bigl\[h\(t\+G\)\-h\(t\)\\bigr\]=w\\,\\mathbb\{E\}\\bigl\[\(t\+G\-x\)^\{\+\}\-\(t\-x\)^\{\+\}\\bigr\]=\\frac\{w\}\{a\}\\,\\bar\{a\}^\{\(x\-t\)^\{\+\}\}\(B\.4\)for everyt≥0t\\geq 0\. In particular,𝔼​max⁡\{x,G\}=x\+a¯x/a\\mathbb\{E\}\\max\\\{x,G\\\}=x\+\\bar\{a\}^\{x\}/a\.

###### Proof of Lemma[A\.2](https://arxiv.org/html/2610.41129#A1.Thmlemma2)\.

Every unresolved task must be answered exactly once and paysfif\_\{i\}exactly once\. Under any policy, taskiicompletes no earlier thanmax⁡\{xi,Ti\}\\max\\\{x\_\{i\},T\_\{i\}\\\}, whereTiT\_\{i\}is the period in which it is answered, and every agent working in every period attains this\.

*Singleton\.*The answer period satisfiesTi≥GT\_\{i\}\\geq G, whereGGis the first available period, and answering atGGis feasible\. Sincehih\_\{i\}is nondecreasing,Vi=fi\+𝔼​hi​\(G\)=fi\+wi​\(xi\+a¯xi/a\)V\_\{i\}=f\_\{i\}\+\\mathbb\{E\}h\_\{i\}\(G\)=f\_\{i\}\+w\_\{i\}\(x\_\{i\}\+\\bar\{a\}^\{x\_\{i\}\}/a\)by \([B\.4](https://arxiv.org/html/2610.41129#A2.E4)\)\.

*Pair\.*Under any policy for the pair, letT\(1\)<T\(2\)T\_\{\(1\)\}<T\_\{\(2\)\}be the two answer periods, letι\\iotabe the task answered second, and letℱ\\mathcal\{F\}be the information available at the end of periodT\(1\)T\_\{\(1\)\}, which determinesι\\iota\. The delay cost equals

hi​\(T\(1\)\)\+hj​\(T\(1\)\)\+\[hι​\(T\(2\)\)−hι​\(T\(1\)\)\]\.h\_\{i\}\(T\_\{\(1\)\}\)\+h\_\{j\}\(T\_\{\(1\)\}\)\+\\bigl\[h\_\{\\iota\}\(T\_\{\(2\)\}\)\-h\_\{\\iota\}\(T\_\{\(1\)\}\)\\bigr\]\.Because availability is independent over time,T\(2\)−T\(1\)T\_\{\(2\)\}\-T\_\{\(1\)\}is at least a geometric random variable independent ofℱ\\mathcal\{F\}\. By \([B\.4](https://arxiv.org/html/2610.41129#A2.E4)\), the conditional expectation of the bracket givenℱ\\mathcal\{F\}is at leastζι​\(T\(1\)\)≥ζ⁡\(T\(1\)\)\\zeta\_\{\\iota\}\(T\_\{\(1\)\}\)\\geq\\zeta\(T\_\{\(1\)\}\), whereζk​\(t\)=\(wk/a\)​a¯\(xk−t\)\+\\zeta\_\{k\}\(t\)=\(w\_\{k\}/a\)\\bar\{a\}^\{\(x\_\{k\}\-t\)^\{\+\}\}andζ=min⁡\{ζi,ζj\}\\zeta=\\min\\\{\\zeta\_\{i\},\\zeta\_\{j\}\\\}\. Bothhkh\_\{k\}andζ\\zetaare nondecreasing andT\(1\)≥GT\_\{\(1\)\}\\geq G, so the expected delay cost is at least𝔼⁡\[hi​\(G\)\+hj​\(G\)\+ζ⁡\(G\)\]\\mathbb\{E\}\[h\_\{i\}\(G\)\+h\_\{j\}\(G\)\+\\zeta\(G\)\]\. Answering atGGthe task with the largerζk​\(G\)\\zeta\_\{k\}\(G\), and the other task at the next available period, attains this bound; it is feasible because the controller can submit, at the start of every period, the question it would answer if the human were available\. Subtracting the singleton values gives \([A\.10](https://arxiv.org/html/2610.41129#A1.E10)\)\.

The monotonicity claims hold pointwise inside the expectation, becausea¯≤1\\bar\{a\}\\leq 1\. Sincea¯\(x−G\)\+≤1\\bar\{a\}^\{\(x\-G\)^\{\+\}\}\\leq 1,Δi​j≤min⁡\(wi,wj\)/a\\Delta\_\{ij\}\\leq\\min\(w\_\{i\},w\_\{j\}\)/a, with equality whenxi,xj≤1x\_\{i\},x\_\{j\}\\leq 1becauseG≥1G\\geq 1\. Whena=1a=1,G=1G=1anda¯\(x−1\)\+=𝟏\{x≤1\}\\bar\{a\}^\{\(x\-1\)^\{\+\}\}=\\mathbf\{1\}\\\{x\\leq 1\\\}\. ∎

###### Proof of Lemma[A\.3](https://arxiv.org/html/2610.41129#A1.Thmlemma3)\.

By Lemma[A\.2](https://arxiv.org/html/2610.41129#A1.Thmlemma2),V^PCP​\(s\)=∑i∈𝒜fi\+Φ⁡\(s\)\\widehat\{V\}\_\{\\rm PCP\}\(s\)=\\sum\_\{i\\in\\mathcal\{A\}\}f\_\{i\}\+\\Phi\(s\), where

Φ⁡\(s\)=CR​\(s\)\+∑i∈𝒜wi​\(xi\+a¯xia\)\+∑i<jΔi​j​\(xi,xj\)\\Phi\(s\)=C\_\{R\}\(s\)\+\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}\\Bigl\(x\_\{i\}\+\\frac\{\\bar\{a\}^\{x\_\{i\}\}\}\{a\}\\Bigr\)\+\\sum\_\{i<j\}\\Delta\_\{ij\}\(x\_\{i\},x\_\{j\}\)depends only on the remaining work and on which tasks are unresolved\. In this regime, no plan searches and every agent with work works\. A submission of questionjjpaysκj\\kappa\_\{j\}now and removesκj\\kappa\_\{j\}fromfjf\_\{j\}at every successor, and an answer paysη\\etaand removes the remainingfj=ηf\_\{j\}=\\eta\. Hence, for everyd∈𝒟\+​\(s\)d\\in\\mathcal\{D\}\_\{\+\}\(s\),

gd​\(s\)\+Pd​V^PCP​\(s\)=ω⁡\(s\)\+∑i∈𝒜fi\+\(1−a\)​Φ​\(s0′\)\+a​Φ​\(sd′\),g\_\{d\}\(s\)\+P\_\{d\}\\widehat\{V\}\_\{\\rm PCP\}\(s\)=\\omega\(s\)\+\\sum\_\{i\\in\\mathcal\{A\}\}f\_\{i\}\+\(1\-a\)\\,\\Phi\(s^\{\\prime\}\_\{0\}\)\+a\\,\\Phi\(s^\{\\prime\}\_\{d\}\),wheres0′s^\{\\prime\}\_\{0\}is the successor in which every agent works and no question is answered, which is the same for all plans, andsd′s^\{\\prime\}\_\{d\}is the successor in the available outcome\. Every unresolved task can be served in the available outcome: a pending question can be served directly, and an unsubmitted one can be submitted and served under rule \(a\)\. Thus exact PCP chooses the service in the available outcome to maximizeΓj=Φ⁡\(s0′\)−Φ⁡\(s\(j\)′\)\\Gamma\_\{j\}=\\Phi\(s^\{\\prime\}\_\{0\}\)\-\\Phi\(s^\{\\prime\}\_\{\(j\)\}\)over unresolved tasksjj, wheres\(j\)′s^\{\\prime\}\_\{\(j\)\}is the successor in whichjjis served, with serving no one counted asΓ=0\\Gamma=0and ties resolved by the tie rule\.

Letyk=\(xk−1\)\+y\_\{k\}=\(x\_\{k\}\-1\)^\{\+\}be the work after the period\. Servingjjreplacesjj’s termwj​\(yj\+a¯yj/a\)w\_\{j\}\(y\_\{j\}\+\\bar\{a\}^\{y\_\{j\}\}/a\)by the resolved costwj​yjw\_\{j\}y\_\{j\}and removes its pairwise prices, so

Γj=wj​a¯yja\+∑k∈𝒜∖\{j\}Δj​k​\(yj,yk\)\.\\Gamma\_\{j\}=\\frac\{w\_\{j\}\\bar\{a\}^\{y\_\{j\}\}\}\{a\}\+\\sum\_\{k\\in\\mathcal\{A\}\\setminus\\\{j\\\}\}\\Delta\_\{jk\}\(y\_\{j\},y\_\{k\}\)\.Ifxi≤1x\_\{i\}\\leq 1, thenyi=0y\_\{i\}=0andΓi≥wi/a\>0\\Gamma\_\{i\}\\geq w\_\{i\}/a\>0, so PCP serves some task\. Supposewj<wiw\_\{j\}<w\_\{i\}\. The priceΔi​j\\Delta\_\{ij\}appears in bothΓi\\Gamma\_\{i\}andΓj\\Gamma\_\{j\}and cancels in their difference\. For every other taskkk,Δi​k​\(0,yk\)≥Δj​k​\(yj,yk\)\\Delta\_\{ik\}\(0,y\_\{k\}\)\\geq\\Delta\_\{jk\}\(y\_\{j\},y\_\{k\}\), becausewi≥wj​a¯\(yj−G\)\+w\_\{i\}\\geq w\_\{j\}\\bar\{a\}^\{\(y\_\{j\}\-G\)^\{\+\}\}pointwise in \([A\.10](https://arxiv.org/html/2610.41129#A1.E10)\)\. Moreover,wi/a\>wj​a¯yj/aw\_\{i\}/a\>w\_\{j\}\\bar\{a\}^\{y\_\{j\}\}/a\. HenceΓi\>Γj\\Gamma\_\{i\}\>\\Gamma\_\{j\}, and PCP does not servejj\.

In terms of the objective in \([14](https://arxiv.org/html/2610.41129#S5.E14)\), servingiiinstead ofjjlowers it bya⁡\(Γi−Γj\)≥wi−wja\(\\Gamma\_\{i\}\-\\Gamma\_\{j\}\)\\geq w\_\{i\}\-w\_\{j\}, and servingiiinstead of no one lowers it bya​Γi≥wia\\Gamma\_\{i\}\\geq w\_\{i\}\. A selector that evaluates every service choice and returns a plan within an absolute toleranceτ⁡\(s\)\\tau\(s\)of the minimum therefore has the same two properties wheneverτ⁡\(s\)\\tau\(s\)is smaller than these margins, that is, smaller thanwiw\_\{i\}and than every positive differencewi−wjw\_\{i\}\-w\_\{j\}, as stated in Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)\. ∎

###### Proof of Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(i\)\.

Letfif\_\{i\}andw𝒜=∑i∈𝒜wiw\_\{\\mathcal\{A\}\}=\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}be as above, so thatK=CR\+∑i∈𝒜fiK=C\_\{R\}\+\\sum\_\{i\\in\\mathcal\{A\}\}f\_\{i\}\.

*Lower bounds on the optimum\.*Every unresolved task completes no earlier than its remaining work and no earlier than period11, soV∗≥K\+BV^\{\*\}\\geq K\+B\. Removing the remaining work of unresolved tasks can only lower the optimum, because every policy remains feasible without the work and completes every task no later; the resulting value isK\+QK\+Qby \([B\.3](https://arxiv.org/html/2610.41129#A2.E3)\)\. Hence

V∗≥K\+max⁡\{B,Q\}\.V^\{\*\}\\geq K\+\\max\\\{B,Q\\\}\.\(B\.5\)
*PCP’s delay cost\.*LetTiT\_\{i\}be the period in which PCP answers taskii\. Every agent works until its work is finished, so taskiicompletes atCi=max⁡\{xi,Ti\}C\_\{i\}=\\max\\\{x\_\{i\},T\_\{i\}\\\}\. Letℓi=max⁡\{xi,1\}\\ell\_\{i\}=\\max\\\{x\_\{i\},1\\\}and letℰi=\{Ti<ℓi\}\\mathcal\{E\}\_\{i\}=\\\{T\_\{i\}<\\ell\_\{i\}\\\}be the event that the answer arrives before the work is finished\. Pathwise,

Ci=\(ℓi−1\)\+𝟏\{ℰi\}\+∑t≥ℓi𝟏\{Ti≥t\}\.C\_\{i\}=\(\\ell\_\{i\}\-1\)\+\\mathbf\{1\}\\\{\\mathcal\{E\}\_\{i\}\\\}\+\\sum\_\{t\\geq\\ell\_\{i\}\}\\mathbf\{1\}\\\{T\_\{i\}\\geq t\\\}\.Indeed, onℰi\\mathcal\{E\}\_\{i\}the task completes atℓi=xi\\ell\_\{i\}=x\_\{i\}and the sum is empty, and otherwise the sum hasTi−ℓi\+1T\_\{i\}\-\\ell\_\{i\}\+1terms\. LetNi=∑t≥ℓi𝟏​\{Ti≥t,the human is available in period​t\}N\_\{i\}=\\sum\_\{t\\geq\\ell\_\{i\}\}\\mathbf\{1\}\\\{T\_\{i\}\\geq t,\\ \\text\{the human is available in period \}t\\\}\. The event\{Ti≥t\}\\\{T\_\{i\}\\geq t\\\}is determined before periodtt’s availability is drawn, so by independence and Tonelli’s theorem,

𝔼∑t≥ℓi𝟏\{Ti≥t\}=1a𝔼Ni\.\\mathbb\{E\}\\sum\_\{t\\geq\\ell\_\{i\}\}\\mathbf\{1\}\\\{T\_\{i\}\\geq t\\\}=\\frac\{1\}\{a\}\\,\\mathbb\{E\}N\_\{i\}\.\(B\.6\)This does not require the service order to be independent of availability\. In every period counted byNiN\_\{i\}, taskiiis unresolved with at most one unit of work left, and the human is available\. By Lemma[A\.3](https://arxiv.org/html/2610.41129#A1.Thmlemma3), PCP serves some taskjjwithwj≥wiw\_\{j\}\\geq w\_\{i\}in that period\. Ifj=ij=i, the period isTiT\_\{i\}, which can be counted only onℰic\\mathcal\{E\}\_\{i\}^\{c\}\. Ifj≠ij\\neq i, charge the period to the pair\{i,j\}\\\{i,j\\\}, at costwi=min⁡\(wi,wj\)w\_\{i\}=\\min\(w\_\{i\},w\_\{j\}\)\. Each pair is charged at most once, because only the member answered first can be served while the other waits, and each task is answered once\. Hence, pathwise,

∑i∈𝒜wi​Ni≤∑i∈𝒜wi​𝟏​\{ℰic\}\+∑i<jmin⁡\(wi,wj\)\.\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}N\_\{i\}\\leq\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}\\mathbf\{1\}\\\{\\mathcal\{E\}\_\{i\}^\{c\}\\\}\+\\sum\_\{i<j\}\\min\(w\_\{i\},w\_\{j\}\)\.Combining this with \([B\.6](https://arxiv.org/html/2610.41129#A2.E6)\), the identity forCiC\_\{i\}, anda≤1a\\leq 1,

∑i∈𝒜wi​𝔼​Ci≤B−w𝒜\+∑iwi​Pr⁡\(ℰi\)\+1a​∑iwi​Pr⁡\(ℰic\)\+1a​∑i<jmin⁡\(wi,wj\)≤B−w𝒜\+Q\.\\sum\_\{i\\in\\mathcal\{A\}\}w\_\{i\}\\mathbb\{E\}C\_\{i\}\\leq B\-w\_\{\\mathcal\{A\}\}\+\\sum\_\{i\}w\_\{i\}\\Pr\(\\mathcal\{E\}\_\{i\}\)\+\\frac\{1\}\{a\}\\sum\_\{i\}w\_\{i\}\\Pr\(\\mathcal\{E\}\_\{i\}^\{c\}\)\+\\frac\{1\}\{a\}\\sum\_\{i<j\}\\min\(w\_\{i\},w\_\{j\}\)\\leq B\-w\_\{\\mathcal\{A\}\}\+Q\.PCP pays each unresolved task’s feesfif\_\{i\}exactly once and the resolved work costCRC\_\{R\}, so

JPCP≤K\+B\+Q−w𝒜\.J^\{\\rm PCP\}\\leq K\+B\+Q\-w\_\{\\mathcal\{A\}\}\.\(B\.7\)The progress guard ensures that all expectations are finite \(Lemma[A\.1](https://arxiv.org/html/2610.41129#A1.Thmlemma1)\)\.

*Conclusion\.*By \([B\.5](https://arxiv.org/html/2610.41129#A2.E5)\),B\+Q≤2​\(V∗−K\)B\+Q\\leq 2\(V^\{\*\}\-K\), so \([B\.7](https://arxiv.org/html/2610.41129#A2.E7)\) givesJPCP≤2​V∗−K−w𝒜≤2​V∗J^\{\\rm PCP\}\\leq 2V^\{\*\}\-K\-w\_\{\\mathcal\{A\}\}\\leq 2V^\{\*\}, which is \([16](https://arxiv.org/html/2610.41129#S5.E16)\)\. The argument uses exact minimization only in the service choice, through Lemma[A\.3](https://arxiv.org/html/2610.41129#A1.Thmlemma3), and holds for every tie rule\. It therefore applies to any implementation that enumerates the admissible submissions and optimizes the service choice exactly in this regime\. It also applies to the coordinate implementation of Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)whenever its absolute tolerance satisfies the condition stated there\.

*Lower boundφ\\varphiunder the no\-submission tie rule\.*This is Lemma[A\.4](https://arxiv.org/html/2610.41129#A1.Thmlemma4), proved in Appendix[B\.10](https://arxiv.org/html/2610.41129#A2.SS10)\. ∎

###### Proof of Corollary[A\.1](https://arxiv.org/html/2610.41129#A1.Thmcorollary1)\.

By \([B\.7](https://arxiv.org/html/2610.41129#A2.E7)\) and \([B\.5](https://arxiv.org/html/2610.41129#A2.E5)\),JPCP−V∗≤B\+Q−w𝒜−max⁡\{B,Q\}=min⁡\{B,Q\}−w𝒜J^\{\\rm PCP\}\-V^\{\*\}\\leq B\+Q\-w\_\{\\mathcal\{A\}\}\-\\max\\\{B,Q\\\}=\\min\\\{B,Q\\\}\-w\_\{\\mathcal\{A\}\}, and dividing byV∗≥K\+max⁡\{B,Q\}V^\{\*\}\\geq K\+\\max\\\{B,Q\\\}gives the first inequality in \([A\.11](https://arxiv.org/html/2610.41129#A1.E11)\)\. The second holds becausemin⁡\{B,Q\}≤max⁡\{B,Q\}\\min\\\{B,Q\\\}\\leq\\max\\\{B,Q\\\}\. Note thatmin⁡\{B,Q\}≥w𝒜\\min\\\{B,Q\\\}\\geq w\_\{\\mathcal\{A\}\}, becauseB≥w𝒜B\\geq w\_\{\\mathcal\{A\}\}andQ≥w𝒜/aQ\\geq w\_\{\\mathcal\{A\}\}/a\. Ifxi≤1x\_\{i\}\\leq 1for all unresolved tasks, thenB=w𝒜B=w\_\{\\mathcal\{A\}\}, soJPCP≤K\+Q≤V∗J^\{\\rm PCP\}\\leq K\+Q\\leq V^\{\*\}and henceJPCP=V∗=K\+QJ^\{\\rm PCP\}=V^\{\*\}=K\+Q\. Moreover,xi\+a¯xi/a=1/ax\_\{i\}\+\\bar\{a\}^\{x\_\{i\}\}/a=1/aforxi∈\{0,1\}x\_\{i\}\\in\\\{0,1\\\}andΔi​j=min⁡\(wi,wj\)/a\\Delta\_\{ij\}=\\min\(w\_\{i\},w\_\{j\}\)/aby Lemma[A\.2](https://arxiv.org/html/2610.41129#A1.Thmlemma2), soV^PCP​\(s\)=K\+Q\\widehat\{V\}\_\{\\rm PCP\}\(s\)=K\+Qby \([A\.7](https://arxiv.org/html/2610.41129#A1.E7)\)\. ∎

### B\.10Proof of Lemma[A\.4](https://arxiv.org/html/2610.41129#A1.Thmlemma4)

Becausepi=0p\_\{i\}=0, the caps are zero and the portfolio is in the human\-resolution regime from the start\. Witha=1a=1, the human can answer one question in every period\. Thejjth question answered is answered no earlier than periodjj, and its task completes no earlier thanmax⁡\{b,j\}\\max\\\{b,j\\\}, soV∗≥∑j=1nmax⁡\{b,j\}V^\{\*\}\\geq\\sum\_\{j=1\}^\{n\}\\max\\\{b,j\\\}; answering one question per period from period 1 attains this bound\.

Ifb≤1b\\leq 1, every unresolved task has at most one unit of work, and Corollary[A\.1](https://arxiv.org/html/2610.41129#A1.Thmcorollary1)shows that PCP is optimal, with cost∑j=1nj=n⁡\(n\+1\)/2\\sum\_\{j=1\}^\{n\}j=n\(n\+1\)/2\.

Letb≥2b\\geq 2\. All agents work in every period, so all unresolved tasks always have the same remaining workxx\. Witha=1a=1and zero fees, the quantityΓj\\Gamma\_\{j\}in the proof of Lemma[A\.3](https://arxiv.org/html/2610.41129#A1.Thmlemma3)is𝟏\{y=0\}\+\(m−1\)𝟏\{y≤1\}\\mathbf\{1\}\\\{y=0\\\}\+\(m\-1\)\\mathbf\{1\}\\\{y\\leq 1\\\}, wherey=\(x−1\)\+y=\(x\-1\)^\{\+\}andmmis the number of unresolved tasks\. Ifx≥3x\\geq 3, theny≥2y\\geq 2andΓj=0\\Gamma\_\{j\}=0for everyjj, so every plan ties, and the no\-submission rule neither submits nor serves\. Ifx=2x=2, theny=1y=1andΓj=m−1\>0\\Gamma\_\{j\}=m\-1\>0, so PCP serves a question\. Afterwards every unresolved task hasx≤1x\\leq 1, and by Lemma[A\.3](https://arxiv.org/html/2610.41129#A1.Thmlemma3)PCP serves one question per period until none remain\. The first question is therefore answered in periodb−1b\-1, whenx=2x=2, and the completion times areb,b,b\+1,…,b\+n−2b,b,b\+1,\\ldots,b\+n\-2\. Their sum isn​b\+\(n−1\)​\(n−2\)/2nb\+\(n\-1\)\(n\-2\)/2\.

For the ratio,2​V∗=n2\+b2\+n−b2V^\{\*\}=n^\{2\}\+b^\{2\}\+n\-bwhenb≤nb\\leq n, andV∗=n​bV^\{\*\}=nbwhenb≥nb\\geq n\. If2≤b≤n2\\leq b\\leq n,

JPCPV∗=2​n​b\+n2−3​n\+2n2\+b2\+n−b≤n2\+2​n​bn2\+b2≤φ\.\\frac\{J^\{\\rm PCP\}\}\{V^\{\*\}\}=\\frac\{2nb\+n^\{2\}\-3n\+2\}\{n^\{2\}\+b^\{2\}\+n\-b\}\\leq\\frac\{n^\{2\}\+2nb\}\{n^\{2\}\+b^\{2\}\}\\leq\\varphi\.The first inequality holds because the cross\-multiplied difference,\(n2\+b2\)​\(2−3​n\)−\(n2\+2​n​b\)​\(n−b\)\(n^\{2\}\+b^\{2\}\)\(2\-3n\)\-\(n^\{2\}\+2nb\)\(n\-b\), is negative\. The second follows fromφ⁡\(n2\+b2\)−\(n2\+2​n​b\)=φ​\(b−n/φ\)2≥0\\varphi\(n^\{2\}\+b^\{2\}\)\-\(n^\{2\}\+2nb\)=\\varphi\(b\-n/\\varphi\)^\{2\}\\geq 0, which usesφ−1=1/φ\\varphi\-1=1/\\varphi\. Ifb≥nb\\geq n, the ratio is1\+\(n−1\)​\(n−2\)/\(2​n​b\)<3/2<φ1\+\(n\-1\)\(n\-2\)/\(2nb\)<3/2<\\varphi\. Alongb=⌊n/φ⌋b=\\lfloor n/\\varphi\\rfloor, the ratio converges to\(1\+2/φ\)/\(1\+1/φ2\)=5/\(3−φ\)=φ\(1\+2/\\varphi\)/\(1\+1/\\varphi^\{2\}\)=\\sqrt\{5\}/\(3\-\\varphi\)=\\varphi\.

Finally, consider a tie rule that prefers serving a question among tied plans\. Then PCP serves a question in every period: whenx≥3x\\geq 3all plans tie, and whenx≤2x\\leq 2serving is strictly better or tied, with every remaining task alike\. Hence it answers one question per period from period 1, which is optimal\. ∎

### B\.11Proofs for the Bellman defect

###### Proof of Lemma[A\.5](https://arxiv.org/html/2610.41129#A1.Thmlemma5)\.

Project planddonto taskiiby keeping taskii’s submission, service, and agent actions and replacing any service of another task by no service\. This is a feasible plan for the singleton problem, with immediate costgidg\_\{i\}^\{d\}and next\-state law equal to the marginal ofSi′S^\{\\prime\}\_\{i\}underdd; the projection uses only the current state\. The singleton value satisfies the Bellman inequalityVi≤g\+P​ViV\_\{i\}\\leq g\+PV\_\{i\}for every feasible singleton plan, including plans that may leave the state unchanged, because using the plan for one period and continuing optimally thereafter is feasible\. Henceλid≥0\\lambda\_\{i\}^\{d\}\\geq 0, and the same argument for pairs givesλi​jd≥0\\lambda\_\{ij\}^\{d\}\\geq 0\.

Forn≥2n\\geq 2, the definitions giveV^PCP=∑i<jVi​j−\(n−2\)​∑iVi\\widehat\{V\}\_\{\\rm PCP\}=\\sum\_\{i<j\}V\_\{ij\}\-\(n\-2\)\\sum\_\{i\}V\_\{i\}, with sums over all tasks, because eachViV\_\{i\}appears inn−1n\-1pair values\. Since∑igid=gd\\sum\_\{i\}g\_\{i\}^\{d\}=g\_\{d\}and eachgidg\_\{i\}^\{d\}appearsn−1n\-1times in the pair sum andn−2n\-2times in the subtracted singleton sum, \([A\.14](https://arxiv.org/html/2610.41129#A1.E14)\) follows; forn=1n=1it reduces togd\+Pd​V1−V1=λ1dg\_\{d\}\+P\_\{d\}V\_\{1\}\-V\_\{1\}=\\lambda\_\{1\}^\{d\}\.

If taskiiis resolved, rule \(d\) makes it work in every period until it is finished, soλid=0\\lambda\_\{i\}^\{d\}=0\. Its pair value with any taskjjis additive at the current state and at every successor, soλi​jd=λjd\\lambda\_\{ij\}^\{d\}=\\lambda\_\{j\}^\{d\}, which is zero ifjjis also resolved\. Then−mn\-mresolved tasks therefore contribute\(n−m\)​∑j∈𝒜λjd\(n\-m\)\\sum\_\{j\\in\\mathcal\{A\}\}\\lambda\_\{j\}^\{d\}to the pair sum in \([A\.14](https://arxiv.org/html/2610.41129#A1.E14)\), which leaves the coefficient−\(m−2\)\-\(m\-2\)on∑j∈𝒜λjd\\sum\_\{j\\in\\mathcal\{A\}\}\\lambda\_\{j\}^\{d\}\. Minimizing over𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)gives \([A\.15](https://arxiv.org/html/2610.41129#A1.E15)\)\. ∎

###### Proof of Proposition[A\.4](https://arxiv.org/html/2610.41129#A1.Thmproposition4)\.

WriteH=V^PCPH=\\widehat\{V\}\_\{\\rm PCP\}and recall thatgd​\(s\)≥ω⁡\(s\)\>0g\_\{d\}\(s\)\\geq\\omega\(s\)\>0at unfinished states andH≥0H\\geq 0, withH=0H=0at terminal states\.

*Part \(i\)\.*By the definitions ofρ\\rhoandeπe\_\{\\pi\}, at every unfinished statessreachable underπ\\pi,

gπ⁡\(s\)​\(s\)\+Pπ⁡\(s\)​H​\(s\)−H⁡\(s\)=ρ⁡\(s\)\+eπ​\(s\)≤\(ϵ\+\+δ\)​ω​\(s\)≤\(ϵ\+\+δ\)​gπ⁡\(s\)​\(s\),g\_\{\\pi\(s\)\}\(s\)\+P\_\{\\pi\(s\)\}H\(s\)\-H\(s\)=\\rho\(s\)\+e\_\{\\pi\}\(s\)\\leq\(\\epsilon\_\{\+\}\+\\delta\)\\,\\omega\(s\)\\leq\(\\epsilon\_\{\+\}\+\\delta\)\\,g\_\{\\pi\(s\)\}\(s\),so\(1−ϵ\+−δ\)​gπ⁡\(s\)​\(s\)≤H⁡\(s\)−Pπ⁡\(s\)​H​\(s\)\(1\-\\epsilon\_\{\+\}\-\\delta\)\\,g\_\{\\pi\(s\)\}\(s\)\\leq H\(s\)\-P\_\{\\pi\(s\)\}H\(s\)\. The policyπ\\pisatisfies the progress guard, so it completes the portfolio with probability one \(Lemma[A\.1](https://arxiv.org/html/2610.41129#A1.Thmlemma1)\)\. Summing along its trajectory up to periodTTgives\(1−ϵ\+−δ\)​𝔼​∑t<Tg⁡\(St\)≤H⁡\(s0\)−𝔼​H​\(ST\)≤H⁡\(s0\)\(1\-\\epsilon\_\{\+\}\-\\delta\)\\,\\mathbb\{E\}\\sum\_\{t<T\}g\(S\_\{t\}\)\\leq H\(s\_\{0\}\)\-\\mathbb\{E\}H\(S\_\{T\}\)\\leq H\(s\_\{0\}\), and monotone convergence asT→∞T\\to\\inftyyieldsJπ​\(s0\)≤H⁡\(s0\)/\(1−ϵ\+−δ\)J^\{\\pi\}\(s\_\{0\}\)\\leq H\(s\_\{0\}\)/\(1\-\\epsilon\_\{\+\}\-\\delta\)\.

*Part \(ii\)\.*Letπ∗\\pi^\{\*\}be the optimal deterministic stationary policy of Proposition[A\.2](https://arxiv.org/html/2610.41129#A1.Thmproposition2), which selects plans in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\); starting froms0s\_\{0\}, it stays in𝒮\\mathcal\{S\}because𝒮\\mathcal\{S\}is forward closed\. For every unfinisheds∈𝒮s\\in\\mathcal\{S\}andd=π∗​\(s\)d=\\pi^\{\*\}\(s\),

gd​\(s\)\+Pd​H​\(s\)−H⁡\(s\)≥ρ⁡\(s\)≥−ϵ−​ω​\(s\)≥−ϵ−​gd​\(s\),g\_\{d\}\(s\)\+P\_\{d\}H\(s\)\-H\(s\)\\geq\\rho\(s\)\\geq\-\\epsilon\_\{\-\}\\,\\omega\(s\)\\geq\-\\epsilon\_\{\-\}\\,g\_\{d\}\(s\),soH⁡\(s\)≤\(1\+ϵ−\)​gd​\(s\)\+Pd​H​\(s\)H\(s\)\\leq\(1\+\\epsilon\_\{\-\}\)\\,g\_\{d\}\(s\)\+P\_\{d\}H\(s\)\. Summing along the trajectory ofπ∗\\pi^\{\*\}up to periodTTgivesH⁡\(s0\)≤\(1\+ϵ−\)​𝔼​∑t<Tg⁡\(St\)\+𝔼​H​\(ST\)H\(s\_\{0\}\)\\leq\(1\+\\epsilon\_\{\-\}\)\\,\\mathbb\{E\}\\sum\_\{t<T\}g\(S\_\{t\}\)\+\\mathbb\{E\}H\(S\_\{T\}\)\. BecauseHHis bounded on the finite state space andSTS\_\{T\}is terminal for all largeTTalmost surely,𝔼​H​\(ST\)→0\\mathbb\{E\}H\(S\_\{T\}\)\\to 0by dominated convergence, soH⁡\(s0\)≤\(1\+ϵ−\)​V∗​\(s0\)H\(s\_\{0\}\)\\leq\(1\+\\epsilon\_\{\-\}\)V^\{\*\}\(s\_\{0\}\)\.

*Combination\.*The states reachable underπ\\pibelong to𝒮\\mathcal\{S\}, becauseπ\\piselects plans in𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\)and𝒮\\mathcal\{S\}is forward closed\. Hence the combined conditions imply those of parts \(i\) and \(ii\), and \([A\.16](https://arxiv.org/html/2610.41129#A1.E16)\) follows\. Neither argument uses a discount factor or removes self\-transitions from𝒯\\mathcal\{T\}\. ∎

###### Proof of Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(ii\)\.

Exact PCP haseπ≡0e\_\{\\pi\}\\equiv 0\. Apply Proposition[A\.4](https://arxiv.org/html/2610.41129#A1.Thmproposition4)withδ=0\\delta=0on the set𝒮\\mathcal\{S\}of Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(ii\)\. ∎

## Appendix CDetails of the Numerical Experiments

This appendix documents the policies, instances, and evaluation methods of the synthetic experiments in Section[6\.1](https://arxiv.org/html/2610.41129#S6.SS1)and of the LLM case study in Section[6\.2](https://arxiv.org/html/2610.41129#S6.SS2)\. It also describes the computing environment, shows that the mechanisms of Section[4](https://arxiv.org/html/2610.41129#S4)extend beyond the settings of the theorems, and reports additional results\. All experiments use the exact dynamic program of Proposition[A\.2](https://arxiv.org/html/2610.41129#A1.Thmproposition2)with the caps of Proposition[A\.1](https://arxiv.org/html/2610.41129#A1.Thmproposition1)\.

### C\.1Policies and implementation

##### PCP and the singleton policy

Both policies minimize \([14](https://arxiv.org/html/2610.41129#S5.E14)\) over𝒟\+​\(s\)\\mathcal\{D\}\_\{\+\}\(s\), with the pairwise and the singleton approximation, respectively, and use exact singleton and pair values\. In the benchmark of Section[6\.1\.1](https://arxiv.org/html/2610.41129#S6.SS1.SSS1)we report both exact minimization, which enumerates every plan, and the coordinate search of Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3)\. The larger portfolios of Section[6\.1\.3](https://arxiv.org/html/2610.41129#S6.SS1.SSS3)and the experiment with misestimated inputs in Section[6\.1\.4](https://arxiv.org/html/2610.41129#S6.SS1.SSS4)use coordinate search\. Both policies break ties with the service\-preferring rule of Appendix[A\.3](https://arxiv.org/html/2610.41129#A1.SS3), and Table[1](https://arxiv.org/html/2610.41129#S6.T1)and Section[6\.1\.2](https://arxiv.org/html/2610.41129#S6.SS1.SSS2)also report PCP with the no\-submission rule\.

##### Rules for when to ask

Always Ask submits, whenever no question is pending, the question of the unresolved task with the largest weight, breaking ties by task index\. It never searches, and the human answers the pending question with the largest weight whenever available\. Random\-order Ask is identical except that the next task is chosen uniformly at random among the unresolved tasks without a question\. Search Once Then Ask lets every agent work until its independent work is finished, then search once if the search can succeed, and makes the task eligible for a question after that search fails\. Among eligible tasks, it submits the question of the task with the largest weight, and pending tasks do not search\. All three rules obey Lemma[1](https://arxiv.org/html/2610.41129#Thmlemma1)\(ii\), so at most one new question is submitted per period\.

### C\.2Instances

Table[C\.1](https://arxiv.org/html/2610.41129#A3.T1)lists the instances of the synthetic experiments\. The benchmark draws the weights with a pseudorandom generator seeded by the name of the portfolio\. The homogeneous family is that of Lemma[A\.4](https://arxiv.org/html/2610.41129#A1.Thmlemma4), and its closed forms agree with the dynamic program for alln≤5n\\leq 5\. In the experiment with misestimated inputs, both policies compute their value tables and decisions from the misestimated parameters, withppcapped at0\.950\.95andaarestricted to\[0\.1,1\]\[0\.1,1\], and are evaluated under the true parameters\. In the mechanism experiments, the no\-withdrawal model forbids search by an agent whose question has been submitted\.

Table C\.1:Instances of the synthetic experiments\. Unless noted otherwise, all tasks in a portfolio sharebb,pp,α\\alpha, andcc,κi=0\.1\\kappa\_\{i\}=0\.1,η=0\.5\\eta=0\.5, the weights are drawn independently and uniformly from\{0\.5,1,2,4\}\\\{0\.5,1,2,4\\\}, and all tasks start unsubmitted with no failed searches\. The benchmark has three weight draws for each combination of the factors, and the human\-resolution regime and the mechanism portfolios have five\. \(a\)wi=1w\_\{i\}=1andκi=η=0\\kappa\_\{i\}=\\eta=0\. \(b\)w=κ=η=1w=\\kappa=\\eta=1, with 81 combinations ofaaandppfor eachα\\alphaandbb\. \(c\) The weights are fixed acrossbb\. \(d\) Each task draws its ownwiw\_\{i\},pip\_\{i\},cic\_\{i\}, andκi∈\{0\.05,0\.1\}\\kappa\_\{i\}\\in\\\{0\.05,0\.1\\\}, andη∈\{0\.05,0\.1\}\\eta\\in\\\{0\.05,0\.1\\\}is common\. \(e\)n∈\{4,8,12,16,24,32,48\}n\\in\\\{4,8,12,16,24,32,48\\\}\.
### C\.3Evaluation

##### Exact evaluation

For the benchmark and the mechanism experiments, the expected cost and the expected numbers of searches, submissions, and answers of every policy follow from a recursion over the states it reaches, with self\-loops eliminated as in \([A\.4](https://arxiv.org/html/2610.41129#A1.E4)\)\. The optimal cost follows from Proposition[A\.2](https://arxiv.org/html/2610.41129#A1.Thmproposition2)\. Savings are averages of portfolio\-level percentage differences\. On a Macbook Pro with an Apple M5 processor, the exact solution of a four\-task portfolio withα=0\.8\\alpha=0\.8takes 5\.7 s on average\.

##### Certificates

For Theorem[3](https://arxiv.org/html/2610.41129#Thmtheorem3)\(ii\), we computeρ⁡\(s\)\\rho\(s\)by \([15](https://arxiv.org/html/2610.41129#S5.E15)\) at every state of the exact dynamic program, which is the set of states reachable from the initial state under any plan of𝒟\+\\mathcal\{D\}\_\{\+\}and is therefore forward closed\. We reportϵ\+=maxs⁡ρ​\(s\)\+/ω~​\(s\)\\epsilon\_\{\+\}=\\max\_\{s\}\\rho\(s\)^\{\+\}/\\widetilde\{\\omega\}\(s\)andϵ−=maxs⁡ρ​\(s\)−/ω~​\(s\)\\epsilon\_\{\-\}=\\max\_\{s\}\\rho\(s\)^\{\-\}/\\widetilde\{\\omega\}\(s\), whereω~\(s\)=∑i:zi≠Rwi≤ω\(s\)\\widetilde\{\\omega\}\(s\)=\\sum\_\{i:z\_\{i\}\\neq R\}w\_\{i\}\\leq\\omega\(s\)is the weight of the unresolved tasks and the maxima run over the states withω~​\(s\)\>0\\widetilde\{\\omega\}\(s\)\>0\. Becauseω~≤ω\\widetilde\{\\omega\}\\leq\\omega, these constants satisfy \([17](https://arxiv.org/html/2610.41129#S5.E17)\) and can only overstate the smallest constants that do\. At a state withω~​\(s\)=0\\widetilde\{\\omega\}\(s\)=0, every requirement is resolved, the remaining cost is the deterministic work of the resolved tasks, andρ⁡\(s\)=0\\rho\(s\)=0, so \([17](https://arxiv.org/html/2610.41129#S5.E17)\) holds there for any constants\.

##### Simulation

For larger portfolios, each instance is simulated on 200 sample paths\. A path fixes, in advance, the recoverability of every task, the availability of the human in every period, and a uniform random number for every search attempt, and every policy is run on the same paths\. The table\-based implementation of PCP reproduces the exact expected cost of the reference implementation on 40 benchmark portfolios, and its simulated costs agree with the exact values within sampling error\.

### C\.4LLM case study

##### Tasks

Each task asks the agent to choose a supplier for one purchase order\. A task has a purchase identifier, a quantity drawn from\{40,60,80,100\}\\\{40,60,80,100\\\}, and four suppliers\. Each supplier has a unit price drawn uniformly from\{15,…,60\}\\\{15,\\ldots,60\\\}, a fixed shipping charge drawn from\{0,…,90\}\\\{0,\\ldots,90\\\}, and a lead time, and the four lead times are a random permutation of\{4,8,12,16\}\\\{4,8,12,16\\\}days\. The hidden requirement is a maximum lead time drawn from\{6,10,14\}\\\{6,10,14\\\}days, independently of the supplier data\. The correct choice is the supplier with the lowest landed cost, the quantity times the unit price plus the shipping charge, among the suppliers whose lead time does not exceed the requirement\.

##### Independent work

The first unit of work presents eight quotes in random order: the current approved quote of each supplier, two superseded quotes with higher prices and shorter lead times, one draft with a lower price, and one approved quote for another purchase with a higher shipping charge\. The agent must return the current approved quote of each supplier\. The second unit asks the agent to compute each supplier’s landed cost from the quotes it extracted\. Neither unit uses the requirement\.

##### Search packets

A search presents six documents in random order, and Table[C\.2](https://arxiv.org/html/2610.41129#A3.T2)shows an example from the run\. Five documents are decoys: an approved requirement for another purchase, a superseded revision of this purchase’s requirement, a draft proposal, a supplier recommendation, and an operations note without a number\. The sixth document is a planning estimate for another purchase when the search fails and the binding requirement when it succeeds\. The binding document is approved, issued by the buyer, and matches the purchase and its current revision\. It also mentions a second figure that is not binding, such as an abandoned proposal or an internal planning estimate, so the agent must identify the binding number\. Document identifiers and the length of the packet carry no information about success\.

Table C\.2:A search packet from the run in which the search succeeds\. The binding document is the last one\.
##### Search outcomes and availability

For each task and portfolio, recoverability is drawn once with probabilitypp\. If the task is recoverable, each search attempt succeeds independently with probabilityα\\alpha\. Outcomes are indexed by attempt, so thekkth search of a task has the same outcome under every policy\. The availability of the human is drawn once for each period and is the same for all policies\. The scripted human answers at most one question in each available period and returns the true requirement\.

##### Prompt

Every agent step uses the prompt below, followed by a JSON object that lists the records to process\. A record contains the action, which issearch,extract,calculate, orfinal, and the public data that the step needs\. The final step receives the requirement learned from search or from the human, together with the agent’s own earlier lead times and costs\.

```
Execute the independent synthetic procurement records supplied below.
Use ONLY the content of each record; do not use tools, files, internet or outside
knowledge. Records are independent: never transfer a fact from one id/purchase to
another. Return JSON {"records":[...]}, exactly one response for each supplied id,
and no prose outside JSON. Every response must include its original id.

For action=search: inspect the document packet using its authority_rule. Only a
buyer-issued APPROVED document for the exact purchase_id and current
requirement_revision establishes the limit. Return found (boolean),
maximum_lead_days (integer or null), evidence_document_id (string or null), and
evidence_text (an exact supporting passage from that document, or null). A draft,
old revision, different purchase, supplier recommendation or vague deadline is
not sufficient. If there is no qualifying explicit numeric calendar-day limit,
return found=false and null for the other three fields. Documents can mention
both an abandoned proposal and the binding limit: apply the binding statement.

For action=extract: use quote_rule and current_quote_revisions to choose one
current approved offer for each supplier. Return suppliers (objects containing
only supplier, unit_price, fixed_shipping, lead_days, sorted by supplier ID) and
lead_days (map from supplier ID to its selected numeric lead time). Do not copy
draft, obsolete or other-purchase offers.

For action=calculate: use the supplied previously extracted suppliers and
quantity. Return costs, a map from supplier ID to quantity*unit_price+fixed_shipping.
Do not substitute numbers from another record or invent missing inputs.

For action=final: use the supplied observed maximum_lead_days and previous
lead_days/costs artifacts. Choose any supplier of minimum supplied landed cost
among those whose supplied lead time is at most maximum_lead_days. Return
supplier, landed_cost, lead_days. If required evidence is missing, return null
for all three. Do not infer a missing requirement from the available suppliers.
```

##### Execution

Calls usegpt\-6\.1\-solwith low reasoning effort throughcodex exec, with an ephemeral session and a read\-only sandbox\. Responses that use tools are rejected\. Each call starts a fresh context and processes up to 24 records from portfolios run by the same policy, so copies of a portfolio under different policies never share a call\. Up to 4 calls run at the same time, each with a timeout of 120 seconds and no retries\. A malformed or failed response would count as a failed step, and none occurred\. The policies use the nominal parameters and the service\-preferring tie rule, and PCP and the singleton policy minimize \([14](https://arxiv.org/html/2610.41129#S5.E14)\) exactly\. The cost of a portfolio is the total cost defined in Section[3](https://arxiv.org/html/2610.41129#S3), and the final choice of supplier does not add to it\. The documents, the prompt, and all random draws were fixed before the first call\. All portfolios finished within 27 periods, below the limit of 60\.

##### Usage

The four policies required 175 calls with 2,287 records, about 4\.1 million input tokens, of which 2\.6 million were cached, and 0\.15 million output tokens\. A call took 23\.7 s on average\.

##### Execution diagnostics

Section[6\.2](https://arxiv.org/html/2610.41129#S6.SS2)reports that every agent step was correct\. The agents made 133, 74, 0, and 160 searches under PCP, the singleton policy, Always Ask, and Search Once Then Ask, respectively\.

##### Evaluation under the model

Because the agents made no errors, the run follows the model exactly, and we evaluate each policy and each decision with the exact dynamic program\. Table[C\.3](https://arxiv.org/html/2610.41129#A3.T3)reports the expected cost of each policy and the optimal cost\. For each decisionddtaken at a statessin the run, we also compute its expected excess costgd​\(s\)\+∑s′Pd​\(s,s′\)​V∗​\(s′\)−V∗​\(s\)g\_\{d\}\(s\)\+\\sum\_\{s^\{\\prime\}\}P\_\{d\}\(s,s^\{\\prime\}\)V^\{\*\}\(s^\{\\prime\}\)\-V^\{\*\}\(s\), the increase in expected cost caused by takingddatssand acting optimally afterward\. Table[C\.4](https://arxiv.org/html/2610.41129#A3.T4)reports its average over the decisions of each policy\. The savings in Section[6\.2](https://arxiv.org/html/2610.41129#S6.SS2)average percentages over portfolios\. For comparison with them, we estimate the model’s expected saving per portfolio from 5,000 simulated portfolios per setting with common random numbers\. Relative to the singleton policy, it is 0\.0%, 0\.0%, 0\.6%, and 9\.4% in the four settings, in the order of Table[C\.3](https://arxiv.org/html/2610.41129#A3.T3), with standard errors of at most 0\.3%\.

Table C\.3:Expected cost under the model in the LLM case study, and PCP’s saving \(%\) relative to the singleton policy computed from these expected costs\.Table C\.4:Average expected excess cost per decision in the LLM case study\.

### C\.5Computing environment

The dynamic programs, the policies, and the simulations are implemented in Python\. The timings reported in Section[6](https://arxiv.org/html/2610.41129#S6)and Appendix[C\.3](https://arxiv.org/html/2610.41129#A3.SS3)are from a Macbook Pro with an Apple M5 processor\. The LLM case study uses the same implementation of the policies and calls the Codex command\-line interface from that computer\. Every number in Section[6](https://arxiv.org/html/2610.41129#S6)and in this appendix is computed from the stored results by a script, without manual transcription\.

### C\.6The mechanisms beyond the settings of the theorems

Theorem[2](https://arxiv.org/html/2610.41129#Thmtheorem2)and Proposition[1](https://arxiv.org/html/2610.41129#Thmproposition1)identify two mechanisms that can increase demand for human attention: useful independent work and the option to withdraw a question after asking\. In both, the mechanism can shift the optimal initial action from searching to asking\. The two results assume a single search attempt \(α=1\\alpha=1\) and at most one unit of work\. This subsection shows that both mechanisms also arise with repeated search, several units of work, and four tasks that share one human, and it measures how often the priority reversal of Proposition[2](https://arxiv.org/html/2610.41129#Thmproposition2)occurs\. All comparisons are between optimal policies, evaluated exactly as in Appendix[C\.3](https://arxiv.org/html/2610.41129#A3.SS3), and Table[C\.1](https://arxiv.org/html/2610.41129#A3.T1)lists the instances\. The single\-task experiments use the cost parameters of Figure[3](https://arxiv.org/html/2610.41129#S4.F3)\.

Figure C\.1:The mechanisms of Section[4](https://arxiv.org/html/2610.41129#S4)beyond the settings of the theorems\. Single tasks havew=κ=η=1w=\\kappa=\\eta=1,c=0\.1c=0\.1, and 81 combinations ofaaandpp\. \(a\) Share of settings in which one more unit of work raises the optimal expected number of human answers\. The curve forα=0\.5\\alpha=0\.5coincides with that forα=0\.65\\alpha=0\.65\. \(b\) Share of settings in which withdrawal lowers the optimal cost and raises the expected number of answers\. The dashed curves show the 90 portfolios of four tasks that share one human, withα=1\\alpha=1\.##### Independent work

Panel \(a\) of Figure[C\.1](https://arxiv.org/html/2610.41129#A3.F1)shows that useful work makes the optimal policy ask more\. When search can be repeated \(α<1\\alpha<1\), adding one unit of work raises the optimal expected number of human answers in at least 88% of settings at every work level, and in every setting whenα≤0\.65\\alpha\\leq 0\.65\. With work, an agent gives up searching sooner, because each failed search delays an answer that could overlap its work\. With a single search attempt, extra work changes the number of answers only when it changes whether the agent searches before asking, which happens in 26% to 56% of settings\. The effect persists when four tasks share the human: when the work of every task rises from zero to one, one to two, and two to three units, the optimal number of answers rises in 59%, 91%, and 84% of portfolios, respectively\.

##### Withdrawal

Panel \(b\) shows that withdrawal often raises human demand while lowering cost\. When search can be repeated, withdrawal lowers the optimal cost in every setting, by 1\.9% to 6\.6% on average depending onα\\alphaandbb, and in 19% to 40% of settings it does so while raising the expected number of answers\. In four\-task portfolios, withdrawal lowers the optimal cost by 2\.6% to 4\.8% on average and raises answers while lowering cost in 19% to 34% of portfolios\.

##### Priority reversals

The reversal behind Proposition[2](https://arxiv.org/html/2610.41129#Thmproposition2)is rare\. We draw 4,000 random portfolios of three tasks of the type in Example[1](https://arxiv.org/html/2610.41129#Thmexample1)\(Table[C\.1](https://arxiv.org/html/2610.41129#A3.T1)\) and compare the optimal costs of serving each task first\. We keep the 3,942 portfolios in which one of the first two tasks should be strictly preferred for the first answer, both with and without the third task\. Among them, adding the third task reverses which of the other two should be answered first in 80 \(2\.0%\)\. In 32 of these \(0\.8% of all 3,942\), the optimal policy serves the reversed choice first, so the reversal changes the optimal decision\. In more than 99% of these portfolios, therefore, the third task does not change which of the other two the optimal policy answers first\.

### C\.7Additional results

Table[C\.5](https://arxiv.org/html/2610.41129#A3.T5)reports the benchmark results of Section[6\.1\.1](https://arxiv.org/html/2610.41129#S6.SS1.SSS1)by factor, and Table[C\.6](https://arxiv.org/html/2610.41129#A3.T6)reports every scenario of the experiment with misestimated inputs in Section[6\.1\.4](https://arxiv.org/html/2610.41129#S6.SS1.SSS4)\.

Table C\.5:Benchmark results by factor: PCP’s mean saving relative to the singleton policy \(%\), mean gaps to the optimal cost \(%\), and the mean difference between PCP and the singleton policy in the expected numbers of answers and searches\.Table C\.6:Policies built with misestimated inputs and evaluated under the true parameters: gap to the true optimal cost \(%\), 144 portfolios\.