Delegated Online Search

1 Introduction

The study of delegation problems is a prominent area with numerous applications. There are two parties - a decision maker (called principal) P and an agent A. n actions or options are available to P. Each option has a utility for P and a (possibly different) utility for A, which are drawn from a known distribution D. Instead of inspecting options herself, P delegates the search for a good option to A. A sees all realized utility values and sends a signal to P. Based on this signal (and D), P chooses an option. Both parties play this game in order to maximize their respective utility from the chosen option.

Many interesting applications can be captured within this framework. For example, consider a company that is trying to hire an expert in a critical area. Instead of searching the market, the company delegates the search to a head-hunting agency that searches the market for suitable candidates. Alternatively, consider an investor, who hires a financial consultant to seek out suitable investment opportunities. Clearly, principal and agent might not always have aligned preferences. While the investor might prefer investments with high interest rates, the financial consultant prefers selling the products for which he gets a provision.

In applications such as searching for job candidates or financial investments, availability of options often changes over time, and the pair of agents needs to solve a stopping problem. For example, many lucrative financial investment opportunities arise only within short notice and expire quickly. Therefore, a consultant has to decide whether or not to recommend an investment without exactly knowing what future investment options might become available. Here A faces an online search problem, in which the n options are realized in a sequential fashion. After seeing the realization of option i, he has to decide whether to propose the option to P or discard it. If the option is proposed, P decides to accept or reject this option and the process ends. Otherwise, the process continues with option i + 1.

In the study of delegation problems, P usually has commitment power, i.e., P specifies in advance her decision for each possible signal, taking into account the subsequent best response of A. This is reasonable in many applications (e.g., an investor can initially restrict the investment options she is interested in, or the company fixes in advance the required qualifications for the new employee). Interestingly, although P commits and restricts herself in advance, this behavior is usually in her favor. The induced best response of A can lead to better utility for P than in any equilibrium, where both parties mutually best respond. Using a revelation-principle style argument, the communication between P and A can be reduced to A revealing the utilities of a single option and P deciding to accept or reject that option (for a discussion, see, e.g. [Kleinberg and Kleinberg, 2018]).

The combination of online search and delegation has been examined before, albeit from a purely technical angle. Kleinberg and Kleinberg [2018] designed approximation algorithms for delegation, showing that P can obtain a constantfactor approximation to the expected utility of her best option in hindsight. Their algorithms heavily rely on techniques and tools developed in the domain of prophet inequalities. However, they are applied to an offline delegation problem. Instead, we consider the natural extension of [Kleinberg and Kleinberg, 2018] to online search. Interestingly, we exhibit a notable contrast - in online delegation a constant-factor approximation might be impossible to achieve. In fact, the approximation ratio can be as low as O(1/n), and this can always be achieved. Motivated by this sharp contrast, we provide a fine-grained analysis based on two natural problem parameters: (1) the discrepancy of utility for the agent, and (2) the misalignment of agent and principal utilities.

1.1 Model

We study online delegation between principal P and agent A in (up to) n rounds. In every round i, an option is drawn independently from a known distribution Di with finite support Ωi of size si. We denote the options of Di by Ωi = {ωi1, . . . , ωi,si } and the random variable of the draw by Oi. For every i ∈ [n] and j ∈ [si], the option ωij has probability pij to be drawn fromDi. If this option is proposed by A and chosen by P, then A has utility aij ≥ 0 and P utility bij ≥ 0.

We assume that P has commitment power. Before the start of the game, she commits to an action scheme φ with a value φij ∈ [0, 1] for each option ωij. φij is the probability that P accepts option ωij when it is proposed by A in round i. For a deterministic scheme with all φij ∈ {0, 1}, we define the sets Ei = {ωij | φij = 1} of acceptable options in each round i.

In contrast to P, A gets to see the n random draws from the distributions in an online fashion. He decides after each round whether he proposes the current option Oi to P or not. If he decides to propose it, then P sees the option and decides based on φ whether or not she accepts it. If P accepts, the utility values of the option are realized; if not, both players get utility 0. In either case, the game ends after P decides. Both players strive to maximize their expected utility.

Initially, both players know the distribution Di for every round i ∈ [n]. The sequence of actions then is as follows: (1) P decides φ and communicates this to A; (2) in each round i, A sees Oi ∼ Di and irrevocably decides to propose or discard Oi; (3) when A decides to propose some option Oi = ωij, then P accepts it with probability φij , and the game ends. 1

A knows the distributions and the action scheme φ of upcoming rounds which determines his expected utility from proposed options. Hence, A essentially faces an online stopping problem that can be solved via backwards induction. We can assume without loss of generality that all decisions (not) to propose an option by A are deterministic: If the expected utility from the realization in the current round is greater than the expected utility obtained in the remaining rounds, propose the current option (otherwise do not). To avoid technicalities, we assume that A breaks ties in favor of P.

Our goal is to design action schemes φ with high expected utility for P. We compare the expected utility to the one in the non-delegated (online) problem, where P searches through the n realized options herself. The latter is a classic stopping problem, for which the expected utilities of optimal online and offline search differ by at most a factor of 2 (due to the basic prophet inequality [Krengel and Sucheston, 1977; Krengel and Sucheston, 1978]).

1 In the full version [Braun et al., 2022], we also consider a variant with k ≥ 1 proposals. Here the game continues until P accepts or after P has rejected k different options. Action schemes become more complicated and must rely on the history of rejected options.

We also analyze scenarios with oblivious and semioblivious proposals. In both these scenarios, A reveals only the utility value bij for P when proposing an option (but not his own value aij). In contrast, when P gets to see the utility values of both agents, we term this conscious proposals. The difference between semi-oblivious and (fully) oblivious scenarios lies in the prior knowledge of P. In the semi-oblivious scenario, P is fully aware of the distributions, including all potential utility values aij for A. In the oblivious scenario, P initially observes the probabilities of all options along with her utility values bij, but the values aij of A remain unknown to P throughout. In the scenarios with restricted discrepancy (in Section 3), we assume P is aware of the bound α = maxi,j aij / mini,j aij .

Example 1. We discuss a simple example to illustrate the definitions. We consider deterministic strategies by P and conscious proposals. There are two rounds with the options distributed according to Table 1. For the benchmark, we assume that P can see and choose the options herself. The best option is ω12. If this is not realized in round 1, the option realized in round 2 is the best choice. Note that this optimal choice for P can be executed even in an online scenario, where she first sees round 1 and gets to see round 2 only after deciding about round 1. The expected utility of this best (online) choice for P is 5.

Now in the delegated scenario, suppose P accepts option ω22. Then A would always wait for round 2 and hope for a realization of ω22, even if ω21 would not be accepted by P. Hence, accepting ω22 leads to an expected utility for P of at most 4. In contrast, the optimal decision scheme for P is to accept only ω12 and ω21 with an expected utility of 4.25. For the (semi-)oblivious scenario, P cannot distinguish the options in round 2, and her expected utility is at most 4.

Clearly, P has to strike a careful balance between (1) accepting a sufficient number of high-profit options to obtain a high expected utility overall and (2) rejecting options to motivate A to propose better options for P in earlier rounds. ♦

1.2 Contribution and Outline

In Section 2 we show that the worst-case approximation ratio for online delegation is Θ(1/n) and this is tight. Intuitively, A waits too long and forgoes many profitable options for P. P can only force A to propose earlier if she refuses to accept later options - this, however, also hurts the utility of P. The instances require a ratio of maximum and minimum utility values for A that is in the order of nΘ(n) . We further show that the bounds extend to more general variants in which (1) A has a lookahead of k rounds, or (2) A can propose up to k options, resulting in tight approximation ratios of Θ(k/n). Note that all impossibility results in this paper apply already for IID instances, while all algorithmic results apply for general instances.

In Section 3, we examine the effect of the discrepancy of utility for A using the ratio α of maximum and minimum utility values. We obtain an Ω(log log α/ log α)-approximation of the optimal (online) search for P. This result is tight. The algorithm limits the acceptable options of P, partitions them into different bins, and then restricts A's search space to the best possible bin for P. The challenge is to design a profitable set of options inside a bin that should be accepted by P without giving A an incentive to forgo proposing many of them. Our algorithm shows that P can obtain a good approximation even if differences in utility of A are polynomial in n.

Additionally, we consider the more challenging oblivious scenario in which P does not get to see the agent's utility of the proposed option. Our algorithm for this scenario achieves an Ω(1/α)-approximation. This is contrasted with a set of instances for which no action scheme can extract more than an O(1/α)-approximation. We study the semi-oblivious scenario in the full version [Braun et al., 2022]. In this scenario, P has a priori knowledge of the prior, but still does not see the agent's utility for proposed options. For this setting, our algorithm achieves an Ω(1/(√α log α))-approximation, and in general O(1/√α) is best-possible. The results highlight the effect of hiding A's utilities from P (in the proposal, or in the proposal and the prior) - the achievable approximation ratios increase from logarithmic to polynomial ratios in α.

In Section 4, we consider the misalignment of agent and principal utilities via a parameter β ≥ 1, which is the smallest value such that all utilities of P and A are related by a factor in [1/β, β]. Limited misalignment also leads to improved approximation results for P. We show an Ω(1/ logβ)-approximation of the optimal (online) search for P. Moreover, every algorithm must have a ratio in O(log logβ/ logβ). For the agent-oblivious variant, we obtain an Ω(1/β)-approximation, whereas every algorithm must have a ratio in O(1/√β).

Additional descriptions, pseudocode for our algorithms as well as all missing proofs can be found in the full version of this paper [Braun et al., 2022].

1.3 RelatedWork

Holmstrom [1977; 1984] initiated the study of delegation as a bilevel optimization between an uninformed principal and a privately informed agent. The principal delegates the decision to the agent who himself has an interest in the choice of decision. Since then, there have been numerous works on various aspects of delegation. For example, [Melumad and Shibano, 1991; Alonso and Matouschek, 2008] studied the impact of (mis)alignment of the agent's and the principal's interests on the optimal delegation sets. Armstrong and Vickers [2010] studied the delegation problem over discrete sets of random cardinality with elements drawn from some distribution. They identify sufficient conditions for the search problem to have an optimal solution.

A similar model to ours was considered in computer science by Kleinberg and Kleinberg [2018], where the option set searched by the agent consists of n IID draws from a known distribution. They show constant-factor approximations of the optimal expected principal utility when performing the search herself rather than delegating it to the agent. For their analysis, they rely on tools from online stopping theory. The key difference between their work and our paper is that - albeit using tools from online optimization - they study an offline problem while we focus on an online version.

Bechtel and Dughmi [2021] recently extended this line of research by combining delegation with stochastic probing. Here a subset of elements can be observed by the agent (subject to some constraints), and several options can be chosen (subject to a different set of constraints). Similarly, Bechtel et al. [2022] study connections between delegation and a generalized Pandora's Box problem.

A related but different area is contract theory, which considers principal-agent settings with uncertainty and monetary transfers. An early formalization was introduced by Grossmann and Hart [1983]. Computational aspects of this problem are recently starting to attract interest, see, e.g., Duetting et al. [2019; 2020] and earlier work (on a slightly different model) [Babaioff et al., 2012; Babaioff and Winter, 2014].

The study of persuasion, another model of strategic communication, has gained a lot of traction at the intersection between economics and computation in recent years. Here, the informed party (the "sender") is the one with commitment power, trying to influence the behavior of the uninformed agent (the "receiver"). Persuasion has proven to be a popular topic in AI. Castiglioni et al. [2022] studied Bayesian posted price auctions where buyers arrive sequentially and receive signals from the revenue maximizing seller. Moreover, signaling may be used in other settings, e.g., persuading voters [Castiglioni et al., 2020a; Castiglioni and Gatti, 2021], or for reducing social cost in congestion games with uncertain delays [Castiglioni et al., 2021a; Griesbach et al., 2022]. Closer to our paper is the study of persuasion in the context of stopping problems [Hahn et al., 2020b; Hahn et al., 2020a]. These works study persuasion problems in a prophet inequality [Hahn et al., 2020a] as well as in a secretary setting [Hahn et al., 2020b].

Other notable algorithmic results on persuasion problems concern optimal policies, hardness, and approximation algorithms in the general case [Dughmi and Xu, 2016] as well as in different variations, e.g., with multiple receivers [Babichenko and Barman, 2017; Badanidiyuru et al., 2018; Dughmi and Xu, 2017; Rubinstein, 2017; Xu, 2020], with limited communication complexity [Dughmi et al., 2016; Gradwohl et al., 2021], or relations to online learning [Castiglioni et al., 2020b; Castiglioni et al., 2021b; Zu et al., 2021]

2 Impossibility

2.1 A Tight Bound

As a first simple observation, note that P can always achieve an n-approximation with a deterministic action scheme, even in with oblivious proposals. P accepts exactly all options in a single round i∗ with optimal expected utility, i.e., Ei∗ = {ωi∗ ,j | j ∈ [si∗]} for i∗ = argmaxi∈[n] E[bij], and Ej = ∅ otherwise. This motivates A to always propose the option from round i∗ , and P gets expected utility E[bi∗ ,j]. By a union bound, the optimal utility from searching through all options herself is upper bounded by E [∑i bij ] ≤ n · E[bi∗ ,j ].

Proposition 1. For online delegation there is a deterministic action scheme φ such that P obtains at least a 1/napproximation of the expected utility for optimal (online) search.

We show a matching impossibility result, even in the IID setting with Di = D for all rounds i ∈ [n], and when P gets to see the full utility pair of any proposed option. There are instances in which P suffers a deterioration in the order of Θ(n) over the expected utility achieved by searching through the options herself.

For the proof, consider the following class of instances. The distribution D can be cast as an independent composition, i.e., we independently draw the utility values for P and A. For P there are two possibilities, either utility 1 with probability 1/n, or utility 0 with probability 1-1/n. For A, there are n possibilities with agent utility of n4ℓ , for ℓ = 1, . . . , n, where each one has probability 1/n. In combination, we can view D as a distribution over j = 1, . . . , 2n options. Options ωj for j = 1, . . . , n have probability 1/n2 and utilities (bj, aj) = (1, n4j ), for j = n + 1, . . . , 2n they have probability 1/n - 1/n2 and utilities (bj , aj ) = (0, n4(j-n) ).

Theorem 1. There is a class of instances of online delegation in the IID setting, in which every action scheme φ obtains at most an O(1/n)-approximation of the expected utility for optimal (online) search.

Proof. For simplicity, we first show the result for schemes φ with φij = 0 for all rounds i ∈ [n] and all j = n+1, . . . , 2n. In the end of the proof we discuss why this can be assumed for an optimal scheme.

Since all options j ∈ [n] have the same utility for P, she wants to accept one of them as soon as it appears. If she searches through the options herself, the probability that there is an option of value 1 is 1 - (1 - 1/n)n ≥ 1 - 1/e. Her expected utility is a constant. In contrast, when delegating the search to A, the drastic utility increase motivates him to wait for the latest round in which a better option is still acceptable by P. As a result, A waits too long, and removing acceptable options in later rounds does not remedy this problem for P.

More formally, interpret an optimal scheme φ as an n × n matrix, for rounds i ∈ [n] and options j ∈ [n]. We outline some adjustments that preserve the optimality of matrix φ.

Consider the set S of all entries with φij ≤ 1/n. For each (i, j) ∈ S, the probability that option j is realized in round i is 1/n2 . When it gets proposed by A, then it is accepted by P with probability at most 1/n. By a union bound, the utility obtained from all these options is at most |S|/n2 ·1/n ≤ 1/n.

Suppose we change the scheme by decreasing φij to 0 for each (i, j) ∈ S. Then each entry in φ is either 0 or at least 1/n. If A makes the same proposals as before, the change decreases the utility of P by at most 1/n. Then again, in the new scheme A can have an incentive to propose other options in earlier rounds. Since all options with φij ̸= 0 have utility 1 for P, this only leads to an increase of utility for P. Moreover, in round 1 we increase all acceptance probabilities to φ1j = 1 for j ∈ [n]. Then, upon arrival of such an option ωj in round 1, the change can incentivize A to propose this option - which is clearly optimal for P, since this is an optimal option for her. Since the change is in round 1, it introduces no incentive to wait for A. As such, it can only increase the utility for P. Now consider any entry φij ≥ 1/n. We observe two properties:

1. Suppose φi′ j ′ ≥ 1/n for i′ < i and j ′ < j. Then P accepts realization ωj ′ in round i′ with positive probability, but she will also accept the better (for A) realization ωj in a later round i with positive probability. A will not propose ωj ′ in round i′ but wait for round i, since the expected utility in the later round i is at least n4j · 1/n2 · φij ≥ n4j-3 > n4(j-1) ≥ n4j ′ · φi′ j ′ , the utility in round i′ . As such, w.l.o.g. we set φi′ j ′ = 0 for all i′ < i and j ′ < j.
2. Suppose φi′ j < φij for i′ < i. By property 1., all realizations ωj ′ with j ′ < j are not accepted in rounds 1, . . . , i - 1. Hence, setting φi′ j = φij does not change the incentives for A w.r.t. other options, and thus only (weakly) increases the expected utility of P. By the same arguments, we set φij ′ = max{φij ′ , φij} for all inferior options j ′ < j in the same round i.

We apply the adjustments implied by the two properties repeatedly, starting for the entries φin in the n-th column for option ωn, then in column n-1, etc. By 1., every positive entry φij ≥ 1/n leads to entries of 0 in all "dominated" entries φi′ j ′ with i′ < i and j ′ < j. As a consequence, the remaining positive entries form a Manhattan path in the matrix φ. The path starts at φ1n, ends at φn1, and for each φij ≥ 1/n it continues either at φi+1,j ≥ 1/n or φi,j-1 ≥ 1/n. See Table 2 for an example.

We can upper bound the expected utility of P by assuming that all 2n - 1 entries on the Manhattan path are 1 (i.e., φ is deterministic) and A proposes an acceptable option whenever possible. The probability that this happens is at most (2n - 1)/n2 = O(1/n) by a union bound. This is an upper bound on the expected utility of P and proves the theorem for schemes with φij = 0 for all i ∈ [n] and j ≥ n + 1.

Finally, suppose φij > 0 for some j ≥ n + 1. Clearly, option ωj adds no value to the expected utility of P. Moreover, the fact that ωj has positive probability to be accepted in round i can only motivate A to refrain from proposing inferior options in earlier rounds. As such, setting φij = 0 only (weakly) increases the utility of P.

The lower bound in Theorem 1 remains robust in several extensions of the model. In the full version of this paper [Braun et al., 2022], we discuss two generalizations (when A has a lookahead of k rounds, and when A is allowed to make k proposals). For both scenarios, we show the following lower bounds (along with simple algorithms providing matching upper bounds).

Corollary 1. Consider online delegation in the IID setting with either (1) lookahead k, or (2) k proposals. For each scenario, there are classes of instances such that every action scheme φ obtains at most an O(k/n)-approximation of the expected utility for optimal (offline) search.

3 Discrepancy of Agent Utilities

3.1 Conscious Proposals

The lower bound instances in Theorem 1 have agent utilities between 1 and nO(n) . Is such a drastic discrepancy necessary to show a substantial lower bound? Can we obtain better approximation results for instances with a smaller ratio of the maximum and minimum utility values for A?

Here, we restrict to aij > 0 for all options and study the cases with aij = 0 in the full version [Braun et al., 2022]. Let α = max{aij | i ∈ [n], j ∈ [si]}/min{aij | i ∈ [n], j ∈ [si]}. W.l.o.g. we scale all utility values to aij ∈ [1, α], where both boundaries α and 1 are attained by at least one option. Then A has α-bounded utilities.

We show how to compute a good action scheme with respect to parameter α. Intuitively, we partition the best options for P that add up a total probability mass of roughly 1/2 into O(logα/ log logα) many bins. Each bin is constructed in a way such that A is incentivized to propose the first option he encounters from that particular bin, assuming that P only accepts options from that bin. The algorithm determines the best bin for P and deterministically restricts the acceptable options to the ones from this bin.

Let us discuss the algorithm in more detail (pseudocode can be found in the full version of this paper [Braun et al., 2022]). As a first step, the algorithm uses a procedure RestrictOptions(D1, . . . ,Dn,m) with parameter m = 1/2 as subroutine. The procedure considers all options in descending order of principal utility until a total probability mass m is reached. Starting out with ˆQ = ∅, options are added to ˆQ = {(i, j) | bij ≥ bi′ ,j ′ ∀(i′ , j ′ ) /∈ ˆQ} as long as ∑(i,j)∈ ˆQ pij < m. The first option (i∗ , j ∗ ) that would reach or surpass the combined mass of m (i.e., such that ∑(i,j)∈ ˆQ∪{(i∗ ,j ∗ )} pij ≥ m) is considered separately. The procedure RestrictOptions then returns either Q = ˆQ or Q = {(i∗ , j ∗ )}, whichever set provides a better expected utility for P. As a consequence, ∑(i,j)∈Q pij · bij ≥ m/2 · Eωij∼Di [maxi∈[n] bij]. Lemma 1 summarizes the claim. The proof can be found in the full version [Braun et al., 2022].

Lemma 1. The subroutine RestrictOptions(D1, . . . ,Dn,m) with distributions D1, . . . , Dn and a parameter 0 < m ≤ 1

as input identifies Q, the best set of options for P, such that

and either (1) the combined mass ∑(i,j)∈Q pij < m or (2) all options in Q arrive in the same round.

If the set Q returned by RestrictOptions only spans a single round i, the agent will always be incentivized to propose an acceptable option in round i. For this scenario, the algorithm only creates a single bin B1. Otherwise, it continues with the second and third step described in the following.

In the second step of the algorithm, the options identified by RestrictOptions are classified by their utility for A. The algorithm divides Q into c = ⌈log2 α⌉ classes depending on the agent utility such that the lowest and highest agent utilities in any given class differ by at most a factor of 2. More precisely, classes C1, . . . , Cc are constructed such that Ck = {(i, j) ∈ Q | aij ∈ [2k-1 , 2k )} for k = 1, . . . , c - 1 and Cc = {(i, j) ∈ Q | aij ∈ [2c-1 , 2c ]}.

For the third step, subsequent classes (by their agent utility value) are combined into bins such that (1) the bins are as big as possible and (2) A optimizes his own expected utility by proposing the first option he encounters from any bin - assuming that only options from this bin are allowed. Classes are either added to a bin completely or not at all. Let s be the index of the class with the highest agent utilities currently considered, i.e., the first class to be added to the current bin Bb. We consider the classes by decreasing agent utility values, i.e., with indices k = s, s-1, . . . . While 2k-1 ≥ 2s · ∑(i,j)∈Bb∪Ck pij, a rational A will always propose the first option available from the current bin if that is the only allowed bin as it has a higher utility than what A can expect from later rounds. Hence, the class currently under consideration can be added to the current bin.

Finally, having constructed all bins, the algorithm simply chooses the best one for P.

Lemma 2 shows that our algorithm achieves an approximation ratio which is linear in the number of bins opened. The subsequent Lemma 3 bounds the number of bins opened, showing that it is in the order of O(logα/ log logα). Together, the lemmas prove Theorem 2, our main result of the section.

Lemma 2. Let ℓ be the number of bins opened by the algorithm. Then the scheme computed by the algorithm obtains at least an 1/(8ℓ)-approximation of the expected utility of the best option for P in hindsight.

Proof. We know that Q satisfies 4 · ∑(i,j)∈Q pij · bij ≥ Eωij∼Di [maxi∈[n] bij ] = OPT by Lemma 1.

Now consider the construction of the bins. Suppose we split Q into ℓ bins B1, B2, . . . , Bℓ. We pick the best one Bb∗ from the ℓ bins B1, . . . , Bℓ, so

The action scheme restricts attention to Bb∗ and accepts each proposed option ωij from the bin with probability 1. Let k- = min{k | Ck ⊆ Bb∗} be the class of smallest index in Bb∗, and k+ the one with largest index, respectively. Now suppose the agent learns in round i that an option ωij with (i, j) ∈ Bb∗ arrives in this round. We claim that A will then decide to propose this option. This is obvious if all options in Bb∗ are only realized in round i. Otherwise, the agent might want to wait for an option in a later round. If A proposes, then his utility is aij. Otherwise, if he waits for another option fromBb∗ in a later round, then a union bound shows that the expected utility is at most

where the second-to-last inequality is a consequence from the construction of the bin. Hence, the first option from the bin that is realized also gets proposed by A and accepted by P.

Now for each option (i, j) ∈ Bb∗, the probability that this option is proposed and accepted is the combination of two independent events: (1) no other option from Bb∗ was realized in any of the rounds i′ < i, (2) option ωij is realized in round i. The probability for event (2) is pij. For event (1), we define mi = ∑(i,j)∈Bb∗ pij. With probability ∏i′<i (1-mi′), no option fromBb∗ is realized in rounds i′ < i. Note that ∑ni=1 mi ≤ 1/2. The term ∏ni=1 (1-mi) is minimized for m1 = 1/2 and mi′ = 0 for 1 < i′ < i. Thus ∏ni=1 (1 -mi) ≥ 1/2, i.e., the probability of event (1) is at least 1/2.

Overall, by linearity of expectation, the expected utility of P when using φ is at least

Lemma 3. Let ℓ be the number of bins opened by the algorithm. It holds that ℓ = O(log α/ log log α).

Proof. Consider a bin B and its mass pB = ∑(i,j)∈B pij. We want to argue that at most O(c/ log c) bins are opened. To do so, we first condition on having ℓ open bins and strive to lower bound the number of classes in these ℓ bins.

Consider a bin B starting at Cs. The algorithm adds classes to B until 2k-1 < 2spB. Thus, s-k+1 > log2(1/pB), i.e., the number of classes in Bi is lower bounded by log2(1/pB). Now consider two bins Bi and Bi+1 and condition on q = pBi + pBi+1 . Together the bins contain at least log2(1/pBi ) + log2(1/(q - pBi )) classes. Taking the derivative for pBi , we see that this lower bound is minimized when pBi = q/2 = pBi+1 . Applying this balancing step repeatedly, the lower bound on the number of classes in all bins is minimized when pBi = pBj for all bins Bi, Bj . Thus, when opening ℓ bins, we obtain the smallest lower bound on the number of classes in these bins by setting pBi = 1/ℓ · ∑(i,j)∈Q pij < 1/(2ℓ) for all bins Bi. Conversely, when opening ℓ bins, we

need to have at least ℓ log2(2ℓ) classes in these bins.

Now, since we need to put c classes into the bins, we need to ensure that for the number ℓ of open bins we have ℓ(log2 ℓ + 1) ≤ c, since otherwise the ℓ bins would require more than c classes in total. This implies that c = Ω(ℓ log2 ℓ) and, hence, ℓ = O(c/ log c) = O(log α/ log log α).

Theorem 2. If the agent has α-bounded utilities, there is a deterministic action scheme such that P obtains an Ω(log logα/ logα)-approximation of the expected utility for optimal (online) search.

Observe that the approximation ratio of this algorithm is tight in general. Consider the instances in Theorem 1 with α = nO(n) . The theorem shows that every scheme can obtain at most a ratio of O(1/n) = O(log log α/ log α).

3.2 Oblivious Proposals

In the previous section, we considered algorithms for P when she learns the utility pair for the proposed option. In this section, we show that (fully) oblivious proposals can be a substantial drawback for P. Obviously, the lower bound in Theorem 1 remains intact even for oblivious proposals, when P does not learn the utility value of the proposed option for A. For oblivious proposals and α-bounded agent utilities, we can significantly strengthen the lower bound. In contrast to the logarithmic approximation guarantee above, we provide a linear lower bound in α for oblivious proposals.

Theorem 3. There is a class of instances of online delegation with α-bounded utilities for the agent and oblivious proposals, in which every action scheme φ obtains at most an O(1/α)-approximation of the expected utility for optimal (online) search.

Proof. Consider the following class of instances. InDi, there are two options with the following probabilities and utilities: ωi1 with pi1 = 1-1/n and (bi1, ai1) = (0, 1), as well as ωi2 with pi2 = 1/n and (bi2, ai2) = (1, xi), where xi ∈ {1, α} and α ∈ [1, n]. In the first rounds i = 1, . . . , i∗ - 1 we have xi = 1, then xi = α for rounds i = i∗ , . . . , n. The expected utility when P performs (undelegated) online search is 1 - (1 - 1/n)n ≥ 1 - 1/e.

P wants that A proposes any profitable option ωi2 as soon as possible. As in the proof of Theorem 1, we can assume that all φi1 = 0 in an optimal scheme - this option has no value for P and can only raise the incentive to wait for A.

Due to oblivious proposals, P has to choose φ without being aware of the value of i∗ . For our impossibility result, we adjust i∗ to the scheme φ chosen by P: Set i∗ ∈ {1, . . . , n} to the largest number such that ∑ni=i∗ φi2 ≥ e · n/α, or i∗ = 1 if no such number exists.

First, suppose that i∗ = 1. Then, even if we force A to propose every option ωi2 as soon as it arises, a union bound shows that the expected utility of P is upper bounded by ∑ni=1 1n · φi2 ≤ eα + 1n . Hence, P obtains only an O(1/α)- approximation, for any α ∈ [1, n].

Now suppose that i∗ > 1. Consider an optimal scheme φ for P. If ωi2 arises in round i, A decides if it is more profitable to propose i or wait for a later round. Indeed, we show that A never proposes ωi2 in any round i < i∗ . Consider the expected utility from proposing the first option ωk2 arising in rounds k = i∗ , . . . , n. This is

i.e., strictly larger than the expected utility φi2 from proposing ωi2 in round i < i∗ . Hence, A only proposes in rounds k = i∗ , . . . , n. Even if A would be able to propose every option ωk2 in rounds k = i∗ , . . . , n, a union bound implies that the expected utility of P from these rounds is upper bounded by ∑nk=i∗ 1n · φk2 ≤ eα + 1n . For any α ∈ [1, n], P obtains an O(1/α)-approximation.

Theorem 4. If the agent has α-bounded utilities and makes oblivious proposals, there is a deterministic action scheme such that P obtains an Ω(1/α)-approximation of the expected utility for optimal (online) search.

For the scheme, P simply sets φij = 1 for all (i, j) ∈ Q, where Q is the set returned by RestrictOptions(D1, . . . , Dn, 1/(2α)). The key insight is that by bounding the combined mass of acceptable options by 1/(2α), A is incentivized to propose the first acceptable option he encounters. Pseudocode as well as the proof of Theorem 4 can be found in the full version [Braun et al., 2022].

4 Misalignment of Principal and Agent Utility

In this section, we consider performance guarantees based on the amount of misalignment of principal and agent utility. For most of the section, we assume that all utility values are strictly positive. Consider the smallest β ≥ 1 such that

for any two options ωij and ωi′ j ′ in the instance. Then the preference of P between any pair ωij, ωi′ j ′ of options is shared by A - up to a factor of at most β. We term this βbounded utilities. Alternatively, consider γ ≥ 1 as a bound on the utility ratio 1/γ · aij ≤ bij ≤ γ · aij for every single ωij. Then the utilities are γ 2 -bounded in the sense defined above, and we obtain asymptotically the same bounds.

Suppose we choose an arbitrary realization ωi′ j ′ . Divide all utility values of P for all realizations by bi′ j ′ , and all utility values of A by ai′ j ′ . Note that this adjustment neither affects the incentives of the players nor the approximation ratios of our algorithms. Considering ωij with the adjusted utilities, we see that 1/β · bij/aij ≤ 1 ≤ β · bij/aij , and thus 1/β ≤ bij/aij ≤ β for all ωi′ j ′ . This condition turns out to be convenient for our analysis.

Our main idea is to use O(logβ) clusters Ck to group all the options that have a utility ratio between 2k and 2k+1 , i.e.,

for k = ⌊log 1/β⌋, . . . , ⌈logβ⌉. Our deterministic scheme restricts the acceptable options to a single cluster Ck∗. Note that here P is assumed to see aij upon a proposal. The principal determines the cluster k∗ , such that the best response by A (i.e., his optimal online algorithm applied with the options from that cluster) delivers the largest expected utility for P.

Theorem 5. If principal and agent have β-bounded utilities, there is a deterministic action scheme such that P obtains an Ω(1/ log β)-approximation of the expected utility for optimal (online) search.

Proof. Consider any cluster Ck. We denote by b(A, k) and a(A, k) the expected utility for P and A when P uses Ck to determine φ. Now consider a hypothetical algorithm for P that observes all realizations and chooses the best option from Ck for P if possible. If there is no such option, it obtains a utility of 0. Let b(P, k) and a(P, k) be the expected utility of the hypothetical algorithm for P and A, respectively. Clearly, b(P, k) ≥ b(A, k) and a(A, k) ≥ a(P, k), but also, by definition of Ck,

Now consider the best option for P in hindsight. The bestoption-algorithm for cluster Ck picks the best option in hindsight if it comes from cluster Ck. Otherwise, it returns a value of 0. Let b∗k be the expected utility of this algorithm for P, and let OPT be the expected utility of the best option in hindsight for P. Then

Hence, since the scheme chooses the cluster k∗ that maximizes b(A, k∗ ), we obtain an Ω(1/ logβ)-approximation.

Acknowledgments

Hahn gratefully acknowledges the support of GIF grant I1419-118.4/2017. Hoefer gratefully acknowledges the support of GIF grant I-1419-118.4/2017 and DFG grants Ho 3831/6-1, 7-1 and 9-1.