---
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
fulldoi: https://doi.org/10.1016/j.artint.2024.104171
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'
...
---
_id: '9293'
abstract:
- lang: eng
  text: 'We consider planning problems for graphs, Markov Decision Processes (MDPs),
    and games on graphs in an explicit state space. While graphs represent the most
    basic planning model, MDPs represent interaction with nature and games on graphs
    represent interaction with an adversarial environment. We consider two planning
    problems with k different target sets: (a) the coverage problem asks whether there
    is a plan for each individual target set; and (b) the sequential target reachability
    problem asks whether the targets can be reached in a given sequence. For the coverage
    problem, we present a linear-time algorithm for graphs, and quadratic conditional
    lower bound for MDPs and games on graphs. For the sequential target problem, we
    present a linear-time algorithm for graphs, a sub-quadratic algorithm for MDPs,
    and a quadratic conditional lower bound for games on graphs. Our results with
    conditional lower bounds, based on the boolean matrix multiplication (BMM) conjecture
    and strong exponential time hypothesis (SETH), establish (i) model-separation
    results showing that for the coverage problem MDPs and games on graphs are harder
    than graphs, and for the sequential reachability problem games on graphs are harder
    than MDPs and graphs; and (ii) problem-separation results showing that for MDPs
    the coverage problem is harder than the sequential target problem.'
article_number: '103499'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Wolfgang
  full_name: Dvořák, Wolfgang
  last_name: Dvořák
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Alexander
  full_name: Svozil, Alexander
  last_name: Svozil
citation:
  ama: Chatterjee K, Dvořák W, Henzinger M, Svozil A. Algorithms and conditional lower
    bounds for planning problems. <i>Artificial Intelligence</i>. 2021;297(8). doi:<a
    href="https://doi.org/10.1016/j.artint.2021.103499">10.1016/j.artint.2021.103499</a>
  apa: Chatterjee, K., Dvořák, W., Henzinger, M., &#38; Svozil, A. (2021). Algorithms
    and conditional lower bounds for planning problems. <i>Artificial Intelligence</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.artint.2021.103499">https://doi.org/10.1016/j.artint.2021.103499</a>
  chicago: Chatterjee, Krishnendu, Wolfgang Dvořák, Monika Henzinger, and Alexander
    Svozil. “Algorithms and Conditional Lower Bounds for Planning Problems.” <i>Artificial
    Intelligence</i>. Elsevier, 2021. <a href="https://doi.org/10.1016/j.artint.2021.103499">https://doi.org/10.1016/j.artint.2021.103499</a>.
  ieee: K. Chatterjee, W. Dvořák, M. Henzinger, and A. Svozil, “Algorithms and conditional
    lower bounds for planning problems,” <i>Artificial Intelligence</i>, vol. 297,
    no. 8. Elsevier, 2021.
  ista: Chatterjee K, Dvořák W, Henzinger M, Svozil A. 2021. Algorithms and conditional
    lower bounds for planning problems. Artificial Intelligence. 297(8), 103499.
  mla: Chatterjee, Krishnendu, et al. “Algorithms and Conditional Lower Bounds for
    Planning Problems.” <i>Artificial Intelligence</i>, vol. 297, no. 8, 103499, Elsevier,
    2021, doi:<a href="https://doi.org/10.1016/j.artint.2021.103499">10.1016/j.artint.2021.103499</a>.
  short: K. Chatterjee, W. Dvořák, M. Henzinger, A. Svozil, Artificial Intelligence
    297 (2021).
corr_author: '1'
date_created: 2021-03-28T22:01:40Z
date_published: 2021-03-16T00:00:00Z
date_updated: 2026-07-07T13:36:04Z
day: '16'
department:
- _id: KrCh
doi: 10.1016/j.artint.2021.103499
external_id:
  arxiv:
  - '1804.07031'
  isi:
  - '000657537500003'
fulldoi: https://doi.org/10.1016/j.artint.2021.103499
intvolume: '       297'
isi: 1
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1804.07031
month: '03'
oa: 1
oa_version: Preprint
publication: Artificial Intelligence
publication_identifier:
  issn:
  - 0004-3702
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '35'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Algorithms and conditional lower bounds for planning problems
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 297
year: '2021'
...