IID Prophet Inequality with Random Horizon: Going Beyond Increasing Hazard Rates
Abstract
Prophet inequalities are a central object of study in optimal stopping theory. In the iid model, a gambler sees values in an online fashion, sampled independently from a given distribution. Upon observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds to observe the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (the offline maximum). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations.
This model has been studied with infinite, finite and unknown number of values. When the gambler faces a random number of values, the model is said to have a random horizon. We consider the model in which the gambler is given a priori knowledge of the horizon’s distribution. Alijani et al. (2020) designed a single-threshold algorithm achieving a ratio of when the random horizon has an increasing hazard rate and is independent of the values. We prove that with a single threshold, a ratio of is actually achievable for several larger classes of horizon distributions, with the largest being known as the class in reliability theory. Moreover, we show that this does not extend to its dual, the class (which includes the decreasing hazard rate class), while it can be extended to low-variance horizons. Finally, we construct the first example of a family of horizons, for which multiple thresholds are necessary to achieve a nonzero ratio. We establish that the Secretary Problem optimal stopping rule provides one such algorithm, paving the way towards the study of the model beyond single-threshold algorithms.
Keywords and phrases:
Online algorithms, Prophet Inequality, Random Horizon, Secretary ProblemCategory:
Track A: Algorithms, Complexity and GamesFunding:
Giordano Giambartolomei: EPSRC grants EP/W005573/1 and EP/X021696/1.Copyright and License:
![[Uncaptioned image]](x1.png)
2012 ACM Subject Classification:
Theory of computation Design and analysis of algorithmsAcknowledgements:
We would like to thank José Correa for his precious advice, Bruno Ziliotto and Vasilis Livanos for early conversations.Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Prophet inequalities are a central object of study in optimal stopping theory. A gambler sees nonnegative values in an online fashion, sampled from an instance of independent random variables with known distributions , in adversarial, random or selected order, depending on the particular model. When observing each value, the gambler either accepts it as a reward, or irrevocably rejects it and proceeds with observing the next value. The goal of the gambler, who cannot see the future, is to maximise the expected value of the reward while competing against the expectation of a prophet (out of metaphor, the offline maximum or supremum, depending on whether the instance is finite or not). In other words, one seeks to maximise the gambler-to-prophet ratio of the expectations.
The gambler represents any online decision maker, such as an algorithm or stopping rule. Probabilistically, we will refer to it as a stopping time . Informally, the term online implies that the gambler, unable to see the future, will always stop at a time such that the event depends only on the first values observed.
1.1 Prophet inequality models
Several models and extensions of prophet inequalities are present in the literature. We introduce the variants upon which our model is built, briefly reviewing the state-of-the-art.
The very first prophet inequality model, typically referred to as classical Prophet Inequality (PI), is due to Krengel and Sucheston [25, 26]. The given instance is composed of countably many integrable independent nonnegative random variables with known distributions in a fixed given order, usually referred to as adversarial. The gambler-to-prophet ratio to be maximised will therefore be over . When working with infinite instances, one often considers only finite stopping rules () and variables such that . The -hardness of PI (shown by Garlin [25]) is tight [26]. A single-threshold -approximation is also possible [35].
IID PI is specialised to independent and identically distributed (iid) according to a given distribution . The hardness of this problem is , where is theoretically derived as solution to an integral equation [21]. The -approximation quantile strategy devised in [10] makes the aforementioned hardness tight.
IID Prophet Inequality with Random Horizon
The IID PI with Random Horizon (RH) was first introduced in [17]. Consider a random variable , which we will call the (random) horizon, with given discrete distribution , that is, supported on an arbitrary subset of . This assumption comes with no loss of generality (formally, it rules out that the horizon has mass at zero). will be assumed finite () and integrable (), which we denote . RH is a relaxation of IID PI, considering integrable iid random variables , with given distribution independent of . This setup, supported on a probability space , models the game where the gambler, facing an unknown number of values , can still use a priori knowledge of when maximising returns. More precisely, denote . The goal is to maximise the gambler-to-prophet ratio of over , where and both expectations run over the randomness of the iid copies of and . The gambler must select the value in ignorance of whether it is the last or not. If the gambler fails to stop by the time the last value is inspected, the return is zero. This ignorance, added to the usual nonanticipative constraint, yields a no easier model than IID PI. On top of the usual disadvantage of playing against a prophet, which knows all future realisations of the values, and chooses the largest; the gambler now competes against a prophet, which can also foresee the random number of values.
1.2 Previous bounds on IID Prophet Inequality with Random Horizon
No constant-approximations are possible for RH [2, Theorem 1.6] (we refer to this by saying that RH is hard). Distributional knowledge of the horizon is not enough to guarantee, in expectation, that the gambler’s return can attain a worst-case constant multiple of the prophet’s return. Therefore, we impose additional restrictions on the distribution of the horizon. The largest distributional class for which a constant-approximation has been found so far is that of horizons with increasing hazard rates . For simplicity, we will use increasing and decreasing instead of nondecreasing and nonincreasing respectively. Recall that the hazard rate of a horizon is defined as follows. Denote the survival function . If , for every , . If , for every , is defined analogously for all , while it is set to for all .
Definition 1 ( and class).
is Increasing Hazard Rate () if for every , . is Decreasing Hazard Rate () if for every , .
One says that and are dual classes, and the geometric distribution is the only discrete distribution that belongs to both of them.
The state-of-the-art for RH consists in the findings of [2]. In [2, Theorem 3.2], through the use of second order stochastic dominance, it is shown that if , , where . This ensures a (uniform) -approximation on the class. Studying monotone hazard rates stems from interpreting RH from a reliability theory point of view: an optimal stopping game under evolving risk (or ageing) that it ends by the next step, and, despite more than years have passed, no progress has been made on classes larger than the class.
1.3 Our contributions
In this paper we contribute to the study of RH by:
-
Extending existing characterisations of the optimal algorithm to unbounded horizons.
-
Complementing and extending key ideas from [2] to yield the existence of single-threshold -approximations on important superclasses of the class, culminating in the class.
-
Showing that the class (dual of the class) admits hard horizons for single-threshold algorithms.
-
Deriving single-threshold constant-approximations for sufficiently concentrated horizons with finite second moments.
-
Showing that RH admits families of horizons for which single-threshold algorithms are not competitive, despite the Secretary Problem (SP) optimal stopping rule providing a constant-approximation (see Section 1.5 for details on SP and its variants).
In this section we give formal statements of the above results, with the exception of Theorem 14 in Section 2, due to the overall degree of technicalities involved. Informally speaking, this theorem characterises the optimal algorithm in terms of a discounted infinite optimal stopping problem, with a special focus on unbounded horizons. As a technical tool, the equivalence of stopping rules for RH with stopping rules for the discounted problem is leveraged not only to obtain hardness results for single-threshold algorithms, but also to formalise heuristic arguments involving the optimal algorithm under geometric horizon. More specifically: we exploit the equivalence between stopping rules for RH and corresponding rules for the discounted problem to extend hardness results to neighbouring instances; we show that with a geometric horizon, if the value distribution is bounded, the optimal algorithm of RH is single-threshold, pinpointing the structural equation for the threshold.
The next three results involve stochastic orders, which we now introduce. Note that several standard facts regarding stochastic orders are often relied upon throughout this work. They will be recalled as remarks, whose proof can always be found in [39]. In the following definitions, and always refer to horizons.
Definition 2 (Probability Generating Function Order).
Given two horizons , , we say that is dominated by in the probability generating function (pgf) order, and denote it as , if for every , .
Remark 3.
if and only if for all , .
The class, consisting of every positive discrete distribution that dominates, in the pgf order, the (-valued) geometric distribution with the same mean, has been introduced in [24].
Definition 4 ( class).
The class consists of every horizon that dominates, in the pgf order, the geometric distribution with the same mean: .
The dual class is obtained by reversing the pgf ordering, and is denoted as . It is well known that , with inclusion being strict. Similarly, . In applications of reliability theory, the classes within and its dual are a staple of modelling many aspects of ageing and more generally of an evolving risk of failure.
Theorem 5.
For all with , a single-threshold -approximation exists.
From [2, Theorem 3.5] it follows that any -approximation on the class is tight. More specifically, the -approximation yielding Theorem 5 is essentially the same as the one used on the class in [2, Theorem 3.1]. The key feature of the stopping rule is to determine the value such that , and then to accept the first value exceeding . The class may be somewhat abstract, compared to its subclasses, which have immediate intuitive interpretations in terms of ageing concepts, such as the class. Its possible interpretations are quite general and go beyond mere ageing, as can be read in [24]. To gain some intuition of how much more general a class it is, the reader is referred to Section 3, where we will describe some of its largest and most well-known subclasses, as evidence that Theorem 5 generalises significantly [2, Theorem 3.1, Theorem 3.2]. We conclude by mentioning that statistical tests for the class (the continuous equivalent of the class) have also been developed [23]. The possibility of adapting them to tests for the class adds to the practical significance of the result.
Our next result requires introducing the stopping rule for SP with deterministic horizon . This consists of rejecting the first values, and subsequently accepting the first value ranked better than all the previous ones. The waiting time as yields the optimal stopping rule (see Section 1.5 for details). In the following, we provide the first example of a family of horizons, for which no single-threshold constant-approximation is possible, and yet an adaptation of the SP stopping rule to random horizons is proven to provide a constant-approximation. The family of horizons we will consider is of the form , with pmf’s parametrised by , large enough and , and will therefore be denoted as . Let be the (optimal) stopping rule for SP with deterministic horizon . Taking the minimum produces a natural adaptation of the SP stopping rule to the random horizon .
Theorem 6.
There exists a family of horizons , such that for all fixed small enough and arbitrary , no single-threshold constant-approximation is possible. Nonetheless, for every fixed , no matter how small, the random horizon SP rule is an approximate constant-approximation, as long as is fixed large enough.
For brevity, we say that the family of horizons is hard for single-threshold algorithms, but the random horizon SP rule is competitive on it. The SP stopping rule only needs information regarding the relative ranks of the values, not the values themselves. Our result opens up a fresh line of investigation into new classes of distributions, to be handled via multiple threshold algorithms, which cannot be accessed via single-threshold algorithms.
Since we showed that single-threshold -approximations exist for the class, finding whether single-threshold constant-approximations exist for the class turns into an interesting problem. The equivalent characterisation of stopping rules for RH in terms of a discounted stopping problem, combined with a perturbation argument on , yields a negative answer.
Theorem 7.
No single-threshold constant-approximation is possible on the class.
In Section 4.2 we will describe more in detail some of the largest and most well-known subclasses of the class. They are no less important than the corresponding subclasses of the class. For example, discrete distributions are crucial in several areas: they have been shown to describe well the number of seasons a show is run before it gets cancelled and the number of periods until failure of a device (a system, or a component, that functions until first failure) governed by a continuous life distribution in the grouped data case [27]. Theorem 7 motivates our conjecture that single-threshold -approximations are not possible on the class either. Since our characterisation result of stopping rules for RH extends to unbounded horizons, it will be a crucial tool in proving this conjecture within our framework, as horizons have support of the form . Furthermore, suitably combining the techniques yielding Theorems 5 and 7 with the fact that the tight geometric instance for -approximations belongs to the class, motivates our second conjecture that the class is essentially optimal for -approximations on horizons.
In our last result, we go back to single-threshold algorithms under horizons satisfying only , denoted . We show that it is possible to exploit concentration bounds, in order to ensure that the same single-threshold algorithm used for the and class is still a -approximation. In the following result, denotes the principal branch of the Lambert function.
Theorem 8.
For every having both and finite, such that
(1) |
a single-threshold -approximation exists.
The Lambert function is readily simulated and one can reliably compute numerically the magnitude of concentration required by 1, so that a -approximation is ensured. To exemplify, we consider the large-market limit, that is, . Under this computationally simpler hypothesis, taking the square root on both sides of 1 yields approximately , where CV is the coefficient of variation of the horizon. Variations on this procedure show that both weaker and stronger than constant-approximations are possible for all suitably concentrated horizons. Consider again the upper bound on CV provided by square-rooting 1 in the large-market limit: . Replacing with yields . This will ensure a weaker -approximation in the large-market limit. As grows, is negative strictly increasing (valued at ) and vanishing. Thus the upper bound on the CV ensuring a -approximation for growing large scales roughly as , meaning that there will be, although progressively weaker, constant-approximations, as long as . In the other direction, stronger -approximations are ensured when taking admissible . When reducing , we clearly cannot go past , as the upper bound on the CV vanishes (approaching a deterministic horizon). At this point, our estimates hit the optimum competitive ratio for single-threshold algorithms on IID PI, [13]. This generalises as follows.
Corollary 9.
For every having both and finite, and every constant , if , then a single-threshold -approximation exists.
The impact of our results concerns online auctions and, more generally, stochastic matching problems, where random horizons are considered and the connection to our model is well-established under perishable inventory assumptions (see Section 1.5).
1.4 Our techniques
The toolbox we assembled can be described in three key points.
Discounted infinite problem.
The optimal algorithm is characterised via a correspondence between stopping rules for RH and stopping rules for a discounted optimal stopping problem, with the discount factors being the survival function of the horizon. More general optimal stopping problems (unbounded random horizon) do not always admit an optimal algorithm [37]. We show that for RH, this is always possible. This is crucial for geometric and horizons, which are unbounded. The generalisation is the product of an original measure-theoretic construction, leveraging trace -algebras.
Stochastic orders.
The extension of the -approximation from the class to the class and horizons is obtained by exploiting stochastic orders, which have never before been applied to prophet inequality problems. Several distributional classes, starting from the class, can be equivalently defined through some stochastic-ordering with respect to the geometric distribution (as previously seen, the largest of such classes exploits the pgf order). Thus our Theorem 5 not only extends to the class, but simplifies the arguments of [2]. The proof of Theorem 8 leverages extremal properties of specific Bernoulli distributions with respect to another stochastic order, the Laplace transform order (see Section 5 for details), for distributions having finite variance.
Hard instance.
Our analysis of the hard instance for single-threshold algorithms is also novel. The literature on prophet inequalities has focused only on bounded discrete instances that are hard for every algorithm. On the other hand, the instance we provide exploits a continuous Pareto distribution, which, combined with a suitable family of horizons, is both hard for single-threshold algorithms, and competitive for the SP stopping rule, against the offline maximum. This requires a more sophisticated and analytic approach. The phenomenon in which certain algorithms fail on an instance but others do not is subtle. To the best of our knowledge, a competitive analysis of the SP stopping rule against the offline maximum with a random horizon is also new (see Section 1.5). It is worth noting that this hard instance is designed to live in a close neighbourhood of the -class, so that perturbing it suitably yields, at the same time, a hard family in the class.
1.5 Additional related work and motivation
The literature on prophet inequalities models with deterministic horizon is vast (see [11, 12, 29, 19] for surveys). We only mention a few models closely related to PI and IID PI for context. In the Random Order PI values arrive in a uniform random order, it is -competitive [7] and -hard [15]). In the Order Selection PI the order can be chosen by the gambler, it is -competitive [6] and inherits -hardness from IID PI. Very recently, Oracle-augmented PI have also been introduced [18]. The existing literature strictly related to RH is limited to [2, 17, 30], which focuses on online automated mechanism design (see [38] for a survey), with emphasis on the multiple-items setting. In [2] a standard machinery has been put in place, which extends results for single-item RH to multiple items, provided the horizons for each item are uniformly bounded. This applies to our results, too. [30] considers the problem of unknown market size (that is, random horizon with unknown distribution, motivated by search keyword auctions such as Google). As previously mentioned, this assumption is hard [17]. In practice, distributional knowledge is available via the history of past transactions, from which RH arises as a natural model. On a technical level, RH is also well recognised as connected to other online stochastic matching problems with a random number of queries, which have recently been shown to admit -approximations [3]. A potential ground for applications of our techniques would be improving such guarantees.
The Secretary Problem (SP) has been extensively studied (see [16, 14] for variations). The classical SP is an online problem where there are secretaries for hire, who show up in a uniform random order at interviews. An employer, who wants to maximise the probability of hiring the best solely based on the relative ranks up to the present, makes the decision of hiring or rejecting and keep interviewing, at each interview. The optimal stopping rule rejects all the first of the secretaries, and accepts the first secretary with relative rank thereafter. The value is such that as , both and the probability of selecting the best tend to [28].
When the number of secretaries is random, denoted by , the secretaries are interviewed in a uniform random order, conditionally on . Depending on the horizon’s distribution, we can have a more complicated set composed of multiple islands, in which it is optimal to stop at a secretary with relative rank , and outside which it is not [33]. The model has been shown to be hard [1].
SP has been studied also in its full-information variant, with and without a random horizon. The common continuous distribution, from which the quality measurement of each of the secretaries is sampled independently, is known to the employer, who directly inspects, at each interview, the secretary’s true quality [16, 4, 32]. Both no- and full-information SP have also been studied under the harder hypothesis of random freeze [36, 37]. More recent developments extend SP to combinatorial structures and unknown horizons [20, 31].
1.6 Organisation of the paper
In Section 2 we give preliminaries on the formal approach to random horizon optimal stopping problems, and prove the equivalence with discounted optimal stopping problem. In Section 3 we prove Theorem 5. In Section 4 we prove Theorem 6. In Section 4.2 we prove Theorem 7. In Section 5 we prove Theorem 8.
2 Preliminaries
In this section we set up our notation, give the details of the probabilistic model, and characterise the optimal algorithm.
2.1 Notation
We denote , , , , , , and for all . We follow standard asymptotic notation for nonnegative functions (and sequences, with trivial extensions to signed functions when the use of absolute value is consistent), here we point out the only slightly less common as if and . We will adopt the convention of omitting the dependence on all parameters not involved in the main limiting process (which will be clear from the context), regardless of whether uniformity (when not relevant to the context) holds within the parametric range. Absolutely continuous distributions will be referred to as continuous. Discontinuous distributions are assumed to satisfy the usual regularity assumption (isolated jumps). The convergence in distribution of random variables is denoted as weak convergence: . Almost surely is abbreviated and denotes that , are identically distributed random variables. The essential supremum of a collection of random variables is denoted by . is called survival function of ( if necessary). We follow the standard probabilistic functional notation for powers, such as and .
2.2 Probabilistic model
As aforementioned in this section (and this section alone), RH is studied from the point of view of optimal stopping, hence horizons admitting mass at zero will also be considered. In Section 1.1 we ruled out any mass at zero, since in all subsequent sections, concerned with competitive analysis, this will be the standard assumption. A formal convention, in fact, restores the equivalence with a scenario admitting mass at zero, from a competitive analysis point of view. Add a value , and set for all . Informally, when the game does not start, both the gambler and the prophet receive no return. Adopt the convention . Having set ensures that the game always starts, unless . Assuming absence of penalty for entering the game even though it does not start yields the equivalence: the ratio being does not affect the worst case competitive ratio.
In RH the gambler must select the value in ignorance of whether it is the last or not: at each step the gambler only learns whether the inspected value is the last or not (that is, whether or ) after the decision of accepting or rejecting it has been made (that is, in the st step). Probabilistically, it is standard to model this as follows. The random list is constructed from the infinite underlying process of iid copies of , whose natural filtration (intuitively, the information associated with the history of the process up to the present) is the sequence of , for every , where (no information at the start: this is the implicit starting point of all filtration we will introduce). Let . The nonanticipative condition and the ignorance aforementioned are modelled by requiring that for every . Intuitively, this second filtration represents the information associated with the history of the game, which combines both the history of the process of the values and the state of the game in all preceding steps (that is, whether it ended or is still running). We recover the original by imposing that the reward is zero if the gambler fails to stop by time on the infinite sequence, that is, defining the reward sequence , where , to which we add .
For technical reasons, we consider the slightly less common class of all possibly infinite stopping times for the problem (), denoted as (). Formally, , means that for all , also admitting . This requires that we compactify the problem, by prescribing a conventional, yet natural, reward value, in the event that the gambler never stops. We set , since , so if the gambler never stops, the horizon will be reached, so there can be no reward. In this way infinite stopping rules do not increase the largest possible expected reward, and the equivalence with the original formulation is maintained. In conclusion, RH has been reformulated as an infinite optimal stopping problem with reward sequence , underlying process and filtration , where (the complete information about the history of the process, which is the ending point of all infinite filtration we will introduce), with respect to the class . We seek to find the value of the problem and, if it exists, an optimal stopping rule . Optimal means that . The reference to the horizon can be made explicit, whenever the need arises, via the notation .
2.3 Optimal algorithm
Under suitable hypotheses, an optimal stopping problem with independent horizon , having survival function , is equivalent to a finite (if is bounded) or infinite (if is unbounded) optimal stopping problem discounted by factors . The discounted problem is , where , for every , . Thus, for we use the filtration , having set and as usual. The latter is used when the problem is infinite. Thus , and the equivalence aforementioned means that .
The bounded horizon case is solved in [37] by backward induction, which does not extend to the unbounded case where an optimal stopping rule is needed explicitly. The main contribution of our Theorem 14 is showing that RH with unbounded horizon admits an explicit optimal stopping rule of the form , where we will take to be the Snell stopping rule for . Let us recall a few facts, adapted from [8, 9] to our compactified framework. Let be the class of all stopping rules in that do not stop before step .
Definition 10 (Snell envelope).
The Snell envelope of is , where .
Note that . The intuitive interpretation of the stochastic process is the best expected return available at step among the rules that have reached step .
Remark 11.
Since for every the Snell envelope satisfies
(2) |
Informally, 2 represents an extension of the dynamic programming principle for the infinite process : at time it is optimal to stop whenever the currently inspected value is greater than the highest expected future return as per the previous informal characterisation of . We use 2 to compute . Note that for finite problems it coincides with backward induction.
Definition 12 (Snell stopping rule).
The Snell rule is .
Remark 13.
If and , then the Snell rule is optimal.
Theorem 14.
Let be a finite horizon with and possibly mass at zero, and let , and as previously defined.
It holds that: ; there exists such that ; is such that .
Furthermore, is characterised as: the backward induction stopping rule for if ; the Snell rule for , if .
Idea of the proof.
The case leads to the equivalent characterisation as backward induction on [37, Theorem 2.1]. For the case , a crucial step is to show that for every stopping rule , we can construct a stopping rule , such that (that is and are equivalent), where . This requires an inductive measure-theoretic construction. For every , let . We have that , where the intersections denote, as standard, the corresponding trace -algebras. Next, we construct inductively mutually disjoint events , such that . These events are then relied upon to define as, informally speaking, a stopping rule that stops when successfully stops by the time the horizon has realised, and does not stop otherwise. Formally, denote , and define for every ,
(3) |
while setting to otherwise. Following the standard convention , we verify by direct computation that is ensured by .
We show that as follows. First, note that . Second, for every , , where is defined as in 3. Third, for every ,
(4) |
with . These facts imply that .
Given an optimal stopping rule , we have that provides an optimal rule based on 4. Furthermore, our assumptions ensure that and . Hence, the Snell envelope of satisfies 2 by Remark 11, and yields the optimal stopping.
We also derive a result, which gives the intuitive interpretation of as the best expected return available at step among the rules that will not stop by or at step .
Lemma 15.
Let be the Snell envelope of . Then
3 Warm-up: a -approximation on the class
We build familiarity with the model by proving Theorem 5, which derives a -approximation on the class, extending the results of [2, Section 3]. Recall that is the distribution of the values and of the horizon (with no mass at zero and ). The expected return of a single-threshold algorithm is readily computed.
Lemma 16.
Let and consider the stopping rule , where . Then , where .
The quantity yields the competitive ratio. With this in mind, we upper-bound by ex-ante relaxation of the prophet, combined with a simple variational argument.
Lemma 17.
Let be continuous and such that . Then we have that .
Idea of the proof.
Let be the probability density function (pdf) of and the pdf of . In order to upper-bound , we solve the variational problem of maximising the functional with constraints: ; for all ; is nonnegative Lebesgue integrable on , the constraint follows from a union bound. The maximal solution is for all , and zero otherwise, with as in the claim. Then .
To prove Theorem 5 we extend Lemma 17 to discontinuous via stochastic tie-breaking. The technique is standard with deterministic horizons, but with random horizons, it is not yet clear that the assumptions imposed on RH are robust enough. We will show that an underlying property of the prophet, Uniform Integrability (UI), is the key. Before that, we derive the equivalent of Lemma 16 for a randomised algorithm (randomisation does not increase the optimal value of optimal stopping problems). Attach to every a biased coin flip, that is iid Bernoulli random variables independent of and , denoting the probability of (heads). Denote the class of adapted, thus randomised, stopping rules as .
Lemma 18.
Let and consider the stopping rule . Then , where .
Idea of the proof of Theorem 5.
Let be continuous. By Lemmas 16 and 17,
where . For any , with , . Let , so that , then
This implies that and the result follows.
Let be discontinuous with cumulative distribution function (cdf) having in correspondence of a jump at , say . Let be the set of discontinuities (increasingly enumerated), one of which is . Let be a small enough positive monotonically vanishing sequence. Linearly interpolate on disjoint intervals of length and keep it unaltered otherwise. This yields an approximating sequence of continuous and piecewise differentiable cdf’s of continuous random variables . Upon showing that the family is UI, define . RH assumptions ensure that is UI too. Since , . By Lemma 17, for every there is such that and . By construction, as , so . All these facts ensure that
To conclude, for any , since , by Lemma 18 the single-threshold algorithm , with , is such that
where .
Remark 19.
If is discontinuous with in correspondence of a discontinuity jump of the survival function of , the -approximation is a single-threshold randomised algorithm, where the threshold is the value at which the discontinuity jump occurs, and the randomisation parameter is , but the argument above shows that if is discontinuous and does not occur in correspondence of a discontinuity jump, the randomisation parameter is , meaning that the nonrandomised algorithm for the continuous case is enough to yield a -approximation.
In the rest of the paper we will omit any explicit adaptation of similar tie-breaking arguments, as we showed that RH is robust enough. Some of the most well-known subclasses of the class, which earned considerable interest in applications, are: (Increasing Hazard Rate in Expectation); (Harmonically Increasing Hazard Rate in Expectation); (New Better than Used); (New Better than Used in Expectation). The following tower of inclusions (and its dual, which will follow in the next section) is well-established [5, 34, 22] and known to be strict: .
The tight instance for the -approximation involves a geometric horizon and was studied in [2, Theorem 3.5]. Their basic assumptions, concerning a two-point distribution, are intuitive facts: that an optimal algorithm with geometric horizon should exist and that it has a single threshold. We show mathematically that they both hold, with the second extending, more in general, to any bounded value distribution. As a bonus, we obtain an equation for the optimal threshold. Recall that denotes the geometric distribution with failure probability .
Lemma 20.
Let , and such that , . Then there exists a threshold such that the corresponding single-threshold algorithm is optimal.
Idea of the proof.
By Theorem 14, . By 2, it holds that Since , by time invariance and Lemma 15 it follows that . Therefore, ; equivalently
The function is strictly increasing and differentiable on , with . Hence the value exists. By Remarks 13 and 12 and time invariance again, it is optimal to stop at the first value greater than or equal to (the expected return).
4 A first step beyond single-threshold algorithms
In this section we construct a parametric family of horizons, which is hard for any single-threshold algorithm, and yet it allows for an adaptive competitive algorithm. We also show that it can be perturbed so that it enters the class, while remaining hard for single-threshold algorithms.
4.1 The hard instance
Let us start with the hard instance for the values, which is a Pareto (Type I) distribution with scale parameter and shape parameter , where is fixed small enough. The corresponding cdf, denoted as , vanishes on , whereas on
(5) |
Since has cdf , which is differentiable for all , we obtain that its density (defined almost everywhere) vanishes on , whereas on . By direct computation, relying on the properties of the Gamma and Beta function, it follows that , as , uniformly in . Consequently, in conjunction with the instance for the values, we consider a family of horizons , with large enough, such that for every fixed such , , with the lower limit . For every fixed, we define the pmf of each horizon by letting, for every ,
(6) |
having defined the normalising constant . Through standard integral estimates of summations, it is shown that
(7) |
and that the following holds.
Lemma 21.
As , uniformly in small enough, , where .
By 7 and integral estimates akin to those leading to Lemma 21 it is straightforward to compute that for every , as ,
(8) |
The properties of the Gamma function ensure that as , . As a result, as vanishes, and we have the following.
Remark 22.
As , uniformly in small enough, .
We are now ready to prove the hardness of the family of horizons for single-threshold algorithms. A stopping rule with a single threshold is denoted as . A crucial point is that the algorithm facing will set a threshold exploiting all distributional knowledge regarding and . Yet, this is not enough to obtain a constant-approximation on the family for all suitably small .
Proposition 23.
Idea of the proof..
Our strategy will be to characterise the sequence of optimal single thresholds (corresponding to horizons for large enough and small enough), where maximizes the value obtained over all single threshold strategies . Denote with the gambler-to-prophet ratio of and . As a consequence of the characterisation obtained, it will follow that there is always a subsequence , such that as , vanishes. This yields the claim, since is an upper bound on any gambler-to-prophet ratio for arbitrary single-threshold algorithms.
Since is continuous, by Lemma 16 we compute , which is nontrivial only if . This is expressed as the product of
Next, we show analytically that the optimal sequence of thresholds satisfies the optimality equation
Bounded case.
Since , vanishes as , for any fixed small enough. Note that this case covers also the trivial case for which there exists a subsequence such that , for which the numerator of becomes upper-bounded by .
Intermediate case.
Before moving on to the general unbounded case, we consider the subcase of divergence to infinity with . Note that by Bernoulli’s inequality we have that
By 8 with it holds that as , for every fixed small enough vanishes, since
Unbounded case.
More in general, we can rely on the previous point to show that the unbounded case overall only allows for to vanish. Consider that since , if all of its convergent subsequences vanish for all small enough, then vanishes for all small enough. We show the sufficient condition by contradiction: assume that as , , with being bounded away from no matter how small is taken. Then we have that as , for fixed small enough, is asymptotically equivalent to a bounded sequence, so it must be bounded too. Thus, we can consider a convergent subsequence of , denoted , such that as , . A sharp asymptotic analysis of reveals that the optimality equation satisfied by allows only for being bounded away from zero, unless it is identically zero. In what follows, it is useful to rewrite the optimality equation as
and denote . By estimating asymptotically the series expansion of with respect to the first argument, uniformly in , the following bound is shown to hold as :
It follows that for small enough, as , if the strictly decreasing function is bounded away from zero. Note that is negative and vanishes as vanishes. Since we have previously shown that if exists, it must be bounded away from zero as vanishes (and thus is bounded away from zero too)), in this case the optimality equation cannot be satisfied, as long as is taken sufficiently small. Thus only would not yield a contradiction at this point, meaning that for all small enough, as . By boundedness, also as . This corresponds to the scenario in the previous point (replace, in that argument, with ) and therefore vanishes. This is in contradiction with the assumption, which ensures , and therefore we must have .
The sequence is thus shown to always admit a vanishing subsequence.
4.2 Hardness of the class
The most notable subclasses of the class are the dual of those introduced at the end of Section 3: . A hint towards the hardness of the class could be that the duality mirrors the estimates of Section 3, meaning that the lower-bound, which provides the competitive ratio ensured, turns into an upper-bound, informally speaking. This mirroring has significance, because the ex-ante relaxation of the prophet is tight on geometric horizons, and is essentially maxed-out by the very definition of the class.
Idea of the proof of Theorem 7.
We show that a perturbation of the hard instance from the previous section prevents any single-threshold constant-approximation on the class.
Step 1.
We start by constructing a family , which is a sequence of horizons arising as a perturbation of horizons in the hard family of 6, with fixed , as grows, for all fixed small enough. This is done by adding to the pmf of said , a (to be suitably rescaled) mass at one, , where . We denote the perturbed horizon for every considered, and observe that the corresponding normalizing constants for the pmf’s and ; and expectations and ; satisfy, as grows, the following:
(9) | ||||
(10) |
Trivially, these follow from 7 and 8 with and the definitions, respectively and . To show that for all large enough, , we have to establish that eventually (short for all large enough from now on), for all ,
which we recast as
(11) |
having set . Let . We establish that eventually for all
(12) |
and that eventually for all
(13) |
This implies 11 for all , since eventually on 11 holds with strict inequality directly by 12, while for all we have that the difference of the left-hand and right-hand side of 11, denoted , is strictly concave ( 13 states precisely that ). Since for all and since it vanishes at both ends of the unit interval, it cannot vanish on , meaning that there cannot be any crossings of the two sides of 11 on , which therefore holds everywhere.
Step 2.
Next, we show that with being set to be the hard instance of values of 5, with fixed small enough as in Step 1, and as grows, for every sequence of thresholds . The first fact follows from Remarks 22 and 9 and observing that the law of total expectation yields
The second fact follows from considering the survival functions of and , respectively and . For all , , whereas . Consider next a single-threshold algorithm , where on horizon . By Theorem 14 (note that the notations and used there are now swapped, as our focus here is on the original stopping rule) for any horizon , there is a stopping rule equivalent to for the problem , denoted as , where is, as per 3, an algorithm for the discounted problem , which stops only when successfully stops by the time the horizon has realised. Intuitively, we can construct as the stopping rule with single threshold on the events . Otherwise it stops at on . The proof of Theorem 14 shows that this can be done, so that is adapted to , and as a result, as grows,
Step 3.
Finally, suppose by contradiction that a constant-approximation exists on the class. Then there exist a sequence of thresholds and such that is a -approximation on by Step 1. By Proposition 23 for all fixed small enough, there exists a subsequence such that , the gambler-to-prophet ratio of over , vanishes. Let be the gambler-to-prophet ratio of over . Combining this with Step 2’s asymptotics yields the following contradiction as grows: .
4.3 The competitive Secretary Problem rule
In this section we show that a straightforward adaptation of the SP stopping rule with deterministic horizon is competitive on the horizons defined in 6. Consider any instance of the values which is a nonnegative integrable continuous random variable. Consider the process , where are iid copies of . We equivalently characterise it in the context of SP via a uniform random permutation . Consider . Since is exchangeable, . Consider now the waiting time for the SP stopping rule, denoted as , and recall that . Consider conditionally on , denoted as . This is the process of the realised values arriving in a uniform random order and reformulates the usual setup for SP. In this reformulation, the classical result of [28] can be restated as
(14) |
Given the stopping rule , denote the event of winning (that is, choosing the best) as and that of winning at time as . Note that by partitioning conditionally on , we have that
(15) |
The proof of 14 relies on the following fact, which we will also exploit:
(16) |
When considering RH, instead of working with as usual, we start from , by defining accordingly . This is equivalent, since for every stopping rule , . Yet it is formally advantageous in the following argument.
Idea of the proof of Theorem 6.
Consider the stopping rule . By 4 in Theorem 14 firstly, and the law of total expectation with respect to secondly, we have that
Since at any given step (greater than ) stopping at the overall maximum implies stopping at the relative maximum,
Therefore,
By 7 and comparison of the summation with the corresponding integral as in Lemma 21, we estimate the survival function of as : since , for all we have that
Define the sequence of functions
For every fixed ,
as , where we used 15, 16, and 14 and the usual integral estimate in the second inequality, whereas the asymptotics come from . It is crucial that is positive and strictly increasing on : even though as , , no matter how small, it still provides a constant approximation for every fixed.
Putting all the above together yields
where , as . This implies the final estimate
Fix small and consider horizons as defined in 6, where is large enough. By Proposition 23, the RH problem under this family does not admit single-threshold constant-approximations for the fixed , assuming it is small enough (the hard instance for the values being the Pareto distribution defined in 5). On the other hand, by our final estimate, provides an approximate -approximation: for every (small) fixed, setting large enough, using yields that for every instance ,
where as .
5 A -approximation for concentrated -horizons
Finally, we prove Theorem 8, extending the -approximation for the class to sufficiently concentrated horizons. We will make use of the following stochastic order.
Definition 24 (Laplace transform order).
Given nonnegative random variables and , is dominated by in the Laplace transform (Lt) order, denoted as , if , .
Remark 25.
Consider a horizon , having finite expectation and variance , and random variables and . Then .
Idea of the proof of Theorem 8.
Recall that the single-threshold -approximation of Theorem 5 obtains at least competitive ratio
with . Since , where is the two-point distribution of Remark 25, it follows that
(17) |
As a result, an inequality that yields a single-threshold -approximation is
(18) |
and straightforward estimates show that this is ensured by , having defined . Furthermore, defining the constraints and , we can rewrite the condition above as . Under the constraints given, this is more explicitly rewritten as , where denotes the principal branch of the Lambert function. The definition of and yields 1. It is possible to substitute suitable values of for in 1, the only issue would arise near the branching point of the Lambert function. With this caveat in mind, we derive Corollary 9 by substituting admissible values of for in 18. Since we obtain
this ensures a -approximation. The degenerate cases establish insightful connections with the literature. The deterministic case () can be recovered directly from 17, which can be reformulated as a guarantee that the competitive ratio () is always greater than the left-hand side of
Therefore, if , the optimal single-threshold algorithm exploited ensures a competitive ratio of . This value is the global maximum of the function on the right-hand side, and coincides with the optimal competitive ratio for single-threshold algorithms for (deterministic) IID PI [13][Theorem 21]. The left-hand side achieves global maximum at , reflecting that a deterministic horizon is no harder than a random horizon. Hence any admissible is constrained to be greater than . This proves Corollary 9 and justifies the admissibility condition.
References
- [1] A. R. Abdel-Hamid, J. A. Bather, and G. B. Trustrum. The secretary problem with an unknown number of candidates. J. Appl. Probab., 19(3):619–630, 1982.
- [2] R. Alijani, S. Banerjee, S. Gollapudi, K. Munagala, and K. Wang. Predict and match: prophet inequalities with uncertain supply. Proc. ACM Meas. Anal. Comput. Syst., 4(1):Article 4, 2020.
- [3] A. Aouad and W. Ma. A nonparametric framework for online stochastic matching with correlated arrivals. In EC, page 114. ACM, 2023. doi:10.1145/3580507.3597773.
- [4] T. Bojdecki. On optimal stopping of a sequence of independent random variables - probability maximizing approach. Stoch. Process. Their Appl., 6:153–163, 1978.
- [5] C. Bracquemond, D. Roy, and M. Xie. On some discrete notions of aging. In System and bayesian reliability. Essays in honor of Prof. E. Barlow on his birthday, pages 185–197. World Scientific, 2001.
- [6] A. Bubna and A. Chiplunkar. Prophet inequality: order selection beats random order. In EC, pages 302–336. ACM, 2023. doi:10.1145/3580507.3597687.
- [7] Z. Chen, Z. Huang, D. Li, and Z. G. Tang. Prophet secretary and matching: the significance of the largest item. In SODA, pages 1371–1401, 2025.
- [8] Y. S. Chow and H. Robbins. On optimal stopping rules. Z. Wahrscheinlichkeitstheorie, 2:33–49, 1963.
- [9] Y. S. Chow, H. Robbins, and D. Siegmund. Great expectations: the theory of optimal stopping. Houghton Mifflin, 1971.
- [10] J. Correa, P. Foncea, R. Hoeksma, R. Oosterwiijk, and T. Vredeveld. Posted price mechanisms for a random stream of customers. In EC, pages 169–189. ACM, 2017.
- [11] J. Correa, P. Foncea, R. Hoeksma, R. Oosterwiijk, and T. Vredeveld. Recent developments in prophet inequalities. SIGecom Exch., 17(1):61–70, 2018. doi:10.1145/3331033.3331039.
- [12] J. Correa, P. Foncea, D. Pizarro, and V. Verdugo. From pricing to prophets, and back! Oper. Res. Lett., 47:25–29, 2019. doi:10.1016/J.ORL.2018.11.010.
- [13] S. Eshani, M. Hajiaghayi, M. Kesselheim, and S. Singla. Prophet secretary for combinatorial auctions and matroids. In SODA, pages 700–714. SIAM, 2018. doi:10.1137/1.9781611975031.46.
- [14] P. R. Freeman. The secretary problem and its extensions: a review. Int. Stat. Rev., 51(2):189–206, 1983.
- [15] G. Giambartolomei, F. Mallmann-Trenn, and S. Saona. Prophet inequalities: Separating Random Order from Order Selection. arXiv:2304.04024 [cs.DS].
- [16] J. P. Gilbert and F. Mosteller. Recognizing the maximum of a sequence. J. Am. Stat. Assoc., 61(313):35–73, 1966.
- [17] M. T. Hajiaghayi, R. D. Kleinberg, and T. Sandholm. Automated online mechanism design and prophet inequalities. In AAAI, pages 58–65, 2007.
- [18] S. Har-Peled, E. Harb, and V. Livanos. Oracle-augmented prophet inequalities. In ICALP, pages 81:1–81:19, 2024.
- [19] T. P. Hill and R. P. Kertz. A survey of prophet inequalities in optimal stopping theory. Contemp. Math., 125:191–207, 1992.
- [20] M. Hoefer and B. Kodric. Combinatorial secretary problems with ordinal information. In ICALP, pages 133:1–133:14, 2017.
- [21] R. P. Kertz. Stop rule and supremum expectations of i.i.d. random variables: a complete comparison by conjugate duality. J. Multivar. Anal., 19(1):88–112, 1986.
- [22] B. Klefsjö. The hnbue and hnwue classes of life distributions. Naval Res. Logist. Quart., 29:331–344, 1982.
- [23] B. Klefsjö. Testing exponentiality against hnbue. Scand. J. Stat., 10(2):65–75, 1983.
- [24] B. Klefsjö. A useful ageing property based on the laplace transform. J. Appl. Prob., 20:615–626, 1983.
- [25] U. Krengel and L. Sucheston. Semiamarts and finite values. Bull. Amer. Math. Soc., 83(4):745–747, 1977.
- [26] U. Krengel and L. Sucheston. On semiamarts, amarts, and processes with finite value. Adv. Probab. Related Topics, 4:197–266, 1978.
- [27] N. A. Langberg, R. V. Léon, J. Lynch, and F. Proschan. Extreme points of the class of discrete decreasing failure life distributions. Math. Oper. Res., 5(1):35–42, 1980. doi:10.1287/MOOR.5.1.35.
- [28] D. V. Lindley. Dynamic programming and decision theory. J. R. Stat. Soc. Ser. C Appl. Stat., 10(1):39–51, 1961.
- [29] B. Lucier. An economic view of prophet inequalities. SIGecom Exch., 16(1):24–47, 2017. doi:10.1145/3144722.3144725.
- [30] M. Mahdian and A. Saberi. Multi-unit auctions with unknown supply. In CEC, pages 243–249. ACM, 2006. doi:10.1145/1134707.1134734.
- [31] S. Oveis Gharan and J. Vondrák. On variants of the matroid secretary problem. Algorithmica, 67:472,497, 2013.
- [32] Z. Poroziński. The full-information best choice problem with a random number of observations. Stoch. Process. Their Appl., 24:293–307, 1987.
- [33] E. L. Presman and I. M. Sonin. The best choice problem for a random number of objects. Theory Probab. its Appl., 17(4):657–668, 1972.
- [34] T. Rolski. Mean residual life. Bull. Int. Statist. Inst., 46:220–266, 1975.
- [35] E. Samuel-Cahn. Comparisons of threshold stop rule and maximum for independent nonnegative random variables. Ann. Probab., 12(4):1213–1216, 1984.
- [36] E. Samuel-Cahn. The best-choice secretary problem with random freeze on jobs. Stoch. Process. Their Appl., 55(2):315–327, 1995.
- [37] E. Samuel-Cahn. Optimal stopping with random horizon with application to the full-information best-choice problem with random freeze. J. Am. Stat. Assoc., 91(433):357–364, 1996.
- [38] T. Sandholm. Automated mechanism design: A new application area for search algorithms. In CP, pages 19–36, 2003.
- [39] M. Shaked and J. G. Shanthikumar. Stochastic orders. Springer, 2007.