| paper | Delegated Online Search |
| authors | Pirmin Braun, Niklas Hahn, Martin Hoefer, Conrad Schecker |
| venue | IJCAI 2023 |
| filed under | unclassified |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given \(n\) rounds, a finite type catalogue \(T\), rational cohort masses \(\mu_i(t)\) with \(\sum_{t\in T}\mu_i(t)=1\), rational utilities \(a_t,b_t>0\), and \(1\le a_t\le\alpha\), compute a deterministic type-level acceptance scheme \(E=(E_1,\ldots,E_n)\) maximizing \(\operatorname{Del}_{\mu}(E)\), or satisfying \(\operatorname{Del}_{\mu}(E)\ge c\frac{\log\log\alpha}{\log\alpha}\operatorname{OS}(\mu)\), when one candidate type is sampled from cohort \(i\) per round and the agent follows the induced optimal stopping response.
A dynamic high-multiplicity cohort society where \(\mu_i(t)\) is the mass of indistinguishable candidate type \(t\) in round \(i\), \(E_i\) is a type-level acceptance set, the sampled candidate remains indivisible, and the objective is expected principal utility under the agent's backward-induction response.
The per-round masses \(\mu_i\) are mathematically identical to the paper's probabilities \(p_{ij}\), so cloning candidates does not affect behavior or create population-level feasibility constraints; this leaves a genuine concern that the construction is a probability reinterpretation rather than a new population regime.
fatal: False
Covers the conscious-proposal approximation guarantees in Theorems 2 and 5; it leaves Theorem 1, Corollary 1, and the oblivious-proposal results Theorems 3 and 4 outside the claim.
The strongest positive case is a high-multiplicity candidate-market mirror of the paper’s delegated online search. The lead anchor is Theorem 2; Theorem 5 is a useful supporting anchor. Both should be classified as likely Class A mirrors in an explicit finite-type representation.
The many agents are potential applicants or investment opportunities, not additional principals or search agents. Imagine a large recurring hiring market. In each public round \(i\), one candidate is sampled from a large exchangeable cohort. A candidate type \(t\) records everything relevant to the problem: the head-hunter’s utility \(a_t\), the principal’s utility \(b_t\), and any observable qualification data. The cohort has rational type masses \(\mu_i(t)\), with \(\sum_t\mu_i(t)=1\). Thus \(\mu_i(t)\) is the fraction of that round’s candidate pool having type \(t\).
This is genuinely a high-multiplicity regime when a large pool contains \(N\mu_i(t)\) indistinguishable candidates of type \(t\), while the number of types is small. Clearing denominators recovers the finite clone population. No candidate may be selected fractionally: all clones of a type receive the same treatment, and the selected candidate remains an indivisible option. The sampling of one candidate per round preserves the paper’s online stopping problem.
The principal commits to a deterministic type-level acceptance scheme \(E=(E_1,\ldots,E_n)\), where \(E_i\subseteq T_i\). When type \(t\) appears in round \(i\), the agent either proposes it or discards it. If proposed, the principal accepts precisely when \(t\in E_i\). The agent’s current expected utility from proposing is \(a_t\) when \(t\in E_i\), and \(0\) otherwise; he compares this with his continuation value from later rounds and follows the paper’s tie-breaking rule. The principal’s objective is the expected \(b_t\) of the accepted candidate.
Formally, let \(V^A_{n+1}=0\), and let \(V^A_i\) be the agent’s continuation value before round \(i\), computed by backward induction from the type masses and the committed scheme. Let \(\operatorname{Del}_\mu(E)\) be the principal’s resulting expected utility. Let \(\operatorname{OS}(\mu)\) be the principal’s expected utility when she searches directly and can accept or discard each observed candidate herself. The continuous optimization problem is to find \(E\) maximizing \(\operatorname{Del}_\mu(E)\), or an \(E\) satisfying a specified approximation guarantee relative to \(\operatorname{OS}(\mu)\).
The mirror is author-recognizable: the principal, agent, commitment power, online arrival process, proposal rule, stopping incentives, and two utility functions are unchanged. Only named candidates are replaced by masses of exchangeable candidates. This is not a continuum of time, a fractional candidate, or a mean-field opinion model.
My lead anchor is Theorem 2, proved in this paper in Section 3.1: “If the agent has \(\alpha\)-bounded utilities, there is a deterministic action scheme such that P obtains an \(\Omega(\log\log\alpha/\log\alpha)\)-approximation of the expected utility for optimal (online) search.”
The corresponding problem is \(\mathrm{CDOS}^{\alpha}_\infty\). An instance consists of the rounds, an explicit finite type catalogue, rational masses \(\mu_i(t)\), positive rational utilities \(a_t,b_t\), and a bound \(\alpha\) such that, after scaling, \(1\le a_t\le\alpha\). A solution is a deterministic type-level acceptance scheme \(E\). Its value is \(\operatorname{Del}_\mu(E)\), and the benchmark is \(\operatorname{OS}(\mu)\). The approximation version asks for a scheme with \(\operatorname{Del}_\mu(E)\ge c\frac{\log\log\alpha}{\log\alpha}\operatorname{OS}(\mu)\) for a universal constant \(c>0\).
I expect this mirror to be Class A. The paper’s RestrictOptions procedure becomes sorting finitely many types by \(b_t\) and adding their masses; the agent-utility classes and bins are formed using \(a_t\) and the same mass sums. Backward induction evaluates the resulting scheme. Nothing in this translation requires distinguishing individual clones, so the high-multiplicity representation is computationally meaningful rather than merely cosmetic.
The supporting anchor is Theorem 5, also proved here: “If principal and agent have \(\beta\)-bounded utilities, there is a deterministic action scheme such that P obtains an \(\Omega(1/\log\beta)\)-approximation of the expected utility for optimal (online) search.”
The corresponding problem is \(\mathrm{CDOS}^{\beta}_\infty\). It has the same population, rounds, masses, utilities, action schemes, and benchmark, but requires the pairwise alignment condition from the paper: for all types \(t,t'\), \( \frac{1}{\beta}\frac{a_t}{a_{t'}}\le \frac{b_t}{b_{t'}}\le \beta\frac{a_t}{a_{t'}} \). The solution is again a deterministic type-level acceptance scheme, with objective \(\operatorname{Del}_\mu(E)\). The target guarantee is \( \operatorname{Del}_\mu(E)\ge c\frac{1}{\log\beta}\operatorname{OS}(\mu) \).
This is also likely Class A. The paper’s clusters \(C_k\), defined by ranges of \(b_t/a_t\), are simply sets of population types. The principal evaluates the induced agent response for each cluster and chooses the best one. With an explicit finite type list, the number of clusters, mass sums, and dynamic-programming values are all computable in time polynomial in the number of rounds, types, and input bit length.
The two anchors cover only the paper’s conscious-proposal approximation results, namely Theorems 2 and 5. I would not claim that the same argument automatically covers Theorem 1’s \(O(1/n)\) impossibility result, because that lower bound is driven mainly by the number of sequential rounds and extreme utility scales rather than by population multiplicity. I would also leave Theorems 3 and 4 outside the main claim: their oblivious-proposal information restriction needs a separate model in which \(a_t\) is part of the true type but hidden from the principal.
Further questions arise naturally: whether the exact optimum \(\max_E\operatorname{Del}_\mu(E)\) is polynomial-time computable; whether the problem is fixed-parameter tractable in the number of types; whether the oblivious and semi-oblivious variants admit robust type-mass formulations; and what happens when the type distribution is given by a density or oracle rather than an explicit finite catalogue.
The weakest point is that the paper already writes each \(D_i\) as a probability distribution. A sceptic can therefore say that this is only a reinterpretation of uncertainty as population composition. I think that objection limits the claim but does not defeat it. The paper’s mathematics uses no identity-specific feature of an option: only its type, mass, utilities, arrival round, and the agent’s continuation incentives matter. A large market of exchangeable applicants sampled through a one-contact-per-round hiring protocol is a credible high-multiplicity scenario, and the mirror preserves the paper’s strategic stopping problem exactly. The honest verdict is therefore a qualified positive: a strong Class A population mirror for Theorems 2 and 5, but not a claim that every online-search interpretation has a useful continuum limit.
The strongest negative case is that the proposed mirror confuses a population mass with a probability law over a single option. That defeats both anchors.
In the paper, \(D_i\) is an exogenous distribution from which one option is realized in round \(i\). After that draw, there is no population whose mass is manipulated, constrained, or aggregated. Constructing \(N\mu_i(t)\) identical candidates and sampling one of them merely implements the same distribution: the induced delegation game is unchanged. For fixed \(n\), letting \(N\) tend to infinity changes nothing. Sampling without replacement only converges to the same independent-draw model. Thus the alleged high multiplicity is a latent physical interpretation of \(p_{ij}\), not a high-multiplicity relaxation of the computational problem.
This is also not a single society \(\mu\) in the programme’s sense. The proposed object is a family \((\mu_1,\ldots,\mu_n)\), one distribution per round. The algorithm never acts on those masses; it acts on one realized candidate. The quantities \(\operatorname{Del}_\mu(E)\) and \(\operatorname{OS}(\mu)\) use the masses only as probabilities. There is no mass transfer, aggregate winning condition, or population-level feasibility constraint.
For Theorem 2, \(\mathrm{CDOS}^{\alpha}_\infty\) is therefore mathematically the same finite-support problem already studied in the paper. Rename \(\mu_i(t)\) as \(p_{ij}\), and the type utilities as \(a_{ij},b_{ij}\). RestrictOptions, the utility classes, the bins, and backward induction are exactly the paper’s existing algorithm. The proposed continuous formulation contributes no new computational object and no use of continuous optimization; it merely changes the interpretation of probabilities into “fractions of a cohort.”
Theorem 5 has precisely the same defect. The clusters defined by \(b_t/a_t\), their weighted masses, and the induced agent response are already defined over the support of the distributions. Recasting support points as candidate types does not make the alignment result a population-computational result. Adding richer qualifications or attributes either leaves them irrelevant to the theorem or creates a different delegation model with new information and state variables.
A better market construction does not repair this while preserving the anchors. If only one candidate is sampled per round, it remains the same stochastic problem. If a positive mass of candidates is presented, or the principal can inspect a large pool, then the availability process, continuation values, and benchmark change; one is no longer mirroring Theorems 2 or 5. In the large-pool limit, either the sampling model remains unchanged or the online stopping problem becomes a different population-availability problem requiring new theorems.
The negative case is not airtight in an absolute modelling sense. A large exchangeable hiring market is a plausible application, and if ChoCo treats an exogenous distribution of potential candidates as a continuous population, the proponent has a legitimate interpretation. But under the programme’s stricter distinction between a society and a probability distribution over individually realized options, both anchors collapse to relabellings of results the paper already proves. On that reading, neither supplies a worthwhile continuous mirror.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.