Delegated online search

Braun P, Hahn N, Hoefer M, Schecker C. 2024. Delegated online search. Artificial Intelligence. 334, 104171.

OA 2024_ArtIntel_Braun.pdf 763.69 KB [Published Version]

Journal Article | Published | English

Scopus indexed
Braun, Pirmin; Hahn, NiklasISTA; Hoefer, Martin; Schecker, Conrad
In a delegation problem, a principal P with commitment power tries to pick one out of 𝑛 options. Each option is drawn independently from a known distribution. Instead of inspecting the options herself, P delegates the information acquisition to a rational and self-interested agent A. After inspection, A proposes one of the options, and P can accept or reject. Delegation is a classic setting in economic information design with many prominent applications, but the computational problems are only poorly understood. In this paper, we study a natural online variant of delegation, in which the agent searches through the options in an online fashion. For each option, he has to irrevocably decide if he wants to propose the current option or discard it, before seeing information on the next option(s). How can we design algorithms for P that approximate the utility of her best option in hindsight? We show that in general P can obtain a Θ(1βˆ•π‘›)-approximation and extend this result to ratios of Θ(π‘˜βˆ•π‘›) in case (1) A has a lookahead of π‘˜ rounds, or (2) A can propose up to π‘˜ different options. We provide fine-grained bounds independent of 𝑛 based on three parameters. If the ratio of maximum and minimum utility for A is bounded by a factor 𝛼, we obtain an Ξ©(loglog π›Όβˆ• log 𝛼)- approximation algorithm, and we show that this is best possible. Additionally, if P cannot distinguish options with the same value for herself, we show that ratios polynomial in 1βˆ•π›Ό cannot be avoided. If there are at most 𝛽 different utility values for A, we show a Θ(1βˆ•π›½)-approximation. If the utilities of P and A for each option are related by a factor 𝛾, we obtain an Ξ©(1βˆ• log 𝛾)- approximation, where 𝑂(log log π›Ύβˆ• log 𝛾) is best possible.
Publishing Year
Date Published
Journal Title
Artificial Intelligence
Article Number

Cite this

Braun P, Hahn N, Hoefer M, Schecker C. Delegated online search. Artificial Intelligence. 2024;334. doi:10.1016/j.artint.2024.104171
Braun, P., Hahn, N., Hoefer, M., & Schecker, C. (2024). Delegated online search. Artificial Intelligence. Elsevier.
Braun, Pirmin, Niklas Hahn, Martin Hoefer, and Conrad Schecker. β€œDelegated Online Search.” Artificial Intelligence. Elsevier, 2024.
P. Braun, N. Hahn, M. Hoefer, and C. Schecker, β€œDelegated online search,” Artificial Intelligence, vol. 334. Elsevier, 2024.
Braun P, Hahn N, Hoefer M, Schecker C. 2024. Delegated online search. Artificial Intelligence. 334, 104171.
Braun, Pirmin, et al. β€œDelegated Online Search.” Artificial Intelligence, vol. 334, 104171, Elsevier, 2024, doi:10.1016/j.artint.2024.104171.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
File Name
Access Level
OA Open Access
Date Uploaded
MD5 Checksum


Marked Publications

Open Data ISTA Research Explorer


arXiv 2203.01084

Search this title in

Google Scholar