Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Delegated Pandora's box   In delegation problems, a principal does not have the resources necessary to
complete a particular task, so they delegate the task to an untrusted agent
whose interests may differ from their own. Given any family of such problems
and space of mechanisms for the principal to choose from, the delegation gap is
the worst-case ratio of the principal's optimal utility when they delegate
versus their optimal utility when solving the problem on their own. In this
work, we consider the delegation gap of the generalized Pandora's box problem,
a search problem in which searching for solutions incurs known costs and
solutions are restricted by some downward-closed constraint. First, we show
that there is a special case when all random variables have binary support for
which there exist constant-factor delegation gaps for matroid constraints.
However, there is no constant-factor delegation gap for even simple non-binary
instances of the problem. Getting around this impossibility, we consider two
variants: the free-agent model, in which the agent doesn't pay the cost of
probing elements, and discounted-cost approximations, in which we discount all
costs and aim for a bicriteria approximation of the discount factor and
delegation gap. We show that there are constant-factor delegation gaps in the
free-agent model with discounted-cost approximations for certain downward
closed constraints and constant discount factors. However, constant delegation
gaps can not be achieved under either variant alone. Finally, we consider
another variant called the shared-cost model, in which the principal can choose
how costs will be shared between them and the agent before delegating the
search problem. We show that the shared-cost model exhibits a constant-factor
delegation gap for certain downward closed constraints.

17
The categories of this paper are: q-fin
20
The categories of this paper are: acc-phys
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
10
The categories of this paper are: q-bio
21
The categories of this paper are: adap-org
37
The categories of this paper are: supr-con
36
The categories of this paper are: cmp-lg
3
The categories of this paper are: physics
15
The categories of this paper are: nucl-ex
0
The categories of this paper are: hep-ph
34
The categories of this paper are: chem-ph
6
The categories of this paper are: astro-ph
7
The categories of this paper are: hep-th
31
The categories of this paper are: ao-sci
11
The categories of this paper are: hep-lat