Delegated Stochastic Probing

Our model features a collection of elements, each of which is associated with a (random) utility for each of the principal and the agent. We assume that different elements are independently distributed, though the principal’s and the agent’s utilities for the same element may be correlated. We allow constraining both the sampled and the selected set of elements via outer and inner constraints, respectively. Each constraint is a downwards-closed set system on the ground set of elements. A probing algorithm for an instance of our model adaptively probes some set of elements subject to the outer constraint, learning their associated utilities in the process. The algorithm then selects as its solution a subset of the probed elements satisfying the inner constraint. We assume that, for both the principal and the agent, utility for a solution is the sum of its per-element utilities.

To situate the non-game-theoretic component of our model within the literature on stochastic probing problems, note that we allow an arbitrary utility distribution for each element, rather than a binary-support distribution characterizing “feasibility”. Moreover, unlike “probe and commit” models, we also allow our algorithm to select its solution after all probes are complete. In both these respects, our model is akin to the stochastic multi-value probing model of [5]. As for our game-theoretic modeling, we assume that the utility distributions, as well as the inner and outer constraints, are common knowledge. The realized utilities, however, are only observed by the agent upon probing.

In the traditional (non-delegation) setting, the principal implements the probing algorithm optimizing her own utility, in expectation. In the delegation setting, the principal and agent engage in the following Stackelberg game. The principal moves first by committing to a policy, or mechanism. Such a policy is a (possibly randomized) map from a set of signals to solutions satisfying the inner constraint, with each element in the solution labeled with its (presumptive) utility for both the principal and the agent. Moving second, the agent probes some set of elements subject to the outer constraint, and maps the observed utilities to a signal. The outcome of the game is then the solution which results from applying the principal’s policy to the agent’s signal. We assume that the principal and agent utilities are additive across elements in the solution, so long as it is labeled with the true per-element utilities. Otherwise, we assume that the principal can detect this discrepancy and effectively “quit” the game, imposing a utility of zero for both parties. We adopt the perspective of the principal, who seeks a policy maximizing her expected utility. The agent, naturally, responds with a strategy maximizing his own expected utility given the policy.

By an argument analogous to that in [16], which we prove in our general setting for completeness’ sake, we can restrict attention to single-proposal mechanisms. In a deterministic single-proposal mechanism, the set of signals is a “menu” of acceptable (labeled) solutions satisfying the inner constraint, as well as a “null” signal which in our setting we can take to be the empty set. The agent, facing such a mechanism, without loss simply implements a probing algorithm to compute a “proposed” solution, tagging each element in the solution with its observed utilities, and ensuring that the solution is acceptable to the principal. We also consider randomized single-proposal mechanisms, where the menu consists of acceptable lotteries (i.e., distributions) over (labeled) solutions, and an agent’s probing algorithm proposes a lottery on the menu.

We study delegation mechanisms which approximate the principal’s non-delegated utility. We refer to the best multiplicative approximation factor as the delegation gap of the associated instance.

Our main set of results concern the design of deterministic single-proposal mechanisms which prove constant delegation gaps for natural classes of inner and outer constraints. Our approach is modular, and reduces a (constructive) $\alpha\beta$ bound on the delegation gap to a (constructive) $\alpha$ generalized prophet inequality of a particular form on the inner constraint, and a (constructive) bound of $\beta$ on the adaptivity gap associated with the outer constraint and the rank function of the inner constraint. Drawing on recent work in [9], which derives prophet inequalities of our required form, and in [4, 5], which bounds the adaptivity gap, we obtain constant bounds on the delegation gap for instances of our model with a variety of inner and outer constraints such as matroids and their intersections, among others.

We also begin an exploration of randomized single-proposal mechanisms, where the principal’s menu consists of acceptable lotteries over solutions. We show that, even in the simple setting of no outer constraint and a $1$-uniform inner constraint, there are instances for which randomized mechanisms significantly outperform optimal deterministic ones. Nevertheless, there exist worst-case instances where both deterministic and randomized mechanisms suffer a $1/2$ delegation gap. We leave open whether randomized mechanisms can lead to better bounds on the worst-case delegation gap for more intricate classes of inner and outer constraints.

Since the economic literature on delegation is extensive, we only describe a select sample here. The groundwork for the formal study of optimal delegation in economics was initially laid by Holstrom [14, 13]. Subsequent work in economics has considered a variety of optimization problems as the task being delegated (e.g. [2, 23, 3]). We mention the work of Kovac and Mylovanov [18] as being related to our results in Section 5: To our knowledge, they were the first to examine the power of randomized mechanisms for delegation.

Most relevant to the present paper is the aforementioned work of Kleinberg and Kleinberg [16], who examine approximations for optimal delegation. Their distributional model is closely related to the model of Armstrong and Vickers [3], and the optimization problem being delegated in their binary model is a special case of Weitzman’s box problem [27]. Both optimization problems fit nicely in the general literature on stochastic probing (see e.g. [26]), motivating our examination of delegated stochastic probing more broadly.

Also related is the recent work of Khodabakhsh et al [15], who consider a very general model of delegation with discrete actions and states of the world, and an agent who fully observes the state (no outer constraints or sampling costs). They show optimal delegation to be NP-hard and examine limited “bias” assumptions under which simple threshold mechanisms are approximately optimal. Notably, they don’t impose sampling constraints on the agent and their approximations are with respect to the optimal delegation policy rather than the optimal non-delegated policy. For these reasons, our results are not directly comparable.

The optimization problems being delegated in our model fit in the broad class of stochastic probing problems. We do not attempt a thorough accounting of this literature, and instead refer the reader to related work discussions in [26, 5]. To our knowledge, the term “stochastic probing” was originally coined by Gupta and Nagarajan [10], though their binary probe-and-commit model is quite different from ours. More closely related to us are the models of [5, 4], which capture stochastic probing problems with multi-valued reward distributions, no commitment, and combinatorial inner and outer constraints.

As previously mentioned, our work draws on the literature on prophet inequalities. The foundational result in this setting is the (single-choice) prophet inequality of Krengel, Sucheston, and Garling [19, 20]. Generalized prophet inequalities, with respect to various combinatorial constraints, adversaries, and arrival models, have received much attention in the last decade (e.g. [12, 17, 8, 9]); the associated body of work is large, and we recommend the survey by [22]. Closely related to generalized prophet inequalities are contention resolution schemes (see e.g. [6, 9, 1]), with reductions going in both directions [21]. Key to our results are the “greedy” generalized prophet inequalities, derived through “greedy” contention resolution, by Feldman et al [9].

Finally, we briefly elaborate on the relationship between our model and the two models of Kleinberg and Kleinberg [16]. The natural variant of their binary model which replaces sampling costs with combinatorial constraints on the set of samples (outer constraints, in our nomenclature) fits squarely in our model. Their distributional model, which allows $n$ i.i.d. samples from a distribution over utility pairs, initially appears to be a special case of ours. However, our principal is afforded additional power through their ability to distinguish elements by name alone. Nevertheless, we recover their main result as a special case of ours by observing that our mechanism treats elements symmetrically.

A set system is a pair $(E,\mathcal{I})$ where $E$ is a finite set of elements and $\mathcal{I}\subseteq 2^{E}$ is a family of feasible sets. We focus on downwards-closed set systems, satisfying the following two conditions: (1) $\emptyset\in\mathcal{I}$, i.e. the empty set is feasible, and (2) if $T\in\mathcal{I}$ then $S\in\mathcal{I}$ for all $S\subseteq T$, i.e. any subset of a feasible set is feasible. Matroids, matching constraints, and knapsack constraints are all examples of downwards-closed set systems.

For a set system $\mathcal{M}=(E,\mathcal{I})$ and $F\subseteq E$, we use $\mathcal{M}|F=(F,\mathcal{I}\,\cap\,2^{F})$ to denote the restriction of $\mathcal{M}$ to $F$.

A generalized prophet inequality problem is given by a set system $\mathcal{M}=(E,\mathcal{I})$, and for each element $e\in E$ an independent random variable $X_{e}$ supported on the nonnegative real numbers. Here we adopt the perspective of a gambler, who is given $\mathcal{M}$ and the distributions of the random variables $\left\{X_{e}\right\}_{e\in E}$ in advance, then encounters the elements $E$ in an order chosen by an adversary. On encountering $e$, the gambler observes the realization $x_{e}$ of the random variable $X_{e}$, and must immediately decide whether to accept $e$, subject to the accepted set $S$ of elements remaining feasible in $\mathcal{M}$. The gambler seeks to maximize his utility $x(S)=\sum_{e\in S}x_{e}$, and in particular to compete with a prophet who knows the realization of all random variables in advance. If the gambler can guarantee an $\alpha$ fraction of the prophet’s utility in expectation, we say that we obtain a generalized prophet inequality with a factor of $\alpha$.

For each possible realization $x_{e}$ of $X_{e}$, we refer to the pair $(e,x_{e})\in E\times\mathbb{R}_{+}$ as an outcome. When the gambler accepts $e\in E$ given a realization $x_{e}$ of $X_{e}$, we also say the gambler accepts the outcome $(e,x_{e})$.

Although it is most common to consider an adversary who fixes an order of the elements upfront, some recent work has investigated much more powerful adversaries [17, 9]. In this paper, we are interested in the almighty adversary, who knows in advance the realizations of all random variables as well as any random coin flips used by the gambler’s strategy. The almighty adversary can perfectly predict the future and choose a truly worst-case ordering.

Key to our results is the notion of a “greedy” strategy for the gambler. We take inspiration from [9], who defined greedy online contention resolution schemes, and extend their definition to prophet inequality problems.

We note that Samuel-Cahn’s [25] threshold rule for the single-choice prophet inequality is greedy, and its competitive factor of $\frac{1}{2}$ holds for the almighty adversary [24]. More generally, Feldman et al. [9] show that there exist constant-factor greedy prophet inequalities against the almighty adversary for many classes of constraints.

Another key notion we will use is the adaptivity gap for stochastic set function optimization problems. For a detailed introduction, see [4].

We consider maximizing a stochastic set function $f:2^{E}\to\mathbb{R}_{+}$ constrained by a downwards-closed set system $\mathcal{M}=(E,\mathcal{I})$. We assume $f$ is determined by a collection $\left\{X_{e}\right\}_{e\in E}$ of independent random variables, with the stipulation that $f(S)$ does not depend on any random variables $X_{e}$ for which $e\notin S$.¹¹1In other words, one can evaluate $f(S)$ given access to the realizations of the random variables $\left\{X_{e}\right\}_{e\in S}$. We are tasked with “probing” some $S\subseteq E$, feasible for $\mathcal{M}$, with the goal of maximizing $f(S)$. An adaptive algorithm for this problem probes elements one at a time, where probing $e$ results in learning the realization of $X_{e}$. Such an algorithm can use the realizations of probed variables to decide on a next element to probe. A non-adaptive algorithm chooses the set $S$ all at once, independently of the random variables $\left\{X_{e}\right\}_{e\in E}$. The adaptivity gap is the minimum (worst-case) ratio of the expected value of the optimal non-adaptive algorithm versus the expected value of the optimal adaptive algorithm.

In [4], Asadpour and Nazerzadeh showed that the adaptivity gap for instances with monotone submodular functions and matroid constraints is $1-\frac{1}{e}$. Furthermore, they provided an efficient non-adaptive algorithm that achieves this bound. Finally, in [5], Bradac et al. showed that the adaptivity gap is constant for instances with “prefix-closed” constraints (which include all downward-closed constraints) and functions that are the weighted rank function of the intersection of a constant number of matroids.

Given such an instance, we will additionally define: $(X_{e},Y_{e})\sim\mu_{e}$ as random variables denoting the utilities for the principal and agent of element $e$; $\Omega$ as the set of outcomes $(e,x,y)$ for all $e\in E$ and all $(x,y)\in\operatorname{supp}(\mu_{e})$; and $\Omega_{\text{in}}\subseteq 2^{\Omega}$ as the family of all sets of outcomes whose elements are distinct and feasible in the inner constraint. For convenience, we will also overload notation by considering $x$ and $y$ to be utility functions for the principal and agent. Given any subset of outcomes $T\subseteq\Omega$, let $x(T)=\sum_{(e,x,y)\in T}x$ and $y(T)=\sum_{(e,x,y)\in T}y$ be the total utility of outcomes in $T$. Similarly for any subset of elements $F\subseteq E$, let $x(F)=\sum_{e\in F}X_{e}$ and $y(F)=\sum_{e\in F}Y_{e}$ be random variables representing the randomized total utility of elements in $F$.

A natural mechanism that the principal might choose to implement is called a single-proposal mechanism. Here, the principal describes the space of solutions she is willing to accept, and then the agent uses this information to search the solution space and propose a single feasible solution.

In the deterministic single-proposal setting, the principal first commits to a family of sets of outcomes $\mathcal{R}\subseteq\Omega_{\text{in}}$ and announces $\mathcal{R}$ to the agent. The sets in $\mathcal{R}$ are called acceptable, and the principal’s choice of $\mathcal{R}$ is called their policy (or mechanism). After learning $\mathcal{R}$, the agent will select elements to probe, so long as each element is probed at most once and the set of probed elements is feasible in $\mathcal{M}_{\text{out}}$. We allow the agent to probe adaptively, deciding what to do next based on previously probed elements. Let’s say that they probe elements $F\subseteq E$ and obtain outcomes $S\subseteq\Omega$. The agent will then choose some set of outcomes $T\subseteq\Omega$ and propose it to the principal. If $T$ is acceptable and also a subset of $S$ then the principal and agent receive $x(T)$ and $y(T)$ utility, respectively. Otherwise, they both receive $0$ utility.

In the above-described mechanism design setting, we assume that both the principal and agent act to maximize their expected utility. We also assume that all parameters of the problem, except for the realizations of the random variables, are common knowledge.

We note that, similar to the setup in [16], our model assumes that our agent cannot benefit from lying, say by labeling an element $e$ with utilities other than $X_{e}$ and $Y_{e}$, or by proposing an element he has not probed. We argue that this is a natural assumption to make: In many applications we foresee (e.g., a firm hiring an employee, or exploring some mergers), a proposal will be accompanied by an easy to verify proof of the claimed utilities (e.g., in the form of a CV for the applicant, or a detailed analysis of the merger).

As in [16], we compare delegation mechanisms against the optimal non-delegated strategy. By non-delegated strategy, we mean the strategy of the principal when they act as both the principal and agent (i.e. they have power to probe and propose as well as accept outcomes).

Given any $F\subseteq E$, let $u(F)$ be the optimal utility of the non-delegating principal when they probe elements in $F$ and accept their own favorite set of outcomes, and let $v_{\mathcal{R}}(F)$ be the utility of the delegating principal with policy $\mathcal{R}$ when the agent probes elements in $F$ and proposes their favorite acceptable set of outcomes. We can write $u$ and $v_{\mathcal{R}}$ as

where $\Omega_{G}\subseteq\Omega$ is the set of outcomes from the probed set of elements $G$. In the case of ties in the definition of $v_{\mathcal{R}}$, our results hold for arbitrary (even adversarial) tie-breaking.

Having formally defined the model, we will now describe a broad generalization of single-proposal mechanisms, called signaling mechanisms, and show that these mechanisms don’t provide the principal with any additional power. Note that this discussion is inspired by Section 2.2 from [16], and we simply extend their work to our model.

A signaling mechanism allows the principal to ask the agent for more (or different) information than just a proposed solution. The principal will then take this information and transform it into a solution, which they will accept. One might suspect that expanding the space of mechanisms in this way would give the principal more power. However, as we will show, this isn’t the case even for a broad class of delegation models, which we will now define formally.

We note that the above definition generalizes the delegation problems of Definition 3.1. In particular: the state space $S$ represents all possible realizations of per-element utilities of the principal and the agent; the solution space $\Psi$ is the family of feasible subsets of outcomes $\Omega_{\text{in}}$, where $\bot$ is the empty set of outcomes; $\mathcal{P}$ corresponds to probing algorithms which respect the outer constraint; $\sigma_{p}(s)$ is the set of outcomes obtained by invoking algorithm $p$ in state $s$; both utility functions depend on the state $s\in S$ and the probing algorithm $p\in\mathcal{P}$, evaluating to $0$ for solutions $\psi$ that are inconsistent with the state $s$, or if the probing algorithm $p$ applied to $s$ does not the probe the elements in $\psi$.

Given a generalized delegation problem, we define signaling mechanisms as follows.

Notice that this model can be made to capture the design of randomized delegation mechanisms by extending $\Psi$ to the space $\Delta(\Psi)$ of distributions (henceforth lotteries) over solutions, and extending both utility functions to lotteries by taking expectations.

We contrast this broad definition of signaling mechanisms with the comparatively simple single-proposal mechanisms.

Intuitively, in a single proposal mechanism the principal declares a menu of acceptable solutions. The agent then proposes a solution, which is accepted if it is on the menu, and replaced with the null solution otherwise. Now we will show that single-proposal mechanisms are just as powerful as signaling mechanisms. In particular, for every signaling mechanism there is a single-proposal mechanism which selects the same solution and the same probing strategy for each state of nature, at equilibrium. This lemma is a simple extension of [16, Lemma 1] to the our generalized delegation model.

We will now consider instances of delegated stochastic probing for which there is no outer constraint. We will then combine the results from this section with Theorem 4.5 to get solutions to delegation problems with both inner and outer constraints.

To simulate the lack of an outer constraint, we will consider instances of delegation for which the outer constraint is the trivial set system in which all subsets of the elements are feasible. For any ground set $E$ of elements, we will write this trivial set system as $\mathcal{M}^{*}_{E}$, omitting the subscript when the set of elements $E$ is clear from context.

We note that by construction of the principal’s policy $\mathcal{R}$, this theorem holds even when the principal is unaware of the agent’s utility values $y$. This is comparable to the reduction in [16] which similarly worked regardless of the principal’s knowledge of the agent’s utilities.

Unfortunately, applications of this theorem rely on the existence of competitive strategies against the almighty adversary, which is a very strong condition. It is natural to ask whether it’s really necessary in the reduction for the adversary to be almighty. We provide some evidence that this is indeed necessary by considering the special case of a 1-uniform inner matroid. In this case, it’s easy to construct instances for which the utility of the principal and agent sum to a constant value for all outcomes, i.e. $X_{e}+Y_{e}=c$ for all $e$ and some constant $c$. In such an instance, the agent’s goals are directly opposed to the principal’s, so the agent will always propose the principal’s least favorite acceptable outcome. In the corresponding instance of the prophet inequality, the almighty adversary can guarantee that the gambler chooses their least favorite acceptable outcome, while weaker adversaries (that don’t know the realizations of variables) cannot enforce the same guarantee.

Using some known greedy prophet inequalities against the almighty adversary, we get the following corollaries.

We note that it is open whether there exists a $\frac{1}{2}$-OCRS for matroids against the almighty adversary [21]. The existence of such an OCRS, if greedy, would imply the existence of $\frac{1}{2}$-policy for delegated stochastic probing with a matroid inner constraint and no outer constraint.

Although Corollary 4.2 applies to a model very similar to the distributional delegation model from [16], our principal has the additional power of being able to distinguish between otherwise identical elements by their name alone. However, by observing that Theorem 4.1 turns greedy prophet inequalities that don’t distinguish between identical elements into delegation policies that also don’t distinguish between identical elements, we can derive delegation policies that recover the $\frac{1}{2}$-factor guarantee from [16] for their distributional model. We leave the details for Section A.1.

Using the adaptivity gap from Section 2.3, we will now show that there are large classes of delegated stochastic probing problems with nontrivial outer constraints for which the principal can achieve, in expectation, a constant-factor of their non-delegated optimal utility.

The increased power of lottery mechanisms means that for some instances of delegated stochastic probing there exist lottery policies that provide the principal with a better expected utility than the best deterministic policies. In fact, we will show that there are instances for which some lottery policies nearly achieve the principal’s non-delegated expected utility, while the best deterministic policies achieve only about half of this value.

First, we will make the observation that it never benefits the principal to declare two lotteries in $\mathcal{R}$ with identical support but different distributions. This is because the principal knows the utility function of the agent and can predict which lottery the agent will prefer. Therefore, we can assume that for any given support, the principal will declare at most one lottery.

Unfortunately, there is good reason not to be too optimistic about the increased power of lottery mechanisms. As we will now show, there also exist instances for which the best lottery policies and the best deterministic policies all achieve approximately half of the principal’s non-delegated expected utility. Since Corollary 4.2 gives us a deterministic $\frac{1}{2}$-policy, this tells us that, in the worst case, the factor $\frac{1}{2}$ is tight even for lottery policies in the special case of no outer constraint and a 1-uniform inner constraint.