  In a delegation problem, a principal P with commitment power tries to pick
one out of $n$ 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 $\Theta(1/n)$-approximation and extend
this result to ratios of $\Theta(k/n)$ in case (1) A has a lookahead of $k$
rounds, or (2) A can propose up to $k$ different options. We provide
fine-grained bounds independent of $n$ based on two parameters. If the ratio of
maximum and minimum utility for A is bounded by a factor $\alpha$, we obtain an
$\Omega(\log \log \alpha / \log \alpha)$-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/\alpha$ cannot
be avoided. If the utilities of P and A for each option are related by a factor
$\beta$, we obtain an $\Omega(1/ \log \beta)$-approximation, where $O(\log \log
\beta/ \log \beta)$ is best possible.
