@article{17188,
  abstract     = {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.},
  author       = {Braun, Pirmin and Hahn, Niklas and Hoefer, Martin and Schecker, Conrad},
  issn         = {0004-3702},
  journal      = {Artificial Intelligence},
  publisher    = {Elsevier},
  title        = {{Delegated online search}},
  doi          = {10.1016/j.artint.2024.104171},
  volume       = {334},
  year         = {2024},
}

@article{9293,
  abstract     = {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.},
  author       = {Chatterjee, Krishnendu and Dvořák, Wolfgang and Henzinger, Monika H and Svozil, Alexander},
  issn         = {0004-3702},
  journal      = {Artificial Intelligence},
  number       = {8},
  publisher    = {Elsevier},
  title        = {{Algorithms and conditional lower bounds for planning problems}},
  doi          = {10.1016/j.artint.2021.103499},
  volume       = {297},
  year         = {2021},
}