key: cord-0664558-exa33l54 authors: Arnosti, Nick; Ma, Will title: Tight Guarantees for Static Threshold Policies in the Prophet Secretary Problem date: 2021-08-29 journal: nan DOI: nan sha: b26cf396647747075f7c9e1d67a400e3d3d08346 doc_id: 664558 cord_uid: exa33l54 In the prophet secretary problem, $n$ values are drawn independently from known distributions, and presented in random order. A decision-maker must accept or reject each value when it is presented, and may accept at most $k$ values in total. The objective is to maximize the expected sum of accepted values. We study the performance of static threshold policies, which accept the first $k$ values exceeding a fixed threshold (or all such values, if fewer than $k$ exist). We show that using an optimal threshold guarantees a $gamma_k = 1 - e^{-k}k^k/k!$ fraction of the offline optimal solution, and provide an example demonstrating that this guarantee is tight. We also provide simple algorithms that achieve this guarantee. The first sets a threshold such that the expected number of values exceeding the threshold is equal to $k$, and offers a guarantee of $gamma_k$ if $k geq 5$. The second sets a threshold so that $k cdot gamma_k$ values are accepted in expectation, and offers a guarantee of $gamma_k$ for all $k$. To establish these guarantees, we prove a result about sums of independent Bernoulli random variables, which extends a classical result of Hoeffding (1956) and is of general interest. Finally, we note that our algorithms can be implemented in settings with restricted information about agents' values. This makes them practical in settings such as the allocation of COVID-19 vaccines. Consider an online decision-maker endowed with k identical, indivisible items to allocate among n > k applicants who arrive sequentially. Each applicant i = 1, . . . , n has a value V i ≥ 0 for receiving an item. Upon the arrival of applicant i, the decision-maker observes V i and must either immediately "accept" and allocate an item to applicant i, or irrevocably "reject" applicant i (which is the only Before presenting our three main theorems, we introduce our terminology. An instance of the prophet secretary problem is specified by positive integers k, n, and non-negative cumulative distribution functions {F i } n i=1 . We refer to the expected sum of the k largest values as the prophet's value. We consider the class of static threshold policies, defined by a non-negative threshold t and a tiebreak probability p ∈ [0, 1]. So long as fewer than k applicants have been accepted so far, the policy (t, p) accepts applicants with value V i > t, rejects those with V i < t, and flips a coin with success probability p (independently of all other randomness) to decide whether to accept applicants with V i = t. Randomized tie-breaking allows our policies to adjust the "threshold" (t, p) continuously, and is also assumed by Ehsani et al. (2018) and Chawla et al. (2020) . As long as the distribution functions F i are continuous, tie-breaking is unnecessary. In much of the paper, we implicitly make this assumption by suppressing p and referencing only t. Nonetheless, all of our results also hold for discrete distributions. We say that the value of a static threshold policy is the expected sum of values of accepted applicants, where the expectation is taken over the realized values and the arrival order of applicants, as well as the randomization of the algorithm in the case where distributions are discrete and tie-breaking is needed. We first derive an upper bound on the value of any static threshold policy. For k ≥ 1, we define the constant γ k by γ k := 1 − e −k k k k! . (1) Theorem 1. For any k ≥ 1, and any > 0, there exists an instance with IID values such that the value of every static threshold policy is less than γ k + times the prophet's value. The constant γ k appears elsewhere in the literature, and 1/γ k is referred to as the correlation gap by Yan (2011) . It is well-known that no online algorithm can guarantee more than a γ k fraction of a stronger benchmark which only has to accept k values in expectation (rather than on each realization). Theorem 1 shows that the same upper bound holds relative to the weaker benchmark of the prophet's value, if the decision-maker is restricted to static threshold policies. Ehsani et al. (2018) establish this result when k = 1, as γ 1 = 1 − 1/e ≈ 0.632. We fill an important gap in the literature by establishing this result for all k > 1. We note that the upper bound of γ k no longer holds if adaptive policies are allowed. In this case, when k = 1 it is possible to offer guarantees of 0.669 (Correa et al. 2020 ) -and 0.745 if values are IID (Correa et al. 2017 ). The proof of Theorem 1 consists of a careful analysis of the following example. Example 1. Let the values V i be IID according to where W k = k P(Pois(k)k) , and Pois(k) denotes a Poisson random variable with mean k. On this example, the omniscient benchmark always accepts k values, and takes high values whenever they occur. It achieves a value close to k + W k . For a static threshold algorithm, the key question is whether to accept applicants with V i = 1. Always accepting such applicants results in a value close to k, while rejecting them results in a value close to W k . We show that even accepting these applicants with some probability p ∈ (0, 1) cannot do better than γ k (k + W k ). Given any set of values V = {V i } n i=1 , we define the demand at threshold t to be the number of values above t: Given that we can accept k applicants, one natural algorithm is to set the threshold t such that expected demand is equal to k. We refer to this as the expected demand policy. A simple analysis establishes that this policy achieves an optimal guarantee of γ k when values are IID. Proposition 1. If values are IID, then the value of the expected demand policy is at least γ k times the prophet's value. Given this result, one might hope that the expected demand policy would provide the same guarantee for values drawn from non-identical distributions, but presented in a random order. Unfortunately, this is not the case, as the following example demonstrates. Example 2. Fix k and consider a small ε > 0. Let there be k + 1 applicants, k of whom have a value of 1 with probability 1 − ε/k and 0 otherwise. The final applicant's value is 1/ε 2 with probability ε and 0 otherwise. On this example, the prophet's value is at least 1/ε, as this is the expected value of the final applicant. Meanwhile, the expected demand policy accepts the first k applicants whose values are not zero. Whenever the first k applicants all have a value of 1 and arrive before the final applicant, the final applicant is rejected regardless of his or her value. By a union bound, the probability of this is at least 1−ε k+1 . Because the contribution from the first k applicants is upper-bounded by k, the value of the expected demand policy is at most Taking ε → 0, this shows that the expected demand policy does not guarantee more than k k+1 times the prophet's value. When k = 1, we have k k+1 = 1 2 , which is achievable even with an arbitrary (rather than random) arrival order. Examples 1 and 2 provide upper bounds on the performance of the expected demand policy. Our first positive result establishes that these examples are in fact the worst cases for this policy. Theorem 2. On every instance, the value of the expected demand policy is at least min{γ k , k k+1 } times the prophet's value. It can be verified that min{γ k , k k+1 } is k k+1 when k < 5, and γ k when k ≥ 5. Therefore, Theorems 1 and 2 jointly imply that the expected demand policy achieves an optimal guarantee when k ≥ 5. When k ≤ 4, Example 2 illustrates that the expected demand policy may set a threshold that accepts too many applicants, and miss out on a high-value applicant as a result. It is tempting to adjust the target demand downward to reduce this risk. Indeed, Hajiaghayi et al. (2007) consider one such policy, which sets a threshold such that expected demand is equal to k − √ 2k ln k. One might hope that a well-chosen demand target would guarantee γ k times the prophet's value. However, the next result establishes that this is not the case for k ≤ 4. Proposition 2. For any k ≤ 4, and any demand target d, there exists an instance for which setting a threshold such that expected demand is equal to d results in a value strictly less than γ k times the prophet's value. Proposition 2 is established in two cases. If d < k, then the policy fails on an instance where all valuations deterministically equal to 1, in which case it accepts too few applicants. On the other hand, if d > k, then the adversary can create an instance where all values are zero, except for a single applicant who has an infinitesimal probability of having a non-zero value. In this case, the algorithm with target demand of d accepts too many zero applicants, and risks being unable to accept the positive value when it occurs. Proposition 2 establishes that when k ≤ 4, we cannot guarantee γ k times the prophet's value simply by setting expected demand equal to some target level. We now introduce a second algorithm, which sets a target for the number of accepted applicants. We define the expected utilization of an algorithm to be the expected number of accepted applicants, divided by k. Our final result establishes that targeting a utilization of γ k indeed delivers an optimal guarantee. Theorem 3. For any k ≥ 1, setting a threshold so that expected utilization is equal to γ k earns a value at least γ k times the prophet's value on all instances. In the worst-case arrival model, Alaei (2014) presented a dynamic policy that is (1 − 1 √ k+3 )-competitive (shown in black). More recently Chawla et al. (2020) show that static threshold policies achieve the bound in red, which is better for k < 20. Neither bound is known to be tight. Even in the random arrival ("prophet secretary") model which is our focus, these were the best-known bounds for k > 1 prior to our work. We establish the bound in blue. This bound is tight for static threshold policies, and establishes a new lower-bound for the optimal dynamic policy. We note that for all k > 1, Theorem 3 implies the best-known guarantees for any online policy in the prophet secretary problem. Even when k = 2, our guarantee of 1 − 2e −2 ≈ 0.729 for static threshold policies exceeds the previous best guarantee of 0.669 for adaptive policies from Correa et al. (2020) . In Figure 1 , we also compare our guarantees to the lower bounds inherited from the prophet inequality problem (where the arrival order is arbitrary), showing that guarantees are much better with a random arrival order. Furthermore, because our guarantee γ k is of order 1 − Θ( 1 k ), this establishes a separation in the asymptotic performance of static threshold policies between the prophet secretary problem and the prophet inequality problem, which in the latter case is 1 − Θ( log k k ) (Hajiaghayi et al. 2007, Ghosh and Kleinberg 2016) . Section 2 provides a more detailed review of prior work, and situates our results in the literature. Subsection 2.1 provides a proof sketch for our positive results Theorem 2 and 3, including a detailed comparison of our techniques to existing ones. The proofs themselves are then presented in Sections 3-5, with a Bernoulli optimization theorem of general interest (Theorem 4) established in Section 4. Our main negative result, Theorem 1, is proven in Section 6. Discussion about the implementability and robustness of our policies, and why these features are important in applications such as COVID-19 vaccine allocation, is provided in Section 7. All missing proofs of intermediate/auxiliary propositions and lemmas are deferred to the Appendices. We focus on reviewing papers that either study the prophet secretary problem or derive prophet inequalities based on the number of units k, and summarize the results most related to ours in Table 1 . For a more expansive survey of prophet inequalities, we refer to Correa et al. (2018) . Technically, our paper is most similar to the two papers Chawla et al. (2020) , Ehsani et al. (2018) , and we describe differences in our techniques while outlining our proofs in Subsection 2.1. Prophet secretary. The prophet secretary problem with a single item was introduced in Esfandiari et al. (2017), where it was shown that an adaptive threshold policy can earn 1 − 1/e ≈ 0.632 times the prophet's value. This guarantee was improved to 1 − 1/e + 1/400 in Azar et al. (2018) , and more recently to 0.669 in Correa et al. (2020) . We note that the tight guarantee for adaptive policies when values are IID is known to be 0.745 (Hill and Kertz 1982, Correa et al. 2017 ). To our understanding, none of these analyses are easy to generalize to take advantage of the number of units k being greater than 1. Therefore, our guarantee of 1 − e −k k k k! based on analyzing static threshold policies is the best-known lower bound for all k > 1. Static thresholds for prophet secretary. It was originally shown in Esfandiari et al. (2017) that a static threshold which is not allowed to change over time cannot earn more than 1/2 times the prophet's value. However, Ehsani et al. (2018) later showed that the tight ratio actually becomes 1 − 1/e if one assumes continuous distributions, or equivalently allows for randomized tie-breaking when a discrete realization matches the threshold. Our paper considers this model (where a staticthreshold policy is allowed to perform randomized tie-breaking) and establishes the tight guarantee of 1 − e −k k k k! for every k, generalizing the result of Ehsani et al. (2018) for k = 1. k-dependent guarantees. Alaei (2014) has previously shown that an online algorithm can earn 1− 1 √ k+3 times the prophet's value, under a worst-case arrival order, and this guarantee was recently improved for small k in Chawla et al. (2020) . On the other extreme, k-dependent guarantees for free-order prophet inequalities, where the agents can be approached in a chosen desirable order, have been derived by Yan (2011) and improved by Beyhaghi et al. (2020) . In the special case of IID applicants (where order does not matter), the result of Yan (2011) implies a guarantee of γ k . Our work extends this guarantee to the prophet secretary setting where the arrival order is random, and also shows that this guarantee is tight for the class of static threshold policies. Asymptotic dependence on k. Under worst-case arrival order, asymptotic k-dependent guarantees have been previously derived, specifically for the class of static-threshold policies. Hajiaghayi et al. (2007) show that a simple static-threshold policy can asymptotically earn 1 − O( log k k ) times the prophet's value, with the loss of Θ( log k k ) recently proven to be tight in Ghosh and Kleinberg (2016) . By proving tightness of the guarantee 1 − e −k k k k! , we show that the asymptotic loss under the less stringent random-order arrival model is Θ( 1 √ k ), establishing a separation of order √ log k between the two models. We outline our framework for establishing Theorems 2 and 3, which analyze the expected demand and utilization algorithms respectively. Technically, our paper is most similar to Chawla et al. (2020) and Ehsani et al. (2018) , so we highlight the differences throughout the outline. Our approach starts outs the same as the one adopted by Chawla et al. (2020) for an arbitrary arrival order. For any fixed t, the prophet's value can be upper-bounded by Krengel et al. (1977) General Hill and Kertz (1982) Online Krengel et al. (1977) Threshold A comparison of the fraction of the offline optimal value ("prophet's value") that can be guaranteed in each of three models: IID, random order ("prophet secretary"), and arbitrary worst-case order ("prophet inequality"). All guarantees are tight unless (lower, upper) bounds are indicated in parentheses. Our work establishes tight performance guarantees for static threshold policies in the random order model, and also shows that the lower bound established by Yan (2011) in the IID case is tight. Our results also provide improved lower bounds for arbitrary policies in the random order model. The constants β k are defined by Chawla et al. (2020) . Meanwhile, the welfare of any threshold policy can be decomposed into the "revenue" t·min{D t , k}, interpreted as the number of items sold at price t each, and the "utility" which is the sum of non-negative surpluses V i − t enjoyed by applicants i who paid t for an item. A prophet inequality can be established by termwise comparing the expected welfare to (3). The ratio for the first term, , exactly what we called target utilization. A new bound for "utility" under random-order arrivals. We now discuss the second term. Under random-order arrivals, one can imagine randomness as being realized in the following sequence. First, every buyer draws their valuation, which fully determines the demand D t . Next, a random order for the buyers to arrive in is drawn. Now fix D t and consider a buyer who cleared their threshold. What is their probability of acceptance, over the random arrival order? This question has a simple answer-it is 1 if D t ≤ k; and it is k/D t otherwise, because the applicant would have to be among the first k of D t interested applicants to arrive. Therefore, the conditional probability of a threshold-clearing applicant being accepted is ]. Unfortunately, conditioning on a particular applicant clearing their threshold inflates D t , lowering the preceding expression for being accepted. Nonetheless, it is easy to see that this conditional probability is lower-bounded by yielding an expression which does not depend on the specific applicant. Returning to (3), this implies that the guarantee for the threshold policy relative to the prophet is at least General Bernoulli optimization theorem. To lower-bound (5), we take the perspective of an adversary who aims to minimize it, and following Chawla et al. (2020) , note that the adversary's optimization problem can be reduced to determining an n and a vector p = (p 1 , . . . , p n ) of probabilities. The demand D t in (5) will then be realized according to a sum of independent Bernoulli random variables with means p 1 , . . . , p n , which we hereafter denote using D p . Note that this adversary faces constraints-for our target demand algorithm, it must be the case that E[D p ] = k, while for our target utilization algorithm, it must be the case that min{D p /k, 1}] = γ k . To analyze both of our algorithms, we establish the following general Bernoulli optimization theorem. For a fixed n any functions f, g : {0, . . . , n} → R, consider the optimization problem of We show that there always exists an optimal solution in which some p i 's are 0, some p i 's are 1, and the remaining p i 's are equal. This theorem is proven and applied for a particular choice of functions f, g in Chawla et al. (2020) , and is also proven by Hoeffding (1956) when g is the identity function. We believe that our theorem, which generalizes both of the preceding results, will be of general interest. show that in fact the second argument in (5) is always binding, and hence we can apply our general theorem with f (D) = min{k/(D + 1), 1} and g(D) = D. For our target utilization algorithm, since the first argument in (5) equals γ k by construction, we can similarly apply our general Bernoulli theorem by setting f to the second argument. In both cases, the result of our theorem allows us to ultimately show that the worst case occurs either as: (i) n → ∞ and each p i is infinitessimally small (approaching a Poisson distribution); or (ii) when n is finite and there are many p i 's equal to 1. We emphasize that this last part still requires a careful and non-trivial analysis, requiring properties about the unimodality and log-concavity of the distribution D p , as well as bounds using Le Cam's theorem. At the end of the day, we arrive at exactly the lower bounds in Theorems 2 and 3, where we note that the worst case is (ii) only for our target demand algorithm when k ≤ 4. Comparison with uniform arrival times in [0,1]. The technique used by Ehsani et al. (2018) to analyze random-order arrivals is based on having the applicants draw independent, uniformly random arrival times from [0,1], which is consistent with them arriving in a uniformly random order. We provide a detailed comparison between our analysis in the special case k = 1, and theirs (Ehsani et al. 2018 , Section 5). Their analysis is based on lower-bounding the probability of the item remaining at any instant in [0,1], calculated by integrating over arrival times. They treat both valuations and arrival times as being random in this integration, and derive a nice analytical lower bound on this probability, leading to the tight guarantee of 1 − 1/e when k = 1. By contrast, our bound is based on the interpretation that all valuations are drawn before any arrivals occur. This leads to a simple new expression (4). Although our analysis for k = 1 is arguably more complex than theirs, it generalizes neatly to arbitrary k > 1. This section presents the first step in our proof, which shows that the performance of any static threshold policy can be lower bounded using only the distribution of demand D t (V), rather than all of the information conveyed by the distributions F. We denote the set of positive integers by N, the set of non-negative integers by N 0 , and the set of non-negative real numbers by R + . When choosing a threshold t, there is a tradeoff. If the threshold t is too high, many items will remain unallocated. If t ∈ R + is too low, there is a risk that a highvalue applicant will arrive after all items have been allocated. We capture each of these risks using simple functions of the realized demand. For k ∈ N and d ∈ N 0 , define The letters UT stand for "utilization": when realized demand is d, UT k (d) gives the fraction of items that are allocated. Meanwhile, the letters AR stand for "acceptance rate": because applicants arrive in random order, an agent who competes with d others for k items will be accepted with probability AR k (d). Intuitively, for any fixed threshold, UT captures the risk from possible underallocation, while AR captures the risk from possibly allocating items too quickly. Proposition 3 justifies this interpretation. Before stating this result, we define the following notation. Definition 1. For k ∈ N and any distributions F = {F i } n i=1 , let OMN k (F) denote the prophet's value (that is, the expected sum of the k highest values), and let ST t k (F) denote the expected value from a static threshold of t. Proposition 3. For all k ∈ N, t ∈ R + and all F, This result is analogous to Lemma 1 in Chawla et al. (2020) . However, they assume a worst-case arrival order, in which the risk from allocating items too quickly is higher than in our randomarrival model. Correspondingly, they capture this risk with PV ∼F (D t (V ) < k). By using the function AR k , we are able to get the improved bounds depicted in Figure 1 . We will use Proposition 3 to bound the performance of the algorithms described in the introduction. We now introduce notation to define these algorithms formally. and let T D k (F) denote the expected value from the static threshold algorithm with threshold td k . Let tu k (F) denote the threshold satisfying and let T U k (F) denote the expected value from the static threshold algorithm with threshold tu k . We now establish the following result. Lemma 1. For all k ∈ N and all F, Lemma 1 states that when setting a threshold so that expected demand is equal to k, expected utilization is weakly higher than the expected acceptance rate. Along with Proposition 3, this implies that for any k ∈ N and any distributions F, Meanwhile, it follows from Proposition 3 and the definition of T U k that for any F, To prove Theorems 2 and 3, it remains to find the choice of distributions F that minimize the lower bounds in (8) and (9). Note that these lower bounds depend on F only through the parameters . Motivated by this, Section 4 studies the problem of choosing probabilities p i to minimize our lower bounds. In the previous section we derived lower bounds on the performance of the target demand algorithm T D k and target utilization algorithm T U k , in terms of the probabilities p 1 , . . . , p n of each agent's value clearing the threshold t. We now choose these probabilities to minimize our lower bounds. To do so, we study a class of optimization problems over independent Bernoulli random variables. For any positive integer n and p = (p 1 , . . . , p n ) ∈ [0, 1] n , let D p denote the sum of independent Bernoulli random variables with means p 1 , . . . , p n (this is often referred to as the "Poisson Binomial" distribution). For any f, g : Remark 1. We write "min" instead of "inf" in (10) because assuming (10) is feasible, the infimum is actually achieved. To see this, note that for any f and g, both E[f (D p )] and E[g(D p )] are continuous functions of p. Therefore, the set of p satisfying E[g(D p )] = φ is compact. Since (10) takes the infimum of a continuous function over a non-empty compact set, the set of optimal solutions is itself a non-empty compact set. We also note that if (10) is feasible, then it is also feasible for all larger n, and has a weakly lower objective value. If we let ID denote the identity function, then (8) implies that Meanwhile, (9) implies that The remainder of this section is dedicated to analyzing the optimization problems Φ n (AR k , UT k , γ k ) and Φ n (AR k , ID, k) appearing in above. We first prove a generic result about the structure of an optimal solution for any f and g. Theorem 4. For any n, f, g, φ such that (10) is feasible, there is an optimal solution p in which every non-degenerate p i is equal. This result seems quite powerful, and somewhat surprising. 2 It says that when optimizing over all possible demand distributions D p , it suffices to consider cases where D p is equal to a constant plus a binomial distribution. Corollary 2.1 in Hoeffding (1956) establishes this result for arbitrary f when g is the identity, and Lemma 7 of Chawla et al. (2020) establishes this result when f = UT k and g(d) = 1(d < k). We show that the same result holds for arbitrary f and g. Allowing for some number of 0 probabilities and some number of 1 probabilities was necessary for optimality in general, as seen in Hoeffding (1956) . We name this result a theorem because it seems likely to be useful in other applications. We now refine this result in the special case where f = AR k and g is the identity. Proposition 4. For all k, n ∈ N with n > k, the optimization problem for Φ n (AR k , ID, k) has an optimal solution in which every nonzero p i is equal. We now turn to the case where f = AR k and g = UT k , and show that the optimal solution occurs when D p follows a binomial distribution. Proposition 5. For all k, n ∈ N, with n > k, and all φ ∈ (0, 1), the optimization problem Φ n (AR k , UT k , φ) has an optimal solution in which all p i are equal. Step Three: Completing the Proofs of Theorems 2 and 3 We now combine the results from Sections 3 and 4 to prove Theorems 2 and 3. Proposition 3 and Lemma 1 imply that Proposition 4 implies that Φ n (AR k , ID, k) must equal E[AR k (D p )] for some probability vector p consisting of n ≤ n non-zero probabilities, all of which are identical. The constraint E[D p ] = k, implies that this identical probability is k/n , with n ≥ k. Furthermore, Remark 1 notes that Φ n is monotonically decreasing. Thus, we have Note that when n = k, the expression on the right is k/(k + 1), and as n → ∞, Le Cam's theorem implies that it approaches E[AR k (Pois(k))], which is equal to γ k by Lemma 2. Therefore, to complete the proof, all that remains is to show that either n = k or n → ∞ is the worst case: inf n≥k E[AR k (Bin(n, k/n))] = min When k ≤ 4, k/(k + 1) ≥ γ k . By Le Cam's theorem, E[AR k (Bin(n, k/n))] ≥ γ k − 2k/n 2 . For n ≥ 42, this is larger than k/(k + 1). Figure 2 verifies that E[AR k (Bin(n, k/n))] ≥ k/(k + 1) for n < 42, completing the proof for k ≤ 4. Figure 2 also plots k ∈ {5, 6, 7, 8}, showing that E[AR k (Bin(n, k/n))] approaches γ k from above as n → ∞. Lemma 11 in Appendix D.1 establishes (11) in the case k > 8, using two lemmas which allow us to algebraically bound the value of E[AR k (Bin(n, k/n))] for large values of k and n. Proposition 3 implies that Value of the expression on the left of (11), for varying k and n (along x axis). Dashed lines represent the lower bound min k k+1 , γ k . When k ≤ 4 (left graph), the minimum value of k k+1 is obtained at n = k. When k ≥ 5 (right graph), the minimum value of γ k is obtained as n → ∞. Meanwhile, if we define p n to be the solution to then Proposition 5 implies that Lemma 12 in Appendix D.2 establishes that p n ≤ k/n. From this, (14) and the fact that AR k is weakly decreasing implies Because Φ n is weakly decreasing in n (see Remark 1), it follows that where the third line follows from Le Cam's theorem and the final line is established by Lemma 13 in Appendix D.2. Combining (16) with (12) completes the proof. We now show that when k applicants can be accepted, the value of a static threshold policy cannot exceed γ k times the prophet's value, even if values are IID. We begin with Lemma 2, which establishes several useful identities for Poisson random variables. We then establish Lemmas 3 and 4, which lower-bound the prophet's value and upper-bound the value of any static threshold policy. Theorem 1 follows immediately by combining Lemmas 3-4 and taking n → ∞. In the remainder of this paper we let Pois(λ) denote a Poisson random variable with rate λ. We also note that for any random variable N on the non-negative integers, Lemma 2. For any k ∈ N and λ ≥ 0, we have and therefore E[min(Pois(k), k)] = kγ k . In addition, For k ∈ N we define Lemma 3. On Example 1, the prophet's value is at least k + W k − 1+W k n+1 . Lemma 4. On Example 1, the value of any static threshold algorithm is at most γ k (k + W k ) + 2kW k (n −2/3 + n −1/3 ). Our results precisely characterize the performance of static threshold policies in the prophet secretary problem. They also improve the best-known guarantees for online policies when k > 1. In addition, our work provides operational insights on how to achieve these guarantees. One natural heuristic is to try to balance supply and demand by setting a threshold so that the expected size of the eligible population is equal to the number of available items. We provide justification for this heuristic by showing that when k ≥ 5, it gives an optimal worst-case guarantee of γ k . Furthermore, this guarantee is large enough to be reassuring: for a vaccination clinic with k = 100 doses, this policy guarantees γ 100 > 96% of the omniscient benchmark. Although we assume that the policymaker knows the distribution of applicants' values, our algorithms and analysis in fact require far less information, as we now discuss. In practice, it may be difficult to determine the exact value of allocating to each applicant. One advantage of our policies is that they only require the policymaker to determine which applicants are highest-value. They do not require knowledge of how much higher one applicant's value is than another. This is useful in settings where only a monotone transformation of values (rather than the values themselves) can be observed. We illustrate this point using the application of COVID-19 vaccination. If the policymaker's goal is to minimize the expected number of deaths, then we can think of the value of vaccinating an individual as their pre-vaccination mortality risk. 3 However, mortality risk is not observed, and may be difficult to estimate. Instead, policymakers use proxies such as age and underlying medical conditions. For this discussion, suppose that the policymaker plans to use an age-based eligibility rule, and that mortality risk is an increasing function of age. Note that the optimal eligibility threshold depends on the exact relationship between age and mortality risk. If only the very elderly face a significant risk of death, then it makes sense to restrict eligibility to this population, even if that means that some doses go to waste. Conversely, if the risk of death is similar for all ages, then eligibility should be expanded, even if that means that some middle-aged people may receive the vaccine before the elderly population is fully vaccinated. By contrast, so long as mortality risk increases with age, the eligibility thresholds selected by our policies do not depend on the exact relationship between the two. Instead, our policies can be implemented using only the distribution of applicants' ages, which may be much easier to estimate. Our policies require policymakers to estimate expected demand or expected utilization, as a function of the eligibility threshold. In some cases, this may be difficult. Even when this is possible, political and other considerations may cause policymakers to use thresholds which differ from those suggested by our algorithms. Our analysis is also useful in these cases, as for any static threshold policy, we provide a guarantee which depends only on their expected utilization. In particular, Proposition 3 shows that the performance of a static threshold policy is lower-bounded by the minimum of its expected utilization and expected acceptance rate, and Proposition 5 allows us to lower-bound the expected acceptance rate as a function of expected utilization. Combining these yields guarantees shown in Figure 3 . In settings where a particular threshold has been used repeatedly, estimating expected utilization at that threshold may be easy, even if estimating utilization at other thresholds is not. In such cases, the bounds in Figure 3 can be used to provide an ex-post assessment of the chosen threshold. In this paper, we focus on policies based on expected demand or expected utilization. However, a similar analysis should be possible for many other metrics of interest. In particular, one could consider a general class of "demand statistic" policies. These policies are defined by a monotonic function g : N → R and a constant φ, and choose the threshold t so that E[g(D t )] = φ. Our expected demand policy is one example, with g(d) = d and φ = k. Meanwhile, our expected utilization policy takes g(d) = min{ d k , 1} and φ = γ k . Demand statistic policies inherit the advantages that we discuss above. They are robust to a monotone transformation of values, enabling their use when only proxies for value are available. Additionally, many organizations already track such statistics, and may therefore have good estimates of E[g(D t )], even if they don't know the full demand distribution. For these reasons, developing performance guarantees based on other demand statistics seems like a worthwhile direction for future work. Theorem 4 provides a useful starting point for this exploration, by simplifying the search for a worst-case demand distribution. One natural question is, which demand statistics g can deliver optimal guarantees, when paired with an appropriate choice of φ? Our work shows that expected utilization policies can, while expected demand policies can if k ≥ 5 but cannot if k < 5. One particularly natural demand statistic to consider is g(d) = 1(d ≥ k), so that E[g(D t )] gives the stockout probability. When k = 1, Ehsani et al. (2018) show that setting a static threshold such that the stockout probability is 1 − 1/e provides an optimal guarantee of γ 1 = 1 − 1/e. In fact, when k = 1, stockout probability is equivalent to expected utilization, so their algorithm coincides with our own. We propose the following generalization of their algorithm for k > 1: set the threshold such that the stockout probability is equal to P(Pois(k) ≥ k). For large k, this means that the stockout probability is just slightly above 1/2. This is a simple policy to explain and implement, and we conjecture that it also guarantees a γ k fraction of the prophet's value. Proof of Proposition 1. Throughout, let F denote the distribution from which each V i is drawn, and let t denote the threshold set by the target demand algorithm T D k . This algorithm Meanwhile, by Lemma 5, Combining these, we see that where we have used the fact that D t (V ) ∼ Bin(n, k/n). By Le Cam's theorem, as n → ∞, Bin(n, k/n) → Pois(k), and the ratio above converges to E[min(Pois(k), k)]/k, which equals γ k by Lemma 2. Proof of Proposition 2. We prove this result in two cases. If d < k, then we can consider the degenerate case in which each variable is identically one. In this case, the static threshold policy accepts each item with probability d/n, and its expected value is the expected number of accepted items, which is E[min(k, Bin(n, d/n))]. As n grows, the fact that d < k implies that this value converges to a constant strictly less than k · γ k . Meanwhile, the prophet's value is equal to k. If d > k, then we can consider the case in which n − 1 values are identically zero, and the remaining value is n with probability 1/n, and zero otherwise. Then the Prophet's value is one. Meanwhile, when n is large, the static threshold policy accepts each zero value item with probability approximately d/n, implying that demand is approximately Poisson distributed with mean d. It follows that when there is an item of value n, it is accepted with probability approximately E[min(1, k 1+Pois(d) )], which is strictly less than γ k because d > k · γ k . Appendix B: Proofs From Section 3 To prove Proposition 3, we define Proposition 3 follows immediately from the following lemmas. Lemma 5. For all k ∈ N, t ∈ R + and all F, Proof of Lemma 5. For any t ∈ R + , we have Lemma 6. For all k ∈ N, t ∈ R + and all F, In our proof, we fix t, and define D i . We write D, D i and D −i , leaving the dependence on V implicit. The following identity can be quickly verified by sequentially considering the cases D < k and D ≥ k: Proof of Lemma 6. Suppose that D i = 1. If competing demand D −i is less than k, then i will certainly be accepted. Otherwise, i is accepted with probability k/(1 + D −i ). From this observation, we can lower bound the performance of any static threshold policy as follows. The fourth line uses (22), the fifth uses the fact that D −i and V i are independent, and the inequality uses the fact that D ≥ D −i and AR k is weakly decreasing. Proof of Lemma 1. We use D, D i and D −i as shorthand for Proof of Lemma 7. We prove this result in several cases. Case 1a: A 2 = 0, A 1 = 0. In this case, if (24) is feasible, then its equality constraint is redundant. Note that the gradient of the objective function at a point (p 1 , p 2 ) is (B 1 + B 2 p 2 , B 1 + B 2 p 1 ). If (p 1 , p 2 ) is a local minimum, then this gradient must equal (0, 0). This can only occur if p 1 = p 2 or B 2 = B 1 = 0 (in which case all feasible points are optimal). This establishes Statement (1) in case 1a. Case 1b: A 2 = 0, A 1 = 0. Then p 1 + p 2 = (φ − A 0 )/A 1 , which makes B 2 p 1 p 2 the only variable term in the objective function to be minimized. If B 2 < 0, then the objective value is strictly reduced by setting p 1 and p 2 to be equal. This proves Statement (2) in case 1b. If B 2 > 0, then the objective value is strictly reduced by setting at least one of p 1 or p 2 to be an extreme point in {0, 1}. If B 2 = 0, then all feasible solutions have the same objective value. Combined, these arguments also establish Statement (1) in case 1b. Case 2: A 2 = 0. Define Then (24) can be reformulated as Case 2a. A 2 = 0, γ = 0. At least one of q 1 , q 2 must be 0. WLOG assume q 1 = 0 and consider the optimization problem over q 2 ∈ [A 1 /A 2 , A 1 /A 2 + 1]. If C 1 < 0, then the unique optimal solution is q 2 = A 1 /A 2 + 1 (i.e. p 2 = 1); if C 1 > 0, then the unique optimal solution is q 2 = A 1 /A 2 (i.e. p 2 = 0); if C 1 = 0, then all feasible solutions are optimal. Moreover, if C 1 < 0 and A 1 /A 2 ≤ −1, then γ = 0 is only feasible if A 1 /A 2 = −1, in which case the unique optimal solution is q 1 = q 2 = 0 (corresponding to p 1 = p 2 = 1). This establishes both Statements (1) and (3) in case 2a. Case 2b. A 2 = 0, γ = 0. In this case we cannot have q 1 = 0, so substitute q 2 = γ/q 1 , making the objective function C 0 + C 1 (q 1 + γ/q 1 ). If C 1 = 0, then all feasible solutions are optimal. If C 1 = 0, then the derivative of the objective can equal zero only if 1 − γ/q 2 1 = 0, in which case q 1 = q 2 (and thus p 1 = p 2 ). Therefore, there is no local minimum with (p 1 , p 2 ) ∈ (0, 1) 2 and p 1 = p 2 . It follows that when C 1 = 0, any global minimum either has p 1 = p 2 or lies on the boundary. This establishes Statement (1) in case 2b. Turning to Statement (3), note that if A 1 /A 2 ≤ −1, then q 1 , q 2 ≤ 0, so the problem is infeasible for γ < 0. Thus, assume γ > 0 and q 1 , q 2 < 0. The second derivative of the objective equals 2C 1 γ/q 3 1 which is strictly positive. By strict convexity, the unique global minimizer must arise at the local minimum where q 1 = − √ γ. Furthermore, if q 1 q 2 = γ has a solution in [A 1 /A 2 , A 1 /A 2 + 1] 2 , then it follows that − √ γ ∈ [A 1 /A 2 , A 1 /A 2 + 1], and therefore the global minimizer is feasible. This establishes Statement (3) in case 2b. Equipped with Lemma 7, we now prove our general Theorem 4 about the existence of an optimal solution p ∈ [0, 1] n satisfying particular properties. Proof of Theorem 4. Suppose for contradiction that all optimal solutions have at least two distinct non-{0,1} probabilities. Select an optimal solution p which maximizes the number of probabilities in {0,1}, which can be at most n − 2 because there must exist indices i, j for which 0 < p i < p j < 1. Relabel these indices i, j to be 1, 2, and consider the problem of optimizing p 1 and p 2 , holding all others fixed. By (23), this is a version of the optimization problem (24). Because we have an interior optimal solution where the two probabilities are unequal, statement 1 of Lemma 7 implies that all feasible solutions must have the same objective value. Note that p 1 and p 2 can be modified to make one of them lie in {0, 1} while preserving feasibility. This leads to an alternate optimal solution which has strictly more probabilities in {0,1}, causing a contradiction and completing the proof. In what follows, we use several established facts about the sum of independent Bernoulli random variables, which we collect in the following lemma. Lemma 8. Fix n ∈ N and p ∈ [0, 1] n , and let λ = E[D p ] = n i=1 p i . For j ∈ N 0 , let h j and H j denote the density and cdf of D p at j. Then 1. The support {j : h j > 0} is an interval. The density h is log-concave, meaning that for all j ≥ 1, Furthermore, this inequality is strict whenever h j > 0. 3. The density h is unimodal, with mode ∈ { λ , λ }. That is, 4. For any j ≥ 2, Proof of Lemma 8. The first fact is obvious. The second is shown by Samuels (1965) , and the third is shown by several papers, including Darroch (1964) , Samuels (1965) , and Wang (1993) . The final fact follows because if the distribution of D p is log-concave, then so is the distribution of n − D p , and log-concave distributions have increasing hazard rates (see An (1995) , Proposition 10). Proof of Proposition 5. If φ > 1, then the optimization problem is infeasible. If φ = 1, then the unique optimal solution is p i = 1 for all i. Therefore, we assume that φ < 1. It follows from the definition of UT in (6) that for any feasible solution, Furthermore, we claim that for any optimal solution, we must have This follows because p i = φ/k for i ∈ {1, . . . k} and p i = 0 for i > k is a feasible solution (that is, and satisfies (27). Take a feasible solution p in which p i = p j . We will show that this solution is not optimal. Without loss of generality, relabel so that i = 1, j = 2, and consider optimizing p 1 and p 2 with all other probabilities fixed. Let h and H denote the density and CDF of the sum of variables {3, 4, . . . n}. We face an optimization problem in the form (24), with Note that the second inequalities for A 1 and A 2 above follow from the observations Meanwhile, we have We first consider the case where A 2 = 0, and then the case where A 2 = 0. Case 1. A 2 = 0. It follows from Lemma 8 part 1 that either or h j = 0 for all j ≤ k − 1. The latter case contradicts the feasibility constraint (26), so (34) must hold. It follows from (34) and (28) that A 1 = 1/k. Furthermore, (31) and (33) imply B 2 = −h k−2 /(k + 1). Thus, B 2 = 0 implies h k−2 = 0, which further implies that D p is at most k − 1 and that E[AR k (D p )] = 1. This contradicts the optimality condition (27). If B 2 < 0, then the second statement of Lemma 7 implies that p cannot be optimal. Case 2. A 2 = 0. By statement 3 of Lemma 7, p is sub-optimal if the following conditions hold: By (28) and (29), (35) holds. All that remains is to show (36). For j ∈ N, define C j = k(k + 1) (j + 1)(j + 2) , and note that 2k(k + 1) (j + 1)(j + 2)(j + 3) = C j − C j+1 . By (28) and (29), A 2 = 0 implies H k−1 ≥ h k−1 > 0. By (28), (29), (32) and (33), we have Part 4 of Lemma 8 implies that and therefore each term in (37) is non-positive, with some term strictly negative. This implies that (36) holds, and therefore by Statement 3 in Lemma 7, that p cannot be optimal. Proof of Proposition 4. By Theorem 4, there exists an optimal solution in which each p i ∈ {0, p, 1}, for some p ∈ (0, 1). Thus, to prove Proposition 4, it suffices to show that any feasible solution which has this property and has p i = p, p j = 1 for some i, j is not optimal. Without loss of generality, relabel so that i = 1 and j = 2. Consider the problem of optimizing over p 1 and p 2 , holding the remaining probabilities fixed. This is a version of the optimization problem (24), in which A 1 = 1, A 2 = 0, and If B 2 < 0, then statement 2 in Lemma 7 implies that our solution is not optimal. Therefore, all that remains is to show that B 2 < 0. Note that . Note that for ≥ k − 1, we have ∞ j= C j = k(k + 1) ( + 1)( + 2) . In particular, taking = k − 1 we see that the C j sum to one. By (38) we have Showing that this is negative is equivalent to showing that h k−2 is larger than a C j -weighted average of h j for j ≥ k − 1. Because p 1 = p, p 2 = 1, the constraint From this and (39) we have We wish to establish that this expression is negative. Because indexes with p i = 0 are irrelevant, we can assume without loss of generality that there are n nonzero p i . Let d be the number of indices i with p i = 1 in our initial solution, so n − d is the number of indices with p i = p. Because n − d ≥ 1 by assumption and i p i = d + p(n − d) = k, we must have Noting that d − 1 ≤ k − 2 by (42), we can use (44) to rewrite the right side of (41) as The sign of this expression is determined by the second term. Substituting (43) into this term, we see that it is equal to This is clearly negative, as both fractions multiplying k k+2 are strictly less than one. Appendix D: Proofs From Section 5 D.1. Proofs from Section 5.1 Lemma 9. For all integers n ≥ k ≥ 1, we have that E[AR k (Bin(n, k n ))] ≥ 1 − ϕ k (n), where ϕ k (n) = 1 − k n + 1 P[Bin(n, k n ) = k] + 1 2(n + 1) . Proof of Lemma 9. We can derive that E[AR k (Bin(n, k/n))] = P[Bin(n, k/n) < k] + n d=k k d + 1 = P[Bin(n, k/n) < k] + n n + 1 P[Bin(n, k/n) > k] + k n P[Bin(n, k/n) = k] where the penultimate equality holds because by independence, Bin(n + 1, k/n) > k if and only if either (i) there are at least k successes in the first n trials; or (ii) there are exactly k successes in the first n trials and the n + 1'st trial is also successful. The proof is then completed by the fact that the median of a Bin(n, k/n) random variable is k, which implies that P[Bin(n, k/n) > k] ≤ 1/2. we have that for all n ≥ k + 2, where the RHS of (46) in increasing in n. Proof of Lemma 10. Define ψ k (n) = (1 − k n+1 )P[Bin(n, k n ) = k], which equals the first term in ϕ k (n). We can derive that Taking the ln of ψ k helps us evaluate its derivative: n d =n−k+1 1/d represents a right Riemann sum for the integral n n−k (1/x)dx. Since 1/x is decreasing, the area under the curve 1/x from x = d − 1 to x = d is greater than 1/d , for all d = n − k + 1, . . . , n. Moreover, since 1/x is convex, this difference is upper-bounded by the area of a triangle with base 1 and height 1 d −1 − 1 d . Therefore, We now use the fact that P[Bin(n, k/n) = k] ≥ e −k k k /k! to lower bound the expression in large parentheses by noting that 1 − 1 n − 1 n−k − 1 n(n−k) ≥ 0 when n ≥ k + 2. Therefore, where the expression is large parentheses is now clearly increasing in n. This completes the proof. Lemma 11. For k > 8, (11) holds. Proof of Lemma 11. Case 1: k ≥ 31. Applying Lemma 10, since the RHS of (46) is increasing in n, we see that for all n ≥ k + 2, we have ) − 1, whose RHS can be numerically verified to be positive for all k ≥ 31. Therefore, ϕ k (n) is increasing over n ≥ k + 2 and we have that Meanwhile, by Lemma 9, we have that where the final equality applies (47) Case 2: 9 ≤ k ≤ 30. Applying Lemma 10, since the RHS of (46) is increasing in n, we see that for all n ≥ k + 11, we have 2(n + 1) 2 ϕ k (n) ≥ k e −k k k k! (1 − 1 k + 11 − 1 11 − 1 11(k + 11) ) − 1, whose RHS can be numerically verified to be positive for all k ≥ 9. This demonstrates that ϕ k (n) is increasing over n ≥ k + 11. However in fact, ϕ k (n) is increasing over integers n ≥ k + 1, for all 9 ≤ k ≤ 30, as we numerically demonstrate in the table of values in Figure 4 . Therefore, for all 9 ≤ k ≤ 30, we have sup n≥k+1 ϕ k (n) = lim n→∞ ϕ k (n) = e −k k k k! , and applying Lemma 9, this implies that inf n≥k E[AR k (Bin(n, The minimum can be numerically verified to equal the final argument for all 9 ≤ k ≤ 30. Lemma 12. If p n is defined as in (13), then (15) holds (that is, p n ≤ k/n). Proof of Lemma 12. Applying (17), we see that for any demand distribution D, Theorem 4 in Hoeffding (1956) implies that for j < k, P(Bin(n, k/n) ≤ j) is decreasing in n, so where the first equality follows from Le Cam's theorem, the second from the identity UT k (D) = 1 k min(D, k) and Lemma 2, and third from (13). Since UT k is an increasing function, E[UT k (Bin(n, p)] is increasing in p, so (49) implies that p n ≤ k, completing the proof. Values of ϕ k (k + ), for all 9 ≤ k ≤ 30 and 1 ≤ ≤ 11. Note that the values in every row, which correspond to a fixed k, are increasing. k = 1 = 2 = 3 = 4 = 5 = 6 = 7 = 8 = 9 = 10 = 11 Proof of Lemma 3. The prophet accepts any buyers whose values realize to the high value of nW k , and then fills any remaining of the k slots with buyers whose values are 1. We can lowerbound the prophet's value as follows: assume that the prophet collects k if there are no high-value realizations, and that the prophet collects k + nW k − 1 if there is at least one high-value realization. The value of this lower bound is k + (nW k − 1) 1 − 1 − 1 n 2 n ≥ k + (nW k − 1) 1 − 1 1 + 1/n = k + W k − 1 + W k n + 1 . The inequality uses the fact that for p ∈ [0, 1] and n ∈ N, (1 + pn)(1 − p) n ≤ 1. Proof of Lemma 4. Clearly any algorithm should accept the high value of nW k , so we can restrict our search to fixed-threshold algorithms parameterized by a probability p ∈ [0, 1] of accepting the lower value of 1. Then each of the n agents clears the threshold independently with probability q = 1/n 2 + (1 − 1/n) 2 p, and the expected number of accepted agents is E[min{Bin(n, q), k}]. Conditional on an agent being accepted, the expectation of her value is 1/n 2 1/n 2 + (1 − 1/n 2 )p · nW k + (1 − 1/n 2 )p 1/n 2 + (1 − 1/n 2 )p · 1 ≤ W k nq + 1. Therefore, the expected value collected by any fixed-threshold algorithm is at most max q∈[1/n 2 ,1] E[min{Bin(n, q), k}] W k nq + 1 . We now consider two cases: either q > n −2/3 or q ≤ n −2/3 . If q > n −2/3 , then nq > n 1/3 and hence the value of (54) is less than k(W k n −1/3 + 1) = k + kW k n −1/3 . Furthermore, γ k > 1/2 and W k ≥ k implies that γ k (k + W k ) > k. In the other case where q ≤ n −2/3 , we note that where we have used Le Cam's theorem to bound the total variation distance between a Bin(n, q) random variable and a Pois(nq) random variable. We conclude that the value of (54) is at most E[min(Pois(nq), k)] W k nq + 1 + 2kW k n −2/3 + 2kn −1/3 . We claim that the first term is maximized when nq = k, when it equals E[min(Pois(k), k)] W k k + 1 = γ k (k + W k ), where the equality follows from Lemma 2. All that remains is to prove that the function E[min(Pois(λ), k)] W k λ + 1 is maximized at λ = k. Using the final part of Lemma 2, we see that the derivative of the function with respect to λ is where the equality follows from Lemma 2 and the definition of W k in (20). In (55), the derivative is clearly seen to be 0 when λ = k. Our goal is now to show that the derivative is positive when λ < k, and negative when λ > k, thereby establishing that the maximum occurs at λ = k. First suppose that λ < k. Then = j>k λ j−2 /j! j>k k j−2 /j! j k. Then we can similarly derive Substituting into (55) shows that the derivative is negative when λ > k, completing the proof. Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers Log-concave probability distributions: Theory and statistical testing Prophet secretary: Surpassing the 1-1/e barrier Improved revenue bounds for posted-price and second-price mechanisms Static pricing for multi-unit prophet inequalities Posted price mechanisms for a random stream of customers Recent developments in prophet inequalities Prophet secretary through blind strategies On the distribution of the number of successes in independent trials Prophet secretary for combinatorial auctions and matroids Prophet secretary Optimal contest design for simple agents Automated online mechanism design and prophet inequalities Comparisons of stop rule and supremum expectations of iid random variables On the distribution of the number of successes in independent trials Semiamarts and finite values Lieber R (2021) How to get the coronavirus vaccine in new york city. The New York Times After unused vaccines are thrown in trash, cuomo loosens rules On the number of successes in independent trials On the number of successes in independent trials Mechanism design via correlation gap In this section we prove the statements from Section 4, which are about the Bernoulli optimization problem defined as Φ n (f, g, φ). To prove these statements, we suppose that n ≥ 2 (note that the statements are vacuously true if n = 1) and consider the problem of re-optimizing the pair of probabilities p 1 , p 2 while holding all other probabilities fixed.Let D − p denote the sum of n − 2 independent Bernoulli random variables with means p 3 , . . . , p n . We note that for any function f : N → R,Note that the terms inside of the expectation operators do not depend on p 1 or p 2 . This motivates the study of optimization problems of the following form.Lemma 7. If the optimization problem (24) is feasible, then:1. Any feasible solution in the interior (0, 1) 2 with p 1 = p 2 is suboptimal, unless all feasible solutions have the same objective value.2. If A 2 = 0, A 1 = 0, and B 2 < 0, then any solution with p 1 = p 2 is suboptimal.3. If A 2 = 0, A 1 /A 2 ≤ −1, and B 1 − B 2 A 1 /A 2 < 0, then any solution with p 1 = p 2 is suboptimal.Proof of Lemma 13. Note that for any λ ≥ 0, Therefore, the remaining claims follow from Lemma 2. Proof of Lemma 2. For any random variable D, we haveWhen D is Poisson with mean λ,Combining (50) and (51) yields (18). From this, it follows thatWe now turn to (19). By (17) From (52) and (53), (19) follows immediately.