Lookback Prophet Inequalities

Authors: ziyad  benomar
dorian  baudry
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-08 22:26:23

Abstract: Prophet inequalities are fundamental optimal stopping problems, where a decision-maker observes sequentially items with values sampled independently from known distributions, and must decide at each new observation to either stop and gain the current value or reject it irrevocably and move to the next step. This model is often too pessimistic and does not adequately represent real-world online selection processes. Potentially, rejectesd items can be revisited and a fraction of their value can be recovered. To analyze this problem, we consider general decay functions $D_1,D_2,\ldots$, quantifying the value to be recovered from a rejected item, depending on how far it has been observed in the past. We analyze how lookback improves, or not, the competitive ratio in prophet inequalities in different order models. 
We show that, under mild monotonicity assumptions on the decay functions, the problem can be reduced to the case where all the decay functions are equal to the same function $x \mapsto \gamma x$, where $\gamma = \inf_{x>0} \inf_{j \geq 1} D_j(x)/x$. Consequently, we focus on this setting and refine the analyses of the competitive ratios, with upper and lower bounds expressed as increasing functions of $\gamma$.

Main paper: 
 introduction: 
 Optimal stopping problems constitute a classical paradigm of decision-making under uncertainty [Dynkin, 1963] Typically, in online algorithms, these problems are formalized as variations of the secretary problem [Lindley, 1961] or the prophet inequality [Krengel and Sucheston, 1977] . In the context of the prophet inequality, the decision-maker observes a finite sequence of items, each having a value drawn independently from a known probability distribution. Upon encountering a new item, the decision-maker faces the choice of either accepting it and concluding the selection process or irreversibly rejecting it, with the objective of maximizing the value of the selected item. However, while the prophet inequality problem is already used in scenarios such as posted-price mechanism design [Hajiaghayi et al., 2007] or online auctions [Syrgkanis, 2017] , it might present a pessimistic model of real-world online selection problems. Indeed, it is in general possible in practice to revisit previously rejected items and potentially recover them or at least recover a fraction of their value.Consider for instance an individual navigating a city in search of a restaurant. When encountering one, they have the choice to stop and dine at this place, continue their search, or revisit a previously passed option, incurring a utility cost that is proportional to the distance of backtracking. In another example drawn from the real estate market, homeowners receive offers from potential buyers. The decision to accept or reject an offer can be revisited later, although buyer interest may have changed, resulting in a potentially lower offer or even a lack of interest. Lastly, in the financial domain, an agent may choose to sell an asset at its current price or opt for a lookback put option, allowing them to sell at the asset's highest price over a specified future period. To make a meaningful comparison between the two, one must account for factors such as discounting (time value of money) and the cost of the option.To encompass diverse scenarios, we propose a general way to quantify the cost incurred by the decision-maker for retrieving a previously rejected value. Definition 1.1 (Decay functions). Let D = (D 1 , D 2 , . . .) be a sequence of non-negative functions defined on [0, ∞). It is a sequence of decay functions if (i) D 1 (x) ≤ x for all x ≥ 0, (ii) the sequence (D j (x)) j≥1 is non-increasing for all x ≥ 0, (iii) the function D j is non-decreasing for all j ≥ 1.In the context of decay functions D, if a value x is rejected, the algorithm can recover D j (x) after j subsequent steps. The three conditions defining decay functions serve as fundamental prerequisites for the problem. The first and second conditions ensure that the recoverable value of a rejected item can only diminish over time, while the final condition implies that an increase in the observed value x corresponds to an increase in the potential recovered value. Although the non-negativity of the decay functions is non-essential, we retain it for convenience, as we can easily revert to this assumption by considering that the algorithm has a reward of zero by not selecting any item.The motivating examples that we introduced can be modeled respectively with decay functions of the form D j (x) = x -c j where (c j ) j≥1 is a non-decreasing positive sequence, D j (x) = ξ j x with ξ j ∼ B(p j ) and (p j ) j≥1 a non-increasing sequence of probabilities, and D j (x) = λ j x with λ ∈ [0, 1]. In one of these examples (housing market), the natural model is to use random decay functions: the buyer makes the same offer if they are still interested, and offers 0 otherwise. Definition 1.1 can be easily extended to consider this case. However, to enhance the clarity of the presentation, we only discuss the deterministic case in the rest of the paper. In Appendix D, we explain how all the proofs and theorems can be generalized to that case.The D-prophet inequality. For any decay functions D, we define the D-prophet inequality problem, where the decision maker, knowing D, observes sequentially the values X 1 , . . . , X n , with X i drawn from a known distribution F i for all i ∈ [n]. If they decide to stop at some step τ , then instead of gaining X τ as in the classical prophet inequality, they can choose to select the current item X τ and have its full value, or select any item X i with i < τ among the rejected ones but only recover a fraction D τ -i (X i ) ≤ X i of its value. Therefore, if an algorithm ALG stops at step τ its reward isALG D (X 1 , . . . , X n ) = max{X τ , D 1 (X τ -1 ), D 2 (X τ -2 ), . . . , D τ -1 (X 1 )} = max 0≤i≤τ -1 {D i (X τ -i )} ,with the convention D 0 (x) = x. If the algorithm does not stop at any step before n, then its reward is ALG D (X 1 , . . . , X n ) = max 1≤i≤n {D i (X π(n-i+1) )}, which corresponds to τ = n + 1.Remark 1.1. As in the standard prophet inequality, an algorithm is defined by its stopping time, i.e., the rule set to decide whether to stop or not. Hence, if D and D ′ are two different sequences of decay functions, any algorithm for the D-prophet inequality, although its stopping time might depend on the particular sequence of functions D, is also an algorithm for the D ′ -prophet inequality. Consider for example an algorithm ALG with stopping time τ (D) that depends on D. Its reward in the D ′ -prophet inequality is ALG D ′ (X 1 , . . . , X n ) = max 0≤i≤τ -1 {D ′ i (X τ (D)-i )}.Observation order. Several variants of the prophet inequality problem have been studied, depending on the order of observations. The standard model is the adversarial (or fixed) order: The instance of the distributions F 1 , . . . , F n is chosen by an adversary, and the algorithm observes the samples X 1 ∼ F 1 , . . . , X n ∼ F n in this order [Krengel and Sucheston, 1977, 1978] . In the random order model, the adversary can again choose the distributions, but the algorithm observes the samples in a uniformly random order. Another setting in which the observation order is no longer important is the IID model [Hill and Kertz, 1982, Correa et al., 2021b] , where all the values are sampled independently from the same distribution F . The D-prophet inequality is well-defined in each of these different order models: if the items are observed in the order X π(1) , . . . , X π(n) with π a permutation of [n], then the reward of the algorithm is ALG D (X 1 , . . . , X n ) = max 0≤i≤τ -1 {D i (X π(τ -i) )}. In this paper, we study the D-prophet inequality in the three models we presented, providing lower and upper bounds in each of them.Competitive ratio. In the D-prophet inequality, an input instance I is a finite sequence of probability distributions (F 1 , . . . , F n ). Thus, for any instance I, we denote by E[ALG D (I)] the expected reward of ALG given I as input, and we denote by E[OPT(I)] the expected maximum of independent random variables (X i ) i∈ [n] , where X i ∼ F i . With these notations, we define the competitive ratio, which will be used to measure the quality of the algorithms. Definition 1.2 (Competitive ratio). Let D be a sequence of decay functions and ALG an algorithm.We define the competitive ratio of ALG byCR D (ALG) = inf I E[ALG D (I)] E[OPT(I)],with the infimum taken over the tuples of all sizes of non-negative distributions with finite expectation.An algorithm is said to be α-competitive if its competitive ratio is at least α, which means that for any possible instance I, the algorithm guarantees a reward of at least αE[OPT(I)]. The notion of competitive ratio is used more broadly in competitive analysis as a metric to evaluate online algorithms [Borodin and El-Yaniv, 2005] .It is trivial that non-zero decay functions D guarantee a better reward compared to the classical prophet inequality. However, in general, this is not sufficient to conclude that the standard upper bounds or the competitive ratio of a given algorithm can be improved. Hence, a first key question is: what condition on D is necessary to surpass the conventional upper bounds of the classical prophet inequality? Surprisingly, the answer hinges solely on the constant γ D , defined as follows,EQUATIONIn the adversarial order model, we demonstrate that the optimal competitive ratio achievable in the D-prophet inequality is determined by the parameter γ D alone. Additionally, in both the random order and IID models, we demonstrate the essential requirement of γ D > 0 for breaking the upper bounds of the classical prophet inequality. In particular, this implies that no improvement can be made with decay functions of the form D j (x) = x -c j with c j > 0, or D j (x) = λ j x with λ ∈ [0, 1). Subsequently, we develop algorithms and provide upper bounds in the D-prophet inequality, uniquely dependent on the parameter γ D . We illustrate them in Figure 1 , comparing them with the identity function γ → γ, which is a trivial lower bound.Prophet inequalities. The first prophet inequality was proven by Krengel and Sucheston [Krengel and Sucheston, 1977, 1978] in the setting where the items are observed in a fixed order, demonstrating that the dynamic programming algorithm has a competitive ratio of 1/2, which is the best possible.It was shown later that the same guarantee can be obtained with simpler algorithms [Samuel-Cahn, 1984, Kleinberg and Weinberg, 2012] , accepting the first value above a carefully chosen threshold. For a more comprehensive and historical overview, we refer the interested reader to surveys on the problem such as [Lucier, 2017 , Correa et al., 2019] . Prophet inequalities have immediate applications in mechanism design [Hajiaghayi et al., 2007 , Deng et al., 2022 , Psomas et al., 2022 , Makur et al., 2024] , auctions [Syrgkanis, 2017 , Dütting et al., 2020] , resource management [Sinclair et al., 2023] , and online matching [Cohen et al., 2019 , Ezra et al., 2020 , Jiang et al., 2021 , Papadimitriou et al., 2021 , Brubach et al., 2021] . Many variants and related problems have been studied, including, for example, the matroid prophet inequality [Kleinberg and Weinberg, 2012, Feldman et al., 2016] , prophet inequality with advice [Diakonikolas et al., 2021] , and variants with fairness considerations [Correa et al., 2021a, Arsenis and Kleinberg, 2022] .0.0 0.2 0.4 0.6 0.8 1.0 D ∈ [0, 1] 1/2 1 -1 ≈ 0.632 √ 3 -1 ≈ 0.Random order and IID models. Esfandiari et al. [2017] introduced the prophet secretary problem, where items are observed in a uniformly random order, and they proved a (1 -1 e )-competitive algorithm. Correa et al. [2021c] showed later a competitive ratio of 0.669, and Harb [2024] enhanced it to 0.6724, which currently stands as the best-known solution for the problem. They also proved an upper bound of √ 3 -1 ≈ 0.732, which was improved to 0.7254 in [Bubna and Chiplunkar, 2023] then 0.723 in [Giambartolomei et al., 2023] . Addressing the gap between the lower and upper bound remains an engaging and actively pursued open question. On the other hand, the study of prophet inequalities with IID random variables dates back to papers such as [Hill and Kertz, 1982, Kertz, 1986] , demonstrating guarantees on the dynamic programming algorithm. The problem was completely solved in [Correa et al., 2021b] , where the authors show that the competitive ratio of the dynamic programming algorithm is 0.745, thus it constitutes an upper bound on the competitive ratio of any algorithm, and they give a simpler adaptive threshold algorithm matching it. Another setting that we do not study in this paper, is the order selection model, where the decision-maker can choose the order in which the items are observed, knowing their distributions [Chawla et al., 2010 , Beyhaghi et al., 2021 , Peng and Tang, 2022] .Beyond the worst-case. In recent years, there has been increasing interest in exploring ways to exceed the worst-case upper bounds of online algorithms by providing the decision-maker with additional capabilities. A notable research avenue is learning-augmented algorithms [Lykouris and Vassilvtiskii, 2018] , which equip the decision-maker with predictions or hints about unknown variables of the problem. Multiple problems have been studied in this framework, such as scheduling [Purohit et al., 2018 , Lassota et al., 2023 , Benomar and Perchet, 2024b] , matching [Antoniadis et al., 2020 , Dinitz et al., 2021 , Chen et al., 2022] , caching [Antoniadis et al., 2023 , Chlkedowski et al., 2021 , Christianson et al., 2023] , the design of data structures [Kraska et al., 2018 , Lin et al., 2022 , Benomar and Coester, 2024] , and in particular, online selection problems [Dütting et al., 2021 , Sun et al., 2021 , Benomar et al., 2023 , Benomar and Perchet, 2024a , Diakonikolas et al., 2021] . More related to our setting, the ability to revisit items in online selection has been studied in problems such as the multiple-choice prophet inequality, where the algorithm can select up to k items and its reward is the maximum selected value [Assaf and Samuel-Cahn, 2000] . This allows for revisiting up to k items, chosen during the execution, for final acceptance or rejection decisions. Similarly, in Pandora's box problem [Weitzman, 1978 , Kleinberg et al., 2016] and its variants [Esfandiari et al., 2019 , Gergatsouli and Tzamos, 2022 , Atsidakou et al., 2024 , Gergatsouli and Tzamos, 2024 , Berger et al., 2024] , the decision maker decides the observation order of the items, but a cost c i is paid for observing each value X i , with the gain being the maximum observed value minus the total opening costs. A very recent work investigates a scenario closely related to the lookback prophet inequality [Ekbatani et al., 2024] where, upon selecting a candidate X i , the decision-maker has the option to discard it and choose a new value X j at any later step j, at a buyback cost of f X i , where f > 0. The authors present an optimal algorithm for the case when f ≥ 1, although the problem remains open for f ∈ (0, 1). Other problems were studied in similar settings, such as online matching [Ekbatani et al., 2022] and online resource allocation [Ekbatani et al., 2023] .2 From D-prophet to the D ∞ -prophet inequality Let us consider a sequence D of decay functions. By Definition 1.1, for any x ∈ [0, ∞] the sequence (D j (x)) j≥1 converges, since it is non-increasing and non-negative. Hence, there exists a mapping D ∞ such that for any x ≥ 0, lim j→∞ D j (x) = D ∞ (x). Furthermore, we can easily verify that D ∞ is non-decreasing and satisfies D ∞ (x) ∈ [0, x] for all x ≥ 0.Thanks to these properties, we obtain that (D ∞ ) j≥1 also satisfies Definition 1.1, and is hence a valid sequence of decay functions. We thus refer to the corresponding problem as the D ∞ -prophet inequality. Since D j ≥ D ∞ for any j ≥ 1, it is straightforward that the stopping problem with the decay functions D ∞ would be less favorable to the decision-maker. More precisely, for any random variables X 1 , . . . , X n , observation order π, and algorithm ALG with stopping time τ , it holds thatALG D (X 1 , . . . , X n ) := max{X π(τ ) , max i<τ D τ -i (X π(i) )} ≥ max{X π(τ ) , max i<τ D ∞ (X π(i) )} ,which corresponds to the output of ALG (with the same decision rule) when all the decay functions are equal to D ∞ . Therefore, any guarantees established for algorithms in the D ∞ -prophet inequality naturally extend to the D-prophet inequality. However, it remains uncertain whether the D-prophet inequality can yield improved competitive ratios compared to the D ∞ -prophet inequality. In the following, we prove that this is not the case, for all the order models presented in Section 1. Theorem 2.1. Let D ∞ be the pointwise limit of the sequence of decay functions D = (D j ) j≥1 . Then for any instance I = (F 1 , . . . , F n ) of non-negative distributions, it holds in the adversarial and the random order models thatEQUATIONwhere the supremum is taken over all the online algorithms A. In the IID model, the same inequality holds with an additional O(n -1/3 ) term, which depends only on the size n of the instance.The main implication of Theorem 2.1 is the following corollary.Corollary 2.1.1. In the adversarial order and the random order models, if A ∞ is an optimal algorithm for the D ∞ -prophet inequality, i.e. with maximal competitive ratio, then A ∞ is also optimal for the D-prophet inequality. Moreover, it holds thatCR D (A ∞ ) = CR D∞ (A ∞ ) .A direct consequence of this result is that, in the adversarial and the random order models, the asymptotic decay D ∞ entirely determines the competitive ratio that is achievable and the upper bounds for the D-prophet inequality. Therefore, we can restrict our analysis to algorithms designed for the problem with identical decay function. In the IID model, the same conclusion holds if the worst-case instances are arbitrarily large, making the additional O(n -1/3 ) term vanish. This is the case in particular in the classical IID prophet inequality [Hill and Kertz, 1982] .2.1 Sketch of the proof of Theorem 2.1While we use different techniques for each order model considered, all the proofs share the same underlying idea. Given any instance I of non-negative distributions, we build an alternative instance J such that the reward of any algorithm on I with decay functions D = (D j ) j is at most its reward on J with decay functions all equal to D ∞ . To do this, we essentially introduce an arbitrarily large number of zero values between two successive observations drawn from distributions belonging to I. Hence, under J, the algorithm cannot recover much more than a fraction D ∞ (X) for any past observation X collected from a distribution F ∈ I.In the adversarial case, implementing this idea is straightforward, since nature can build J by directly inserting m zeros between each pair of consecutive values, and the result is obtained by making m arbitrarily large. For the random order model, we use the same instance J, but extra steps are needed to prove that the number of steps between two non-zero values is very large with high probability.Moving to the IID model, an instance I is defined by a pair (F, n), where F is a non-negative distribution, and n is the size of the instance. In this scenario, we consider an instance consisting of m > n IID random variables(Y i ) i∈[m], each sampled from F with probability n/m, and equal to zero with the remaining probability. We again achieve the desired result by letting m be arbitrarily large compared to n. However, the number of variables sampled from F is not fixed; it follows a Binomial distribution with parameters (m, n/m). We control this variability by using concentration inequalities, which causes the additional term O(n -1/3 ).3 From D ∞ -prophet to the γ D -prophet inequalityAs discussed in Section 2, Theorem 2.1 implies that, for either establishing upper bounds or guarantees on the competitive ratios of algorithms, it is sufficient to study the D ∞ -prophet inequality, where all the decay functions are equal to D ∞ . The remaining question is then to determine which functions D ∞ allow to improve upon the upper bounds of the classical prophet inequality. Before tackling this question, let us make some observations regarding algorithms in the D ∞ -prophet inequality.In the D ∞ -prophet inequality, it is always possible to have a reward of D ∞ (max i∈[n] X i ) by rejecting all the items and then selecting the maximum by the end. Thus, it is suboptimal to stop at a step i where X i ≤ D ∞ (max j<i X j ). An algorithm respecting this decision rule is called rational. Lemma 3.1. For any rational algorithm ALG in the D ∞ -prophet inequality, if we denote by τ its stopping time, then for any instance I = (F 1 , . . . , F n ) and X i ∼ F i for all i ∈ [n] we haveALG D∞ (X 1 , . . . , X n ) = ALG 0 (X 1 , . . . , X n ) + D ∞ max i∈[n] X i 1 τ =n+1 ,where ALG 0 denotes the reward of the algorithm in the standard prophet inequality. Moreover, the optimal dynamic programming algorithm in the D ∞ -prophet inequality is rational.The best competitive ratio in the D ∞ -prophet inequality is achieved, possibly among others, by the optimal dynamic programming algorithm, which is a rational algorithm by the previous Lemma. Hence, it suffices to prove upper bounds on rational algorithms. We use this observation to prove the next propositions.Proposition 3.2. In the D ∞ -prophet inequality, if inf x>0 D∞(x) x = 0, then it holds, in any order model, thatEQUATIONwhere the supremum is taken over all the online algorithms A, and CR 0 denotes the competitive ratio in the standard prophet inequality.Proposition 3.2 implies that if inf x>0 D∞(x) x = 0, then, in any order model, any upper bound on the competitive ratios of all algorithms in the classical prophet inequality is also an upper bound on the competitive ratios of all algorithm in the D ∞ -prophet inequality. Consequently, for surpassing the upper bounds of the classical prophet inequality, it is necessary to have, for some γ > 0, that D ∞ (x) ≥ γx for all x ≥ 0. Furthermore, the next Proposition allows giving upper bounds in the D ∞ -prophet inequality that depend only on inf x>0 D∞(x)x . Proposition 3.3. Let γ = inf x>0 D ∞ (x)/x, and 0 < a < b. Consider an instance I of distributions with support in {0, a, b}, then in any order model and for any algorithm ALG we have thatCR D∞ (ALG) ≤ sup A E[A γ (I)] E[OPT(I)],where E[A γ (I)] is the reward of A if all the decay functions were equal to x → γx.The core idea for proving this proposition is that rescaling an instance, i.e. considering (rX i ) i∈[n] instead of (X i ) i∈[n] , has no impact in the classical prophet inequality. However, in the D ∞ -prophet inequality, rescaling can be exploited to adjust the ratio D∞(rx) rx . By considering instances with random variables taking values in {0, a, b} almost surely, where a < b, a reasonable algorithm facing such an instance would never reject the value b. Consequently, the value it recovers from rejected items is either D ∞ (0) = 0 or D ∞ (a). Rescaling this instance by a factor r = s/a and taking the ratio to the expected maximum, the term D∞(s) s appears, with s a free parameter that can be chosen to satisfy D∞(s) s→ inf x>0 D∞(x) x = γ D . As a consequence, if inf x>0 D∞(x) x= γ, then any upper bound obtained in the γ-prophet inequality (when the decay functions are all equal to x → γx) using instances of random variables (X 1 , . . . , X n ) satisfying X i ∈ {0, a, b} a.s. for all i, is also an upper bound in the D ∞ -prophet inequality.Implication Consider any sequence D of decay functions, and defineγ D := inf x>0 D ∞ (x) x = inf x>0 inf j≥1 D j (x)x .For any x > 0 and j ≥ 1 it holds that D j (x) ≥ γ D x, therefore, any guarantees on the competitive ratio of an algorithm in the γ D -prophet inequality are valid in the D-prophet inequality, under any order model. Furthermore, combining Theorem 2.1 and Proposition 3.3, we obtain that for any instance I of random variables taking values in a set {0, a, b} it holds that∀ALG : CR D (ALG) ≤ sup A E[A γ D (I)] E[OPT(I)],with an additional term of order O(n -1/3 ) in the IID model. In the particular case where γ D = 0, Proposition 3.3 with Theorem 2.1 give a stronger result, showing that no algorithm can surpass the upper bounds of the classical prophet inequality. This is true also for the IID model since the instances used to prove the tight upper bound of ≈ 0.745 are of arbitrarily large size [Hill and Kertz, 1982] .Therefore, by studying the γ-prophet inequality for γ ∈ [0, 1], we can prove upper bounds and lower bounds on the D-prophet inequality for any sequence D of decay functions. 
the γ-prophet inequality: 
 We study in this section the γ-prophet inequality, where all the decay functions are equal to x → γx, for some γ ∈ [0, 1]. For any algorithm ALG with stopping time τ and random variables X 1 , . . . , X n , if the observation order is π, we use the notationALG γ (X 1 , . . . , X n ) = max{X π(τ ) , γX π(τ -1) , . . . , γX π(1) } .and we denote by CR γ (ALG) the competitive ratio of ALG in this setting. In the following, we provide theoretical guarantees for the γ-prophet inequality.For each observation order, we first derive upper bounds on the competitive ratio of any algorithm, depending on γ, using only hard instances satisfying the condition of Proposition 3.3. This would guarantee that the upper bounds extend to the D-prophet inequality if γ D = γ. Then, we design single-threshold algorithms with well-chosen thresholds depending on γ and the distributions, with competitive ratios improving with γ. A crucial property of single-threshold algorithms, which we use to estimate their competitive ratios, is that their reward satisfiesEQUATIONThe additional term appearing due to γ depends only on max i∈[n] X i , which is the reward of the prophet against whom we compete. This property is not satisfied by more general class of algorithms such as multiple-threshold algorithms, where each observation X π(i) is compared with a threshold θ i . Remark 4.1. We only consider instances with continuous distributions in the proofs of lower bounds.The thresholds θ considered are such that Pr(max i∈[n] X i ≥ θ) = g(γ, n, π), with g depending on γ, the order model π and the size of the instance n. Such a threshold is always guaranteed to exist when the distributions are continuous. However, as in the prophet inequality, the algorithms can be easily adapted to non-continuous distributions by allowing stochastic tie-breaking. A detailed strategy for doing this can be found for example in [Correa et al., 2021c] .Before delving into the study of the different models, we provide generic lower and upper bounds, which depend solely on the bounds of the classical prophet inequality and γ. Proposition 4.2. In any order model, if α is a lower bound in the classical prophet inequality, and β an upper bound, then, in the γ-prophet inequality (i) there exists a trivial algorithm with a competitive ratio of at least max{γ, α}, (ii) the competitive ratio of any algorithm is at most (1 -γ)β + γ.We first consider the adversarial order model, and prove the upper bound of 1 2-γ . Then, we provide a single-threshold algorithm with a competitive ratio matching this upper bound, hence fully solving the γ-prophet inequality in this adversarial order model. Theorem 4.3. In the adversarial order model, the competitive ratio of any algorithm is at most 1 2-γ . Furthermore, there exists a single threshold algorithm with a competitive ratio 1 2-γ : given any instance (F 1 , . . . , F n ), this is achieved with the threshold θ satisfyingPr X1∼F1,...,Xn∼Fn (max i∈[n] X i ≤ θ) = 1 2-γ .The upper bound in the previous theorem is proved using instances satisfying the condition of Proposition 3.3. Hence it extends to the D ∞ -then to the D-prophet inequality, with γ = γ D , by Proposition 3.3 and Theorem 2.1.Consider now that the items are observed in a uniformly random order X π(1) , . . . , X π(n) , andX * = max i∈[n] X i .As for the adversarial model, we first prove an upper bound on the competitive ratio as a function of γ, and then prove a lower bound for a single-threshold algorithm. However, for this model, there is a gap between the two bounds, as illustrated in Figure 1 .We first prove an upper bound that depends on γ, matching the upper bound √ 3 -1 of Correa et al. [2021c] when γ = 0 and equal to 1 when γ = 1. Our single-threshold algorithm has a competitive ratio of at least (1 -1 e ) when γ = 0, which is the best competitive ratio of a single threshold algorithm in the prophet inequality [Esfandiari et al., 2017 , Correa et al., 2021c] , and equal to 1 for γ = 1. Theorem 4.4. The competitive ratio of any algorithm ALG in the γ-prophet inequality with random order satisfiesCR γ (ALG) ≤ (1 -γ) 3/2 ( 3 -γ -1 -γ) + γ .Furthermore, denoting by p γ is the unique solution to the equation 1-(1 -γ)p = 1-p -log p , the single-threshold algorithm ALG θ with Pr X1∼F1,...,Xn∼Fn (max i∈[n] X i ≤ θ) = p γ satisfies CR γ (ALG) ≥ 1 -(1 -γ)p γ .Similarly to the adversarial order model, we used instances satisfying the condition of Proposition 3.3 to prove the upper bound, thus it extends to the D-prophet inequality with γ = γ D .While the equation defining p γ cannot be solved analytically, the solution can easily be computed numerically for any γ ∈ [0, 1]. Before moving to the IID case, we propose in the following a more explicit lower bound derived from Theorem 4.4. Corollary 4.4.1. In the random order model, the single threshold algorithm with a threshold θ satisfying Pr(max i∈[n] X i ≥ θ) = 1/e 1-(1-1/e)γ has a competitive ratio of at least 1 -(1-γ)/e 1-(1-1/e)γ .In the classical IID prophet inequality, [Hill and Kertz, 1982] showed that the competitive ratio of any algorithm is at most ≈ 0.745. The proof of this upper bound is hard to generalize for the IID γ-prophet inequality. As an alternative, we prove a weaker upper bound, which equals ≈ 0.778 for γ = 0 and 1 for γ = 1, and the proof relies on instances of arbitrarily large size satisfying the condition of Proposition 3.3, hence the upper bound can be extended to the D-prophet inequality.Subsequently, we present a single-threshold algorithm with the same competitive ratio as the random order algorithm. However, the proof is different, leveraging the fact that the variables are identically distributed. More precisely, we introduce a single-threshold algorithm with guarantees that depend on the size n of the instance, then we show that its competitive ratio is at least that of the algorithm presented in Theorem 4.4, with equality when n approaches infinity.Although it might look surprising that the obtained competitive ratio in the IID model is not better than that of the random-order model, the same behavior occurs in the classical prophet inequality. Indeed, Li et al. [2022] established that no single-threshold algorithm can achieve a competitive ratio better than 1 -1/e in the standard prophet inequality with IID random variables, which is also the best possible with a single-threshold algorithm in the random order. However, considering larger classes of algorithms, the competitive ratios achieved in the IID model are better than those of the random order model.We describe the algorithm and give a first lower bound on its reward depending on the size of the instance in the following lemma.Lemma 4.5. Let a n,γ be the unique solution of the equation1 (1-a/n) n -1 1 a -1 = γ, then for any IID instance X 1 , . . . , X n , the algorithm with threshold θ satisfying Pr(X 1 > θ) = an,γ n has a reward of at least 1 a n,γ 1 -1 - a n,γ n n E[max i∈[n] X i ] .We can prove that the reward presented in the Lemma above is strictly better than that of the random order model. However, both are asymptotically equal as we show in the following theorem.Theorem 4.6. The competitive ratio of any algorithm in the IID γ-prophet inequality is at mostU (γ) = 1 -(1 -γ) e 2 log(3 -γ) -(2 -γ) 2(2e 2 -1) -(3e 2 -1)γ .In particular, U is increasing,EQUATION2 ) ≈ 0.778 and U (1) = 1. Furthermore, there exists a single-threshold algorithm ALG θ satisfyingCR γ (ALG θ ) ≥ 1 -(1 -γ)p γ ,where p γ is defined in Theorem 4.4.To prove the upper bound, we used instances satisfying the condition of Proposition 3.3, guaranteeing that it remains true in the D ∞ -prophet inequality with γ = γ D . On the other hand, Theorem 2.1 ensures that the upper bound extends to the D-prophet inequality, but with an additional O(1/n 1/3 ) term. The latter does change the result, as we considered instances of arbitrarily large size n → ∞. 
conclusion: 
 In this paper, we addressed the D-prophet inequality problem, which models a very broad spectrum of online selection scenarios, accommodating various observation order models and allowing to revisit rejected candidates at a cost. The problem extends the classic prophet inequality, corresponding to the special case where all decay functions are zero. The main result of the paper is a reduction from the general D-prophet inequality to the γ-prophet inequality, where all the decay functions equal to x → γx for some constant γ ∈ [0, 1]. Subsequently, we provide algorithms and upper bounds for the γ-prophet inequality, which remain valid, by the previous reduction, in the D-prophet inequality. Notably, the proved upper and lower bounds match each other for the adversarial order model, hence completely solving the problem. Our analysis paves the way for more practical applications of prophet inequalities, and advances efforts towards closing the gap between theory and practice in online selection problems. 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: The contribution of the paper is mainly theoretical.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: We do not use any assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 
 
 Appendix: Better upper bounds in the D ∞ -prophet inequality. Proposition 3.3 establishes that upper bounds proved in the γ-prophet inequality using instances of random variables with support in some set {0, a, b} remain true in the D ∞ -prophet inequality, hence in the D-prophet inequality by Theorem 2.1. This is enough to establish a tight upper bound in the adversarial order model, but not in the random order and IID models. An interesting question to explore is if more general upper bounds can be extended, or not, from the γto the D-prophet inequality.Algorithms for the γ-prophet inequality. As explained in Section 4, our analysis of the competitive ratio of single-threshold algorithms relies on the identity (4), which is not satisfied for instance by multiple-threshold algorithms. In the adversarial order model, we proved that the optimal competitive ratio 1/(2 -γ) can be achieved with a single-threshold algorithm. However, this is not the case in the random order or IID models. An interesting research avenue is to study other classes of algorithms in the γ-prophet inequality.A From D-prophet to the D ∞ -prophet inequalityIn this section, we prove the reduction from the D-prophet to the D ∞ -prophet inequality problem in the adversarial and random order models, and the reduction up to an additional O(n -1/3 ) term in the IID model. First, we prove Corollary 2.1.1, which is the principal implication of Theorem 2.1.A.1 Proof of Corollary 2.1.1Proof. Let us denote A * ,∞ the algorithm taking optimal decisions for any instance in the D ∞ -prophet inequality (obtained via dynamic programming). Then, by Theorem 2.1 we obtain for the adversarial and random order models thatsup ALG CR D (ALG) ≤ inf I sup A E[A D∞ (I)] E[OPT(I)] = inf I E[A D∞ * ,∞ (I)] E[OPT(I)] = CR D∞ (A * ,∞ ) = sup A CR D∞ (A) .(5) Since CR D (ALG) ≥ CR D∞ (ALG) for any algorithm, we deduce that ( 5) is an equality. If we consider now any algorithm A ∞ that is optimal for the D ∞ -prophet inequality, not necessarily A * ,∞ , then Equation ( 5) providesCR D (A ∞ ) ≥ CR D∞ (A ∞ ) = sup ALG CR D (ALG) .The previous inequality is again an equality, and it implies that Ā∞ is also optimal, in the sense of the competitive ratio, for the D-prophet inequality, andCR D (A ∞ ) = CR D∞ (A ∞ ) .The efficiency of the proof scheme introduced in Section 2.1 relies on the following key argument: if (D j ) j≥1 converges pointwise to D ∞ , then for any algorithm A and any instance I, the output of A when all the decay functions are equal to D m converges to its output when all the decay functions are equal to D ∞ . If X 1 , . . . , X n are the realizations of I observed by A and if σ is the order in which they are observed, then denoting τ the stopping time of A we can write thatE[A Dm (I)] -E[A D∞ (I)] = E[max{X σ(τ ) , D m (max i<τ X σ(i) )}] -E[max{X σ(τ ) , D ∞ (max i<τ X σ(i) )}] ≤ max π∈Sn q∈[n] E[max{X π(q) , D m (max i<q X π(i) )}] -E[max{X π(q) , D ∞ (max i<q X π(i) )}] ,where S n is the set of all permutations of [n]. The latter upper bound is independent of σ and A. We show in the following lemma that it converges to 0 when m → ∞. Lemma A.1. Let S n be the set of all permutations of [n]. For any fixed instanceI = (F 1 , . . . , F n ), considering X i ∼ F i for all i ∈ [n], define for all m ≥ 1 ϵ m (I) = max π∈Sn q∈[n] E[max{X π(q) , D m (max i<q X π(i) )}] -E[max{X π(q) , D ∞ (max i<q X π(i) )}] . If E[max i∈[n] X i ] < ∞, then lim m→∞ ϵ m (I) = 0.Proof. Let us denote f 1 , . . . , f n the respective probability density functions of X 1 , . . . , X q . For any q ∈ [n] and π ∈ S n , let us define for all m ≥ 0 the function φ π,q m : [0, ∞) q → [0, ∞) by φ π,q m (x 1 , . . . , x q ) = max{x π(q) , D m (max i<q x π(i) )} -max{x π(q) , D ∞ (max i<q x π(i) )}. φ π,q m is positive because D m ≥ D ∞ . The sequence (φ π,q m ) m is non-increasing, converges to 0 pointwise, and is dominated by (x 1 , . . . , x q ) → max i∈ [q] x i , which is integrable with respect to the probability measure (x 1 , . . . , x q ) → q i=1 f (x i ). Therefore, using the dominated convergence theorem, we deduce that lim m→∞ E[φ π,q m (X 1 , . . . , X q )] = 0. It follows thatlim m→∞ ϵ m (I) = lim m→∞ max π∈Sn q∈[n]E[φ π,q m (X 1 , . . . , X q )] = 0 .A.3 Proof of Theorem 2.1Proof of Theorem 2.1. We provide a separate proof for each of the adversarial order, random order and IID models.Adversarial order Let I = (F 1 , . . . , F n ) be any instance andX i ∼ F i for all i ∈ [n]. Consider the instance I m = (Y 1 , . . . , Y mn ), where Y km ∼ F k for any k ∈ [n]and Y i = 0 a.s. for all i / ∈ {m, 2m, . . . , mn}. It is clear that no reasonable algorithm would stop at a zero value: if the current observation is 0 it is preferable to wait for a non-null value, or it would have been preferable to stop at the previous non-null value. Hence, τ is a multiple of m: τ = ρm for some ρ ∈ N ⋆ . Given that D j (0) = 0 for all j and the sequence (D j ) j is non-increasing, we have thatE[ALG D (I m )] = E[max i≤τ D τ -i (Y i )] = E[max k≤ρ D τ -km (Y km )] = E[max k≤ρ D ρm-km (X k )] = E[max{X ρ , max k<ρ D (ρ-k)m (X k )}] ≤ E[max{X ρ , max k<ρ D m (X k )}] ≤ E[max{X ρ , max k<ρ D ∞ (X k )}] + ϵ m (I) ,where ϵ m (I) is defined in Lemma A.1. We can then use that the first right-hand term is the output of some other algorithm that would choose a stopping time ρ when facing I in the context of the D ∞ -prophet inequality. More precisely, consider the algorithm A m which, given any instance I = (F 1 , . . . , F n ), simulates the behavior of ALG facing the sequence I m , where at each step i ∈ [mn]• if i / ∈ {m, . . . , nm}: ALG observes Y i = 0, • otherwise, if i = km for some k ∈ [n]: A m observes X k and ALG observes Y km = X k• if ALG stops on Y ρm , then A m also stops, and its reward is X ρ .A m (X 1 , . . . , X n ) stops at the same value as ALG(Y 1 , . . . , Y m ), their reward in the D ∞ -prophet inequality is the same, and since maxi∈[n] X i = max i∈[mn] Y i this yields to CR D (ALG) ≤ E[ALG D (I m )] E[OPT(I m )] ≤ E[A D∞ m (I)] + ϵ m (I) E[OPT(I)] ≤ sup A: algo E[A D∞ (I)] E[OPT(I)] + ϵ m (I) E[OPT(I)],and taking the limit when m → ∞ gives the result, by making the second term vanish.Random order Let I = (F 1 , . . . , F n ) be an instance of distributions andX i ∼ F i for i ∈ [n].Using the notation δ 0 for the Dirac distribution in 0, we consider I m = (F 1 , . . . , F n , δ 0 , . . . , δ 0 ) containing m copies of δ 0 so that the observations from this instance always contain at least m null values. Let Y 1 , . . . , Y m be a realization of this instance. For simplicity, say thatY i = X i for i ∈ [n],andY i = 0 for i > n.We first show that when m → ∞, since the observation order is drawn uniformly at random, the algorithm observes a large number of zeros between every two random variables drawn from (F 1 , . Pr(L ≤ ℓ) = Pr(∪ n-1 i=1 {t i+1 -t i ≤ ℓ}) = Pr ∪ n k=1 ∪ k-1 j=1 |π -1 (k) -π -1 (j)| ≤ ℓ ≤ n(n -1) 2 Pr(|π -1 (1) -π -1 (2)| ≤ ℓ) = n(n -1) 2 Pr( ∪ n+m k=1 (π -1 (1) = k, π -1 (2) ∈ {k -ℓ, . . . , k + ℓ} \ {k}) ≤ n(n -1) 2 × (n + m) × 1 n + m × 2ℓ n + m -1 ≤ n 2 ℓ m .Taking ℓ = √ m, we find that Pr(L ≤ ℓ) ≤ n 2 / √ m. Therefore, for any algorithm ALG, observing that the reward of ALG D is at most max i∈[n] X i a.s., and by independence of max i∈[n] X i and L, we deduce thatEQUATIONLet us denote τ the stopping time of ALG and t ρ = max j∈[n] {t j : t j ≤ τ } the last time when a variable (X j ) j∈ [n] was observed by ALG. The sequence of functions (D j ) j≥1 is non-increasing, hence • if u π(j) = 0, then ALG observes the value Y π(j) = 0,EQUATION• if u π(j) = 1, then A m observes the next value X σ(k) , and ALG observes Y π(j) = X σ(k) ,• when ALG decides to stop, A m also stops, and its reward is the current value X σ(k) .With this construction, (Y j ) j∈[n+m] is indeed a realization of the instance I m , and A m stops on the last value sampled from F 1 , . . . , F n observed by ALG. Therefore, denoting ρ the stopping time of A m , and ϵ ℓ (I) as defined in Lemma A.1, we haveE[ALG D (I m ) | L > ℓ] ≤ E[max Y π(tρ) , max j<ρ D ℓ (Y π(tj ) ) ] = E[max X σ(ρ) , max j<ρ D ℓ (X σ(tj ) ) ] = E[A D ℓ m (I)] ≤ E[A D∞ m (I)] + ϵ ℓ (I) ≤ sup A:algo E[A D∞ (I)] + ϵ ℓ (I) .Taking ℓ = √ m and substituting into Equation ( 6), then observing that E[OPT(I)] = E[OPT(I m )], gives thatCR D (ALG) ≤ E[ALG D (I m )] E[OPT(I m )] ≤ sup A:algo E[A D∞ (I)] E[OPT(I)] + ϵ √ m (I) E[OPT(I)] + n 2 √ m .Finally, taking m → ∞ and using Lemma A.1, we deduce thatCR D (ALG) ≤ sup A:algo E[A D∞ (I)] E[OPT(I)],which completes the proof for the random order.IID random variables For any probability distribution F on [0, ∞) and for any n ≥ 1 we denote E[OPT(F, n)] the expected maximum of n independent random variables drawn from F , and for any algorithm ALG we denote E[ALG D (F, n)] its expected output when given n IID variable sampled from F as input. The proof of Theorem 2.1 for this last model is much more technical than for previous models, so we first prove several auxiliary results that we will later use to provide a concise proof of the last part of the theorem.Lemma A.2. For any probability distribution F and n ≥ 1, ∆ ≥ 0, we haveE[OPT(F, n + ∆)] ≤ 1 + ∆ n E[OPT(F, n)] .Proof. We first writePr(OPT(F, n + ∆) > x) = 1 -F (x) n+∆ = 1 + F (x) n 1 -F (x) ∆ 1 -F (x) n (1 -F (x) n ) = 1 + F (x) n 1 -F (x) ∆ 1 -F (x) n Pr(OPT(F, n) > x) ,and then use thatF (x) ∆ = e ∆ log(F (x)) ≥ 1 + ∆ log(F (x)) = 1 - ∆ n log(1/F (x) n ) ≥ 1 - ∆ n 1 -F (x) n F (x) n ,so we directly obtainF (x) n 1 -F (x) ∆ 1 -F (x) n ≤ ∆ n ,which gives thatPr(OPT(F, n + ∆) > x) ≤ 1 + ∆ n Pr(OPT(F, n) > x) .As we consider non-negative random variables, it follows directly thatE[OPT(F, n + ∆)] ≤ 1 + ∆ n E[OPT(F, n)] . Lemma A.3. Let N ∼ B(m, ε) and let n := E[N ] = εm, then we have E[OPT(F, N )1 N ≥n+n 2/3 ] ≤ 6 n 1/3 E[OPT(F, n + n 2/3 )] , E[OPT(F, N )] ≤ 1 + 3 n 1/3 E[OPT(F, n + n 2/3 )] . Proof. Let ∆, s > 0 such that ∆ ≤ s. For any k ≥ 1 let W k = [s + (k -1)∆, s + k∆). (W k ) k≥1 is a partition of [s, ∞), thus we have E[OPT(F, N )1 N ≥s ] = ∞ k=1 E[OPT(F, N )1 N ∈W k ] ≤ ∞ k=1 E[OPT(F, s + k∆)1 N ∈W k ] = ∞ k=1 E[OPT(F, s + k∆)] Pr(N ∈ W k ) ≤ ∞ k=1 1 + k∆ s E[OPT(F, s)] Pr(N ∈ W k ) = Pr(N ≥ s) + ∆ s ∞ k=1 k Pr(N ∈ W k ) E[OPT(F, s)] ,where we used Lemma A.2 in the penultimate inequality. Furthermore, observing that∞ k=1 k Pr(N ∈ W k ) = ∞ k=1 k-1 ℓ=0 Pr(N ∈ W k ) = ∞ ℓ=0 ∞ k=ℓ+1 Pr(N ∈ W k ) = ∞ ℓ=0 Pr(N ≥ s + ℓ∆) ,we obtain, given ∆ ≤ s, thatEQUATIONN is a Binomial random variable with expectation n. Therefore, Chernoff's inequality gives for any δ ≥ 0 thatPr(N ≥ (1 + δ)n) ≤ exp - δ 2 n 2 + δ ≤ exp - min(δ, δ 2 )n 3 ,where the second inequality can be derived by treating separately δ < 1 and δ ≥ 1. In particular, for any k ≥ 1, taking δ = k∆ n such that ∆ ≤ n yieldsPr(N ≥ n+k∆) ≤ exp - min(k∆, k 2 ∆ 2 /n) 3 ≤ exp - k min(∆, ∆ 2 /n) 3 = exp - k∆ 2 3n .Substituting this Inequality into (11) with s = n + ∆, we obtainE[OPT(F, N )1 N ≥n+∆ ] ≤ 2 ∞ k=1 Pr(N ≥ n + k∆) E[OPT(F, n + ∆)] ≤ 2 ∞ k=1 exp - k∆ 2 3n E[OPT(F, n + ∆)] = 2 exp ∆ 2 3n -1 E[OPT(F, n + ∆)] ≤ 6n ∆ 2 E[OPT(F, n + ∆)] ,and taking ∆ = n 2/3 proves the first inequality of the lemma.Let us move now to the second inequality. We have , s) ] Pr(N < s) , and thus, using Inequality (10), again with s = n + ∆ and ∆ = n 2/3 , it follows thatE[OPT(F, N )1 N <s ] ≤ E[OPT(F, s)1 N <s ] = E[OPT(FE[OPT(F, N )] = E[OPT(F, N )1 N <s ] + E[OPT(F, N )1 N ≥s ] ≤ 1 + ∆ s ∞ k=0 Pr(N ≥ s + k∆) E[OPT(F, s)] ≤ 1 + ∞ k=1 Pr(N ≥ n + k∆) E[OPT(F, s)] ≤ 1 + 3 n 1/3 E[OPT(F, n + ∆)] . Lemma A.4. Let δ 1 , . . . , δ m iid ∼ B(ε), and N = m i=1 δ i . Denoting by n = E[N ] = εm, if n ≥ 4 then E[N 2 OPT(F, N )] ≤ 1 + 8 n 3 n 2 E[OPT(F, n + n 2/3 )] . Proof. For all k ∈ [m], denote by N k = m i=k δ i . We have that N 2 OPT(F, N ) = m i=1 δ i 2 OPT(F, N ) =   m i=1 δ 2 i + 2 i<j δ i δ j   OPT(F, N ) ,and observing that δ 2 i = δ i for all i, we obtain in expectationEQUATION) For j ∈ {1, 2}, the proof of Lemma A.3 can be easily adjusted to prove an upper bound on E[OPT(F, j + N j+1 ), by first bounding E[OPT(F, j + N j+1 )1 Nj+1≥s ] then E[OPT(F, j + N j+1 )1 Nj+1<s ]. The concentration arguments remain the same, replacing m by m -j. The expectation of N j+1 is ε(m -j) = n -εj, hence we obtainE[OPT(F, j + N j+1 )] ≤ 1 + 3 (n -εj) 1/3 E[OPT(F, j + (n -εj) + (n -εj) 2/3 )] = 1 + 3 (n -εj) 1/3 E[OPT(F, j + n + n 2/3 )] ≤ 1 + 3 (n -2) 1/3 E[OPT(F, 2 + n + n 2/3 )] ≤ 1 + 4 n 1/3 E[OPT(F, 2 + n + n 2/3 )] ,where we used respectively in the last inequalities that j ≤ 2 and n ≥ 4. Furthermore, Lemma A.2 gives thatE[OPT(F, j + N j+1 )] ≤ 1 + 4 n 1/3 1 + 2 n + n 2/3 E[OPT(F, n + n 2/3 )] ≤ 1 + 6 n 1/3 E[OPT(F, n + n 2/3 )] ,where the last inequality is true for n ≥ 4. Finally, substituting into 12 yieldsE[N 2 OPT(F, N )] ≤ (m 2 ε 2 + mε) 1 + 6 n 1/3 E[OPT(F, n + n 2/3 )] = (n 2 + n) 1 + 6 n 1/3 E[OPT(F, n + n 2/3 )] = 1 + 1 n 1 + 6 n 1/3 n 2 E[OPT(F, n + n 2/3 )] ≤ 1 + 8 n 1/3 n 2 E[OPT(F, n + n 2/3 )] . Lemma A.5. Let δ 1 , . . . , δ m iid ∼ B(ε), N = m i=1 δ i , n = E[N ] = εm and L = min i̸ =j {|i -j| : δ i = 1, δ j = 1}, then for any ℓ ≥ 0 we have E[OPT(F, N )1 L≤ℓ ] ≤ 7mℓε 2 E[OPT(F, n + n 2/3 )] .Proof. The random variables N and L are not independent, thus we need to adequately compute the distribution of L conditional to N . For any ℓ ≥ 0 and k ≥ 2 we havePr(L ≤ ℓ, N = s) = Pr L ≤ ℓ, m i=1 δ k = s = Pr ∪ m i=1 ∪ i-1 j=max(1,i-ℓ) δ i = δ j = 1, m i=1 δ k = s ≤ mℓ Pr δ 1 = δ 2 = 1, m i=3 δ k = s -2 = mℓ m -2 s -2 ε s (1 -ε) m-s+2 , therefore Pr(L ≤ ℓ | N = s) = Pr(L ≤ ℓ, N = s) Pr(N = s) ≤ mℓ m-2 s-2 ε s (1 -ε) m-s+2 m s ε s (1 -ε) m-s ≤ mℓ m-2 s-2 m s = mℓ s(s -1) m(m -1) ≤ ℓs 2 m .Using this inequality and Lemma A.4, we deduce thatE[OPT(F, N )1 L≤ℓ ] = E[OPT(F, N ) Pr(L ≤ ℓ | N, OPT(F, N ))] = E[OPT(F, N ) Pr(L ≤ ℓ | N )] ≤ ℓ m E[N 2 OPT(F, N )] ≤ 1 + 8 n 1/3 ℓn 2 m E[OPT(F, n + n 2/3 )] = 1 + 8 n 1/3 mℓε 2 E[OPT(F, n + n 2/3 )] = 7mℓε 2 E[OPT(F, n + n 2/3 )] .where we used that 1 + 8 n 1/3 ≤ 7 for n ≥ 4.Using the previous lemmas, we can now prove the theorem. Let m > n ≥ 1, ∆ = n 2/3 , ε = n/m and let Q be the probability distribution of a random variable that is equal to 0 with probability 1 -ε, and drawn from F with probability ε.Let us consider m i.i.d. variables Y 1 , . . . , Y m ∼ Q, and for each i ∈ [m] we denote by δ i the indicator that Y i is drawn from F . Define N = m i=1 δ i ∼ B(m, ε) the number of random variables Y i drawn from the distribution F . In the following, we upper bound the competitive ratio of any algorithm by analyzing its ratio on this particular instance. For this, we first provide a lower bound on E[OPT(Q, m)] using Lemma A.2, and obtainE[OPT(F, n -∆)] ≥ 1 1 + 2∆ n E[OPT(F, n + ∆)] ≥ 1 - 2∆ n E[OPT(F, n + ∆)] ,thus we haveEQUATIONwhere, for the last three inequalities, we used respectively Bernoulli's inequality, Chernoff bound, then e -y ≤ 1/y.Then, we upper bound the reward of any algorithm given the instance (Q, m) as input. Let L = min i̸ =j {|i -j| : δ i = 1, δ j = 1} the smallest gap between two successive variables Y i drawn from F , and let t 1 < . . . < t N the indices for which δ i = 1. We have for any algorithm ALG and positive integer ℓ thatEQUATION)Using Lemma A.3 and Lemma A.5, the first term can be bounded as followsE[ALG D (Q, m)1 N ≥n+∆ or L≤ℓ ] ≤ E[OPT(F, N )1 N ≥n+∆ or L≤ℓ ] ≤ E[OPT(F, N )1 N ≥n+∆ ] + E[OPT(F, N )1 L≤ℓ ] ≤ 6 n 1/3 + 7mℓε 2 E[OPT(F, n + n 2/3 )] .Recalling that ε = m/n and taking ℓ = √ m, we obtainEQUATION)Regarding the second term in Equation ( 14), let τ be the stopping time of ALG and t ρ = max{j ≤ τ : δ j = 1} the last value sampled from F and observed by ALG before it stops. We haveE[ALG D (Q, m)1 N <n+∆,L>ℓ ] ≤ E[ALG D (Q, m) | N < n + ∆, L > ℓ] = E[max i∈[τ ] D τ -i (Y i ) | N < n + ∆, L > ℓ] = E[max j∈[ρ] D τ -tj (Y i ) | N < n + ∆, L > ℓ] ≤ E[max j∈[ρ] D tρ-tj (Y i ) | N < n + ∆, L > ℓ] = E[max Y tρ , max j<ρ D tρ-tj (Y tj ) | N < n + ∆, L > ℓ] ≤ E[max Y tρ , max j<ρ D ℓ (Y tj ) | N < n + ∆] .We then prove that the last term is the reward of an algorithm A m in the D ℓ -prophet inequality. Let us A m be the algorithm that takes as input an instance X 1 , . . . , X n+∆-1 of n + ∆ IID random variables,then simulates ALG D (Q, m) | N < n + ∆ as follows: let δ 1 , . . . , δ m iid ∼ B(n/m) set N A = 0 and for each i ∈ [m] • if δ i = 0: ALG observes the value Y i = 0, • if δ i = 1: increment N , then A m observes the next value X k , and ALG observes Y i = X k , • if N A = n + ∆ -1 or ALG stops, then A m also stops.When ALG decides to stop, the current value observed by A m is X ρ : the last value Y tρ observed by ALG such that δ tρ = 0. Observe that stopping when N A = n + ∆ + 1, is equivalent to letting ALG observe zero values until the end, and stopping when ALG stops. Hence, the variables Y 1 , . . . , Y m have the same distribution as m IID samples from Q conditional to N < n + ∆. Denoting ρ the stopping time of A m and ϵ ℓ (F, n + ∆) as defined in Lemma A.1, we deduce thatEQUATIONSubstituting ( 15) and ( 16) in ( 14), with ℓ = √ m, yieldsE[ALG D (Q, m)] ≤ 6 n 1/3 + 7n 2 √ m E[OPT(F, n + ∆)] + E[A D∞ m (F, n + ∆)] + ϵ √ m (F, n + ∆) ,and using Inequality 13, it follows thatCR D (ALG) ≤ E[ALG D (Q, m)] E[OPT(Q, m)] ≤ 6 n 1/3 + 7n 2 √ m 1 -4 n 1/3 + E[A D∞ m (F, n + ∆)] + ϵ √ m (F, n + ∆) (1 -4 n 1/3 )E[OPT(F, n + ∆)] ≤ 6 n 1/3 + 7n 2 √ m 1 -4 n 1/3 + 1 1 -4 n 1/3 ϵ √ m (F, n + ∆) E[OPT(F, n + ∆)] + sup A:algo E[A D∞ (F, n + ∆)] E[OPT(F, n + ∆)] ,taking the limit m → ∞ and using Lemma A.1 givesCR D (ALG) ≤ 6 n 1/3 1 -4 n 1/3 + 1 1 -4 n 1/3 sup A:algo E[A D∞ (F, n + ∆)] E[OPT(F, n + ∆)] = 6 n 1/3 -4 + 1 + 4 n 1/3 -4 sup A:algo E[A D∞ (F, n + ∆)] E[OPT(F, n + ∆)] ≤ 10 n 1/3 -4 + sup A:algo E[A D∞ (F, n + n 2/3 )] E[OPT(F, n + n 2/3 )].where the last inequality holds becauseE[A D∞ (F, n + ∆)] ≤ E[OPT(F, n + ∆)] for any algorithm A.From here, the statement of the theorem can be deduced by observing that, for k = n + n 2/3 , we have n ≥ (n + n 2/3 )/2 = k/2, thus n 1/3 ≥ k 1/3 /2, and we obtainCR D (ALG) ≤ 20 k 1/3 -8 + sup A:algo E[A D∞ (F, k)] E[OPT(F, k)] = sup A:algo E[A D∞ (F, k)] E[OPT(F, k)] + O 1 k 1/3 . B From D ∞ -prophet to the γ D -prophet inequality B.1 Proof of Lemma 3.1Proof. Let ALG be any rational algorithm in the D ∞ -prophet inequality. If ALG stops at some step τ ∈ [n], then by definition we have that X τ > D ∞ (max j<τ X j ), and thus ALG D∞ (X 1 , . . . , X n ) = ALG 0 (X 1 , . . . , X n ). Otherwise, if it stops at τ = n + 1, then its reward is max i∈[n] D ∞ (X i ) = D ∞ (max i∈[n] X i ), because D ∞ -is non increasing.On the other hand, let A * be the optimal dynamic programming algorithm for the D ∞ -prophet inequality. At any step i, if X i < D ∞ (max j<i X j ), then stopping at i gives a reward of D ∞ (max j<i X j ), while by rejecting X i , the final reward is guaranteed to be at least D ∞ (max j<i X j ). Thus rejecting X i can only increase the reward, it is therefore the optimal decision. Let I = (F 1 , . . . , F n ) an instance of non-negative random variables with finite expectation, andX i ∼ F i for all i ∈ [n].Let ALG be a rational algorithm for the D ∞ -prophet inequality and let us denote τ its stopping time. Denoting X * := max i∈[n] X i and using Lemma 3.1, we have for any constant C > 0 that thatEQUATIONLet k ≥ 1 a positive integer, M a positive constant, and consider the instanceI k of random variables (X k 1 , . . . , X k n ) with X k i ∼ s k M X i for all i ∈ [n]. We have that OPT(I k ) = s k M OPT(I) and sup A E[A 0 (I k )] = s k M sup A E[A 0 (I)].Therefore, using Inequality (17) with I k instead of I andC = s k M , then dividing by OPT(I k ) gives that CR D∞ (ALG) ≤ E[ALG D∞ (I k )] E[OPT(I k )] ≤ sup A E[A 0 (I)] E[OPT(I)] + D ∞ (s k ) s k M E[OPT(I)] + E[ s k M X * 1 X * >M ] s k M E[OPT(I)] = sup A E[A 0 (I)] E[OPT(I)] + M E[OPT(I)] D ∞ (s k ) s k + E[X * 1 X * >M ] E[OPT(I)],and taking the limit k → ∞, we obtainCR D∞ (ALG) ≤ sup A E[A 0 (I)] E[OPT(I)] + E[X * 1 X * >M ] E[OPT(I)],and since X * has finite expectation, taking the limit M → ∞ givesCR D∞ (ALG) ≤ sup A E[A 0 (I)] E[OPT(I)].Finally, taking the infimum over all instances, we obtain thatCR D∞ (ALG) ≤ sup A CR 0 (A) .As in the proof of Corollary 2.1.1, permuting inf I and sup A is possible because there is an algorithm (dynamic programming) achieving the supremum for any instance. By Lemma 3.1, the inequality above holds for in particular for the optimal dynamic programming algorithm, which has a maximal competitive ratio. Therefore, the inequality remains true for any other algorithm A, not necessarily rational.Proof. Let us place ourselves in any order model or in the IID model. Sinceγ = inf x>0 D∞(x) x, there exists a sequence (s k ) k≥1 of positive numbers such that lim k→∞D∞(s k ) s k = γ.For the random variables X 1 , . . . , X n taking values in {0, a, b} a.s., in any order model, it is clear that the optimal decision when observing a zero value is to reject it, and when observing the value b is to accept it. Let ALG be an algorithm satisfying this property and let τ be its stopping time.If τ = n + 1 then necessarily max i∈[n] X i ̸ = b, and the reward of ALG in that case is D ∞ (a) if max i∈[n] X i and 0 otherwise. In particular, ALG is rational in the D ∞ -prophet inequality and we have by Lemma 3.1 thatEQUATIONConsider now the instanceI k of random variables (X k 1 , . . . , X k n ) where X k i = s k a X i for all i ∈ [n]. I k satisfies the same assumptions as I with a k = s k and b k = s k ba , and we haveE[OPT(I k )] = s k a E[OPT(I)], E[ALG 0 (I k )] ≤ s k a sup A E[A 0 (I)] and (max i∈[n] X k i = a k ) ⇐⇒ (max i∈[n] X i = a). It follows that E[ALG D∞ (I k )] E[OPT(I k )] ≤ sup A E[A 0 (I)] E[OPT(I)] + D ∞ (s k ) s k a E[OPT(I)] Pr(τ = n + 1, max i∈[n] X i = a) = sup A E[A 0 (I)] E[OPT(I)] + D ∞ (s k ) s k a E[OPT(I)] Pr(τ = n + 1, max i∈[n]X i = a) .Taking the limit k → ∞ givesCR D∞ (ALG) ≤ sup A E[A 0 (I)] + γa Pr(τ = n + 1, max i∈[n] X i = a) E[OPT(I)] = sup A (E[A 0 (I)] + E[γ(max i∈[n] X i )1 τ =n+1 ]) E[OPT(I)].ALG is also rational in the γ-prophet inequality. Therefore, using Lemma 3.1, we deduce thatCR D∞ (ALG) ≤ E[ALG γ (I)] E[OPT(I)] ≤ sup A E[A γ (I)] E[OPT(I)].This upper bound is true for the optimal dynamic programming algorithm, since it rejects all zeros and accepts b, therefore the upper bound also holds for any other algorithm.C The γ D -prophet inequality C.1 Proof of Proposition 4.2Proof. For the lower bound, it suffices to consider the following trivial algorithm: if α > γ then run A α , and if γ > α then observe all the items then select the one with maximum value.For the upper bound, let I = (F 1 , . . . , F n ) be an instance of the problem and X i ∼ F i for all i, and letβ I := sup A E[A 0 (I)] E[OPT(I)] .Let A be any algorithm, τ its stopping time, and Y τ = max i<τ X π(i) , where π is the observation order. With the previous notations, we can write that E[A γ (I)] = E[max(X π(τ ) , γY τ )]. For any x, y ≥ 0, the application γ → max(x, γy) is convex on [0, 1], hence it can be upper bounded by (1 -γ)x + γ max(x, y). ThereforeE[A γ (I)] ≤ (1 -γ)E[X π(τ ) ] + γE[max(X π(τ ) , Y τ )] ≤ (1 -γ)E[A 0 (I)] + γE[OPT(I)] ≤ (1 -γ)β I + γ E[OPT(I)] . Therefore, CR γ (ALG) ≤ ((1 -γ)β I + γ).Taking the infimum over all the instances I gives the result. Indeed, if we denote A * the optimal dynamic programming algorithm for the standard prophet inequality, theninf I β I = inf I E[A 0 * (I)] E[OPT(I)] = CR 0 (A * ) ≤ β .Proof. We first prove the upper bound, and then analyze the single threshold algorithm proposed in the theorem.Upper bound Let ε ∈ (0, 1 -γ), and let a =1 1-(1-ε)γ (such that 1 + (1 -ε)γa = a).Let X 1 , X 2 the two random variables defined by X 1 = a almost surely andX 2 = 1 ε w.p. ε 0 w.p. 1 -ε .Stopping at the first step gives a reward of a, while stopping at the second step givesE[max(γa, X 2 )] = ε × 1 ε + (1 -ε) × γa = 1 + (1 -ε)γa = a ,hence the expected output of any algorithm is exactly equal to a. On the other handE[max(X 1 , X 2 )] = 1 + (1 -ε)a ,and we deduce that, for any algorithm ALG for the γ-prophet inequality, we haveCR(ALG) ≤ E[ALG(X 1 , X 2 )] E[max(X 1 , X 2 )] = a 1 + (1 -ε)a ,and this is true for any ε ∈ (0, 1 -γ), thus taking ε → 0 givesCR(ALG) ≤ 1 1-γ 1 + 1 1-γ = 1 2 -γ .Lower bound Consider an algorithm with an acceptance threshold θ, i.e. that accepts the first value larger than θ. Let I = (F 1 , . . . , F n ) be any instance, such that X i ∼ F i for all i, and let us define X * = max i∈[n] X i and p = Pr(X * ≤ θ). In the classical prophet inequality, if no value is larger than θ then the reward of the algorithm is zero, and we have the classical lower boundE[ALG 0 (I)] ≥ (1 -p)θ + pE[(X * -θ) + ],For the γ-prophet, if no value is larger than θ (i.e X * ≤ θ), then the algorithm gains γX * instead of 0. Therefore, it holds thatE[ALG γ (I)] = E[ALG 0 (I)] + E[X * 1 X * ≤θ ] ≥ (1 -p)θ + pE[(X * -θ) + ] + γE[X * 1 X * ≤θ ] = (1 -p)θ + pE[(X * -θ)1 X * >θ ] + γE[X * 1 X * ≤θ ] = (1 -p)θ + p(E[X * 1 X * >θ ] -(1 -p)θ) + γE[X * 1 X * ≤θ ] = (1 -p) 2 θ + pE[X * 1 X * >θ ] + γE[X * 1 X * ≤θ ] ,and observing thatθ = E[θ1 X * ≤θ ] p ≥ E[X * 1 X * ≤θ ] p ,we deduce the lower boundE[ALG γ (I)] ≥ pE[X * 1 X * >θ ] + γ + (1 -p) 2 p E[X * 1 X * ≤θ ] ≥ min p, γ + (1 -p) 2 p E[X * ] .The right term is maximized for p satisfying p = γ + (1-p) 2 p , that leads top = γ + (1 -p) 2 p ⇐⇒ p 2 = γp + 1 -2p + p 2 ⇐⇒ p = 1 2 -γ .Hence, by choosing a threshold θ satisfying Pr(X * ≤ θ) = 1 2-γ we obtain a competitive ratio of at least 1 2-γ .We prove here the upper and lower bounds stated in Theorem 4.4.Proof. We first prove the upper bound, and then derive the analysis for single threshold algorithms.Upper bound Let a > 0, and let X 1 , . . . , X n+1 be independent random variables such that X n+1 = a a.s. and for1 ≤ i ≤ n X i ∼ n w.p. 1 n 2 0 w.p. 1 -1 n 2 .Any reasonable algorithm skips zero values and stops when observing the value n. The only strategic decision to make is thus to stop or not when observing X n+1 = a. By analyzing the dynamic programming solution ALG ⋆ we obtain that the optimal decision rule is to skip a if it is observed before a certain step j, and select it otherwise. The step j corresponds to the time when the expectation of the future reward is less than a. Let π be the random order in which the variables are observed. Then, if π -1 (n + 1) < j, i.e. if the value a is observed before time j, X n=1 is not selected. The output of this algorithm is hence n if at least one random variable equals n, and γa otherwise. This leads toE[ALG γ ⋆ (X) | π -1 (n + 1) < j] = n 1 -1 - 1 n 2 n + γa 1 - 1 n 2 n ≤ 1 + γa ,where we used the inequality 1 -1 n 2n ≥ 1 -1 n . On the other hand, if π -1 (n) ≥ j, then a is selected if the value n has not been observed before it, hence for any i ≥ j we haveE[ALG γ ⋆ (X) | π -1 (n + 1) = i] = n 1 -1 - 1 n 2 i-1 + a 1 - 1 n 2 i-1 ≤ i -1 n + a ,we deduce thatE[ALG γ ⋆ (X)] ≤ (1 + γa) Pr(π -1 (n) ≤ j -1) + n+1 i=j i -1 n + a Pr(π -1 (n) = i) = j -1 n + 1 (1 + γa) + 1 n + 1 n+1 i=j i -1 n + a = (1 -(1 -γ)a) j n - 1 2 j n 2 + 1 2 + a + o(1) ≤ 1 + 2γa + (1 -γ) 2 a 2 + o(1) ,where the last inequality is obtained by maximizing over j/n. Finally, we directly obtain thatE[max i X i ] = n 1 -1 - 1 n 2 n + a 1 - 1 n 2 n = 1 + a + o(1) ,so for any algorithm ALG we obtain thatCR γ (ALG) ≤ CR γ (ALG ⋆ ) ≤ 1 + 2γa + (1 -γ) 2 a 2 1 + a .The function above is minimized for a = 3-γ 1-γ -1, which translates toCR γ (ALG) ≤ (1 -γ) 3/2 ( 3 -γ -1 -γ) + γ .Lower bound We still denote by I = (F 1 , . . . , F n ) the input instance and X i ∼ F i for all i ∈ [n].Let ALG be the algorithm with single threshold θ, then it is direct thatEQUATIONWe start by giving a lower bound on E[ALG 0 ]. We use from Correa et al. [2021c] (Theorem 2.1) that for any x < θ it holds that Pr(ALG 0 (I) ≥ x) = Pr(ALG 0 (I) ≥ θ) = Pr(X * ≥ θ) = 1 -p , and for x ≥ θ it holds thatPr(ALG 0 (I) ≥ x) ≥ 1 -p -log p Pr(X * ≥ x) ,from which we deduce thatEQUATION)On the other hand, we obtain thatE[X * 1 X * <θ ] = ∞ 0 Pr(X * 1 X * <θ ≥ x)dx = ∞ 0 Pr(x ≤ X * < θ)dx = θ 0 (Pr(X * > x) -Pr(X * ≥ θ))dx = θ 0 Pr(X * > x)dx -(1 -p)θ . (21) Pr(X * ≥ x)dx + ∞ θ Pr(X * ≥ x)dx = min 1 -(1 -γ)p , 1 -p -log p E[X * ] .Finally, choosing p = p γ gives the result.C.3.2 Proof of Corollary 4.4.1Proof. For p =1/e 1-(1-1/e)γ , we have immediately that1 -(1 -γ)p = 1 - (1 -γ)/e 1 -(1 -1/e)γ,and p ∈ [1/e, 1] for any γ ∈ [0, 1]. Since the function x → (1 -x)/ log(1/x) is concave, we can lower bound it on [1/e, 1] by x → 1 -1/e + x-1/e e-1 , which is the line intersecting it in 1/e and 1. Therefore we have1 -p -log p ≥ 1 -1/e + p -1/e e -1 = 1 - (1 -γ)/e 1 -(1 -1/e)γ .Finally, using the previous theorem, this choice of p guarantees a competitive ratio of at leastmin 1 -(1 -γ)p , 1 -p -log p = 1 - (1 -γ)/e 1 -(1 -1/e)γ .Proof of Lemma 4.5Proof of Lemma 4.5. Let F be the cumulative distribution function of X 1 , a > 0 and ALG the algorithm with single threshold θ such that 1 -F (θ) = a n . We denote X * = max i∈[n] X i . As in the previous proofs, we will begin by lower bounding ALG 0 (F, n). For any i ∈ [n], ALG stops at step i if and only if X i > θ and all the previous items were rejected, i.e. X j ≤ θ for all j < i. Thus we can writeEQUATIONwhere the second equality is true by the independence of the random variables (X i ) i . On the other hand, we can upper bound E[X * 1 X * >θ ] as followsE[X * 1 X * >θ ] ≤ Pr(X * > θ)θ + E[(X * -θ) + ] ≤ Pr(X * > θ)θ + E n i=1 (X i -θ) + = Pr(X * > θ)θ + n E[X 1 1 X1>θ ] -Pr(X 1 > θ)θ = (1 -F (θ) n -a)θ + nE[X 1 1 X1>θ ] .Using the definition of θ, the independence of (X i ) i then Bernoulli's inequality we have thatPr(X * > θ) = 1 -F (θ) n = 1 -1 - a n n ≤ 1 -(1 -n × a n ) = a ,and observing that θ =E[θ1 X * ≤θ ] F (θ) n ≥ E[X * 1 X * ≤θ ] F (θ) n , we deduce that E[X * 1 X * >θ ] ≤ -1 - 1 -a F (θ) n E[X * 1 X * ≤θ ] + nE[X 1 1 X1>θ ] .by substituting into (22), we obtainE[ALG 0 (F, n)] ≥ 1 -F (θ) n a E[X * 1 X * >θ ] + 1 - 1 -a F (θ) n E[X * 1 X * ≤θ ] .Finally, the reward in the γ-prophet inequality isE[ALG γ (F, n)] = E[ALG 0 (F, n)] + γE[X * 1 X * <θ ] ≥ 1 -F (θ) n a E[X * 1 X * >θ ] + 1 -F (θ) n a 1 - 1 -a F (θ) n + γ E[X * 1 X * <θ ] ≥ min 1 -F (θ) n a , 1 -F (θ) n a 1 - 1 -a F (θ) n + γ E[X * ] .The equationEQUATIONand for any n ≥ 2 the function a → 1 (1-a/n) n -1 1 a -1 is decreasing on (0, 1] and goes from 1 to 0, thus Equation ( 23) admits a unique solution a n,γ , and taking a = a n,γ guarantees a reward of1-F (θ) n an,γ E[X * ] = 1-(1- an,γ n ) n an,γ E[X * ].Proof of Theorem 4.6Proof. We first prove the upper bound, and then we give the single-threshold algorithm satisfying the lower bound.We consider an instance similar to the one used in the proof of Theorem 4.4. Let a, x > 0, and let X 1 , . . . , X n be IID random variables with the following the distribution F defined byX 1 ∼    n w.p. 1 n 2 a w.p. x n 0 w.p. 1 -x n -1 n 2 .A reasonable algorithm would always reject the value 0 and accept the value n. However, if the algorithm faces an item with value a, it must decide to either accept it, or reject it with a guarantee of recovering γa at the end. By analyzing the dynamic programming algorithm ALG ⋆ , we find that the optimal decision is to reject a if observed before a certain step j, and accept it otherwise. Let us denote τ the stopping time of ALG ⋆ . By convention, we write τ = n + 1 to say that no value was selected by the algorithm, in which case the reward is γ max i∈[n] X i .If τ ≤ j -1 then necessarily X τ = n, because ALG ⋆ rejects the value a if it is met before step j, and if τ = n + 1 then max i∈[n] X i ∈ {0, a}, because otherwise the algorithm would have selected the value n and stopped earlier. It follows that the expected output of ALG ⋆ on this instance isEQUATIONLet us now compute the terms above one by one.Pr(τ < j) = Pr(∃i ∈ [j -1] : X i = n) = 1 -1 - 1 n 2 j-1 ≤ j n 2 ,where we used Bernoulli's inequality (1 -1/n 2 ) j-1 ≥ 1 -j-1 n 2 > 1 -j n 2 . For i ∈ {j, . . . , n}, ALG ⋆ stops at i if X i ∈ {a, n} and if it has not stopped before, i.e. X k ∈ {0, a} for all k < j and X k = 0 for all k ∈ {j, . . . , i -1}, hencePr(τ = i) = Pr(∀k < j :X k ̸ = n and ∀j ≤ k ≤ i -1 : X k = 0 and X i ̸ = 0) = 1 - 1 n 2 j-1 1 - x n - 1 n 2 i-j Pr(X i ̸ = 0) ≤ 1 - x n i-jPr(X i ̸ = 0) , the second equality is true by independence, and the last inequality holds because 1 -1 n 2 ≤ 1 and 1 -x n -1 n 2 ≤ 1 -x n . By independence of the variables (X k ) k , we also have that E[X i | τ = i] = E[X i | X i ̸ = 0] = E[X i ] Pr(X i ̸ = 0) = 1 + ax n Pr(X i ̸ = 0).Finally, the event(τ = n + 1, max i∈[n] X i = a) is equivalent (max i∈[j-1] X i = a, ∀k ≥ j : X k = 0).In fact, the algorithm does not stop before n + 1 if and only if X k ̸ = n for all k < j and X k = 0 for all j ≤ k ≤ n, and under these conditions, it holds that max i∈[n] X i = max i∈[j-1] X i . ThereforePr(τ = n + 1, max i∈[n] X i = a) = Pr( max i∈[j-1] X i = a, ∀k ≥ j : X k = 0) ≤ Pr( max i∈[j-1] X i ̸ = 0) Pr(∀k ≥ j : X k = 0) = 1 -1 - x n - 1 n 2 j-1 1 - x n - 1 n 2 n-j = 1 -e -xj n + o(1) e -x+ xj n + o(1) = e xj n -1 e -x + o(1). All in all, we obtain by substituting into 24 thatE[ALG γ ⋆ (F, n)] ≤ j n + 1 + ax n n i=j 1 - x n i-j + γae -x e xj n -1 + o(1) = j n + 1 + ax n 1 -(1 -x/n) n-j+1 x/n + γae -x e xj n -1 + o(1) = j n + 1 x + a 1 -e -x+ xj n + o(1) + γae -x e xj n -1 + o(1) = j n -1 x + (1 -γ)a e xj n + 1 x + a -γae -x + o(1) ≤ max s>0 s -1 x + (1 -γ)a e xs + 1 x + (1 -γe -x )a + o(1) = - 1 x log(1 + (1 -γ)ax) + 1 -x + 1 x + (1 -γe -x )a + o(1) = - 1 x log(1 + (1 -γ)ax) + 1 + (1 -γe -x )a + o(1) .On the other hand, we have thatPr(max i∈[n] X i = n) = 1 -1 - 1 n 2 n = 1 n + o(1/n) , Pr(max i∈[n] X i = 0) = 1 - x n - 1 n 2 = e -x + o(1) , Pr(max i∈[n] X i = a) = 1 -Pr(max i∈[n] X i = 0) -Pr(max i∈[n] X i = n) = 1 -e -x + o(1) ,therefore, the expected maximum value isE[max i∈[n] X i ] = n Pr(max i∈[n] X i = n) + a Pr(max i∈[n] X i = a) = 1 + 1 -e -x a + o(1) .We deduce thatE[ALG γ ⋆ (F, n)] E[max i∈[n] X i ] ≤ -1 x log(1 + (1 -γ)ax) + 1 + (1 -γe -x )a 1 + 1 -e -x a + o(1) = 1 - 1 x log(1 + (1 -γ)ax) -(1 -γ)ae -x 1 + 1 -e -x a + o(1) .Consequently, for any a, x > 0 and for any algorithm ALG we haveCR(ALG) ≤ CR(ALG ⋆ ) ≤ lim n→∞ E[ALG γ ⋆ (F, n)] E[max i∈[n] X i ] ≤ 1 - log(1 + (1 -γ)ax) -(1 -γ)axe -xx + 1 -e -x ax .In particular, for x = 2 and a = 1-γ/2 1-γ we find thatCR(ALG) ≤ 1 - log(3 -γ) -(2 -γ)e -2 2 + 2-γ 1-γ (1 -e -2 ) = 1 -(1 -γ) e 2 log(3 -γ) -(2 -γ) 2(2e 2 -1) -γ(3e 2 -1) = U (γ) .This proves the upper bound stated in the theorem, and we can verify that it is increasing, and satisfiesU (0) = 4-log 3 4-2/e 2 U (1) = 1Lower bound on the competitive ratio We will prove that the algorithm presented in Lemma 4.5 has a competitive ratio of at least (1 -(1 -γ)p γ ), where p γ , first introduced in Theorem 4.4, is the unique solution of the equation(1-(1-γ)p) = 1-p -log p , which is equivalent to 1 p -1 1 log(1/p) -1 = γ.Let a γ = -log(p γ ). It follows from the definition of p γ that a γ is the unique solution of the equation (e a -1)( 1 a -1) = γ. For any n ≥ 2 and x ≥ 0 we have that (1 -x/n) n ≤ e -x , hence, by definition of a n,γ and a γ 1 e -an,γ -1EQUATIONMoreover, the function x → (e x -1)(1/x -1) is decreasing on (0, 1). In fact its derivative at any point x ∈ (0, 1) isd dx 1 e -x -1 1 x -1 = 1 x -1 e x - e x -1 x 2 = 1 x 2 1 -x 2 -(1 -x)e x = 1 -x x 2 (1 + x -e x ) < 0 .It follows from ( 25) that a γ ≤ a n,γ . Finally, given that x → 1-e -xx is non-increasing on (0, 1], we deduce that1 -(1 - an,γ n ) n a n,γ ≥ 1 -e -an,γ a n,γ ≥ 1 -e -aγ a γ .We deduce that the competitive ratio of the algorithm described in Theorem 4.6 is at least1-e -aγ aγ = 1-pγ log(1/pγ ) = 1 -(1 -γ)p γ .While we only studied deterministic decay functions in the paper, it is also possible to have scenarios with random decay functions. Consider for example that rejected items remain available after j steps with a probability p j , this is modeled by D j (x) = ξ j x with ξ j a Bernoulli random variable with parameter p j . We explain in this section how the definitions and our results extend to this case. Definition D.1 (Random process). Let X is a non-empty set. A random process o X is a collection of random variables {Z x } x∈X . Two random processes Z = {Z x } x∈X and Z ′ = {Z ′ x } x∈X ′ are independent if any finite sub-process of Z is independent of any sub-process of Z ′ . For simplicity, let us say that the random processes {Z 1x } x∈X 1 , . . . , {Z m x } x∈X m are mutually independent if, for any x 1 ∈ X 1 , . . . , x m ∈ X m , the random variables Z 1 x1 , . . . , Z m xm are mutually independent. Definition D.2 (Random decay functions). Let D = (D 1 , D 2 , . . .) be a sequence of mutually independent random processes. We say that D is a sequence of random decay functions if 1. Pr(D j (x) / ∈ [0, x]) = 0 for any x ≥ 0 and j ≥ 1, 2. j ∈ N ≥1 → Pr(D j (x) ≥ a) is non-increasing for any x, a ≥ 0, 3. x ≥ 0 → Pr(D j (x) ≥ a) is non-decreasing for any j ∈ N ≥1 and a ≥ 0.The second condition asserts that the random variable D j-1 (x) has first-order stochastic dominance over D j (x). Along with the first condition, reflect that the distributions of the rejected values become progressively smaller. The last condition indicates that for any integer j ≥ 1 and non-negative real numbers x < y, D j (y) has a first-order stochastic dominance over D j (x), which means that, as the value of x increases, so does the potential recovered value after j steps.The decision-maker In the D-prophet inequality with deterministic decay functions, we assumed that the decision-maker has full knowledge of the functions D 1 , D 2 . . .. In the randomized setting, we assume instead that the decision-maker knows the distributions of the decay functions, i.e. knows the distribution of the random variables D j (x) for all x ≥ 0 and j ≥ 1. However, they do not observe their values until they decide to stop. The online selection process is therefore as follows: the algorithm knows beforehand the distributions of the decay functions, then at each step, it observes a new item with value X i , and decides to stop or continue. Once they decide to stop at some time τ , they observe the values D 1 (X τ -1 ), . . . , D τ (X 1 ) and then they choose the maximal one. As a consequence, the stopping time τ is independent of the randomness induced by the decay functions.As in the deterministic case, the expected reward of any algorithm ALG can be written asE[ALG D (X 1 , . . . , X n )] = E[ max 0≤i≤τ -1 {D i (X τ -i )}] .The limit decay A key result in our paper is the reduction of the problem to the case where all the decay functions are identical, and we prove this reduction by considering the pointwise limit of the decay functions. In the case of random decay functions, instead of the pointwise convergence, it holds for all x ≥ 0 that the random variables (D j (x)) j converge in distribution to some random variable D ∞ (x). In fact, for any x ≥ 0 and a ≥ 0, the sequence (Pr(D j (x) ≥ a)) j≥1 is non-increasing and non-negative, thus it converges to some constant G(x, a). Given that x → Pr(D j (x) ≥ a) is non-decreasing for any j, we obtain by taking the limit j → ∞ that x → G(x, a) is non-increasing, and with similar argument we obtain, for any x ≥ 0, that G(x, a) = 1 for all a ≤ 0 and G(x, a) = 0 for all a > x. Therefore, a → 1 -G(x, a) defined the cumulative distribution of a random variable D ∞ such that • x ≥ 0 → Pr(D ∞ (x) ≥ a) is non-decreasing for all a ≥ 0,• Pr(D ∞ (x) / ∈ [0, x]) = 0 for al x ≥ 0.Therefore, for all x ≥ 0, D ∞ (x) is the limit in distribution of (D j (x)) j , hence a sequence D ′ = (D ′ 1 , D ′ 2 , . . .) of mutually independent random processes such that D ′ j (x) ∼ D ∞ (x) for any j ≥ 1 and x ≥ 0 defines a sequence of decay functions. We say in this case that all the decay functions are identically distributed as D ∞ . Moreover, it holds for all x ≥ 0 that E[D ∞ (x)] = lim j→∞ E[D j (x)] = inf j≥1 E[D j (x)] From there, all the proofs of Section 2 can be easily generalized to the case of random decay functions, and it follows that we can restrict ourselves to studying identically distributed decay functions. Moreover, Proposition 3.2 can be generalized to the case of random decay functions, and the necessary condition for surpassing 1/2 becomes inf x>0x > 0. Similarly, using that the stopping time τ of the algorithm is independent of randomness induced by D ∞ , Proposition 3.3 remains true with γ = inf x>0x.Lower bounds For establishing lower bounds, observe that, for any random decay functions D, if we denote H j (x) = E[D j (x)] for all x, then H = (H 1 , H 2 , . . .) defines a sequence of deterministic decay functions. Furthermore, for any instance X 1 , . . . , X n and any algorithm ALG, it holds thatE[ALG D (X 1 , . . . , X n )] = E[ max 0≤i≤τ -1 {D i (X τ -i )}] = E E[ max 0≤i≤τ -1 {D i (X τ -i )} | τ, X 1 , . . . , X n ] ≥ E max 0≤i≤τ -1 E[D i (X τ -i ) | τ, X 1 , . . . , X n ] = E max 0≤i≤τ -1 {H i (X τ -i )} = E[ALG H (X 1 , . . . , X n )].It follows that lower bounds established for deterministic decay functions can be extended to random decay functions by considering their expectations.Implications With the previous observations, both the lower and upper bounds, depending on γ D that we proved in the deterministic D-prophet inequality can be generalized to the random D-prophet inequality, by takingγ D = inf x>0 inf j≥1 E[D j (x)]x .• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024). 


Decision: The submission introduces a new and well-motivated variant of the Prophet Inequality. 
The reviewers are generally satisfied with both the results and techniques.
I recommend accept.

Reviews: review: paper_summary: paper_summary: This paper studies a variant of prophet inequalities where the agent can reuse a previous item at a decaying price. Analyzing three models, adversarial model, random order model, and iid model, this paper gives various lower and upper bounds about the competitve ratio that an algorithm may achieve in these setups.

The paper mainly follows a reduction idea. It first show that for any decaying function family $\mathcal D$, the optimal competitive ratio is close to that for the limiting decaying function $D_{\infty}$, which reduces the $\mathcal D$-prophet problem to a $D_{\infty}$ one. This idea is further generalized so that it suffices to consider linear functions (i.e., $x\mapsto \gamma x$ for some $\gamma$) as the CR for $D_{\infty}$ is again close to that of $x\mapsto (\lim_{x\to \infty} \frac{D_{\infty}(x)}{x})x$. Equipped with these reductions, the authors
1. establish an upper bound on the CR in the adversarial model, where a matching online algorithm is also proposed;
2. develop an upper bound that is more general than previous works (considering classical prophet inequalities) in the random order model, but the lower bound algorithm is neither computationally feasible nor optimal; and
3. design an algorithm in the iid case whose asymptotic CR is the same as that in the random order model.
strength_weakness: strength_weakness: 1. For the first reduction ($\mathcal D$ to $D_{\infty}$), it seems that only some order models mentioned in the main text allows such a reduction. Why you only consider these models, and are there any other models excluded from this reduction (or do you have any intuition on what kinds of order models can ensure the reduction)?
2. For random order models and iid models, the algorithms designed are sub-optimal and cannot be implemented easily.
questions: questions: 1. See Weakness 1
2. 'However, considering larger classes of algorithms, the competitive ratios achieved in the IID model are better than those of the random order model.' Can you give some examples? I see in the limitations you mentioned that such algorithms are not designed in your $\mathcal D$-prophet model. Why they do not generalize?
limitations: limitations: Clearly stated
paper_summary: paper_summary: **Problem Studied**

This paper introduces the problem of "lookback prophet inequalities", which is a variant of prophet inequalities. In this problem, at the stopping time, instead of always selecting the current item, the algorithm is allowed to select any item that has arrived up to now. However, items in the past have their value discounted by known decay functions. The goal is to design algorithms with a good competitive ratio, which is the ratio of the algorithm's expected value to the expectation of the highest-value item in hindsight.

**Main Results / Contributions**

The first main contribution of this paper is to define the problem of lookback prophet inequalities. The paper considers the problem in the adversarial order, random order, and IID models. It turns out that for all three models, when analyzing the worst-case competitive ratio, one can assume that the decay functions are all of the form $x \to \gamma x$, for some $\gamma$. For the adversarial model, matching upper and lower bounds are derived.  For the random order and IID models, upper and lower bounds are derived, but they do not match.
strength_weakness: strength_weakness: There are already numerous papers on variants of the prophet inequality, and this paper introduces yet another one. At this point, one must question how interesting or significant this contribution is. However, the problem definition appears reasonable, and the proofs seem to be fairly clean, which is why I am recommending a weak acceptance.
questions: questions: 1. I think the real estate example doesn't make too much sense. If the seller returns to a previous buyer, and it turns out the buyer is no longer interested, the seller can continue to sell the house. 

2. The restaurant example also seems a bit strange to me. If the cost of revisiting a restaurant depends on the distance you need to walk back to it, this doesn't seem to be capturable with the current definitions of the decay functions, no? (Currently, the decay functions only model how many steps back into the past you look. E.g. If you are going from restaurant 3 to restaurant 1, this uses the same decay function as going from restaurant 5 to restaurant 3.)

3. It seems like the reduction to $\mathcal{D}_\infty$ relies on the fact that $n$ goes to infinity. Are there better competitive ratios that are possible for a fixed $n$?

4. There are several typos in the paper, notably in the title ("Inequalitites" -> "Inequalities").
limitations: limitations: Yes.
paper_summary: paper_summary: This paper extends the standard online selection problem by enabling the decision-maker to choose previous items with some discount that is captured by decay functions. The authors analyze the competitive ratio for different observation orders by giving a reduction from general decay functions to simple decay function.
strength_weakness: strength_weakness: 1. The analyses for random order and IID cases are not ideal. It seems neither upper nor lower bounds are tight for general $\gamma$.
2. I am not sure about the technical contribution of this paper. What is the biggest technical challenge in the analysis?
questions: questions: 1. What is the biggest technical challenge in the analysis?
2. I feel it is better to emphasize the choice of distribution with support ${0,a,b}$ when proving the upper bound of $\gamma$-prophet inequality (maybe change the statement of theorems). This is because $CR^D(ALG) \le \sup_A \frac{\mathbb{E}[A^{\gamma_D}(I)]}{\mathbb{E}[OPT(I)]}$ for $I$ taking values in $0,a,b$ and $\sup_A CR^{\gamma_D}(A) =  \sup_A \inf_I \frac{\mathbb{E}[A^{\gamma_D}(I)]}{\mathbb{E}[OPT(I)]} \le f(\gamma_D)$ (current statement in Theorem 4.4/4.5) does not directly imply $CR^D(ALG) \le f(\gamma_D)$.
limitations: limitations: Yes.

Comments: comment: Thanks for your response! I'd like to keep my score unchanged.
Thank you for your response, I appreciate it!
We thank the reviewer for getting back to us. We understand from their response that we have adequately addressed the concerns raised in their review. If this is the case, we hope the reviewer will consider raising their rating to reflect their satisfaction with our response. Otherwise, we are more than willing to engage in further discussion and provide the necessary clarifications.
I thank the authors for the response. I do not have further questions now.