---
res:
bibo_abstract:
- "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.@eng"
bibo_authorlist:
- foaf_Person:
foaf_givenName: Pirmin
foaf_name: Braun, Pirmin
foaf_surname: Braun
- foaf_Person:
foaf_givenName: Niklas
foaf_name: Hahn, Niklas
foaf_surname: Hahn
foaf_workInfoHomepage: http://www.librecat.org/personId=0a01c7b2-b823-11ed-9928-cc3f874f9ffd
- foaf_Person:
foaf_givenName: Martin
foaf_name: Hoefer, Martin
foaf_surname: Hoefer
- foaf_Person:
foaf_givenName: Conrad
foaf_name: Schecker, Conrad
foaf_surname: Schecker
bibo_doi: 10.1016/j.artint.2024.104171
bibo_volume: 334
dct_date: 2024^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0004-3702
dct_language: eng
dct_publisher: Elsevier@
dct_title: Delegated online search@
...