---
OA_place: publisher
OA_type: hybrid
_id: '17188'
abstract:
- lang: eng
  text: "In a delegation problem, a principal P with commitment power tries to pick
    one out of \U0001D45B options.\r\nEach option is drawn independently from a known
    distribution. Instead of inspecting the options\r\nherself, P delegates the information
    acquisition to a rational and self-interested agent A. After\r\ninspection, A
    proposes one of the options, and P can accept or reject.\r\nDelegation is a classic
    setting in economic information design with many prominent applications,\r\nbut
    the computational problems are only poorly understood. In this paper, we study
    a natural\r\nonline variant of delegation, in which the agent searches through
    the options in an online fashion.\r\nFor each option, he has to irrevocably decide
    if he wants to propose the current option or discard\r\nit, before seeing information
    on the next option(s). How can we design algorithms for P that\r\napproximate
    the utility of her best option in hindsight?\r\nWe show that in general P can
    obtain a Θ(1∕\U0001D45B)-approximation and extend this result to ratios\r\nof
    Θ(\U0001D458∕\U0001D45B) in case (1) A has a lookahead of \U0001D458 rounds, or
    (2) A can propose up to \U0001D458 different\r\noptions. We provide fine-grained
    bounds independent of \U0001D45B based on three parameters. If the ratio\r\nof
    maximum and minimum utility for A is bounded by a factor \U0001D6FC, we obtain
    an Ω(loglog \U0001D6FC∕ log \U0001D6FC)-\r\napproximation algorithm, and we show
    that this is best possible. Additionally, if P cannot\r\ndistinguish options with
    the same value for herself, we show that ratios polynomial in 1∕\U0001D6FC cannot\r\nbe
    avoided. If there are at most \U0001D6FD different utility values for A, we show
    a Θ(1∕\U0001D6FD)-approximation.\r\nIf the utilities of P and A for each option
    are related by a factor \U0001D6FE, we obtain an Ω(1∕ log \U0001D6FE)-\r\napproximation,
    where \U0001D442(log log \U0001D6FE∕ log \U0001D6FE) is best possible."
acknowledgement: Hahn gratefully acknowledges the support of GIF grant I-1419-118.4/2017.
  Hoefer gratefully acknowledges the support of GIF grant I-1419-118.4/2017, DFG Research
  Unit ADYN (project number 411362735), and DFG grant Ho 3831/9-1 (project number
  514505843).
article_number: '104171'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Pirmin
  full_name: Braun, Pirmin
  last_name: Braun
- first_name: Niklas
  full_name: Hahn, Niklas
  id: 0a01c7b2-b823-11ed-9928-cc3f874f9ffd
  last_name: Hahn
- first_name: Martin
  full_name: Hoefer, Martin
  last_name: Hoefer
- first_name: Conrad
  full_name: Schecker, Conrad
  last_name: Schecker
citation:
  ama: Braun P, Hahn N, Hoefer M, Schecker C. Delegated online search. <i>Artificial
    Intelligence</i>. 2024;334. doi:<a href="https://doi.org/10.1016/j.artint.2024.104171">10.1016/j.artint.2024.104171</a>
  apa: Braun, P., Hahn, N., Hoefer, M., &#38; Schecker, C. (2024). Delegated online
    search. <i>Artificial Intelligence</i>. Elsevier. <a href="https://doi.org/10.1016/j.artint.2024.104171">https://doi.org/10.1016/j.artint.2024.104171</a>
  chicago: Braun, Pirmin, Niklas Hahn, Martin Hoefer, and Conrad Schecker. “Delegated
    Online Search.” <i>Artificial Intelligence</i>. Elsevier, 2024. <a href="https://doi.org/10.1016/j.artint.2024.104171">https://doi.org/10.1016/j.artint.2024.104171</a>.
  ieee: P. Braun, N. Hahn, M. Hoefer, and C. Schecker, “Delegated online search,”
    <i>Artificial Intelligence</i>, vol. 334. Elsevier, 2024.
  ista: Braun P, Hahn N, Hoefer M, Schecker C. 2024. Delegated online search. Artificial
    Intelligence. 334, 104171.
  mla: Braun, Pirmin, et al. “Delegated Online Search.” <i>Artificial Intelligence</i>,
    vol. 334, 104171, Elsevier, 2024, doi:<a href="https://doi.org/10.1016/j.artint.2024.104171">10.1016/j.artint.2024.104171</a>.
  short: P. Braun, N. Hahn, M. Hoefer, C. Schecker, Artificial Intelligence 334 (2024).
corr_author: '1'
date_created: 2024-06-30T22:01:05Z
date_published: 2024-09-01T00:00:00Z
date_updated: 2025-09-08T08:00:42Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1016/j.artint.2024.104171
external_id:
  arxiv:
  - '2203.01084'
  isi:
  - '001260448100001'
file:
- access_level: open_access
  checksum: f02a56bc7ea88f41fcc68968e4ceddf3
  content_type: application/pdf
  creator: dernst
  date_created: 2025-01-09T10:45:24Z
  date_updated: 2025-01-09T10:45:24Z
  file_id: '18806'
  file_name: 2024_ArtificialIntelligence_Braun.pdf
  file_size: 772226
  relation: main_file
  success: 1
file_date_updated: 2025-01-09T10:45:24Z
has_accepted_license: '1'
intvolume: '       334'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
publication: Artificial Intelligence
publication_identifier:
  issn:
  - 0004-3702
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Delegated online search
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 334
year: '2024'
...