11institutetext: University of Texas at Austin
11email<EMAIL_ADDRESS>
22institutetext: Drexel University
22email<EMAIL_ADDRESS>
33institutetext: Oberlin College
33email<EMAIL_ADDRESS>
# Simple Delegated Choice

Ali Khodabakhsh 11 Emmanouil Pountourakis 22 Samuel Taggart 33

###### Abstract

This paper studies delegation in a model of discrete choice. In the delegation
problem, an uninformed principal must consult an informed agent to make a
decision. Both the agent and principal have preferences over the decided-upon
action which vary based on the state of the world, and which may not be
aligned. The principal may commit to a mechanism, which maps reports of the
agent to actions. When this mechanism is deterministic, it can take the form
of a menu of actions, from which the agent simply chooses upon observing the
state. In this case, the principal is said to have delegated the choice of
action to the agent.

We consider a setting where the decision being delegated is a choice of a
utility-maximizing action from a set of several options. We assume the shared
portion of the agent’s and principal’s utilities is drawn from a distribution
known to the principal, and that utility misalignment takes the form of a
known bias for or against each action. We provide tight approximation analyses
for simple threshold policies under three increasingly general sets of
assumptions. With independently-distributed utilities, we prove a
$3$-approximation. When the agent has an outside option the principal cannot
rule out, the constant-approximation fails, but we prove a
$\log\rho/\log\log\rho$-approximation, where $\rho$ is the ratio of the
maximum value to the optimal utility. We also give a weaker but tight bound
that holds for correlated values, and complement our upper bounds with
hardness results. One special case of our model is utility-based assortment
optimization, for which our results are new. ††Emmanouil Pountourakis was
partially supported by NSF CCF 2218813. Samuel Taggart was partially supported
by NSF CCF 2218814.

##  1 Introduction

This paper considers a model of delegated stochastic probing. A decisionmaker
(the principal) must pick one of $n$ actions, each of which yields randomly
distributed reward. Rather than observe rewards directly, the decisionmaker
chooses a subset of the actions to allow an agent to consider. The agent
observes the realized rewards exactly, but may be biased towards certain
actions and away from others. The principal’s goal is to select a set of
actions that will maximize their expected reward from the agent’s biased
choice. This template captures a range of economic and managerial dilemmas. As
examples, a firm might seek to replace a piece of expensive equipment, or a
national health service must choose which treatment to provide to a patient
who might display a range of symptoms. The equipment operators know their
needs better than managers, and the health service relies on doctors to
observe patients. In such arrangements, the agent and principal tend not to
have preferences which are perfectly aligned: the firm must pay for new
equipment (while the operator does not), and specialist doctors might peddle
lucrative optional procedures.

The algorithmic problem above can be couched as mechanism design. In a
revelation mechanism, the agent would observe the actions’ rewards and report
these to the mechanism, which would choose a possibly randomized action. The
_taxation principle_ states that every deterministic mechanism is equivalent
to a menu: the principal selects the set of allowable actions, and the agent
simply chooses their preferred action upon observing the rewards. Such
mechanisms eliminate the need for communication between the agent and
principal, and are therefore so common in practice that they are often taken
for granted as a managerial tool. In economics, delegation refers exactly to
this problem of menu design for a better-informed agent, coined by Holmstrom
(1978).

In the examples above, the alignment of the agent and principals’ preferences
is well-structured. The principal’s main uncertainty in the choice problem is
payoff-relevant for both parties: in replacing equipment, both the operator
and firm want to purchase the right tool for the job. Meanwhile, misalignment
of preferences is predictable – the firm will pay for the new purchase, and
prices are likely known in advance. Under these conditions, a particularly
salient family of mechanisms is threshold mechanisms, which restrict the agent
to actions where the misalignment of preferences is not too great. For our
firm and operator, this would take the form of a budget.

#### Our Contributions.

This work gives a model for delegated choice scenarios like those discussed
above. In our model, the agent and principals’ preferences for a particular
action are captured by two quantities. First, each action $i$ has a shared
value $v_{i}$, which is unknown to the principal (but distributed according to
a known prior) but observable to the agent. Second, each action has a
commonly-known and fixed bias $b_{i}$, which captures the amount the agents’
utility differs from that of the principal. The agent may also have outside
options which the principal cannot prohibit; we extend our model to capture
this issue as well.

We study three increasingly general regimes, distinguished by the correlation
or independence of the value distributions and the absence or presence of an
outside option. For each, we give computational hardness, then take a simple-
versus-optimal perspective by completely characterizing the performance of
threshold mechanisms. In more detail:

  * •

With independently distributed values and no outside option, we show that
threshold mechanisms are a $3$-approximation to the optimal mechanism.111Our
results also hold with an outside option if that action has a fixed value,
which we make precise subsequently. We show that this problem is NP-hard.

  * •

With independently distributed values and an outside option, threshold
mechanisms cannot obtain any nontrivial approximation in general. However, we
show a parametrized $\log\rho/\log\log\rho$-approximation, where $\rho$ is the
ratio of largest possible value to OPT. This problem generalizes the previous
problem, and is thus also NP-hard.

  * •

With correlation, we give a $\log p_{\text{min}}^{-1}$ approximation, where
$p_{\text{min}}$ is the probability of the least likely value profile. We show
this problem is NP-hard to approximate below a constant factor.

We match all three approximation analyses of thresholds with tight examples. A
special case of our model is utility-based assortment optimization, a
canonical model from revenue management (discussed in Section 3). All our
results are new to that literature.

#### Roadmap

In Section 2, we give our formal model. We then survey existing work on
delegation in Section 3, and make specific comparisons to existing work on
delegated search and assortment optimization. Section 4 contains our hardness
result and constant-approximation under independence and lays the groundwork
for our parametrized analysis with an outside option in Section 5. Finally, we
analyze delegation with correlated values in Section 6.

##  2 Model

We now give our model of delegated choice. The principal seeks to choose from
a discrete set $\Omega$ of $n$ actions. The principal’s utility for action $i$
is given by a random value $v_{i}\geq 0$, which the principal is unable to
observe. To assist in selecting an action, the principal may consult an agent,
who observes all actions’ values, and may communicate with the principal after
observation. We decompose the agent’s utility for action $i$ into its value,
shared with the principal, and an unshared bias term. That is, the agent’s
utility is given by $u_{i}=v_{i}+b_{i}$. Throughout the paper, we assume each
bias $b_{i}$ is constant and known to the principal.

We assume the principal has the power to commit ex ante to a mechanism for
communicating with the agent and selecting an action, and study deterministic
mechanisms. By the taxation principle, it suffices to consider mechanisms
described by menus over actions. The agent observes all actions’ values and
selects their utility-maximizing action from the menu — which may differ from
the principal’s preferred action. Taking this perspective, we consider the
algorithmic problem of selecting a menu $A$ to maximize the principal’s
expected utility when the agent selects their preferred action according to
the observed values. We further assume the existence of an outside option for
the agent, denoted action $0$, with value $v_{0}$ and bias $b_{0}$. We assume
that regardless of the principal’s choice of $A$, the agent may always select
this action.

Formally, when presented with action set $A\subseteq\Omega$ and after
observing the vector of values ${\mathbf{v}}$, denote the agent’s preferred
choice by $g(A,{\mathbf{v}})$. That is, $g(A,{\mathbf{v}})=\text{argmax}_{a\in
A\cup\\{0\\}}(v_{i}+b_{i})$. The principal is faced with a set function
optimization problem. We assume the principal has a prior distribution $F$
over the values ${\mathbf{v}}$, and must select a menu $A$ for the agent which
maximizes their own expected utility.222We assume the agent breaks ties in the
principal’s favor, then lexicographically. That is, the principal solves:

$\underset{A\subseteq\Omega}{\text{maximize}}\,\,\,f(A)\coloneqq\int_{{\mathbf{v}}}v_{g(A,{\mathbf{v}})}\,dF({\mathbf{v}}).$

The model above captures applications such those described in Section 1. Note
that we allow the agent’s utility to be negative, and that the model is
invariant to additive shifts in the agent’s bias for every action. We will
study a particularly simple set of mechanisms, namely threshold mechanisms.
The threshold mechanism with bias $t$ is given by $A_{t}=\\{i\,|\,b_{i}\leq
t\\}$. Note that since the number of threshold policies is at most the number
of actions, the principal may compute an optimal threshold efficiently. We
analyze the approximation ratio between the best threshold menu and the
optimal menu overall.

###### Example 1

The equipment purchase example described in the introduction can be formulated
as follows. The firm (principal) needs to buy a piece of equipment, which will
be used by a specialist (agent) with knowledge of the quality of different
brands. Each brand $i$ has quality $q_{i}$, and price $p_{i}$. Qualities are
unknown to the principal, and prices are known. We may write values as
$v_{i}=q_{i}-p_{i}$ and biases $b_{i}=p_{i}$. Note that the values are random,
while biases are known, as required. A threshold policy restricts to actions
with bias —and hence price— at most $t$.

###### Example 2

The health services example from the introduction may be heavily stylized as
follows. A national health service (principal) needs to select a treatment for
a patient with the help of a doctor (agent) who has expertise and observes the
patient’s condition. Each potential treatment $i$ has cost $c_{i}$ (known to
the doctor and the health service), and given the patient’s condition an
efficacy $e_{i}$ (known to the doctor but not the health service). The health
service seeks to maximize the patient’s health less costs,
$u^{P}_{i}=e_{i}-c_{i}$. The doctor is paid a portion of the costs, and shares
some concern for the patient’s health. For some $\alpha,\beta>0$, we may
therefore write $u^{A}_{i}=\alpha e_{i}+\beta c_{i}$. To cast this in our
model, note that scaling agent utilities by $1/\alpha$ will not change their
decision, so we may normalize $\alpha=1$. After normalization, we have
$v_{i}=e_{i}-c_{i}$ and $b_{i}=(\beta+1)c_{i}$. As required, the value $v_{i}$
depends on $e_{i}$ and is hence unknown to the principal, and the bias $b_{i}$
depends only on $c_{i}$, and is hence known to the principal. Further note
that a threshold set corresponds to a price cap, restricting the doctor away
from the highest-cost procedures.

##  3 Related Work

#### Simple Versus Optimal Mechanisms.

A primary contribution of computer science to the study of mechanism design is
the use of approximation to explain the prevalence of simple mechanisms. For
example, Hartline and Roughgarden (2009) prove that the simple auctions often
observed in practice can obtain a constant factor of the sometimes-
complicated, rarely-used optimal mechanisms. Hartline (2013) surveys similar
results for auctions. Recently, Dütting et al. (2019) and Castiglioni et al.
(2021) make similar forays into contract theory, characterizing the power of
simple linear contracts. Our work initiates the study of delegated choice
through a similar lens.

#### Real-Valued Delegation.

Delegated decisionmaking is a canonical problem in microeconomic theory and
managerial science. Much of the literature subsequent to Holmstrom (1978) has
focused on the special case where the state and action space are continuous
and real-valued, and where the preferences of both the agent and principal are
single-peaked, but differ by a known bias. Notable examples include Melumad
and Shibano (1991), Martimort and Semenov (2006), Alonso and Matouschek
(2008), and Amador and Bagwell (2010), who characterize the structure of
optimal mechanisms under increasingly general variants of the single-peaked
model. The main conclusions from these papers are necessary and sufficient
conditions for the optimal delegation set to be an interval on the real line.
Our work makes a similar known bias assumption, but in a model more amenable
to algorithmic analysis. We obtain similar conclusions: the principal can
secure high utility by restricting the agent away from extreme actions.

Additional work on similar models includes Kovác and Mylovanov (2009), who
study the gap in performance between randomized and deterministic mechanisms,
and Ambrus and Egorov (2017), who study a principal who can add additional
nonmonetary costs to incentivize more preferred decisions. Aghion and Tirole
(1997) and Szalay (2005) consider models in which one or more of the principal
and the agent may expend effort to observe a signal about the state. For
multiple decisions, Frankel (2014) considers maxmin robust delegation and
Kleiner (2023) studies Bayesian optimal mechanisms. With the exception of
Armstrong and Vickers (2010) and followup works, though, the economics
literature has focused on the real-valued model for decisions. Our work
considers the mathematically incomparable but similarly common setting of
discrete choice. In the latter setting, the structure of the problem renders
exact characterization of optimal mechanisms difficult, and motivates the use
of a simple-versus-optimal approach.

#### Delegated Search.

The model of delegated project choice from Armstrong and Vickers (2010) is
perhaps closest to ours. The authors consider an agent who chooses between $n$
discrete actions. The principal is able to verify the utilities provided by
the selected action, and restrict the agent’s choice based on this
information. Subsequent followups by Kleinberg and Kleinberg (2018), Bechtel
and Dughmi (2021), and Bechtel et al. (2022) note a strong connection between
the Armstrong and Vickers (2010) model and well-studied online stochastic
optimization problems. They upperbound the delegation gap: they show that even
when the agent must pay a search cost to discover each action’s utility, the
principal can obtain utility within a constant factor of the first-best
solution, where they solve the search problem themselves. More recently, Braun
et al. (2022) give a version where the agent searches online, and make similar
comparisons to first-best, and Hajiaghayi et al. (2023) study a multi-agent
version of the model.

Our model differs from the delegated search literature in two notable ways.
First is the absence of search. Our agent can perfectly observe the values of
all actions. More significantly, our principal is unable to verify the
utilities provided by the agent’s selected action; they may only rule actions
in or out completely. In our model, the first-best solution is
$\mathbb{E}[\max_{i}v_{i}]$. The following example shows that no delegation
set may approximate the first-best to a factor better than $n$. This contrasts
with the constant-approximation results from the work cited above.

###### Example 3

Consider an instance with $n$ independently-distributed actions. Action $i$
has a value $v_{i}$ which is $1-\epsilon$ with probability $1/n$ and $0$
otherwise. Each action $i$ has bias $b_{i}=i$. The first-best expected utility
is constant, while in any delegation set, the agent will always pick the
highest-indexed action, yielding expected utility $(1-\epsilon)/n$.

#### Stochastic Probing.

There is a by now extensive literature on stochastic probing beyond the
economically-inspired settings of this paper and those discussed above. Rather
than survey the literature, we offer a few key recent papers, and refer the
reader to these for deeper references: Chen et al. (2016); Goel et al. (2006);
Mehta et al. (2020); Segev and Singla (2021) Despite similarity of motivation,
we employ techniques that largely differ from this literature.

#### Assortment Optimization.

Our model captures special cases of the well-studied assortment optimization
problem. In assortment optimization, a seller must decide which among a set of
fixed-price items to offer. A variety of models are common for the buyer’s
purchase choice, including nested logit models (Davis et al., 2014; Li et al.,
2015) and Markov chain-based choice (Feldman and Topaloglu, 2017), along with
equivalent models based on random buyer utility (Berbeglia, 2016; Aouad et
al., 2018, 2023), which includes the especially prevalent multinomial logit
(MNL) model as a special case. Our model subsumes assortment optimization with
utility-based choice. To see this, consider $n$ items, where the buyer utility
$w_{i}$ for each item $i$ is random, and the revenue $r_{i}$ for item $i$ is
known to the seller. Taking $v_{i}=r_{i}+\epsilon w_{i}$ and
$b_{i}=-(1+\epsilon)r_{i}$ for sufficiently small $\epsilon>0$ yields an
equivalent delegation problem. Under this transformation, an outside option
with $v_{0}=0$ corresponds to the no-buy option, and the option to buy
elsewhere with positive utility can be captured with a randomized outside
option.

Threshold mechanisms in our model correspond to revenue-ordered assortments, a
well-studied class of solutions for assortment optimization. A series of
papers analyze the approximation ratio of revenue-ordered assortments under
increasingly general models: Talluri and Van Ryzin (2004) show that revenue-
ordered assortments are optimal for several choice models including MNL;
Rusmevichientong et al. (2014) analyze revenue-ordered assortments for
mixtures of MNL models, and further prove NP-hardness of computing the optimal
assortment; Berbeglia and Joret (2020) give parametrized analyses under a
general choice model. Our approximation analyses for independently-distributed
values with an random outside option (Sections 5) apply to utility-based
assortment optimization, and are new to this literature. Our logarithmic
approximation for correlated values (Section 6) resembles that of Berbeglia
and Joret (2020); it is less finely parametrized, but extends to more general
forms of delegation.

Other work on computational hardness or approximation in assortment
optimization includes Désir et al. (2020), who hardness of approximation under
a knapsack-constrained version of the problem, and Immorlica et al. (2018),
who study a version where the buyer has combinatorial preferences over
bundles.

##  4 Threshold Delegation with Independent Values

We now consider the simplest case of the model, where the principal’s prior
$F$ over values is a product distribution, and hence, actions’ values are
independent. We further assume that the outside option’s value, $v_{0}$, is
deterministic, which subsumes the no-outside-option case, as we could have
$b_{0}=-\infty$. We present our approximation result first, and defer hardness
to Section 4.4

###### Theorem 4.1

Under independent values and a deterministic outside option, there always
exists a threshold mechanism with expected utility that is a $3$-approximation
to the optimal deterministic mechanism.

Theorem 4.1 holds regardless of choice of the outside option’s fixed value and
bias. Before giving the details of the proof, we derive two technical results
which will facilitate analysis. In Section 4.1 for any delegation set, we give
a decomposition of the principal’s utility into two quantities, one aligned
with the agent’s utility and one not. Then, in Section 4.2 we use independence
obtain a lower bound on the value from threshold sets which will prove useful
for both this and the next section’s analyses.

###  4.1 Utility Decomposition

The principal’s task is to balance two sources of utility. On the one hand,
when some action has very high value, preferences are aligned: the principal
benefits from giving the agent the flexibility to select this action. On the
other hand, when actions have smaller values, the principal must control
misalignment: they may benefit from restricting the agent away from actions
with higher bias, inducing the agent to take actions that provide better
value. We now decompose the principal’s utility for the optimal delegation set
into two quantities, Sur and BDif, which roughly correspond to the value from
each of these two cases.

To make the decomposition precise, note that for the optimal delegation set
$A^{*}$, there are two lower bounds imposed on the agent utility from any
selection: first, the chosen action must be preferred to the outside option,
action $0$, which gives utility at least $b_{0}$. Second, the agent’s utility
is at least the bias of the most-biased action in $A^{*}$. Denote the better
of these bounds by $\underline{u}$. We can therefore think of the contribution
of any action $i\in A^{*}$ as decomposing into a bias difference
$\underline{u}-b_{i}$ and a surplus $v_{i}-(\underline{u}-b_{i})$.
Intuitively, the surplus captures the principal’s utility from giving the
agent latitude to pick high-valued actions, and the bias difference captures
the misaligned portion of the principal’s utility. Formally, the decomposition
is the following.

###### Lemma 1

Let $A^{*}$ denote the optimal delegation set, and let
$\underline{u}=\max\\{b_{i}\,|\,i\in A^{*}\cup\\{0\\}\\}$. Define Sur and BDif
as follows:

Sur
$\displaystyle=\int_{{\mathbf{v}}}v_{g(A^{*},{\mathbf{v}})}-(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\,dF({\mathbf{v}})$
BDif
$\displaystyle=\int_{{\mathbf{v}}}\underline{u}-b_{g(A^{*},{\mathbf{v}})}\,dF({\mathbf{v}}).$

Then we can write $f(A^{*})=\textsc{Sur}+\textsc{BDif}$.

To verify the intuition that Sur captures the aligned portion of the
principal’s utility, note that choosing the smallest threshold set containing
all of $A^{*}\cup\\{0\\}$ secures Sur for the principal. Formally:

###### Lemma 2

Let $A_{\underline{u}}=\\{i\,|\,b_{i}\leq\underline{u}\\}$. Then
$f(A_{\underline{u}})\geq\textsc{Sur}$.

###### Proof

We will argue pointwise for each value profile ${\mathbf{v}}$. The action
chosen by the agent under $A_{\underline{u}}$ is
$g(A_{\underline{u}},{\mathbf{v}})$, which has
$b_{g(A_{\underline{u}},{\mathbf{v}})}\leq\underline{u}$. Since
$g(A_{\underline{u}},{\mathbf{v}})$ is the agent’s favorite, we have
$v_{g(A_{\underline{u}},{\mathbf{v}})}+b_{g(A_{\underline{u}},{\mathbf{v}})}\geq
v_{g(A^{*},{\mathbf{v}})}+b_{g(A^{*},{\mathbf{v}})}$. Hence,

$\displaystyle v_{g(A_{\underline{u}},{\mathbf{v}})}$ $\displaystyle\geq
v_{g(A^{*},{\mathbf{v}})}+b_{g(A^{*},{\mathbf{v}})}-b_{g(A_{\underline{u}},{\mathbf{v}})}$
$\displaystyle\geq
v_{g(A^{*},{\mathbf{v}})}-(\underline{u}-b_{g(A^{*},{\mathbf{v}})}).$

Taking expectation over ${\mathbf{v}}$ yields the lemma.

Lemma 2 implies that the main difficulty for obtaining approximately-optimal
delegation sets is managing the misaligned portion of the principal’s utility.
Section 4.3 gives this analysis for the case with $v_{0}$ fixed, yielding a
$3$-approximation. Note Lemmas 1 and 2 hold even when the outside option’s
value $v_{0}$ is randomized. We will therefore make further use of them in our
analysis of that case in Section 5.

###  4.2 Lower Bounds via Partial Derandomization

To compare the performance of a threshold set $A_{t}$ to the optimal set
$A^{*}$, we will show that threshold sets can retain sufficient value from
$A_{t}\cap A^{*}$ without introducing actions in $A_{t}\setminus A^{*}$ which
overly distort the agent’s choices. Independence allows us to summarize the
interference of $A_{t}\setminus A^{*}$ with a single deterministic action.
This will greatly simplify subsequent analyses. This section focuses on the
case of fixed outside options, but we state our lemma for possibly randomized
outside options. We will reuse the result in Section 5.

###### Lemma 3

Assume values are independently distributed. Then for any threshold set
$A_{t}$, there exists a single action $a(t)$ with bias $b_{a(t)}=t$ and
deterministic value $v_{a(t)}$ such that $f(A_{t})\geq f(A_{t}\cap
A^{*}\cup\\{a(t)\\})$.

Note that $a(t)$ need not be an action from the original delegation instance.
The proof will follow from picking the worst realization of actions in
$A_{t}\setminus A^{*}$ for the principal. Note further that $a(t)$ may differ
for every threshold $t$: hence our lower bounds correspond not to one
derandomized delegation instance, but to one per threshold.

###### Proof

For brevity, denote $A_{t}\setminus A^{*}$ by $B_{t}$. Actions in $B_{t}$ may
have randomized values. The principal’s expected utility $f(A_{t})$ can be
computed by first realizing $v_{i}$ for all $i\in B_{t}$, then computing the
principal’s expected utility over the values of actions in $G_{t}=A_{t}\cap
A^{*}\cup\\{0\\}$. Hence, there must exist a joint realization of values
$\hat{v}_{i}$ for each $i\in B_{t}$ for which this latter expectation is at
most $f(A_{t})$. Let $\hat{B}_{t}$ denote a new set of actions consisting of
the actions $i\in B_{t}$ with $v_{i}$ fixed as $\hat{v}_{i}$. We have
$f(G_{t}\cup B_{t})\geq f(G_{t}\cup\hat{B}_{t})$. Any actions which are not
selected in any realization of the values for $G_{t}$ may be removed from
$\hat{B}_{t}$ without consequence. However, since values are fixed for each
$i\in\hat{B}_{t}$, the agent consistently prefers some particular action
$\hat{i}\in\hat{B}_{t}$ over the others in $\hat{B}_{t}$. Hence, we may remove
all actions but $\hat{i}$ from $\hat{B}_{t}$ without changing the principal’s
utility.

We finally use this remaining action $\hat{i}$ to construct $a(t)$. Let
$v_{\hat{i}}$ and $b_{\hat{i}}$ denote the value and bias of $\hat{i}$. Define
$a(t)$ to have bias $t$ and value $v_{\hat{i}}-(t-b_{\hat{i}})$. Note that
$v_{\hat{i}}+b_{\hat{i}}=v_{a(t)}+b_{a(t)}$. Hence, the agent will choose
$a(t)$ from $G_{t}\cup\\{a(t)\\}$ if and only if they would choose $\hat{i}$
from $G_{t}\cup\\{\hat{i}\\}$. Moreover, $v_{a(t)}=v_{\hat{i}}$. Hence,
$f(G_{t}\cup\\{a(t)\\})\leq f(G_{t}\cup\\{\hat{i}\\})\leq f(A_{t})$.

###  4.3 Proof of Theorem 4.1

We now show how to obtain a $3$-approximation to the optimal delegation
utility using threshold mechanisms, assuming $v_{0}$ is fixed. Lemma 1
decomposes the optimal utility into an aligned portion, Sur, and a misaligned
portion, BDif. Furthermore, Lemma 2 states that Sur can be $1$-approximated
using a threshold set. Hence, it will suffice to obtain a $2$-approximation to
BDif using thresholds. To do so, we use the derandomization of Lemma 3 to
derive an even stronger lower bound which holds when $v_{0}$ is fixed. We then
select a threshold for which this lower bound is guaranteed to be large.

###### Lemma 4

For any threshold set $A_{t}$:

$f(A_{t})\geq\min\Big{(}\underline{u}-t,\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[g(A^{*},{\mathbf{v}})\in
A_{t}\cup\\{0\\}]\,dF({\mathbf{v}})\Big{)}.$

To understand our lower bound, note two pitfalls a threshold set could face.
First, a too-expansive threshold could include high-bias actions which attract
the agent while providing little value. Second, a too-restrictive threshold
could leave the agent with too few options. Lemma 4 states that these are the
only two problems: if a threshold $t$ is sufficiently low and includes enough
of the actions providing BDif for $A^{*}$, $t$ will perform well.

######  Proof (Proof of Lemma 4)

We argue with respect to the derandomized action $a(t)$. For brevity, write
$\underline{A}_{t}=A_{t}\setminus A^{*}\cup\\{a(t)\\}$. Depending on
$v_{a(t)}+b_{a(t)}$, we have two cases, each of which produces a lower bound
on $f(\underline{A}_{t})$,

  * •

Case 1: $v_{a(t)}+b_{a(t)}<\underline{u}$. In this case, any time
$g(A^{*},{\mathbf{v}})\in A_{t}\cup\\{0\\}$, we have
$g(A^{*},{\mathbf{v}})=g(\underline{A}_{t},{\mathbf{v}})$. Since every choice
from $A^{*}$ gives the agent utility at least $\underline{u}$, we have
$v_{g(\underline{A}_{t},{\mathbf{v}})}+b_{g(\underline{A}_{t},{\mathbf{v}})}\geq\underline{u},$
and hence
$v_{g(\underline{A}_{t},{\mathbf{v}})}\geq\underline{u}-b_{g(\underline{A}_{t},{\mathbf{v}})}$.
Integrating over all ${\mathbf{v}}$ yields

$f(A_{t})\geq
f(\underline{A}_{t})\geq\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[g(A^{*},{\mathbf{v}})\in
A_{t}\cup\\{0\\}]\,dF({\mathbf{v}}).$

  * •

Case 2: $v_{a(t)}+b_{a(t)}\geq\underline{u}$. Then regardless of
${\mathbf{v}}$, we have
$v_{g(\underline{A}_{t},{\mathbf{v}})}+b_{g(\underline{A}_{t},{\mathbf{v}})}\geq\underline{u}$.
Since the agent breaks ties in the principal’s favor, we also have that
$g(\underline{A}_{t},{\mathbf{v}})\neq 0$, so
$b_{g(\underline{A}_{t},{\mathbf{v}})}\leq t$. We may conclude that for all
${\mathbf{v}}$,
$v_{g(A_{t},{\mathbf{v}})}\geq\underline{u}-b_{g(A_{t},{\mathbf{v}})}\geq\underline{u}-t$,
and hence

$f(A_{t})\geq f(\underline{A}_{t})\geq\underline{u}-t.$

Hence the lemma holds in both cases.

The lower bound in Lemma 4 is a minimum of two terms. We will now study the
threshold $\hat{t}=\underline{u}-\textsc{BDif}/2$, and observe that both terms
in the minimum are at least $\textsc{BDif}/2$. In particular, we can lower
bound the second term as follows:

###### Lemma 5

Let $\hat{t}=\underline{u}-\textsc{BDif}/2$. Then we have:

$\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[g(A^{*},{\mathbf{v}})\in
A_{\hat{t}}\cup\\{0\\}]\,dF({\mathbf{v}})\geq\textsc{BDif}/2.$

###### Proof

Let $\mathcal{E}_{2}$ denote the event that $g(A^{*},{\mathbf{v}})\in
A_{\hat{t}}\cup\\{0\\}$. The following sequence of inequalities, explained
below, implies the lemma:

BDif
$\displaystyle=\int_{{\mathbf{v}}}\underline{u}-b_{g(A^{*},{\mathbf{v}})}\,dF({\mathbf{v}})$
$\displaystyle=\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{2}]\,dF({\mathbf{v}})+\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\overline{\mathcal{E}_{2}}]\,dF({\mathbf{v}})$
$\displaystyle<\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{2}]\,dF({\mathbf{v}})+(\underline{u}-\hat{t})$
$\displaystyle=\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{2}]\,dF({\mathbf{v}})-\textsc{BDif}/2.$

The first equality is the definition of BDif. The third equality follows from
the fact that under $\overline{\mathcal{E}_{2}},$
$b_{g(A^{*},{\mathbf{v}})}>\hat{t}$, and from the fact that this occurs with
probability at most $1$. The last equality follows from the definition of
$\hat{t}$.

######  Proof (Proof of Theorem 4.1)

By combining Lemma 4, with the definition of $\hat{t}$ and Lemma 5, we have:

$\displaystyle f(A_{\hat{t}})$
$\displaystyle\geq\min\Big{(}(\underline{u}-\hat{t}),\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[g(A^{*},{\mathbf{v}})\in
A_{\hat{t}}\cup\\{0\\}]\,dF({\mathbf{v}})\Big{)}$
$\displaystyle=\min\Big{(}\tfrac{\textsc{BDif}}{2},\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[g(A^{*},{\mathbf{v}})\in
A_{\hat{t}}\cup\\{0\\}]\,dF({\mathbf{v}})\Big{)}$
$\displaystyle\geq\min\left(\tfrac{\textsc{BDif}}{2},\tfrac{\textsc{BDif}}{2}\right)=\tfrac{\textsc{BDif}}{2}.$

The theorem now follows from noting that
$f(A^{*})=\textsc{Sur}+\textsc{BDif}\leq
f(A_{\underline{u}})+2f(A_{\hat{t}}).$

The proof of Theorem 4.1 used independence once, in the derandomization step
of Lemma 3. Nevertheless, we show in Section 6 that independence is critical
to guaranteeing the performance of threshold mechanisms by giving a super-
constant lower bound in its absence. With independence, the following example
matches the upper bound exactly:

###### Example 4

Our example will have five actions, with biases and value distributions given
below. The outside option will have $b_{0}=-\infty$, and therefore can be
ignored. Take two small numbers, $\delta$ and $\epsilon$, with $\delta$ much
smaller than $\epsilon$. Actions will be as follows:

  * •

$b_{1}=0$. $v_{1}$ is $1+2\delta$ with probability $\epsilon$, and $0$
otherwise.

  * •

$b_{2}=1-\epsilon-\delta$. $v_{2}=4\delta+\epsilon$.

  * •

$b_{3}=1-\epsilon$. $v_{3}=\epsilon+\delta$.

  * •

$b_{4}=1-\delta$. $v_{4}=5\delta$.

  * •

$b_{5}=1$. $v_{5}$ is $1$ with probability $\epsilon$, and $0$ otherwise.

We may analyze the instance neglecting $\delta$ terms, which only serve to
break ties for the agent. The optimal delegation set is $\\{1,3,5\\}$, with
principal utility $(1-(1-\epsilon)^{2})+\epsilon(1-\epsilon)^{2}$, where the
first term comes from the event that either actions $1$ or $5$ realize their
high values (in which case they are chosen), and the second term comes from
the event that $1$ and $5$ are low-valued, in which case the agent prefers
action $3$. As $\epsilon\rightarrow 0$, the optimal value goes to $0$ as
$\approx 3\epsilon$. Meanwhile, no threshold obtains expected value better
than $\epsilon$. This yields an approximation ratio of $3$ in the limit.

###  4.4 Computational Hardness

We conclude the section by discussing the complexity of the delegation problem
with independent values. For the discrete version of the problem, where every
action $i$ is specified by a bias $b_{i}$ and a list of realizations
$((v_{i}^{1},p_{i}^{1}),\ldots,(v_{i}^{n},p_{i}^{n}))$, we prove:

###### Theorem 4.2

Delegation with independent values is NP-complete, even with no outside
option.

The challenge in proving NP-hardness is managing the rigid structure of the
joint value distribution imposed by independence. We adopt a similar strategy
to Chen et al. (2014), who show that pricing to a unit-demand buyer is hard.
We reduce from Integer Partition: given integers $c_{1},\ldots,c_{n}$, the
goal is to find a subset $S\subseteq[n]$ such that $\sum_{i\in
S}c_{i}=\tfrac{1}{2}\sum_{i=1}^{n}c_{i}$. We associate each integer $c_{i}$
with an action $i$. Each such action impacts the principal’s utility via two
low-probability realizations: a bad realization which harms the principal’s
utility and a good realization which improves the principal’s utility. These
low probabilities are tuned in such a way that only first- and second-order
terms in the probability calculation are relevant. Furthermore, the tuning is
such that the bad events scale linearly with the $c_{i}$s, while the good
events scale in a concave way, with the principal’s utility being maximized
when actions taken correspond to an even split of the integers. Full details
can be found in Appendix 0.A.1. Note that Theorem 4.2 also implies hardness of
the model in the next section, with a random outside option.

##  5 Randomized Outside Options

In Section 4, we showed that with a fixed (or non-existent) outside option, a
simple delegation set secures a constant fraction of the utility from the
optimal delegation set. We now consider the case where the outside option’s
value is randomized. This may be more realistic in scenarios such as
assortment optimization, where the agent’s outside option is taking an action
(i.e. buying a good) somewhere else. In this regime, we again give tight
bounds. In Section 5.1, we show that no nontrivial multiplicative
approximation is possible with threshold sets: there are examples where
thresholds give no better than an $\Omega(n)$-approximation, which can be
matched trivially. However, in Section 5.2 we show that such lower bound
examples are necessarily unnatural. In particular, we parametrize our analysis
by the ratio $\rho=v_{\max}/\textsc{OPT}$, where OPT is the optimal principal
utility and $v_{\max}$ the highest value in any action’s support. We prove
that the worst-case approximation is $\Theta(\log\rho/\log\log\rho)$: hence,
whenever thresholds perform poorly, it is because the optimal solution relies
on exponentially large, exponentially rare values.

###  5.1 Unparametrized Analysis: Impossibility

This section gives an unparametrized analysis of threshold delegation with a
randomized outside option. We show that it is not possible to guarantee a
nontrivial approximation factor which holds across all instances.

Our constant-approximation in Section 4 relied on our ability to separate the
optimal utility into two parts, BDif and Sur. Approximating the bias
difference BDif was the crux of the analysis. The following example shows that
with a random outside option value $v_{0}$, this analysis — and in particular
the approximation of BDif — fails. We will choose our distribution over
$v_{0}$ to streamline exposition, but the example that follows could be
adjusted so that the distribution over $v_{0}$ satisfies nearly any desired
regularity condition.

###### Example 5

Our example will feature two sets of actions: good actions, which are taken by
the optimal delegation set, and bad actions, which are not. We will index the
actions so that the $i$th good action is $g(i)$, and the bad action between
good actions $g(i-1)$ and $g(i)$ is $b(i)$. For $i\in\\{1,\ldots,n\\}$ $g(i)$
will have:

  * •

bias $n^{n-1}-n^{n-i}$:

  * •

value $n^{n-i}+i\epsilon$ with probability $1/n$, and $0$ otherwise.333It is
equivalent for this example to use distribution $n^{n-i}+i\epsilon$ with
probability $1/n$, and $n^{n-i}-\epsilon$ otherwise. Under this distribution,
the example becomes an instance of assortment optimization, as described in
Section 3. This makes our parametrized analysis in Section 5.2 tight even for
that special case.

The bad actions will be indexed by $b(i)$ for $i\in\\{2,\ldots,n\\}$. Bad
action $b(i)$ will have

  * •

bias $n^{n-1}-n^{n-i}$.

  * •

value $n^{n-i}+(i-1)\epsilon+\delta$, for $\delta\ll\epsilon$.

The outside option will have bias $n^{n-1}$ and value $v_{0}$ distributed
according to a discrete distribution. We will set
$\Pr[v_{0}=\epsilon/2]=n^{-(n-1)}$. For $i>1$, we will choose probability mass
function $\Pr[v_{0}=i\epsilon-\epsilon/2]=n^{-(n-i)}-n^{-(n-i+1)}$. Note that
we have picked these probabilities so that $\Pr[v_{0}<i\epsilon]=n^{-(n-i)}$.
The values of all actions described above are independent.

A solution to the delegation instance we just described is to take only good
actions. The probability that at least one good action takes its high value is
$1-(1-1/n)^{n}\geq 1-1/e$. Assume this event has occurred, and that the
agent’s preferred good action is $g(i)$. Then $g(i)$ is preferred to the
outside option with probability $n^{-(n-i)}$. Hence, the principal’s expected
utility from choosing only good actions is at least:

$f(\\{g(1),\ldots,g(n)\\})\geq(1-1/e)n^{-(n-i)}(n^{n-i}+\epsilon i)\geq
1-1/e.$

Now consider a threshold set $A_{t}$. It is without loss of generality to
consider $t=n^{n-1}-n^{n-j}$ for some $j$, which implies that the highest-bias
actions in $A_{t}$ are $g(j)$ and $b(j)$. For any good action $g(i)$, with
$i<j$, the agent’s utility for $g(i)$ on a high-valued realization is
$n^{n-1}+i\epsilon<n^{n-1}+(j-1)\epsilon+\delta$. Hence, the agent ignores all
actions other than $g(j)$, $b(j)$, and the outside option. If $g(j)$ draws its
high value, the principal gets utility $n^{n-j}+j\epsilon$ utility if and only
if $g(j)$ survives the outside option, which happens with probability
$n^{-(n-j)}$. Otherwise, the agent looks to action $b(j)$, and takes it over
the outside option with probability $n^{-(n-j+1)}$. Ignoring value from the
outside option, which goes to $0$ as $\epsilon\rightarrow 0$, we can account
for the utility from $A_{t}$ as follows:

$\displaystyle f(A_{t})$
$\displaystyle=\tfrac{1}{n}n^{-(n-j)}(n^{n-j}+j\epsilon)+(1-\tfrac{1}{n})(n^{n-j}+(j-1)\epsilon+\delta)n^{-(n-j+1)}.$
$\displaystyle\approx\tfrac{1}{n}+(1-1/n)\tfrac{1}{n},$

where the latter approximation holds for $\epsilon$ and $\delta$ sufficiently
small. This implies that every threshold incurs a loss which is $\Omega(n)$.

An upper bound of $n$ for threshold mechanisms is trivial, by the following
lemma. Hence, up to a constant, the lower bound in Example 5 is tight.

###### Lemma 6

For any set $A$ and $i\in A\cup\\{0\\}$, let
$A^{i}=\int_{{\mathbf{v}}}v_{i}\,\mathbb{I}[g(A,{\mathbf{v}})=i]\,d{\mathbf{v}}$
denote the contribution to $f(A)$ from action $i$. Then $f(A_{b_{i}})\geq
A^{i}$.

###### Proof

Consider any ${\mathbf{v}}$ where $g(A,{\mathbf{v}})=i$. The action chosen by
the agent under $A_{b_{i}}$ is $g(A_{b_{i}},{\mathbf{v}})$, which has
$b_{g(A_{b_{i}},{\mathbf{v}})}\leq b_{i}$. Since $g(A_{b_{i}},{\mathbf{v}})$
is the agent’s favorite, we have
$v_{g(A_{b_{i}},{\mathbf{v}})}+b_{g(A_{b_{i}},{\mathbf{v}})}\geq
v_{g(A,{\mathbf{v}})}+b_{g(A,{\mathbf{v}})}=v_{i}+b_{i}$. Hence,
$v_{g(A_{b_{i}},{\mathbf{v}})}\geq
v_{i}+b_{i}-b_{g(A_{b_{i}},{\mathbf{v}})}\geq v_{i}$. Taking expectation over
${\mathbf{v}},$ we obtain:

$f(A_{b_{i}})=\int_{{\mathbf{v}}}v_{g(A_{b_{i}},{\mathbf{v}})}\,dF({\mathbf{v}})\geq\int_{{\mathbf{v}}}v_{g(A_{b_{i}},{\mathbf{v}})}\,\mathbb{I}[g(A,{\mathbf{v}})=i]\,dF({\mathbf{v}})\geq\int_{{\mathbf{v}}}v_{i}\,\mathbb{I}[g(A,{\mathbf{v}})=i]\,dF({\mathbf{v}}),$

where the first inequality follows from the nonnegativity of $v_{i}$.

An $n$-approximation then follows from noting that for any set $A$,
$f(A)=\sum_{i}A^{i}$.

###### Corollary 5.1

With independent values (and possibly randomized outside option), the best
threshold is an $n$-approximation to the optimal delegation set.

###  5.2 Parametrized Approximation

In the previous section, we gave an example where no threshold set was better
than an $\Omega(n)$-approximation. However, this example was extreme, in the
sense that while the optimal solution obtained $O(1)$ utility, some actions
had values which were as large as $n^{n-1}$. We now show that this is no
coincidence: any example where threshold mechanisms perform poorly must be
unnatural in this way.

###### Theorem 5.1

Let $\rho=v_{\max}/\textsc{OPT}$, where OPT is the optimal principal utility
and $v_{\max}$ the highest value in any action’s support. Then with
independent values (and a possibly randomized outside option), the best
threshold is a $O(\log\rho/\log\log\rho)$-approximation to OPT.

Theorem 5.1 is of particular interest for the application of assortment
optimization. For an instance of the latter problem, each item $i$ yields
revenue $p_{i}$ for the seller, and value $w_{i}$ for the buyer. Framed as a
delegation problem, we have $v_{i}=p_{i}+\epsilon w_{i}$, for sufficiently
small $\epsilon$. Hence, Theorem 5.1 implies that the prices $p_{i}$ must be
extreme whenever revenue-ordered assortments perform poorly. Another
consequence of Theorem 5.1 is a bicriteria approximation when values lie in
$[0,1]$: either some threshold obtains a small multiplicative approximation,
or it is trivial to obtain an additive approximation.

######  Proof (Proof of Theorem 5.1)

We will argue the contrapositive. That is, we will argue with respect to some
integer $\alpha\geq 4$, and assume that no threshold obtains a
$\beta$-approximation for any $\beta<16\alpha$. Under this assumption, we show
that there must be an action with value at least
$(\alpha-2)^{\alpha-1}\textsc{OPT}/8\alpha$ with positive probability. The
analysis will roughly proceed in three steps. First, we partition the optimal
solution into $\alpha$ subsets with roughly equal contribution to OPT. We then
consider the thresholds based on each of these subsets, and compare their
utility to that from the sets themselves; by assumption, no such threshold
will outperform its respective subset. Finally, we combine the resulting
inequalities to show that the only way all can hold simultaneously is if the
bias of one of these thresholds is extreme. This will imply the existence of a
comparably high value. Throughout, we will make use of our decomposition and
derandomization from Lemmas 1 and 3, respectively.

#### Decomposing OPT

Before defining our thresholds, we note that when no threshold approximates
OPT well, we may draw several simplifying conclusions about the structure of
OPT. Let $A^{*}$ be an optimal subset of actions, and assume every action in
$A^{*}$ is selected with positive probability. Following Lemma 1, write
$\textsc{OPT}=f(A^{*})=\textsc{Sur}+\textsc{BDif}$, and write
$\underline{u}=\max\\{b_{i}\,|\,i\in A^{*}\cup\\{0\\}\\}$. By Lemma 2, it must
be that $\textsc{Sur}<\textsc{OPT}/\alpha$, or else the grand threshold
$A_{\underline{u}}$ would be an $\alpha$-approximation, contradicting the
nonexistence of any $\beta<16\alpha$-approximation. We may therefore focus our
analysis on
$\textsc{BDif}=\int_{{\mathbf{v}}}\underline{u}-b_{g(A^{*},{\mathbf{v}})}\,dF({\mathbf{v}})$.
It must again be that no threshold obtains better than an
$8\alpha$-approximation to
$\textsc{BDif}>(1-1/\alpha)\textsc{OPT}\geq\textsc{OPT}/2$.

Next, note that no one action can comprise a large fraction of BDif. More
precisely, let

$\displaystyle\textsc{OPT}^{i}=\int_{{\mathbf{v}}}v_{i}\mathbb{I}[g(A^{*},{\mathbf{v}})=i]\,dF({\mathbf{v}})$
$\displaystyle\textsc{BDif}^{i}=\int_{{\mathbf{v}}}(\underline{u}-b_{i})\mathbb{I}[g(A^{*},{\mathbf{v}})=i]\,dF({\mathbf{v}})$

denote the contribution of action $i$ to OPT and BDif, respectively. Since
$g(A^{*},{\mathbf{v}})=i$ only if $v_{i}\geq(\underline{u}-b_{i})$, we must
have $\textsc{OPT}^{i}\geq\textsc{BDif}^{i}$. Lemma 6 implies that we may
obtain $\textsc{OPT}^{i}$ from a threshold set for any $i\in
A^{*}\cup\\{0\\}$. We must therefore have that
$\textsc{BDif}^{0}\leq\textsc{BDif}/8\alpha$, and therefore that
$\textsc{BDif}-\textsc{BDif}^{0}\geq(1-1/8\alpha)\textsc{BDif}\geq\textsc{BDif}/2$.
The remainder of the proof will focus on approximating
$\textsc{BDif}-\textsc{BDif}^{0}$, assuming no approximation better than
$4\alpha$ is possible. Lemma 6 implies that
$\textsc{BDif}^{i}\leq(\textsc{BDif}-\textsc{BDif}^{0})/4\alpha$ for all $i\in
A^{*}$.

#### Constructing Thresholds

We now obtain a sequence of candidate thresholds by partitioning the actions
in $A^{*}$ based on their contribution to $\textsc{BDif}-\textsc{BDif}^{0}$.
Let $m=|A^{*}|$, and relabel the actions in $A^{*}$ as $1,\ldots,m$, with
$b_{i}\leq b_{i+1}$ for all $i\in\\{1,\ldots,m-1\\}$. Actions not in $A^{*}$
will be indexed $m+1,\ldots,n$ (with $0$ keeping its label). We will partition
$A^{*}$ greedily to produce $\alpha$ subsets of roughly equal contribution to
$\textsc{BDif}-\textsc{BDif}^{0}$. More precisely, define the first breakpoint
between subsets as $k_{0}=0$, and for $j\in\\{1,\ldots,\alpha\\}$, define
subsequent breakpoints $k_{j}$ recursively as the smallest
$k\in\\{k_{j-1}+1,\ldots,m\\}$ such that $\sum_{i=1}^{k}\textsc{BDif}^{i}\geq
j(\textsc{BDif}-\textsc{BDif}^{0})/\alpha$. Define the partition as
$A^{*}(j)=\\{k_{j-1}+1,\ldots,k_{j}\\}$ for all $j$. We can upper- and
lowerbound the distortion of each bin: since
$\textsc{BDif}^{i}<(\textsc{BDif}-\textsc{BDif}^{0})/4\alpha$ for all $i$, it
must be that $A^{*}(j)$ is nonempty for $j\in\\{1,\ldots,\alpha\\}$. Further
define $\textsc{BDif}(j)=\sum_{i\in A^{*}(j)}\textsc{BDif}^{i}$. We must also
have $\textsc{BDif}(j)\geq(\textsc{BDif}-\textsc{BDif}^{0})/2\alpha$ for all
$j$, and hence no threshold can attain better than a $2$-approximation to
$\textsc{BDif}(j)$ for any $j$. We will define candidate thresholds based on
each bin: let $t_{j}=b_{k_{j}}$ (with $t_{0}=\min_{i\in A^{*}}b_{i}$), and
define the threshold sets $A_{j}=\\{i\,|\,b_{i}\leq b_{k_{j}}\\}$ for all $j$.

#### Lower Bounding Threshold Utilities

To lower bound the principal utility from $A_{j}$, we apply Lemma 3 and
consider $f(A_{j}\cap A^{*}\cup\\{a(t_{j})\\})$ for some suitably constructed
interfering action $a(t_{j})$ with bias $t_{j}$. We write
$\underline{A}_{j}=A_{j}\cap A^{*}\cup\\{a(t_{j})\\}$. Note that the
interfering action $a(t_{j})$ must give the agent high utility, or else
$\underline{A}_{j}$ would perform as well as its respective bin $A^{*}(j)$.
Formally, let $\mathcal{E}_{j}$ be the event that the agent’s preferred action
from $A^{*}$ is in $A^{*}(j)$. (Note that the agent may still ultimately
choose action $0$ under either $\mathcal{E}_{j}$ or
$\overline{\mathcal{E}}_{j}$, and that
$\sum_{j}\text{Pr}[\mathcal{E}_{j}]=1$.) If
$v_{a(t_{j})}+b_{a(t_{j})}<\underline{u}$, then the threshold performance
$f(\underline{A}_{j})$ can be written as

$\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\,dF({\mathbf{v}})\geq\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\mathbb{I}[\mathcal{E}_{j}]\,dF({\mathbf{v}})=\int_{{\mathbf{v}}}v_{g(A^{*},{\mathbf{v}})}\mathbb{I}[\mathcal{E}_{j}]\,dF({\mathbf{v}})\geq\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}]\,dF({\mathbf{v}}).$

The righthand expression is the bias difference conditioned on
$\mathcal{E}_{j}$, which is at least $\textsc{BDif}(j).$ This contradicts our
assumption that no threshold approximates $\textsc{BDif}(j)$ to a factor
better than $2$.

We will now lowerbound $f(\underline{A}_{j})$ by decomposing it into two
terms, depending on the event $\mathcal{E}_{j}$:

$f(\underline{A}_{j})=\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\,dF({\mathbf{v}})=\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\mathbb{I}[\mathcal{E}_{j}]\,dF({\mathbf{v}})+\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\mathbb{I}[\overline{\mathcal{E}}_{j}]\,dF({\mathbf{v}})$
(1)

To lowerbound the first term the right of (1), define the event
$\mathcal{E}^{+}_{j}$ to be the event that
$g(\underline{A}_{j},\mathbf{v})\neq 0$, and ${\mathcal{E}}^{=}_{j}$ to be the
event that the agent’s favorite action in $A^{*}(j)$ is also their favorite in
$\underline{A}_{j}$. In ${\mathcal{E}}^{=}_{j}$, the agent may still
ultimately take the outside option. We may now write:

$\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\mathbb{I}[\mathcal{E}_{j}]\,dF({\mathbf{v}})=\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})\geq\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}}),$

where the inequality comes from the fact that under
$\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}$, the agent
chooses the same thing from $A^{*}$ as they would from $\underline{A}_{j}$,
and hence that action gives the agent utility at least $\underline{u}$.

To lowerbound the second term on the right of (1), let
$\mathcal{E}_{j}^{\leq}$ be the event that the agent prefers $a(t_{j})$ to the
outside option, i.e. $v_{0}+b_{0}\leq v_{a(t_{j})}+b_{a(t_{j})}$. We may then
lowerbound the second term as:

$\int_{{\mathbf{v}}}v_{g(\underline{A}_{j},{\mathbf{v}})}\mathbb{I}[\overline{\mathcal{E}}_{j}\cap\mathcal{E}^{+}_{j}]\,dF({\mathbf{v}})\geq\int_{{\mathbf{v}}}(\underline{u}-t_{j})\mathbb{I}[\overline{\mathcal{E}}_{j}\cap\mathcal{E}^{+}_{j}]\,dF({\mathbf{v}})\geq(\underline{u}-t_{j})\text{Pr}[\overline{\mathcal{E}}_{j}]\text{Pr}[\mathcal{E}_{j}^{\leq}].$

The first inequality follows from the fact that the action chosen in
$\underline{A}_{j}$ yields utility at least $v_{a(t_{j})}+t_{j}$ and has bias
at most $t_{j}$. The second inequality follows from the facts that
$\mathcal{E}_{j}^{\leq}\leq\mathcal{E}^{+}_{j}$ and $\mathcal{E}_{j}^{\leq}$
and $\mathcal{E}_{j}$ are independent. Taking the two terms together, we have
the lower bound

$f(\underline{A}_{j})\geq\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})+(\underline{u}-t_{j})\text{Pr}[\overline{\mathcal{E}}_{j}]\text{Pr}[\mathcal{E}_{j}^{\leq}].$
(2)

Figure 1: List of events for proof of Theorem 5.1.

  * •

$\mathcal{E}_{j}$: agent’s favorite non-$0$ action in $A^{*}$ is in
$A^{*}(j)$.

  * •

$\mathcal{E}^{+}_{j}$: $g(\underline{A}_{j},{\mathbf{v}})\neq 0$.

  * •

${\mathcal{E}}^{=}_{j}$: the agent’s favorite action in $A^{*}(j)$ is also
their favorite in $\underline{A}_{j}$.

  * •

$\mathcal{E}_{j}^{\leq}$: $v_{0}+b_{0}\leq v_{a(t_{j})}+b_{a(t_{j})}$.

  * •

$\mathcal{E}^{*}$: $g(A^{*},{\mathbf{v}})\neq 0$

#### Upper Bounding $\textsc{BDif}(j)$

Next, we upperbound the contribution of $A^{*}(j)$ to BDif. We will split
$\textsc{BDif}(j)$ based on the event ${\mathcal{E}}^{=}_{j}$ that the agent’s
favorite action is the same between $A^{*}(j)$ and $\underline{A}_{j}$. Let
$\mathcal{E}^{*}$ denote the event that $g(A^{*},{\mathbf{v}})\neq 0$. We
have:

$\displaystyle\textsc{BDif}(j)$
$\displaystyle=\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{*}]\,dF({\mathbf{v}})$
$\displaystyle=\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{*}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})+\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{*}\cap\overline{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}}).$
(3)

We can now upperbound each term in (3), starting by rewriting the leftmost. In
the intersection event $\mathcal{E}_{j}\cap{\mathcal{E}}^{=}_{j}$, the
favorite non-$0$ action from $A^{*}$ and $\underline{A}_{j}$ are the same.
Hence conditioned on this event,
$g(\underline{A}_{j},\mathbf{v})=g(A^{*},\mathbf{v})$ and
$\mathcal{E}^{*}=\mathcal{E}^{+}_{j}$. Therefore:

$\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{*}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})=\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}}).$

To upperbound the second term in (3), note first that in the event
$\mathcal{E}_{j}\cap\mathcal{E}^{*}$, the chosen action’s bias is at least
$t_{j-1}$ and hence the bias difference is at most $\underline{u}-t_{j-1}$.
Second, note that conditioned on
$\mathcal{E}_{j}\cap\overline{\mathcal{E}}^{=}_{j}$, it must be that the agent
prefers $a(t_{j})$ to all actions in $A^{*}(j)$. Hence, conditioned on
$\mathcal{E}_{j}\cap\overline{\mathcal{E}}^{=}_{j}$, it must be that any time
the agent prefers an action in $A^{*}(j)$ to the outside option, it must be
that they also prefer $a(t_{j})$. Hence,
$\mathcal{E}_{j}\cap\mathcal{E}^{*}\cap\overline{\mathcal{E}}^{=}_{j}\subseteq\mathcal{E}_{j}\cap\mathcal{E}_{j}^{\leq}\cap\overline{\mathcal{E}}^{=}_{j}$.
Finally, note that $\mathcal{E}_{j}$ and $\mathcal{E}_{j}^{\leq}$ are
independent. These facts imply:

$\displaystyle\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{*}\cap\overline{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})$
$\displaystyle\leq(\underline{u}-t_{j-1})\int_{{\mathbf{v}}}\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{*}\cap\overline{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})$
$\displaystyle\leq(\underline{u}-t_{j-1})\int_{{\mathbf{v}}}\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}_{j}^{\leq}\cap\overline{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})$
$\displaystyle\leq(\underline{u}-t_{j-1})\text{Pr}[\mathcal{E}_{j}\cap\mathcal{E}_{j}^{\leq}]$
$\displaystyle=(\underline{u}-t_{j-1})\text{Pr}[\mathcal{E}_{j}]\text{Pr}[\mathcal{E}_{j}^{\leq}].$

Combining the two terms, we have:

$\textsc{BDif}(j)\leq\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})+(\underline{u}-t_{j-1})\text{Pr}[\mathcal{E}_{j}]\text{Pr}[\mathcal{E}_{j}^{\leq}].$
(4)

#### Lowerbounding Bias Differences

Inequality (2) lowerbounds $f(\underline{A}_{j})$ in terms of $t_{j}$, and
inequality (4) upperbounds $\textsc{BDif}(j)$ in terms of $t_{j-1}$. Since no
threshold is better than a $2$-approximation to $\textsc{BDif}(j)$, it must
hold that our upper bound on $\textsc{BDif}(j)$ exceeds our lower bound on
$f(\underline{A}_{j})$. That is:

$\displaystyle\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})+(\underline{u}-t_{j})\text{Pr}[\overline{\mathcal{E}}_{j}]\text{Pr}[\mathcal{E}_{j}^{\leq}]$
$\displaystyle\quad\quad\quad\leq\int_{{\mathbf{v}}}(\underline{u}-b_{g(A^{*},{\mathbf{v}})})\mathbb{I}[\mathcal{E}_{j}\cap\mathcal{E}^{+}_{j}\cap{\mathcal{E}}^{=}_{j}]\,dF({\mathbf{v}})+(\underline{u}-t_{j-1})\text{Pr}[\mathcal{E}_{j}]\text{Pr}[\mathcal{E}_{j}^{\leq}].$

We may rearrange this as

$\frac{\underline{u}-t_{j-1}}{\underline{u}-t_{j}}\geq\frac{1-\text{Pr}[\mathcal{E}_{j}]}{\text{Pr}[\mathcal{E}_{j}]}.$

Taking the product over all $j\leq\alpha-1$ and canceling yields:

$\frac{\underline{u}-t_{0}}{\underline{u}-t_{\alpha-1}}\geq\prod_{j=1}^{\alpha-1}\frac{1-\text{Pr}[\mathcal{E}_{j}]}{\text{Pr}[\mathcal{E}_{j}]}.$

Note that the righthand side is a convex, symmetric function of the
$\text{Pr}[\mathcal{E}_{j}]$s. Moreover, we have
$\sum_{j=1}^{\alpha-1}\text{Pr}[\mathcal{E}_{j}]\leq\sum_{j=1}^{\alpha}\text{Pr}[\mathcal{E}_{j}]=1$.
Hence, minimizing the righthand side as a function of the
$\text{Pr}[\mathcal{E}_{j}]$s yields a minimum at
$\text{Pr}[\mathcal{E}_{j}]=1/(\alpha-1)$ for all $j$, and hence
$(\underline{u}-t_{0})/(\underline{u}-t_{\alpha-1})\geq(\alpha-2)^{\alpha-1}$.
Note also that
$\textsc{BDif}(\alpha)\geq(\textsc{BDif}-\textsc{BDif}^{0})/2\alpha$. Since
$\textsc{BDif}(\alpha)\leq(\underline{u}-t_{\alpha-1})\text{Pr}[\mathcal{E}_{\alpha}]\leq(\underline{u}-t_{\alpha-1})$,
we obtain:

$\underline{u}-t_{0}\geq\frac{(\alpha-2)^{\alpha-1}}{2\alpha}(\textsc{BDif}-\textsc{BDif}^{0}).$

Since every action in $A^{*}$ is selected with positive probability, and since
$t_{0}=\min_{i\in A^{*}}b_{i}$, it must be that some action in $A^{*}$ has
value at least $\underline{u}-t_{0}$ with positive probability. Since
$\textsc{BDif}-\textsc{BDif}^{0}\geq\textsc{BDif}/2\geq\textsc{OPT}/4$, we
obtain the desired lower bound on $v_{\max}/\textsc{OPT}$.

##  6 Threshold Delegation with Correlated Values

In the previous sections, we showed that under independently-distributed
values, simple threshold rules obtain a close approximation the optimal
principal utility. We now allow arbitrarily correlated values and show that
the situation worsens considerably. Assuming the value distribution is
discrete, prove tight a approximation guarantee for the principal’s best
threshold policy, showing that it is a $\Theta(\log
p_{\text{min}}^{-1})$-approximation, where $p_{\text{min}}$ denotes the lowest
probability mass of any value profile realization. Hence, absent independence,
threshold policies still perform well under low levels of uncertainty, but
their performance gradually degrades as the uncertainty grows more extreme. We
state our results formally below, starting with our upper bound.

###### Theorem 6.1

There always exists a threshold policy which is a
$4\log(p_{\text{min}}^{-1})$-approximation where $p_{\text{min}}$ is the mass
of the least likely value profile.

###### Proof

Let $OPT$ be the optimal delegation set, and let $t_{0}$ be the maximum bias
across actions in $OPT$. Let $B$ be the random variable that corresponds to
the bias of the action chosen in $OPT$. Let $t_{1}$ be the bias threshold such
that $\Pr[B\in[t_{1},t_{0}]]\leq\frac{1}{2}$ and
$\Pr[B\in[0,t_{1}]]\geq\frac{1}{2}$. Let $OPT([t_{1},t_{0}])$ be the principal
utility generated conditioned on $B\in[t_{1},t_{0}]$. We claim that the
principal utility generated by using a best threshold out $A_{t_{1}}$ or
$A_{t_{0}}$ achieves principal utility at least
$\frac{1}{4}OPT([t_{1},t_{0}])$.

First consider the threshold $A_{t_{0}}$. Consider any realization where $OPT$
picks an action with bias at least $t_{0}$. Let $v,b$ be the value and bias of
the action chosen by $OPT$ and let $v^{\prime},b^{\prime}$ be the value and
bias of the action chosen by $A_{t_{0}}$ respectively. Since the action chosen
by $OPT$ is available in $A_{t_{0}}$ it must be that

$v^{\prime}+b^{\prime}\geq v+b\Leftrightarrow v-v^{\prime}\leq b^{\prime}-b.$

Note that from our assumptions $b^{\prime}\leq t_{0}$ and $b\geq t_{1}$,
therefore the pointwise loss of $A_{t_{0}}$ compared to $OPT$ is at most
$t_{0}-t_{1}$ in this event. As a result we can lower bound the principal
utility of $A_{t_{0}}$ as follows:

$f(A_{t_{0}})\geq\Pr[B\in[t_{1},t_{0}]](OPT([t_{1},t_{0}])-t_{0}+t_{1})\geq\frac{1}{2}(OPT([t_{1},t_{0}])-t_{0}+t_{1}).$

Second, consider the threshold $A_{t_{1}}$. Every time $OPT$ chooses an action
with bias less than or equal to $t_{1}$ this action is also available to
$A_{t_{1}}$. Note that if such action is chosen its agent utility must be at
least $t_{0}$ otherwise the action with the maximum bias would have been
chosen instead. The action chosen in $A_{t_{1}}$ therefore must have at least
agent utility $t_{0}$. Since the bias is at most $t_{1}$ this means that the
principal utility from that action is at least $t_{1}-t_{0}$. We conclude that

$f(A_{t_{1}})\geq(t_{0}-t_{1})\Pr[B\in[0,t_{1}]\geq\frac{1}{2}(t_{0}-t_{1}).$

As a result,

$f(A_{t_{0}})+f(A_{t_{1}})\geq\frac{1}{2}[OPT([t_{1},t_{0}])-t_{0}+t_{1}+t_{0}-t_{1}]=\frac{1}{2}OPT([t_{1},t_{0}])].$

Hence, the best out of both of these sets provides at least
$\frac{1}{4}OPT([t_{1},t_{0}])$ principal utility. Note that $OPT$ gets at
most $\Pr[B\in[t_{1},t_{0}]]OPT([t_{1},t_{0}])$ utility from this event
therefore the best of these threshold provides a $4$-approximation to the
events’ contribution to $OPT$’s principal utility.

We have shown that there exists a threshold that approximates the utility of
$OPT$ conditioned that $B\in[t_{1},t_{0}]$ that is

$\Pr[B\in[t_{1},t_{0}]]OPT([t_{1},t_{0}]).$

Let us focus on the remaining principal utility that is obtained by $OPT$ in
the event that $B\in[0,t_{2}]$ where $t_{2}$ bias of the most-biased action
smaller than $t_{1}$. One key observation is that this event happens with
probability at most $1/2$ by our choice of $t_{1}$ since
$\Pr[B\in[t_{1},t_{0}]]\geq\frac{1}{2}$.

If we consider the conditional distributions on this event we can repeat the
same analysis to prove that there exists bias threshold $t_{3}<t_{2}$ such
that $Prob[B\in[t_{3},t_{2})\mid B\in[0,t_{2}]]\geq 1/2$ and also

$\max\\{f(A_{t_{2}}),f(A_{t_{3}})\\}\geq\frac{1}{4}\Pr[B\in[0,t_{2}]]OPT([t_{3},t_{2}])\geq\frac{1}{4}\Pr[B\in[t_{3},t_{2}]]OPT([t_{3},t_{2}]),$

which corresponds to $4$-approximation to the contribution to $OPT$ solution’s
principal utility in this interval. Note that

$\Pr[B\in[0,t_{3})\mid B\in[0,t_{2}]]\leq 1/2\Rightarrow\Pr[B\in[0,t_{3}]]\leq
1/4.$

Repeating this process shrinks the probability of the remaining probability
space by half. Let $m$ be the maximum number of times we can repeat this
process. There are two ways this process can stop. Either we are left with a
single action or the probability that $B$ ($OPT$ bias) is strictly below the
last used threshold is $0$. Since the minimum probability of any realization
is $p_{min}$ and each time we repeat this process the probability is shrunk by
half $m$ cannot be larger than $\log{p_{min}^{-1}}$.

This process generates $m$ disjoint events $B\in[t_{2i+1},t_{2i}]$ for
$i=0,\dots,m-1$ such that

$OPT=\sum_{i=0}^{m-1}OPT([t_{2i+1},t_{2i}])Prob[B\in[t_{2i+1},t_{2i}]]$

and in addition

$\max\\{f(A_{t_{2i+1}},A_{t_{2i}}\\}\geq\frac{1}{4}OPT([t_{2i+1},t_{2i}])\Pr[B\in[t_{2i+1},t_{2i}]]$

If we combined these two equations together we get that

$\max_{i\in\\{0,\dots,2m-1\\}}f(A_{t_{i}})\geq\frac{m}{4}OPT$

Since $m\leq\log{p_{min}^{-1}}$ we get that the best possible threshold is at
least a $4\log{p_{min}^{-1}}$ approximation.

#### Matching lower bound.

The above analysis is tight. We show in Appendix 0.A.2 that our analysis in
Theorem 6.1 is tight up to a constant factor. We do so by providing instances
where no threshold policy can outperform the logarithmic approximation ratio.

###### Theorem 6.2

There exists a family of instances where no threshold policy is better than a
$\Omega(\log p_{\text{min}}^{-1})$-approximation.

In Appendix 0.A.3, we also prove the following supplementary hardness result
for the case with discretely-distributed, correlated values:

###### Theorem 6.3

With correlated, discrete values, there exists a constant $c$ such that it is
NP-hard to compute a mechanism with approximation factor better than $c$.

To prove this result, we reduce from bounded-degree vertex cover, which is
similarly hard to approximate.

### Acknowledgments

The authors thank Bobby Kleinberg, Hamsa Bastani, Rediet Abebe, and Shaddin
Dughmi for helpful discussions. The authors further thank Yuanzhe Liu, Yichi
Zhang, and Pucheng Xiong for their help as undergraduate research assistants
on this and related projects. Part of this work was done while Ali Khodabakhsh
and Emmanouil Pountourakis were visiting the Simons Institute for the Theory
of Computing.

## References

  * (1)
  * Aghion and Tirole (1997) Philippe Aghion and Jean Tirole. 1997.  Formal and real authority in organizations.  _Journal of political economy_ 105, 1 (1997), 1–29.
  * Alonso and Matouschek (2008) Ricardo Alonso and Niko Matouschek. 2008.  Optimal delegation.  _The Review of Economic Studies_ 75, 1 (2008), 259–293.
  * Amador and Bagwell (2010) Manuel Amador and Kyle Bagwell. 2010.  On the optimality of tariff caps.  _Unpublished working paper_ (2010).
  * Ambrus and Egorov (2017) Attila Ambrus and Georgy Egorov. 2017.  Delegation and nonmonetary incentives.  _Journal of Economic Theory_ 171 (2017), 101–135.
  * Aouad et al. (2018) Ali Aouad, Vivek Farias, Retsef Levi, and Danny Segev. 2018\.  The approximability of assortment optimization under ranking preferences.  _Operations Research_ 66, 6 (2018), 1661–1669.
  * Aouad et al. (2023) Ali Aouad, Jacob Feldman, and Danny Segev. 2023.  The exponomial choice model for assortment optimization: an alternative to the MNL model?  _Management Science_ 69, 5 (2023), 2814–2832.
  * Armstrong and Vickers (2010) Mark Armstrong and John Vickers. 2010.  A model of delegated project choice.  _Econometrica_ 78, 1 (2010), 213–244.
  * Bechtel and Dughmi (2021) Curtis Bechtel and Shaddin Dughmi. 2021.  Delegated Stochastic Probing. In _12th Innovations in Theoretical Computer Science Conference (ITCS 2021)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik.
  * Bechtel et al. (2022) Curtis Bechtel, Shaddin Dughmi, and Neel Patel. 2022\.  Delegated Pandora’s box.  _arXiv preprint arXiv:2202.10382_ (2022).
  * Berbeglia (2016) Gerardo Berbeglia. 2016\.  Discrete choice models based on random walks.  _Operations Research Letters_ 44, 2 (2016), 234–237.
  * Berbeglia and Joret (2020) Gerardo Berbeglia and Gwenaël Joret. 2020.  Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments.  _Algorithmica_ 82, 4 (2020), 681–720.
  * Braun et al. (2022) Pirmin Braun, Niklas Hahn, Martin Hoefer, and Conrad Schecker. 2022.  Delegated Online Search.  _arXiv preprint arXiv:2203.01084_ (2022).
  * Castiglioni et al. (2021) Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. 2021\.  Bayesian Agency: Linear versus Tractable Contracts.  _arXiv preprint arXiv:2106.00319_ (2021).
  * Chen et al. (2016) Wei Chen, Wei Hu, Fu Li, Jian Li, Yu Liu, and Pinyan Lu. 2016.  Combinatorial multi-armed bandit with general reward functions.  _Advances in Neural Information Processing Systems_ 29 (2016).
  * Chen et al. (2014) Xi Chen, Ilias Diakonikolas, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis. 2014\.  The complexity of optimal multidimensional pricing. In _Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms_. SIAM, 1319–1328.
  * Clementi and Trevisan (1999) Andrea EF Clementi and Luca Trevisan. 1999.  Improved non-approximability results for minimum vertex cover with density constraints.  _Theoretical Computer Science_ 225, 1-2 (1999), 113–128.
  * Davis et al. (2014) James M Davis, Guillermo Gallego, and Huseyin Topaloglu. 2014\.  Assortment optimization under variants of the nested logit model.  _Operations Research_ 62, 2 (2014), 250–273.
  * Désir et al. (2020) Antoine Désir, Vineet Goyal, Danny Segev, and Chun Ye. 2020\.  Constrained assortment optimization under the Markov chain–based choice model.  _Management Science_ 66, 2 (2020), 698–721.
  * Dütting et al. (2019) Paul Dütting, Tim Roughgarden, and Inbal Talgam-Cohen. 2019\.  Simple versus optimal contracts. In _Proceedings of the 2019 ACM Conference on Economics and Computation_. 369–387.
  * Feldman and Topaloglu (2017) Jacob B Feldman and Huseyin Topaloglu. 2017.  Revenue management under the Markov chain choice model.  _Operations Research_ 65, 5 (2017), 1322–1342.
  * Frankel (2014) Alexander Frankel. 2014\.  Aligned delegation.  _American Economic Review_ 104, 1 (2014), 66–83.
  * Goel et al. (2006) Ashish Goel, Sudipto Guha, and Kamesh Munagala. 2006\.  Asking the right questions: Model-driven optimization using probes. In _Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_. 203–212.
  * Hajiaghayi et al. (2023) MohammadTaghi Hajiaghayi, Keivan Rezaei, and Suho Shin. 2023\.  Multi-agent Delegated Search. In _Proceedings of the 2023 ACM Conference on Economics and Computation_. ACM.
  * Hartline (2013) Jason D Hartline. 2013\.  Mechanism design and approximation.  _Book draft. October_ 122 (2013), 1.
  * Hartline and Roughgarden (2009) Jason D Hartline and Tim Roughgarden. 2009.  Simple versus optimal mechanisms. In _Proceedings of the 10th ACM conference on Electronic commerce_. 225–234.
  * Holmstrom (1978) Bengt Robert Holmstrom. 1978\.  _On Incentives and Control in Organizations_.  Ph. D. Dissertation.
  * Immorlica et al. (2018) Nicole Immorlica, Brendan Lucier, Jieming Mao, Vasilis Syrgkanis, and Christos Tzamos. 2018.  Combinatorial Assortment Optimization. In _International Conference on Web and Internet Economics_. Springer, 218–231.
  * Kleinberg and Kleinberg (2018) Jon Kleinberg and Robert Kleinberg. 2018.  Delegated Search Approximates Efficient Search. In _Proceedings of the 2018 ACM Conference on Economics and Computation_. ACM, 287–302.
  * Kleiner (2023) Andreas Kleiner. 2023\.  Optimal Delegation in a Multidimensional World. In _Proceedings of the 2023 ACM Conference on Economics and Computation_. ACM.
  * Kovác and Mylovanov (2009) Eugen Kovác and Tymofiy Mylovanov. 2009.  Stochastic mechanisms in settings without monetary transfers: The regular case.  _Journal of Economic Theory_ 144, 4 (2009), 1373–1395.
  * Li et al. (2015) Guang Li, Paat Rusmevichientong, and Huseyin Topaloglu. 2015\.  The d-level nested logit model: Assortment and price optimization problems.  _Operations Research_ 63, 2 (2015), 325–342.
  * Martimort and Semenov (2006) David Martimort and Aggey Semenov. 2006.  Continuity in mechanism design without transfers.  _Economics Letters_ 93, 2 (2006), 182–189.
  * Mehta et al. (2020) Aranyak Mehta, Uri Nadav, Alexandros Psomas, and Aviad Rubinstein. 2020.  Hitting the high notes: Subset selection for maximizing expected order statistics.  _Advances in Neural Information Processing Systems_ 33 (2020), 15800–15810.
  * Melumad and Shibano (1991) Nahum D Melumad and Toshiyuki Shibano. 1991.  Communication in settings with no transfers.  _The RAND Journal of Economics_ (1991), 173–198.
  * Rusmevichientong et al. (2014) Paat Rusmevichientong, David Shmoys, Chaoxu Tong, and Huseyin Topaloglu. 2014.  Assortment optimization under the multinomial logit model with random choice parameters.  _Production and Operations Management_ 23, 11 (2014), 2023–2039.
  * Segev and Singla (2021) Danny Segev and Sahil Singla. 2021.  Efficient approximation schemes for stochastic probing and prophet problems. In _Proceedings of the 22nd ACM Conference on Economics and Computation_. 793–794.
  * Szalay (2005) Dezsö Szalay. 2005\.  The economics of clear advice and extreme options.  _The Review of Economic Studies_ 72, 4 (2005), 1173–1198.
  * Talluri and Van Ryzin (2004) Kalyan Talluri and Garrett Van Ryzin. 2004.  Revenue management under a general discrete choice model of consumer behavior.  _Management Science_ 50, 1 (2004), 15–33.

##  Appendix 0.A Supplementary materials

###  0.A.1 Proof of Theorem 4.2

To see that the problem is in NP, note that given an action set $S$, we may
compute the principal’s expected utility in polynomial time. Specifically, let
$S_{i}$ be the first $i$ elements of $S$, let
$\textsc{opt}_{i}(u)=\mathbb{E}[v_{g(S_{i},\mathbf{v})}~{}|~{}v_{g(S_{i},\mathbf{v})}+b_{g(S_{i},\mathbf{v})}=u]$
and $p_{i}(u)=\text{Pr}[v_{g(S_{i},\mathbf{v})}+b_{g(S_{i},\mathbf{v})}=u]$.
Both can be computed for all $u$ by a simple dynamic program, considering
$i=1,\ldots,n$. The utility of $S$ can then be computed using the law of total
expectation.

To show hardness, we will reduce from Integer Partition. An instance of this
problem is integers $c_{1},\ldots,c_{n}$. The goal is to find a subset
$S\subseteq[n]$ such that $\sum_{i\in
S}c_{i}=\tfrac{1}{2}\sum_{i=1}^{n}c_{i}$. Let $C=\sum_{i=1}^{n}c_{i}$, and
$c_{\max}=\max_{i}c_{i}$. Consider the following delegation instance, with
$n+1$ actions.

  * •

Actions $1,\ldots,n$ have bias $M^{2}(1-C/2M)$ for some $M$ (large, to be
chosen). Let $\delta$ be a number small enough to only matter for agent
tiebreaking (and which we will omit from all principal utility computations).
The value of action $i$ will be

    * *

(high realization) $1+2\delta$ with probability
$p_{i}=\tfrac{c_{i}}{M^{3}}-\tfrac{c_{i}^{2}}{2M^{4}(1-C/2M)}$

    * *

(low realization) $1$ with probability $q_{i}=\tfrac{c_{i}}{M}$

  * •

Action $n+1$ has value $0$ with probability $1/2$ and with probability $1/2$
takes value $M^{2}(1-C/2M)+1+\delta$. Action $n+1$ will have bias $0$.

First observe that any set of actions not containing action $n+1$ is
suboptimal. By a union bound, the utility from such a set is at most
$\sum_{i=1}^{n}(p_{i}+q_{i})\leq 2C/M$. The utility from taking action $n+1$
alone, meanwhile, is $M^{2}(1-C/2M)+1\geq 1$, which is at least $2C/M$ as long
as $M\geq 2C$. It follows that the principal’s problem is to pick which of
actions $1,\ldots,n$ to pick alongside $n+1$. Now consider the principal
utility from a set $T=S\cup\\{n+1\\}$ for some $S\subseteq[n]$. To compute the
principal’s utility, consider the following two events:

  * •

Let $\mathcal{E}_{1}$ be the event that at least one action in $S$ has a high
realization. In this event, the agent will choose such an action over $n+1$,
no matter the value of action $n+1$.

We can approximate the probability of this event using only first-order terms.
In more detail, this event has probability

$1-\prod_{i\in S}(1-p_{i})=\sum_{i\in
S}p_{i}-\sum_{k=2}^{|S|}(-1)^{k}\sum_{\begin{subarray}{c}S_{k}\subseteq S:\\\
|S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}p_{j}$

Call the second term on the right $C_{1}$. We can show that
$C_{1}\in[-\frac{4n^{2}c_{\max}^{2}}{M^{6}},\frac{4n^{2}c_{\max}^{2}}{M^{6}}]$:

$\displaystyle|C_{1}|$
$\displaystyle=\Bigg{|}\sum_{k=2}^{|S|}(-1)^{k}\sum_{\begin{subarray}{c}S_{k}\subseteq
S:\\\ |S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}p_{j}\Bigg{|}$
$\displaystyle\leq\sum_{k=2}^{n}\sum_{\begin{subarray}{c}S_{k}\subseteq[n]:\\\
|S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}p_{j}$
$\displaystyle\leq\sum_{k=2}^{n}\binom{n}{k}\left(\frac{c_{\max}}{M^{3}}\right)^{k}$
$\displaystyle\leq\sum_{k=2}^{n}\left(\frac{ne}{k}\right)^{k}\left(\frac{c_{\max}}{M^{3}}\right)^{k}$
$\displaystyle\leq 2\sum_{k=2}^{n}\left(\frac{nc_{\max}}{M^{3}}\right)^{k}$
$\displaystyle\leq
2\sum_{k=2}^{\infty}\left(\frac{nc_{\max}}{M^{3}}\right)^{k}$
$\displaystyle=\frac{2n^{2}c_{\max}^{2}}{M^{4}}\sum_{k=0}^{\infty}\left(\frac{nc_{\max}}{M^{3}}\right)^{k}$
$\displaystyle=\frac{2n^{2}c_{\max}^{2}}{M^{6}}\frac{1}{1-\tfrac{nc_{\max}}{M^{3}}}.$

As long as $nc_{\max}/M^{3}\leq 1/2$, we have the desired upper bound.

  * •

Let $\mathcal{E}_{2}$ be the event that no action in $S$ has a high
realization, and at least one has a low realization. Then this event has
probability:

$\displaystyle\text{Pr}[\overline{\mathcal{E}_{1}}]-\prod_{i\in
S}(1-p_{i}-q_{i})$ $\displaystyle=1-\sum_{i\in S}p_{i}+C_{1}-\prod_{i\in
S}(1-p_{i}-q_{i})$ $\displaystyle=1-\sum_{i\in S}p_{i}+C_{1}-1+\sum_{i\in
S}(p_{i}+q_{i})-\sum_{i\neq j\in
S}(p_{i}+q_{i})(p_{j}+q_{j})+\sum_{k=3}^{|S|}(-1)^{k}\sum_{\begin{subarray}{c}S_{k}\subseteq
S:\\\ |S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}(p_{j}+q_{j})$
$\displaystyle=C_{1}+\sum_{i\in S}q_{i}-\sum_{i\neq j\in
S}(p_{i}+q_{i})(p_{j}+q_{j})+\sum_{k=3}^{|S|}(-1)^{k}\sum_{\begin{subarray}{c}S_{k}\subseteq
S:\\\ |S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}(p_{j}+q_{j}).$

Call the last term $C_{2}$. A similar argument to the one for $C_{1}$ shows
that
$C_{2}\in[-\frac{16n^{3}c_{\max}^{3}}{M^{3}},\frac{16n^{3}c_{\max}^{3}}{M^{3}}]$.
We include it below for completeness.

$\displaystyle|C_{2}|$
$\displaystyle=\Bigg{|}\sum_{k=3}^{|S|}(-1)^{k}\sum_{\begin{subarray}{c}S_{k}\subseteq
S:\\\ |S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}(p_{j}+q_{j})\Bigg{|}$
$\displaystyle\leq\sum_{k=3}^{|S|}\sum_{\begin{subarray}{c}S_{k}\subseteq
S:\\\ |S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}(p_{j}+q_{j})$
$\displaystyle\leq\sum_{k=3}^{n}\sum_{\begin{subarray}{c}S_{k}\subseteq S:\\\
|S_{k}|=k\end{subarray}}\prod_{j\in S_{k}}(p_{j}+q_{j})$
$\displaystyle\leq\sum_{k=3}^{n}\binom{n}{k}\left(\frac{2c_{\max}}{M}\right)^{k}$
$\displaystyle\leq\sum_{k=3}^{n}\left(\frac{ne}{k}\right)^{k}\left(\frac{2c_{\max}}{M}\right)^{k}$
$\displaystyle\leq\sum_{k=3}^{n}\left(\frac{2nc_{\max}}{M}\right)^{k}$
$\displaystyle\leq\frac{8n^{3}c_{\max}^{3}}{M^{3}}\frac{1}{1-\tfrac{2nc_{\max}}{M}}$

This implies the desired bound as long as $M\geq 4nc_{\max}$.

The third term above can also be simplified:

$\sum_{i\neq j\in S}(p_{i}+q_{i})(p_{j}+q_{j})=\sum_{i\neq j\in
S}p_{i}p_{j}+2\sum_{i\neq j\in S}p_{i}q_{j}+\sum_{i\neq j\in S}q_{i}q_{j}.$

Call the first two terms above $C_{3}$. Since for any $i$, $0\leq p_{i}\leq
c_{\max}/M^{3}$ and $0\leq q_{i}\leq c_{\max}$, we have
$C_{3}\in[0,\frac{3n^{2}c_{\max}}{M^{4}}]$. We therefore have
$\text{Pr}[\mathcal{E}_{2}]=\sum_{i\in S}q_{i}-\sum_{i\neq j\in
S}q_{i}q_{j}+C_{1}+C_{2}-C_{3}$.

#### Analyzing the Principal’s Utility

Given actions $S$, we can write the principal’s utility as:

$\frac{1}{2}\left((1+2\delta)\text{Pr}[\mathcal{E}_{1}]+(M^{2}(1-C/2M)+1+\delta)\text{Pr}[\overline{\mathcal{E}_{1}}]\right)+\frac{1}{2}(\text{Pr}[\mathcal{E}_{2}]+(1+2\delta)\text{Pr}[\mathcal{E}_{1}]).$

Taking $\delta\rightarrow 0$, we obtain:

$\displaystyle\frac{1}{2}\left(\text{Pr}[\mathcal{E}_{1}]+(M^{2}(1-C/2M)+1)\text{Pr}[\overline{\mathcal{E}_{1}}]\right)+\frac{1}{2}(\text{Pr}[\mathcal{E}_{2}]+\text{Pr}[\mathcal{E}_{1}]).$
$\displaystyle\quad\quad\quad\quad=\frac{1}{2}(M^{2}(1-C/2M)+1)+\frac{1}{2}(\text{Pr}[\mathcal{E}_{2}]+\text{Pr}[\mathcal{E}_{1}]-M^{2}(1-C/2M)\text{Pr}[\mathcal{E}_{1}])$
$\displaystyle\quad\quad\quad\quad=\frac{1}{2}(M^{2}(1-C/2M)+1)+\frac{1}{2}(\text{Pr}[\mathcal{E}_{2}]-M^{2}(1-C/2M)\text{Pr}[\mathcal{E}_{1}])+\text{Pr}[\mathcal{E}_{1}]/2.$

The first term does not depend on $S$, and the last term will turn out to be
negligibly small. We next analyze the middle term, leaving out $C_{1}$,
$C_{2}$, and $C_{3}$ for the moment.

$\displaystyle\text{Pr}[\mathcal{E}_{2}]-M^{2}(1-C/2M)\text{Pr}[\mathcal{E}_{1}]$
$\displaystyle\approx\sum_{i\in S}\frac{c_{i}}{M}-\sum_{i\neq j\in
S}\frac{c_{i}c_{j}}{M^{2}}-\left(1-\frac{C}{2M}\right)\left(\sum_{i\in
S}\frac{c_{i}}{M}-\sum_{i\in
S}\frac{c_{i}^{2}}{2M^{2}(1-\tfrac{C}{2M})}\right)$
$\displaystyle=\frac{C}{2M}\sum_{i\in S}\frac{c_{i}}{M}-\sum_{i\neq j\in
S}\frac{c_{i}c_{j}}{M^{2}}-\sum_{i\in S}\frac{c_{i}^{2}}{2M^{2}}$
$\displaystyle=\frac{1}{2M^{2}}\left(\sum_{i\in S}c_{i}+\sum_{j\notin
S}c_{j}\right)\sum_{i\in S}c_{i}-\sum_{i\neq j\in
S}\frac{c_{i}c_{j}}{M^{2}}-\sum_{i\in S}\frac{c_{i}^{2}}{2M^{2}}$
$\displaystyle=\frac{1}{2M^{2}}\left(\sum_{i\in
S}c_{i}\right)\left(\sum_{j\notin S}c_{i}\right).$

This latter expression takes value $C^{2}/8M^{2}$ if the integers can be
exactly partitioned, and value at most
$(C^{2}/4-1)/2M^{2}=C^{2}/8M^{2}-1/2M^{2}$ otherwise. Now we can take $C_{1}$,
$C_{2}$, $C_{3}$, and $\text{Pr}[\mathcal{E}_{1}]/2$ into account.
Specifically, we can write:

$\displaystyle\Bigg{|}\frac{1}{2}(\text{Pr}[\mathcal{E}_{2}]-M^{2}(1-C/2M)\text{Pr}[\mathcal{E}_{1}])+\text{Pr}[\mathcal{E}_{1}]/2-\frac{1}{2M^{2}}\left(\sum_{i\in
S}c_{i}\right)\left(\sum_{j\notin S}c_{i}\right)\Bigg{|}$
$\displaystyle\quad\quad\quad\quad=\Big{|}\frac{1}{2}(C_{1}+C_{2}-C_{3})+\frac{M^{2}}{2}(1-C/2M)C_{1}+\text{Pr}[\mathcal{E}_{1}]/2\Big{|}$
$\displaystyle\quad\quad\quad\quad\leq\frac{1}{2}\left(\frac{4n^{2}c_{\max}^{2}}{M^{6}}+\frac{16n^{3}c_{\max}^{3}}{M^{3}}+\frac{3n^{2}c_{\max}}{M^{4}}\right)+\frac{M^{2}}{2}(1-C/2M)\frac{4n^{2}c_{\max}^{2}}{M^{6}}+\frac{nc_{\max}}{2M^{3}}$
$\displaystyle\quad\quad\quad\quad\leq\frac{16n^{3}c_{\max}^{3}}{M^{3}}.$

The first inequality follows from applying the triangle inequality, along with
our existing bounds on $C_{1}$, $C_{2}$, and $C_{3}$ and the fact that
$\text{Pr}[\mathcal{E}_{1}]\leq\frac{nc_{\max}}{M^{3}}$ by a union bound. As
long as $M\geq 128n^{3}c_{\max}^{3}$, we will have that
$16n^{3}c_{\max}^{3}/M^{3}\leq 1/8M^{2}$. We can therefore solve our Integer
Partition instance by asking if our constructed instance of delegation has
value at least $(M^{2}(1-C/2M)+1)/2+C^{2}/8M^{2}-1/8M^{2}$. Any solution that
exactly partitions the integers will obtain at least this value, and any
solution that fails to do so will have objective value at most
$(M^{2}(1-C/2M)+1)/2+C^{2}/8M^{2}-1/2M^{2}+1/8M^{2}\leq(M^{2}(1-C/2M)+1)/2+C^{2}/8M^{2}-1/8M^{2}$.

###  0.A.2 Proof of Theorem 6.2

In this appendix, we show that the logarithmic approximation upper bond of
Theorem 6.1 is tight, up to a constant factor. That is, no threshold algorithm
can perform better than $\log p_{min}^{-1}$. To prove the tightness of our
analysis in Section 6, we construct an infinite family of instances.

For any $k\geq 2$, consider an instance with $n=2k-1$ actions. The correlated
distribution has $m=2^{k}-1$ value profile realizations. We construct a value
matrix where each row correspond to an action and each column corresponds to a
realization. Therefore, the value at cell $V_{i,j}$ gives the value of action
$i$ at realization value profile $j$. The distribution over value profiles
simply selects and value realization uniformly at random.

$\displaystyle V=$ (5)
$\displaystyle\left[\begin{array}[]{c|c|c|c|c|c|c|c|c|c|c}2^{k}&&&&&&&&&&\\\
\hline\cr 2^{k-1}+2\epsilon&&&&&&&&&&\\\ \hline\cr&2^{k-1}&2^{k-1}&&&&&&&&\\\
\hline\cr 2^{k-2}+3\epsilon&2^{k-2}+3\epsilon&2^{k-2}+3\epsilon&&&&&&&&\\\
\hline\cr&&&2^{k-2}&2^{k-2}&2^{k-2}&2^{k-2}&&&&\\\ \hline\cr
2^{k-3}+4\epsilon&2^{k-3}+4\epsilon&2^{k-3}+4\epsilon&2^{k-3}+4\epsilon&2^{k-3}+4\epsilon&2^{k-3}+4\epsilon&2^{k-3}+4\epsilon&&&&\\\
\hline\cr\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\vdots&\ddots&&&\\\
\hline\cr
2+O(k\epsilon)&2+O(k\epsilon)&2+O(k\epsilon)&2+O(k\epsilon)&2+O(k\epsilon)&2+O(k\epsilon)&2+O(k\epsilon)&\dots&&&\\\
\hline\cr&&&&&&&\dots&\makebox[0.0pt][l]{$\smash{\underbrace{\phantom{\begin{matrix}2&\dots&2\end{matrix}}}_{\text{$2^{k-1}$}}}$}2&\dots&2\end{array}\right]$
(15)

Note that all the empty entries in the above matrix are zero, and are removed
to make the structure of the matrix more apparent. Also, every solution
corresponds to eliminating a a set of rows. For each realization (column) the
row with maximum agent utility is selected. The optimal solution is to select
set of odd actions (with size $k$). The colored entries indicate
(realization,action) pairs that contribute to the optimal principal’s utility
($OPT$). The optimal utility is equally divided between the odd rows, leaving
$2^{k}$ for each one: the first row has $2^{k}$ in the first column, the third
row has $2^{k-1}$ in columns 2 and 3, the fifth row has $2^{k-2}$ over the
next $4$ columns and so on. In the example, the even actions are constructed
to lower the principal’s utility whenever they are included in a threshold
solution. In every state (column), we divide the colored utility by 2 to find
the utility of the next row, and keep dividing by 2 to complete the subsequent
even rows. The $\epsilon$ terms are added to break the ties and are of little
importance.

Next, we define the bias: we set $b_{1}=0$, and the rest of actions have the
following bias:

$b_{2i+1}=\sum_{j=1}^{i}2^{k-j},\quad b_{2i}=b_{2i+1}-\epsilon,\qquad
i\in\\{1,...,k-1\\}.$ (16)

Now that all the parameters are set, it is easy to verify that given the set
of odd actions (rows), the agent will indeed pick the colored entries. This
generates the optimal utility, since it is optimal in every single
realization. Since each value profiled is realized with probability
$\frac{1}{m}$ the optimal expected utility is equal to:

$OPT=\frac{k\times 2^{k}}{m}.$

However, the best threshold solution in the constructed instance is to allow
the entire set of actions ($\Omega$). To see this, assume that the principal
allows actions with bias less than or equal to $b_{2\ell-1}$ for some
$\ell\leq k$. (Thresholds set at even-indexed actions can be easily shown to
be suboptimal.) Note that every even action is preferred by the agent to any
other action with less bias. Therefore, the only actions chosen by the agent
are $2\ell-1$ or $2\ell-2$ In this case, the principal will get utility of
$2^{k-\ell+1}+O(\ell\epsilon)$ from the first $2^{\ell}-1$ states, and zero
from the remaining states.

Observe that the overall utility $(2^{\ell}-1)\times 2^{k-\ell+1}$ is an
increasing function in $\ell$, meaning that the best strategy for the
principal is to not limit the agent. In this case, the agent will pick the
penultimate action in the first half of columns, and the last action for the
second half, generating utility of (almost) 2 for principal in every state.
More precisely, we have:

$APX=2+O(k\epsilon).$

We get the desired lower bound by dividing the above objectives:

$\frac{OPT}{APX}=\frac{k\times
2^{k}}{2n+O(nk\epsilon)}\cong\frac{k}{2}\cong\frac{\log{n}}{2}.$

###### Example 6

In order to make sure that the above construction is clear, here we present
the full matrices for the case of $k=3$, which translates into $n=5$ actions
and $m=7$ realizations. The value matrix in this case is

$V=\left[\begin{array}[]{c|c|c|c|c|c|c}8&0&0&0&0&0&0\\\ \hline\cr
4+2\epsilon&0&0&0&0&0&0\\\ \hline\cr 0&4&4&0&0&0&0\\\ \hline\cr
2+3\epsilon&2+3\epsilon&2+3\epsilon&0&0&0&0\\\ \hline\cr
0&0&0&2&2&2&2\end{array}\right]$

Calculating the bias in (16) results in:

$\mathbf{b}=(0,4-\epsilon,4,6-\epsilon,6)$

It is clear that the value matrix $V$ is non-negative, and the agent’s utility
$V+B$ will be:

$V+B=\left[\begin{array}[]{c|c|c|c|c|c|c}8&0&0&0&0&0&0\\\ \hline\cr
8+\epsilon&4-\epsilon&4-\epsilon&4-\epsilon&4-\epsilon&4-\epsilon&4-\epsilon\\\
\hline\cr 4&8&8&4&4&4&4\\\ \hline\cr
8+2\epsilon&8+2\epsilon&8+2\epsilon&6-\epsilon&6-\epsilon&6-\epsilon&6-\epsilon\\\
\hline\cr 6&6&6&8&8&8&8\end{array}\right]$

Observe that $OPT=24/7$ by the set of odd actions $\\{1,3,5\\}$, while
$APX=(14+9\epsilon)/7$ from the entire set of actions
$\Omega=\\{1,2,3,4,5\\}$.

###  0.A.3 Proof of Theorem 6.3

###### Proof

We give a reduction from the bounded degree vertex cover problem, i.e., the
vertex cover problem on graphs with degree at most $B$ (constant). This
problem is known to be APX-hard Clementi and Trevisan (1999). Consider an
instance of the bounded degree vertex cover problem
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$ with ${\tilde{n}}$ nodes and
${\tilde{m}}$ edges (where ${\tilde{m}}\leq
B\cdot{\tilde{n}}/2={O}({\tilde{n}})$).444To distinguish between the
parameters of the vertex cover instance and the delegation instance, we use
tilde ($\sim$) for the graph instance.

We construct an instance of the delegation problem with ${\tilde{n}}+1$
actions with action $a_{i}$ corresponding to node $i$ and an additional
“default” action $a_{0}$. All actions have $0$ bias apart from $a_{0}$ which
has bias $-1$. The correlated distribution of the actions values is defined as
follows: we pick an edge $e=\\{i,j\\}$ or some node $i$ uniformly at random,
i.e., each element with probability $({\tilde{m}}+{\tilde{n}})^{-1}$

If we picked some edge $e=\\{i,j\\}$ then we assign value $5$ to actions
$a_{i}$ and $a_{j}$, $2$ to the default action $a_{0}$, and $0$ for all other
actions. If we picked a node $i$ we assign value $2$ to $a_{i}$ and $a_{0}$
(default action) and $0$ for all other actions.

We claim that the optimal solution of the delegation problem produces a
utility of $(5{\tilde{m}}+3{\tilde{n}}-{\tilde{k}})/({\tilde{m}}+{\tilde{n}})$
for the principal, where ${\tilde{k}}$ is the size of the smallest vertex
cover of ${\mathcal{G}}$. To see this, first note that any solution
${\mathcal{S}}\subseteq{\mathcal{V}}$ can be improved by including $a_{0}$,
since $a_{0}$ has a negative bias. Any time the agent would choose $a_{0}$, it
is the optimal choice for the principal as well. We therefore only consider
solutions containing $a_{0}$.

Now if ${\mathcal{S}}$ is a vertex cover of ${\mathcal{G}}$ with
$\lvert{\mathcal{S}}\rvert={\tilde{k}}$, consider the corresponding delegation
set where the principal allows actions
$\\{a_{i}:i\in{\mathcal{S}}\\}\cup\\{a_{0}\\}$. If we generate the values by
picking an edge, the agent will pick the action corresponding to one end of
that edge (one is guaranteed to be in the cover ${\mathcal{S}}$) to get a
utility of $5$ compared to $2-1$ achievable from the default action. This
choice will also generate utility of $5$ for the principal, which makes
$5{\tilde{m}}$ in total. If the utility is generated by picking node $i$ the
agent will pick action $a_{i}$ which generates the utility of $2$ for both
principal and agent. This will make $2{\tilde{k}}$ in total. Finally, if the
utilities are generated using some node
$i\in{\mathcal{V}}\backslash{\mathcal{S}}$ the agent picks the default action
which generates a utility of $2-1$ for the agent but $2+1$ for the principal.
This will give $3({\tilde{n}}-{\tilde{k}})$ in total. As a result the
principal utility in expectation is
$(5{\tilde{m}}+3{\tilde{n}}-{\tilde{k}})/({\tilde{m}}+{\tilde{n}})$.

For the converse, consider an optimal solution $A$ to the delegation problem.
We show that the nodes corresponding to the actions in $A$ (excluding the
default action) induce a vertex cover; otherwise the solution can be improved.
Assume that there exists an edge $e=\\{i,j\\}$ where neither $a_{i}$ nor
$a_{j}$ is allowed in $A$. If we add action $a_{i}$ to $A$, the principal gets
a utility of $5$ if the utilities are generated from pick edge $e$, compared
to current utility of $3$ from the default action. On the other hand, the
utility of the principal decreases from $3$ to $2$ if the values are generated
by action $i$. So the total utility of $A\cup\\{a_{i}\\}$ is more than $A$
which contradicts the optimality of $A$. Therefore $A$ should be a vertex
cover (plus default action). This in turn implies that the utility is at most
$(5{\tilde{m}}+3{\tilde{n}}-{\tilde{k}})/({\tilde{m}}+{\tilde{n}})$ where
${\tilde{k}}$ is the size of the minimum vertex cover.

Since ${\tilde{m}}=\Theta({\tilde{n}})$ and the minimum vertex cover has size
at least ${\tilde{m}}/B=\Omega({\tilde{n}})$, a constant factor gap in the
bounded degree vertex cover problem translates into a constant factor gap in
the optimal solution of the delegation problem, which yields the desired
hardness result.