Lookback Prophet Inequalities
Authors: Ziyad Benomar
Dorian Baudry
Vianney Perchet
Venue: NeurIPS 2024 poster (2024)
Keywords: prophet inequalitity
online algorithms
decision-making under uncertainty
Primary area: algorithmic_game_theory

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$.

Lookback Prophet Inequalities
Ziyad Benomar ENSAE, Ecole Polytechnique, FairPlay joint team
Dorian Baudry
Department of Statistics,
University of Oxford
ziyad. benomar@ensae.
dorian. baudryy@x ac uk
Vianney Perchet
CREST, ENSAE, Criteo Al LAB Fairplay joint team
saameeyy.errhherrommmaaeeeeu. org
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 irrevocably and move the next step. This model is often too pessimistic and does not adequately represent real-world online selection processes. Potentially, rejected items can be revisited and fraction of their value can be recovered. To analyze this problem, we consider general decay functions D1, D2...., 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, 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 + ye, where 7 infaso inf (z)z)/z. Consequently, we focus on this setting and refine the analyses of the competitive ratios, with upper and lower bounds expressed as increasing functions of 7
Introduction
Optimal stopping problems constitute a classical paradigm of decision-making under uncertainty [Dynkin] [963 Typically, in online algorithms, these problems are formalized as variations of the secretary problem Lindley [961]] or the prophet inequality [Krengel and Sucheston 1977). In the context of the prophet incquality, the decision-maker observes finite sequence of items, each having a value drawn independently from a known probability distribution. Upon encountering new item, faces the choice of either accepting it and concluding the selection process or
the decision-male 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. (2077] online auctions [Syrgkanis) 2017]. it might present pessimistic model of real-world online selection problems. Indeed, is in general possible in practice to revisit previously rejected items and potentially recover them or at least recover fraction of their value.
Consider for instance an individual navigating city in search of restaurant. When encountering one, they have the choice to stop and dine at this place, continue their search, or revisit previously passed option, incurring a utility cost that proportional 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
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

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.
1.1 Formal problem and notation
To encompass diverse scenarios, we propose a general way to quantify the cost incurred by the pecision-maker for retrieving a previously rejected value.
Definition 1.1 (Decay functions). Let D (D1, D2.... be sequence of non-negative functions defined on [0, oo). It is a sequence of decay functions if
(i) (x) x for all 2 0.
(ii) the sequence (D₃
is non-increasing for all 0,
(ii) the function Dy is non-decreasing for all j 1.
In the context of decay functions D, if value x is rejected, the algorithm can recover Dz(x) after j subsequent steps. The three conditions defining decay functions serve fundamental prerequisites for the problem. The first and second conditions ensure that the recoverable value a rejected item can only diminish over time, while the final condition implies that increase in the observed value corresponds to an increase in the potential recovered value. Although the non-negativity of the decay functions is non-essential, considering that the algorithm has a reward of zero by not selecting any item.
retain it for convenience, as we can easily revert this assumption by
The motivating examples that we introduced can be modeled respectively with decay functions of the form (2) = x cc where (cz)521 is a non-decreasing positive sequence, Dy ε,æ with E ~ B(pj) and (p))22 a non-increasing sequence of probabilities, and D) = X with A E [0, 1]. In one of these examples (housing market), the natural model is to use random decay functions: the buyer makes the same offer 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 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 ......, Xx. with X, drawn from a known distribution F; for all i E [n]. If they decide to stop at some step T, then instead of gaining X, in the classical prophet inequality, they can choose to select the current item X, and have its full value, or select any item X; with i < 7 among the rejected ones but only recover a fraction DX,)(,)) I X, of its value. Therefore, if an algorithm ALG stops step its reward is
ALG LLGP(XI,.o Xn) = max(X,, (X,, D2(X,-)), Dx(x)) D,. Dx-1(X1)3
0SiST-1 (D)(X,-)))
with the convention Do(æ) = x. If the algorithm does not stop at any step before n. then its reward is ALG (XI...., X..) maxigisn (X
which corresponds to n + 1.
Remark 1.1. As in the standard prophet inequality, an algoritim is defined by its stopping time, i.e.. the rule set decide whether to stop or not. Hence, D and D' are two different sequences of decay functions, any algorithu for the D- D-prophet inequality, although its stopping time might depend on the particular sequence of functions DD is also an algorithm for the D' proophet inequality. Consider for example an algorithu ALG with stopping time T (D) that depends on D. Its reward in the D'' -'rrophet inequality is A (X1,..., X,)) = (D((
Observation order: Several variants of the prophet inequality problem have been studied, depending on the order of observations. The standard model the adversarial (or fixed) order: The instance of the distributions F,,..., Fn is chosen by an adversary, and the algorithm observes the samples X, ~ Fi,..., X,, F2 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

---

uniformly random order. Another setting in which the observation order is no longer important is the IID model [Hill and Kertz, 1982 Correa al. 202Tb], 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 xx(1))-... (m))) with л permutation of [n], In this paper, we study the D-prophet incquality in the three models we presented, providing lower and upper bounds in each of them.
then the reward of the algorithm is ALG (X1,..., ALG"
X,) maxosisr-1
Competitive ratio. In the D-p D-prophet inequality, an input instance / a finite sequence of probability distributions (Fi..... Fn). Thus, for any instance I. we denote by E|ALG" (1)] the expected reward of ALG given 1 as input, and we denote by [[)) the expected maximum of independent random variables (X (e)t)) where X; ~ F.. With these notations, we define the competitive ratio, which will be used measure the quality of the algorithms.
Definition 1.2 (Competitive ratio). Let D be sequence of decay functions and ALG an algorithm. We define the competitive ratio of ALG by
E[ALG (T)
CR (ALG) inf [(PTT(T)
with the infinum taken over the tuples of all sizes of non-negative distributions with finite expectation.
An algorithm is said to be a-competitive its competitive ratio is least a, which means that for any possible instance I, the algorithm guarantees reward of at least (E))PT The notion of competitive ratio is used more broadly in competitive analysis as metric to evaluate online algorithms [Borodin and El- Yaniv 2005].
1.2 Contributions
It is trivial that non-zero decay functions 'D guarantee 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 given algorithm can be improved. Hence, 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 yD. defined as follows,
(2(x)
TD = inf inf
(I)
#>0
In the adversarial order model, we demonstrate that the optimal competitive ratio achievable in the D-prophet inequality is determined by the parameter "rD alone. Additionally, in both the random order and IID models, we demonstrate the essential requirement of 7/D 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 (z) = x - C, with c, > or (z(x) Xx with [0, 1). Subsequently, we develop algorithms and provide upper bounds in the D-prophet inequality, uniquely dependent on the parameter YDD We illustrate them in Figure [] comparing them with the identity function y + 7 which is trivial lower bound.
1.3 Related work
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 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 HHjjighayi et al. 2007]]Den et al. 2022, Psomas et al., 2022 Makur et al. 2024], auctions [Syrgkanis]] [201 | Dütting et al. 2020), resource management Siinllarr et al. [023] 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).
3

---

[Adversarial] lower and upper hound
[Random and [ID] lower bound
[Bandom] upper bound
[ID] upper bound
y2
V3- 0.732
0.632
1/2
0.0
0.2
0.4
0.6
0.8
e [0.1]
Figure I:
Lower and upper bounds on the competitive ratio in the D-prophet inequality depending on YD, in the adversarial order (Thhm random order (Thm 4.4) and IID) (Thm 4.6 models
prophet inequality with advice [Diakonikolas al. 2021 and variants with fairness considerations Correa et al. 2021a Arsenis and Kleinberg, [0022]
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 (1 --competitivee algorithm. Correa et al. [202]c] showed later a competitive ratio of 0.669, and Harb [2044 enhanced
it to 0.6724, which currently stands as the best-known solution for the problem. They also proved an upper bound of /3- R 0.732, which was improved to 0.7254 in [Bubna and Chiplunkar 2023 then 0.723 in Giambartolomei al., 2023]. Addressing the gap between the lower and upper bound remains 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 [982] Kertz, 1986). demonstrating guarantees on the dynamic programming algorithm. The problem was completely solved in [Correa al. 202Tb), where the authors show that the competitive ratio of the dynamic programming algorithm is 0.745, thus it constitutes 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 algorithms [Lykouris and Vassilvtiskil 2018), which equip the decision-make with predictions hints about unknown variables of the problem. Multiple problems have been studied in this framework, such as scheduling
additional capabilities. A notable research avenue is
[Prroht et al. 20188 Lassota et al. 2023, Benomar and Perchet 2002bb]. matching [Antoniadis et al.
2020 Dinitz et al. 2021 Chen et al. 2022], caching [Antoniadis et al. 2023 Chikedowski et al.
2021 Christianson et al. 2023), the design of data structures [Krask al.) 2018 al. 2022
Benomar and Coester (0244] [224], and in particular, online selection problems [Dütting et al. 202 Sun
al.] 2021 Benomar et al. 22023 Benomar and Perchet 2024a] Diakonikolas et al.) [021] More
related to our setting, the ability to revisit items in online selection has been studied in problems
such the multiple-choice prophet inequality, where the algorithm can select up items and its
reward is the maximum selected value [Assaf and Samuel-Cahm 2000). This allows for revisiting up l: items, chosen during the execution, for final acceptance or rejection decisions. Similarly, in Pandora's '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 cost is paid for observing each value X, with the gain being the maximum observed value minus the total opening costs. A very recent work investigates scenario closely related to the lookback prophet inequality

---

[Ekbatani et al., 2024] where, upon selecting a candidate X,, the decision maker has the option to discard and choose new value Xj any later step j. at a buyback cost of fX,, where f > 0. The authors present optimal algorithm for the case when f 2 1, although the problem remains open for f E (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 -prophe inequality
Let us consider a sequence D of decay functions. By Defimition 1.1 for any x E [0, oo] the sequence (D)()));21 converges, since it is non-increasing and non-negative. Hence, there exists mapping Do such that for any x 2 O, lim (x) = D (x) Furthermore, we can easily verify that Doc non-decreasing and satisfies (x) E [0,z]] for all x: 2 0.
Thanks to these properties, we obtain that (D>o);21 also satisfies Definition 1.1 and is hence a valid sequence of decay functions. We thus refer to the corresponding problem as the D inequality. Since D, 2 Doe for any j 2 1, it straightforward that the stopping problem with the decay functions Doe would be less favorable to the decision-makes More precisely, for any random variables Xi,..., Xn. observation order π, and algorithm ALG with stopping time т, it holds that
ALGP (X,,..., X,) max X (r)) max D Dr-i(X=(0)3 2 max (F)) max D (Xx(i)) seT
which corresponds 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 -ro-phet inequality naturally extend the D-prophet inequality. However, it remains uncertain whether the D-prophet inequality can yield improved competitive ratios compared to the Doe -prophet inequality. In the following, we prove that this is not the case, for all the order models presented in Section [
Theorem 2.1. Let Doo be the pointwise limit of the sequence of decay functions D (Dz)s21. Then of non-negative distributions, holds in the adversarial and the
for any instance I I= (Fi,...,, random order models that
E[A Doo (T)
VALG: CR CRP(ALG) S sup
A E[OPT())
where the supremum is taken over all the online algorithms A. In the IID model, the same inequality holds with an additional O(n 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'o is an optimal algorithm for the -ropphtt inequality, i.e. with maximal competitive ratio, then Aoo is also optimal for the DDprophet inequality. Moreover, it holds that
CR (Ax) CRR (Axo)
A direct consequence of this result is that, in the adversarial and the random order models, the asymptotic decay D.x entirely determines the competitive ratio that is achievable and the upper bounds for the D-prophet incquality. 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 the classical IID prophet inequality (Hill and Kertz 1982.
2.1 Sketch of the proof of Theorem 2.1
While we use different techniques for each order model considered, all the proofs share the same underlying idea. Given any instance of negnneiae distributions, we build an alternative instance J such that the reward of any algorithm on with decay functions D (D;); is at most its reward on with decay functions all equal to Dxx- number of zero values between two successive observations drawn from distributions belonging to
this, we essentially introduce an arbitrarily large
T. Hence, under J, the algorithm cannot recover much more than fraction (X) for any past observation X collected from a distribution F I.
5

---

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 is defined by a pair nF,,,, where F is non-negative distribution, and is the size of the instance. In this scenario, we consider an instance consisting of m > IID random variables [Y)) 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 Binomial distribution with parameters (m, n/ m). We control this variability by using concentration inequalities, which causes the additional term O(n 1/33.
3 From -xopphet to the yp-prophet inequality
As discussed in Section Theorem 2.1 limplies that, for either establishing upper bounds or guarantees on the competitive ratios of algorithms, is sufficient to study the D -prophet inequality, where all the decay functions are equal to Do. The remaining question is then to determine which functions Do 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 -poohhtt inequality.
In the Doe proppht inequality, it is always possible to have a reward of Doo (max4e(n) Xz) 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; S Doo (maxj<i Xj). An algorithm respecting this decision rule called rational.
Lemma 3.1. For any rational algorithm ALG in the Dso-prophet inequality, if we denote by its stopping time, then for any instance (F1,...,
.,, Fn) and X, Foror all E [n] we have
ALG (X1..... X,,) A x,).. Doc mmax iEIn|
X.) 1=
where ALG' denotes the reward of the algorithu in the standard prophet inequality. Moreover, the optimal dynamic programming algorithm in the ~ropphtp inequality is rational.
The best competitive ratio in the Dxo -pophht inequality is achieved, possibly among others, by the optimal dynamic programming algorithm, which is 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. the Dropprephet inequality, ininl Do then holds, in any order model, that
YALG: CRD> (ALG) S sup (A)
(3)
where the supremum is taken over all the online algorithmss A and CR denotes the competitive ratio in the standard prophet inequality.
(x) O, then, in any order model, any upper bound on the competitive ratios of all algorithms the classical prophet inequality also an upper bound on the competitive ratios of all algorithm in the Dxo -prophet inequality. Consequently, for surpassing the upper bounds of the classical prophet inequality, it is necessary to have, for some 7 >> O, that Doo (x) qa for all æ 2 O. Furthermore, the next Proposition allows giving upper bounds in the Do - prophet inequality that depend only on inf Dx.(x)
Proposition 3.2 implies that if inf x>0
Proposition 3.3. Let 7 infasa (zo(x)/a x, and O < < 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 that
E [T)
CR (ALG) S sup
A E((OT(())
where (T) is the reward of A if all the decay functions were equal to x +> yr.
The core idea for proving this proposition is that rescaling an instance, i.e. considering (r ())) instead of (X)))e(n), has impact in the classical prophet inequality. However, in the Dx -ropphet

---

inequality, rescaling can be exploited to adjust the ratio (=(r=)) By considering instances with random variables taking values (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 either (0) = or (a). Rescaling this instance by a factor 8/a and taking the ratio to the expected maximum, the term (s) appears, with free parameter that can be chosen to satisfy [=(+) + inf (=(()] YD.
As consequence, if infa>0 (=(a) y, then any upper bound obtained in the 7-prophet inequality (when the decay functions are all equal to a + y2) using instances of random variables (X.....,X) Xn) satisfying X; {0, a, by a.s. for all i, is also an upper bound in the Doo -prophet inequality.
Implication Consider any sequence DD of decay functions, and define
D (x((2) inf inf (2(a))
TD == inf =>0
#20
For any x > and j 2 it holds that D, (x) 2 YDD, therefore, any guarantees on the competitive ratio of an algorithm in the "D "vpproppeet inequality are valid in the D-prophet inequality, under any order model. Furthermore, combining Theorem 2.T and Proposition [3. we obtain that for any instance I of random variables taking values in set {0, a,, b} it holds that
EAA (T)
YALG: : CR S sup
A E[OPT(I))
with an additional term of order ((n 1/33) in the IID model. In the particular case where TD = 0, Proposition 3.3 with Theorem 2.1] 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 prove the tight upper bound of A 0.745 are of arbitrarily large size (Hill and Kertz 1982].
Therefore, by studying the 7-prophet inequality for 7 E [0, 1], we can prove upper bounds and lower bounds on the D-prophet inequality for any sequence D of decay functions.
4 The 7-prophet inequality
We study in this section the 7-prophet inequality, where all the decay functions are equal to x + ye, for some E [0, 1]. For any algorithm ALG with stopping time and random variables Xi,...; Xn.. the observation order is n, we use the notation
ALG (Xi,.... X,) max(Xa (
( >X=
and we denote by CR (ALG) the competitive ratio of ALG in this setting. In the following, we provide theoretical guarantees for the y-prophet inequality.
For each observation order, we first derive upper bounds on the competitive ratio of any algorithm, depending y, using only hard instances satisfying the condition of Proposition 3.3 This would guarantee that the upper bounds extend to the D- D-prophet inequality if Tp = 7 Then, we design hinglethressolk algorithms with well-chosen thresholds depending on 7 and the distributions, with competitive ratios improving with 7. A crucial property of single-threshold algorithms, which we use to estimate their competitive ratios, is that their reward satisfies
ALG'(XI. X,) ALG (XI...., ...) + 7mmxx X.) (max, X.<0) P
The additional term appearing due to 7 depends only on max;e]n] Xi. 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 Xx(9) is compared with a threshold O,,
Remark 4.1. We only consider instances with continuous distributions the proofs of lower bounds. The thresholds 9 considered are such that Pr(maxie(m) X; 2 0) g(y, n. T), with g depending on y, 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].
7

---

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 7,
Proposition 4.2. In any order model, if a lower bound in the classical prophet inequality, and an upper bound, then, in the 7yprophet inequality
(i) there exists a trivial algorithm with a competitive ratio of at least max a))
(ii) the competitive ratio of any algorithm is at most (1-7)8++
4.1 Adversarial order
We first consider the adversarial order model, and prove the upper bound of بيك Then, we provide a single-threshold algorithm with a competitive ratio matching this upper bound, hence fully solving the 7-prophet inequality in this adversarial order model.
Theorem 4.3. In the adversarial order model, the competitive ratio of any algorithm is at most 2-yy Furthermore, there exists a single threshold algorithum with comperitive ratio 2- given any instance (F1...., Fn), this is achieved with the threshold O satisfying
Prx Fr (max;e[n) X₃ S 0) 2-7
The upper bound in the previous theorem is proved using instances satisfying the condition of Proposition 3.3 Hence it extends to the Doe then the D-prophet inequality, with y = YDD by
Proposition 3.3 and Theorem 2.1
4.2 Random order
Consider now that the items are observed in a uniformly random order X²(1). ..., Xm(n) and X maxse[n] X, As for the adversarial model, we first prove an upper bound on the competitive ratio function of 7, and then prove lower bound for a single-threshold algorithm. However, for this model, there is gap between the two bounds, as illustrated in Figure
We first prove an upper bound that depends on 7, matching the upper bound v3 1 of Correa et al. (2021c) when ? 0 and equal to when 7 1. Our three-lh algorithm has competitive ratio of at least (1 -1=1) =) when y = O, which is the best competitive ratio a single threshold algorithm in the prophet inequality [Esfandiari et al. 2017 Correa al. 2021c), and equal to 1 for 7
Theorem 4.4. The competitive ratio of any algorithm ALG in the y-prophet inequality with random order satisfies
CR' (ALG) S S (1-
- +y
Furthermore, denoting by Py is the unique solution to the equation 1 - (1 -7)p 1-p_ the algorithm ALGa with Prx,~Fi,.... X.r.E. (max:c(() X, 5) P. satisfies
CR (ALG) 2 (-1--7))
Similarly to the adversarial order model, we used instances satisfying the condition of Proposition prove the upper bound, thus extends to the D-prophet inequality with 7 = TDD
3.3
While the equation defining py cannot be solved analytically, the solution can easily be computed numerically for any 7 E [0, 1]. Before moving 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 1/c
satisfying Pr(max;ejn) x, 0) 1-(1-1/ey has competitive ratio of at least 1 (1-7)/6
I-(1-1/e)
4.3 IID Random Variables
In the classical IID prophet inequality, HHil and Kertz 1982 showed that the competitive ratio of any algorithm is at most 0.745. The proof this upper bound is hard to generalize for the IID y prrophhtt inequality. As an alternative, we prove weaker upper bound, which equals so 0.778

---

for y 0 and for 1, and the proof relies 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 single-threshoke 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 al. [2022] established that single-threshole algorithm
achieve competitive ratio 1/e in the standard prophet inequality with IID random variables, which also the best possible with 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.
better than
We describe the algorithm and give first lower bound on its reward depending on the size of the instance in the following lemma.
Lemma 4.5. Let on, be the unique solution of the equation [T-a/p]p 1) (1 -1) = 7 then for
any IID instance X Xns the algorithm with threshold satisfying Pr(Xi > 0) = an. has
reward of at least
anly (1- an.2) (--1122) n
B[max Xi] xE(m)
We can prove that the reward presented 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 7-prophet inequality is most
e² log(3 7) - (2 7) U()) 1 (1 (1-7) 2(2 1) (3e² 1)7
In particular, is increasing, (0))
RJ 0.778 and U(1) = 1. Furthermore, there exists 2(2-
log
single-threshold algorithm ALGa satisfying
CR (ALG)) 2 1 (1-1(11))p -2-)p
where 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 -prophet inequality with 7 TD. On the other hand, Theorem 2. ensures that the upper bound extends to the D D-prophet inequality, but with additional O(L/n 73) term. The latter does change the result, as we considered instances of arbitrarily large size n - oo.
Conclusion
In this paper, we addressed the D-prropht inequality problem, which models a very broad spectrum of online selection scenarios, accommodating various observation order models and allowing 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 7-prophet inequality, where all the decay functions equal to r + ya for some constant ? E [0, 1]. Subsequently, we provide algorithms and upper bounds for the y-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.

---

Limitations and future work
establishes that upper bounds proved in the 7-prophet inequality using instances of random variables with support in some set {0, a, b} remain true in the > -roppht inequality, hence in the D-prophet inequality by Theorem 2.1 This is enough to establish tight upper bound in the adversarial order model, but not in the random order and ITD models. interesting question to explore if more general upper bounds can be extended, or not, from the 7- to the D-prophet inequality.
Better upper bounds in the -pophhtt inequality. Proposition 3.3
Algorithms for the p-poophet incquality. As explained Section our analysis of the competitive ratio of tingle-treehoold algorithms relies on the identity 4 which is not satisfied for instance by cultiple-thresholl algorithms. In the adversarial order model, we proved that the optimal competitive ratio 1/(2 - 7) can be achieved with singlettreshol algorithm. However, this is not the case in the random order or IID models. An interesting research avenue to study other classes algorithms in the 7-prophet inequality.
Acknowledgements
This research was supported in part by the French National Research Agency (ANR) in the framework of the PEPR IA FOUNDRY project
NAR-23-PEIA-00033 and through the grant DOOM ANR- 23-CE23-0000 It was also funded by the European Union (ERC, Ocean, 101071601) Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those the European Union or the European Research Council Executive Agency. Neither the European Union nor granting authority can be held responsible for them.
Dorian Baudry thanks the support of the French National Research Agency: ANR-19-CHIA SCAI, SER-22-SRSE-O00P Ocean, and LNR-23-CE23-0007 Doom. Dorian Baudry was partially funded by UK Research and Innovation (UKRI) under the UK government's 's Horizon Europe funding guarantee [grant number EP/Y028333/1J.
References
Antonios Antoniadis, Themis Goulcakis, Picter Kleer, and Pavel Kolev. Secretary and online matching problems with machine learned advice. Advances in Neural Information Processing Systems, 33: 7933-7944, 2020.
Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim Larsen, Adam Polak, and Bertrand Simon. Paging with succinct predictions. In International Conference on Machine Learning, pages 952-968. PMLR, 2023.
Makis Arsenis and Robert Kleinberg. Individual fairness in prophet inequalities. In Proceedings of the 23rd ACM Conference on Economics and Computation, pages 245-245, 2022.
David Assaf and Ester Samuel-Cahn. Simple ratio prophet inequalities for a mortal with multiple choices. Journal of applied probability, 37(4): 1084):00441199 2000.
Alexia Atsidakou, Constantine Caramanis, Evangelia Gergatsouli, Orestis Papadigenopoulos, and Christos Tzamos. Contextual pandora's box. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10944-10952, 2024.
Ziyad Benomar and Christian Coester. Learning Learning-augment augmented priority queues. 244.:22006.04793, 2024.
arXiv preprint
Ziyad Benomar and Vianney Perchet. Advice querying under budget constraint for online algorithms. Advances in Neural Information Processing Systems, 36, 2024a.
Ziyad Benomar and Vianney Perchet. Non-clairvoyant scheduling with partial predictions. In Forty-first International Conference on Machine Learning. 2024b.
Ziyad Benomar, Evgenii Chzhen, Nicolas Schreuder, and Vianney Perchet, Addressing bias online selection with limited budget of comparisons. arXiv preprint arXiv:2303. 2023.
10

---

Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco. Pandora's 's problem with deadlines. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 20337-20343, 2024.
Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin Pál, and Balasubramanian Sivan. Improved revenue bounds for posted-prict and second-price mechanisms. Operations Research, 680611185-1182, 2021.
Allan Borodin and Ran El-Yaniv. Online computation and competitive analysis. cambridge university press, 2005.
Brian Brubach, Nathaniel Grammel, Will Ma, and Aravind Srinivasan. Improved guarantees for offline stochastic matching via new ordered contention resolution schemes. Advances in Neural Information Processing Systems, 34:271 14 181184--777 84-17195, 2021.
Archit Bubna and Ashish Chiplunkar. Prophet inequality: Order selection beats random order. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 302-336, 2023.
Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan. mechanism design and sequential posted pricing. In Proceedings of the forty-second ACM sympo- sium on Theory of computing, pages 31 311-320, 2010.
Justin Chen, Sandeep Silwal, Ali Vakilian, and Fred Zhang. Faster fundamental graph algorithms via learned predictions. In International Conference on Machine Learning, pages 3583-3602, PMLR, 2022.
Jakub Chikedowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz Zolna. Robust learning- augmented caching: An experimental study. International Conference on Machine Learning, pages 1920-1930. PMLR, 2021.
Nicolas Christianson, Junxuan Shen, and Adam Wierman. Optimal robustness-conse consistenn tradeoffs for leaming- metrical task systems. International Conference on Artificial Intelligence and Statistics, pages 9377-9399. PMLR, 2023.
Alon Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, and Shay Moran. Learning to screen. Advances in Neural Information Processing Systems, 32, 2019.
Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Recent developments prophet inequalities. ACM SIGecom Exchanges, 17(1):61-77) 2019.
Jose Correa, Andres Cristi, Paul Ductting, and Ashkan Norouzi-Fard, Fairness and bias in online selection. In International conference machine learning, pages 2112-2121. PMLR, 2021a.
José Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld. Posted price mechanisms and optimal threshold strategies for random arrivals. Mathematics of operations research, 46(4): 4452-1478 2021b.
Jose Correa, Raimundo Saona, and Bruno Ziliotto. Prophet secretary through blind strategies. Mathematical Programming. 190(1-2) (00(1-2):43--35 2021c.
Yuan Deng, Vahab Mirrokni, and Hanrui Zhang. Posted pricing and dynamic prior-independent mechanisms with value maximizers. Advances in Neural Information Processing Systems, 35: 24158-24169, 2022.
Haass Diakonikolas, Vasilis Kontonis, Christos Tzamos, Ali Vakilian, and Nikos Zarifis. Learning online algorithms with distributional advice. In International Conference on Machine Learning, pages 2687-2696. PMLR, 2021.
Michael Dinitz, Sungjin Im. Thomas Lavastida, Benjamin Moseley, and Sergei Vassilvitskii. Faster matchings via learned duals. Advances in neural information processing systems, 34: 10393-10406 2021.
Paul Dütting, Thomas Kesselheim, and Brendan Lucier. An o (log log m) prophet inequality for subadditive combinatorial auctions. ACM SIGecom Exchanges, 18(2):32-7,, 2020. 2020.

---

Paul Dütting, Silvio Lattanzi, Renato Paes Leme, and Sergei Vassilvitskii. Secretaries with advice. In Proceedings of the 22nd ACM Conference on Economics and Computation, pages 409-429, 2021.
Evgenii Borisovich Dynkin. The optimum choice of the instant for stopping markov process. Sovier Mathematics, 4:627-629, 1963.
Farbod Ekbatani, Yiding Feng, and Rad Niazadeh. Online matching with cancellation costs, arXiv preprint arXiv:2210.11577 2022.
Farbod Ekbatani, Yiding Feng, and Rad Niazadeh. Online resource allocation with buyback: Optimal algorithms via primal-dual. In Proceedings of the 24th ACM Conference on Economics and Computation, pages 583-583, 2023.
Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, and Jan Vondrák. Prophet inequalities with cancellation costs. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, pages 1247- 1258, 2024.
Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh, Prophet secretary. SIAM Journal on Discrete Mathematics, 31(3):685-1701, 2017.
Hossein Esfandiari, Johammad'Tagh HajiAghayi, Brendan Lucier, and Michael Mitzenmacher. On- line pandora's 's boxes and bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 1885-1892, 2019.
Tomer Ezra. Michal Feldman, Nick Gravin, and Zhihao Gavin Tang. Online stochastic max-weight matching: prophet inequality for vertex and edge arrival models. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 769-787, 2020.
Moran Feldman, Ola Svensson, and Rico Zenklusen. Online contention resolution schemes. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pages 1014-1033. SIAM, 2016.
Evangelia Gergatsouli and Christos Tzamos. Online learning for min sum set cover and pandora's box. In International Conference on Machine Leurning, pages 7382-7403. PMLR, 2022.
Evangelia Gergatsouli and Christos Tzamos. Weitzman's 's rule for pandora's box with correlations. Advances in Neural Information Processing Systems, 36, 2024.
Giordano Giambartolomei, Frederik Mallmann-Trean and Raimundo Saona. Prophet incqualities: Separating random order from order selection. arXiv preprint 20t:23300404024, 2023.
Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm. Automated online mecha- nism design and prophet inequalities. In AAAI, volume 7, pages 58-65, 2007.
Elfarouk Harb. New prophet inequalities via poissonization and sharding, 2024.
Theodore P Hill and Robert P Kertz. Comparisons stop rule and supremum expectations of iid random variables. The Annals of Probability, pages 336-345, 1982.
Zhihao Jiang, Pinyan Lu, Zhihao Gavin Tang, and Yuhao Zhang. Online selection problems against constrained adversary. In International Conference on Machine Learning, pages 5002-5012. PMLR, 2021.
Robert Kertz. Stop rule and supremum expectations of iid random variables: a complete comparison by conjugate duality. Journal of multivariate analysis, 19(1):88-112 1986.
Robert Kleinberg and Seth Matthew Weinberg. Matroid prophet inequalities. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 136-136. 2012.
Robert Kleinberg, Bo Waggoner, and E Glen Weyl. Descending price optimally coordinates search. arXiv preprint arXiv: 1603v:/603.07682 2016.
Tim Kraska, Alex Beutel, Ed H Chi, Jeffrey Dean, and Neoklis Polyzotis. The case for learned index structures. In Proceedings of the 2018 international conference on management of data, pages 489-504, 2018.
12

---

Ulrich Krengel and Louis Sucheston. Semiamarts and finite values. 1977.
Ulrich Krengel and Louis Sucheston. On semiamarts, amarts, and processes with finite value. Probability on Banuch spaces, 4:197-266, 1978.
Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter. Minimalistic predictions to schedule jobs with online precedence constraints. In International Conference Machine Learning, pages 18563-18583. PMLR, 2023.
Bo Li, Xiaowei Wu, and Yutong Wu. Query efficient prophet inequality with unknown iid distributions. arXiv preprint Stt.::2000005575 2022.
Honghao Lin, Tian Luo, and David Woodruff. Learning augmented binary search trees. In Interna- tional Conference on Machine Learning, pages 13431-13440. PMLR, 2022.
Denis V Lindley. Dynamic programming and decision theory. Journal of the Royal Statistical Society: Series (Applied Stutistics), 10(1):3--51, 1961.
Brendan Lucier. An economic view of prophet inequalities. ACM SIGecom Exchanges, 16(1):24 47, 2017.
Thodoris Lykouris and Sergei Vassilvtiskii. Competitive caching with machine learned advice. In International Conference on Machine Learning, pages 3296-3305. PMLR, 2018
Anuran Makur, Marios Mertzanidis, Alexandros Psomas, and Athina Terzoglou. On the robustness of mechanism design under total variation distance. Advances in Neural Information Processing Systems, 36, 2024.
Christos Papadimitriou, Tristan Pollner, Amin Saberi, and David Waje. Online stochastic max-weight bipartite matching: Beyond prophet inequalities. Proceedings of the 22nd ACM Conference on Economics and Computation, pages 763-764, 2021.
Bo Peng and Zhihao Gavin Tang. Order selection prophet inequality: From threshold optimization to arrival time design. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 171-178. IEEE, 2022.
Alexandros Psomas, Ariel Schvartzman Cohenca, and Weinberg. On infinite separations between simple and optimal mechanisms. Advances in Neural Information Processing Systems, 35:4818 1888 4829, 2022.
Manish Purohit, Zoya Svitkina, and Ravi Kumar. Improving online algorithms via ml predictions. Advances in Neural Information Processing Systems, 31, 2018.
Ester Samuel-Cale Cahnn Comparison of threshold stop rules and maximum for independent nonnegative random variables. the Annals of Probability, pages 1213-1216, 1984.
Sean Sinclair, Felipe Vieira Frujeri, Ching-An Cheng, Luke Marshall, Hugo De Oliveira Barbalho, Jingling Li, Jennifer Neville, Ishai Menache, and Adith Swaminathan. Hindsight learning for mdps with exogenous inputs. In International Conference on Machine Learning, pages 31 8777-3191. PMLR, 2023.
Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang. Pareto-optimal learning- -ugmented algorithms for online conversion problems. Advances in Neural Information Processing Systems, 34: 14:3999--00350 2021.
Vasilis Syrgkanis. A sample complexity measure with applications to learning optimal auctions. Advances in Neural Information Processing Systems, 30, 2017.
Martin Weitzman. Optimal search for the best alternative, volume 78. Department of Energy, 1978.
13

---

A From D-prophet to the ~x-pprphhet inequality
In this section, we prove the reduction from the D- D-prophet to the >o prophhtt inequality problem in the adversarial and random order models, and the reduction up an additional On 1/3) term 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.1
Proof. Let denote co the algorithm taking optimal decisions for any instance in the De prophet inequality (obtained via dynamic programming). Then, by Theorem 2.1 we obtain for the adversarial and random order models that
B (1) inf E (1) [()(
< inf sup sup CR (ALG)= ALG
CR (A., = sup CR Pa (A)
I A [(P((T))
A
(5)
Since CR?(ALG) 2 CR. (ALG) for any algorithm, we deduce that ( is an equality.
consider now any algorithm Axx. that is optimal for the ~roppht inequality, not necessarily A., then Equation 5
provides
CR CR P~ (Axo) = sup CR? (ALG).
ALG
The previous inequality is again equality, and it implies that Ax is also optimal, in the sense of the competitive ratio, for the D-prophet inequality, and
CR (A.o) CR (Aoo)-
A.2 Auxilary Lemma
The efficiency of the proof scheme introduced in Section 2. relies on the following key argument: if (Dz)22 converges pointwise Dx., then for any algorithm A and any instance I, the output of A when all the decay functions are equal to Dm converges to its output when all the decay functions are equal Dxc. If X...... Xn, are the realizations of I observed by A and if the order in which they are observed, then denoting T the stopping time of A we can write that
IE[A Pm (1)] EAA (I)
B|maxt (o(t): Dm (max Xx(0) [emmmaaXXX(rr Doo (max X :24
sET
Elmax Dm (max (x))) ) 18 WImxx ( Doo (max X=(o)]]
max TES, <E(n)
:<q
k<q
where S. is the set of all permutations of (n]. The latter upper bound is independent of a and A. We show in the following lemma that it converges to 0 when
oc.
Lemma A.1. Let Sn be the set of all permutations of [n]. For any fixed instance I = (F1. Fn). considering X, ~ Foror all E [n), define for all m 2
Xx(0)1
Cm (I) max E.S. (E[m]
E maxx
X r(g): Dm (max X (x)) E maxx x()) Doe (max i<q
i<q
E maxxe[x) Xi) xc, then lim em (T) 0.
120000
Proof. Let us denote fi,..., fo the respective probability density functions of XI..... ..... Xy. For any q [n]] and Sn, let define for all m > the function 6 00) 00, oo) by (2).... xTg) = ( Dm (max ox())} max(Fatg)= Dx (max4eg ()))) F is positive because Dm 2 Doo. The sequence (4 m is non-increasing, converges pointwise, and is dominated by (#1...., ......... 2z) + max 24, which is integrable with respect to the probability
14

---

measure (z1...., Fq) + IT 1= f(x)). Therefore, using the dominated convergence theorem, we
deduce that limm- El (X1..... X,)] It follows that
lim cm = lim m=+00
max Blym" (X (X1...... X,)1 = 0.
m--00
RES, gE(n]
A.3 Proof of Theorem 2.1
Proof of Theorem 2.7 and IID models.
We provide separate proof for each of the adversarial order, random order
F.)) be any instance and X; ~ F; for all E [na]. Consider a.s. for all i & {m, 2m,... .... mnn. It is clear that no reasonable algorithm would stop at a zero value: if the current observation is is preferable to wait for non-null value, or would have been preferable to stop at the previous non-null value. Hence, is multiple of m: 7 pm for some E N Given that (0) for all j and the sequence (D,), non-increasing. we have that
Adversarial order Let 7 1=
the instance I (Y (Yi..... ........... m.... where Ykm F& for any k E [n] and Y;
E|ALG (Im)] [[mxx D, +Y,) isT
E [max D (mkkmmmmmm) km (Ykm)]
kSP
E[max D Dpm Amm (Xx)
kSP
[[max
X max D (p- (p-A)mm( (Xx)
k<p
[[max| (Xpr max Dm (Xx)Hl
k<p
E maxx Xp, max Dxc +m
k<p
where 6m (7) 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 p when facing / in the context of the Doo -prophet inequality. More precisely, consider the algorithm An which, given any instance (Fi,..., simulates the behavior ALG facing the sequence Im, where each step i E [mm]
i & {m,..., nm): ALG observes Y; O,
otherwise, if Jem for some k [n]: Am observes X and ALG observes Ykm Xx
if ALG stops on Ypm. then Am also stops, and its reward is Xpp
(X,,,..... X,,) stops at the same value as ALG Ym). their reward in the prophett inequality is the same, and since maxie(m] X, = [mmn] Y; this yields to
E'ALG D (Im) EAADx (T) + cm E[OPT(!))
EAA P (T) E [(OPT( [[OP(())
6m (T)
(ALG) S E(OPT(Lm)
A: algo
and taking the limit when
gives the result, by making the second term vanish.
Random order Let 1 (Fi...., F.) ) be an instance of distributions and X; ~ F, for E [n]. Using the notation dn for the Dirac distribution in 0, consider 4,, = (F1..... F., 8p ... . Qn) containing m copies of & so that the observations from this instance always contain at least m null values. Let Y ...... Y. be realization of this instance. For simplicity, say that Y, X; for i [n], and Y; = 0 for n.
We first show that when the algorithm observes a large number of zeros between every two random variables drawn from Fx). Let denote by the uniformly random order in which the observations received,
since the observation order is drawn uniformly random,
15

---

Le. the algorithms observes Ym)), Yx (z( and let e 2 be some positive integer, and ti,.... tn be the increasing indices in which the variables ...... ... Y, are observed, i.c. 2 < ... tn and
(4,....m) { (1),.... (n)). Therefore, any observation outside (Yn(t.)--... Y (a(t))) is
zero. Using the notation L = [1) - t.l, we obtain that
Pr(L = Pr(Ut= (t4+1 - 4, -
= Pr (UR Uي=1 (1m- x - se))
n(n - 1) (1) x (2) 1
n(n - 1) Pr( ( (σ (1) k, (2) E (k- l,...,k 03 (K))
n(n - 1) x (n m) x
2
n n+m m
n2 m 1
m
Taking L = vm, we find that Pr(L S () S /n///m/m Therefore, for any algorithm ALG, observing is at most |a X, a.s., and by independence of maxie[a] X; and L,
that the reward of ALG D deduce that
E[ALG
D (Im)) [[ B[ALG 2 B[ALG (mm)
$ TEALG (Tm) T>> f + E (max X sE(n]
asd
n²
- (EJALG((Im)
L> 8 + Emax X,]
(6)
sE/nl
/m
Let denote the stopping time of ALG and I,- maxje(n] (1y 1 I 7) the last time when variable (Xy)se(v) was observed by ALG. The sequence of functions (Dz)j2 is non-increasing. hence
E[ALG" D (Im) 1 f = Elmax D D7-i((=(1) L > !]
[E([]]
= E/max - (Y (e(t,)) L > E
(7)
< E[max Dr Dep-s (Yr(t))) |L>6
(8)
E/max { (Y
max 1 (Ya(t))) |L> !
jep
< E/max (Y>(t,)) max (Y (Yx(t)))]
(9)
jcp
Equation 7 holds because the only non-zero values up to step r are (Yn((,)) )Ejp)- Inequality 8 uses that the sequence (Dz) is non-increasing, and (9) uses, in addition to that, the independence of and (Xxg)))e(w) We now argue that the term E mmxx (Yr(s,) maxx<p (Y }]] is the expected reward of an algorithm in the Dy-inequality. Given that π is uniform random permutation of [n + ml and by definition of f1, .1,...; fnn the application Therefore we consider the algorithm Am that receives as input the instance / = (FI...., F.), then values, and a uniformly random permutation æ of in + m]. then simulates ALG (Jm. as follows: at each step j E [n + m]
1 [n] - aTt&) is a random permutation of [m].
considers the array (1...., 1, ...... 0) composed of n values equal 1 and
if Ur(()) 0, then ALG observes the value Yx() 0,
if Ur(() 1, then Am observes the next value Xo(k). and ALG observes Y=() Xo(())+
when ALG decides to stop, Am also stops, and its reward is the current value Xa(k)-
With this construction, (Yz)se(n+m) indeed a realization of the instance I.. and A, stops on the last value sampled from F. Fi,..., Fn observed by ALG. Therefore, denoting the stopping time of
16

---

Am, and (T) as defined in Lemma A.1
we have
IE[ALG (mm) L < M[max T(( max De (e(( (X)()))
M|max {Xo(o))
max Dz De(Xo(t,)))
sSP
EIAM (T)
E (T) + +
sup E[A P (T) + (T)) Azalo
Taking & m and substituting into Equation (6). then observing that E[OPT( = E[OPT(!mm)
gives that
E|ALG" D (Im)) ET [4m)]
EA D (T) [()
Vm (1) E[OPT([)] + n²
CR CRL(ALG)
sup Acalgo
Vm
Finally, taking m + oo and using Lemmal
we deduce that
E Po (1) E OPT(
CRO(ALGS
sup A.algo
which completes the proof for the random order.
IID random variables For any probability distribution F' on [0, 00) and for any 2 we denote EIOPT n]] the expected maximum of independent random variables drawn from F, and for any algorithm ALG we denote BTALG" P (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 2 1,A 2 0, we have
A
E[OPT(F. A)] S
1 1
E E[OPT(F,
Proof. We first write
Pr(OPT(F,, A) x) = 1 - F(x)n+s
F(a)" 1 - F(x)
(1 F(=)))
1- F(x)"
F(x)
1+ F(a)" =IFF(()) FF()))
Pr(OOP(F,.)) > x)
and then use that
A
A (1- (1-F(x)")
F(z) - (o)( 2 31+A1oge Alog(F(2))
log 1og(L/(()))211-
n F(x)"
n
so we directly obtain
F(x)" 1- F(x)
A
S
1 1- F(x)
n
which gives that
Pr(OPT A) x) 1 -
(r(OOT(F,n) x)
As we consider nog-negative random variables, it follows directly that
E(OPT(E, + A)] < 1 +
E[OPT(F,n)]
17

---

Lemma A.3. Let N ~ B(m,E) and let := == E[N] = Em, then we have
B[OPT[F, N2n+nera] z 12/33
E[OPT[ n + n2/3)]]
3
1+
E( + + n//3]]
n1/3
Proof. Let A, s > 0 such that S s. For any 2 let Wx = [s + - + -A). (W4)221 partition of [s, oo), thus have
E(OPT s + +A)]NEWLL
E(OPT 8 + PAN ( W&)) W
KA
1
EJOPT(F, 8) Pr(N E Wt)
k=1
2 kPI(N E Wo) EIOPT s)]
Pr(N 2 8)
k=1
where we used Lemma A.2
in the penultimate inequality. Furthermore, observing that
k-1
kPr(N W
Pr(N E W.)
Pr(N 2 s+
1=1
k= t=
Ł=0 k=tt1
E=
we obtain, given A that
A 20 Pr(N 8) Pr(N P #[OPT(F.s))
(F,
(10)
2[N2s+ha)
(11)
N is a Binomial random variable with expectation n. Therefore, Chernoff's inequality gives for any
5 2 0 that
82 S exp (- (-ming) min(6,82)m
Pr(N 2 (1 + 6)m) S exp
2 5
3
where the second inequality can be derived by treating separately 8 << 1 and 5 2 1. In particular, for any 1: 2 1, taking 5 = kA such that A < n yields
min (k,, A m))
(A, (A, = exp
AA
Pr(N 2 ++ < exp
I exp
3
3
3n
Substituting this Inequality into with = n + A. we obtain
[(OPT(F, N)]N2444) <
2
Pr(N 2 +
E[OPT(F, A)]
1=1
<
2
exp
3n
k=
2
EF A)
A3
exp
6n
A
18

---

and taking A = 2 proves the first inequality of the lemma.
Let us move the second inequality. We have E|OPT(F, N s E|OPT () = Pr(N <) and thus, using Inequality (T)). again with
A and A n2//3, it follows that
E(OPT(F, EIOPT =
Pr(N 2
E[OPT(F,s))
km0
1
Pr(N ((
[(OPT(F,s))
1 n\/3
Lemma A.4. Let Si,..., 5m B(s), and N = Eis dz. Denoting by n [[N] em, if 2
then
8
E|N O)T(E, S
1+ n
n 2
EEPT(E, n/33]]
Proof.
For all l E [m], denote by N₂ ci=k
We have that
2
m
(F,
Σ
8
OPT(F,N)
m
Σ
8
555,
OPT(F,N),
and observing that 63 6; for all i, we obtain in expectation
E[N"OPT N)] (P N2)] + m(m 12 Na)]
+ N2) + m(m 1) + 82 + Ns)l
OFEE N2)) - 1 Ns)l
()=
mcE N2)] m = + Na)]
(12)
For j E {1,2). the proof of Lemma A.3 can be easily adjusted to prove an upper bound on E(OPT(F,j Nj+1). by first bounding E[OPT( N then E[PP
The Ny+1) The concentration arguments remain the same, replacing m by expectation of NJ+1 is 8(m - j) n Ej. hence we obtain
1+ 3
E(OPT(F.j + +N,+1) <
E[OPT(F.j (n Ej) + (n - -3))/881
(n --])
+ (n (n-ej)113
E[O 223
ej)1/3
F, 2/33
+
(n 2/1/3
E EEOPT + n +2233]
4/3
where we used respectively in the last inequalities that j < 2 and 2 4. Furthermore, Lemma A.2 gives that
4
2
E(OPT(F,. + N5+1)] 5
1 +
1+
(F,
1/3
2/3
6
1 +
E (F, + n 2/3)]
1/3
19

---

where the last inequality is true for n 2 4. Finally, substituting into 12 yields
6
[|N < (m²2² + +m)
1
+
E [F n + n2/00]
n/3
= (n² + +n) (1
1
FF n + (
n2/33
+ -
1
+
6
(OP, n + 2113]
1/3
1 +
n²E[OPT [F, n P 22/1]
n
n//3
m Lemma A.5. Let Ó1..... 5m id B(E), N N= EZE 6g n [[ em and min {ii jl
5, = 1. = 1}, for any l 2 0 we have
E [IOPT NY1 S 7mmke T + n=
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 É 2 0 and k 2 2 we have
Pr(L. S.N. 8) = Pr = e 2 6x =
m
Pr | Uf-max(1, - 13 (6; = 85 = 1, Σ 6% s)
<ml Pr (01 82 = 1, Σ 8% - 2)
=me ml 11 - 2)
E1 8) m-
8-2 2
therefore
Pr(L S E, N = 8)
Pr(L S N = 5)
Pr(N 8)
me( 2) ))²²1 m
E0(1 (1 2)m mm--
< ml (m-2)
ml 8(s 1)
m(m 1)
ls
m
Using this inequality and Lemma A.4 (OOPT(F,N)1110
we deduce that
E(OPT(F, Pr < N, OP), (E)) & N)]
OPT
m
8
Ln
1
E(OPT(F, n + n 221331
1/3
m
8
1
n 1/3
7més_
(P.
20

---

where we used that 1 +
8 n17 7 for 2 4.
Using the previous lemmas, we can now prove the theorem. Let m > n 2 1, A n²/3 n/m and let Q be the probability distribution of random variable that is equal to with probability 1 and drawn from F with probability E.
Let consider m i.i.d. variables Y Yi....,Y, indicator that Y; is drawn from F. Define N = E 63 B(m,e) the number of random variables Y, drawn from the distribution F. In the following, algorithm by analyzing its ratio on this particular instance. For this, we first provide lower bound on E(OPT(Q m)] using Lemma A.2 and obtain
Q, and for each i [m]] we denote by ó; the
upper bound the competitive ratio of any
1
(1-22) (1- n
24 EIOPT(F, +A],
E EIOPT(P,n A)]
24
thus we have
BIOPT(Q, m)] [[
E[OPT(F, - A)
n Pr] A)
24
Pr(N 2 OI +A]
n
2A
Pr(N <n- 4) E[OPT(F,
n
2n
exp( exp(-n1/3/2) +(OPT(F,*+A))
4n 1/3) E(O
(13)
where, for the last three inequalities, used respectively Bernoulli's inequality, Chernoff bound, then - < 1/y.
Then, we upper bound the reward of any algorithm given the instance (Q, m) as input. Let L = ili - -] 52 1, = 1} the smallest gap between two successive variables Y, drawn from
F, and let l < < Ix the indices for which 8 1. We have for any algorithm ALG and positive
integer f that
E|ALG (Q, m]] EAAG mQ L EJALG" (Q, m))Ncccsa (14)
Using Lemma A.3 and Lemma A.5 the first term can be bounded as follows
[AALG (Q, Nr
< E(OPT F, N)T N2=+4 L.t
< (F, N2 (
6
1/3 7mll?
EIOPT(F, -//3)))+)/3]]]
Recalling that ε m/n and taking = /m, we obtain
6
7 2
OF +
(15)
1/3
21

---

Regarding the second term in Equation (14), let be the stopping time of ALG and t max S T: 63 1} the last value sampled from and observed by ALG before stops. We have
E E[ALG" (Q, (Q.m)lNentt.Ldd - ETALG' (Q, m)) N < < <
|llnax D, (Y;) N + A,4>
E[max jElpl
1, (Yi) N < n < <
S Elmnxx Di,- (Yi) N < n < jE(A)
R|max (Y,,, max Dr (Y1)) } N <n+ !
jEP
S E|max (Y,,, max (V()))) N <
We then prove that the last term is the reward of an algorithm Am in the De-prophet inequality. Let us Am be the algorithm that takes as input an instance XI,..., Xa+A-1 of n - A IID random variables, idd B(n/m) set NA 0 and then simulates ALG (Q,m) m) N A follows: let ō1 _1,..., 5m for each E [m]]
if 6; = 0: ALG observes the value Y, = 0,
if d; 1: increment N, then Am observes the value Xg. and ALG observes Y; Xk.
if NA + A or ALG stops, then A., also stops.
When ALG decides to stop. the current value observed by Am is Xp: the last value Y,, observed by
ALG such that 6,,- O. Observe that stopping when NA n + Á 1,1, equivalent letting ALG observe zero values until the end, and stopping when ALG stops. Hence, the variables Yi...., Y have the same distribution as m IID samples from Q conditional to N < n + A. Denoting p the we deduce that
stopping time of Am and cg F, A) defined in Lemma A.1.
BAALG (A, N < A. 4 < mmxxx {Y,,, max D&(Y,)) I <n++
s<p
E/max {X max (x(X))
E (F, A)
EE (F, + A)] + (F
(16)
Substituting (15) and
16 in
14
with e = Vm, yields
7
E|ALG P (Q, m)]
<
E(OPT(F, n+ + A)] + EAA (F,+ ())++))==0 + + (F, +A)
1/3
Vm
and using Inequality
13 it follows that
E[ P (Q,m)]
CRP(ALG)
EEOPT(Q, m)]
EI
Doc
(F,n+ A)I + F (F, A)
w/3
Vi
1
4
n1/3 DE(PT(FF A)]
1/8
7
1
( A)
A D (Fi A)]
+ sup A:algo
E(OPT(F, A]]
OPT
n
22

---

taking the limit m - 0o and using Lemma A.1
gives
E[A D= E[OPT( A)
A)
CR (ALG)
S
sup Aralgo
1
1/5
727
6
+ (1
4
EAAA P~ (F, n + A)] E(OPT(F, A)
1/3 4
n/33
sup Asalgo
10
E[A x= (F
2
+ sup A:algo
1/3 4
E OPT F, n + n2/3)]
where the last inequality holds because E[A Da (F, n + A) S [[OPT + A)] 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 2 (n + + = k/2,, thus n 1/3 2 1/13 /2, and we obtain
20
E[A D (F,A))
CR"(ALG) $
+ sup Aualgn
k1/3
8
E [(OPT(FFA))
E D [)]
1 1:/3
sup Azago
+ +0
E (F)
B From -oopophtet to the Yo-prophet inequality
B.1 Proof of Lemma 3.1
Proof. Let ALG be any rational algorithm in the Doo -popphet inequality. If ALG stops at some step E [n]. then by definition we have that X, > Doc (maxj<r Xj), and thus ALG Px (X Xn) =
ALG X.)) Otherwise, if it stops at = + 1, then its reward is maxie[1] Dx,
X.).
Do [max4e[n] X;), because Dis non increasing.
On the other hand, let A,, be the optimal dynamic programming algorithm for the -prophe in-prophetinnquull inequal-
ity. At any step i, if X; < Doc (maxj<s X,). then stopping at i gives reward of D oc (max X,), while by rejecting X4, the final reward guaranteed be least Doo (maxz<i Xz). Thus rejecting X; can only increase the reward, it is therefore the optimal decision.
B.2 Proof of Proposition 3.2
Proof. Let us place ourselves in any order model, or in the IID model. Assume that infaso Deo 0, then there exist a sequence (sx)a21 such that lim
(z)+)) 8
Let I (Fi..... Fx) an instance of non-negativy random variables with finite expectation, and X; ~ F, for all i E [m]. Let ALG be a rational algorithm for the Dx inequality and let us denote t its stopping time. Denoting X* == max4e[n] X; and using Lemma 3.1 we have for any constant C' > 0 that that
B[ALG Pr (7) = E|ALG (AALGG(()11-500 EJD
< IEJALG (IAAL (DD (X"))
< sup E/A EXX
(17)
Let 1: > positive integer, M positive constant, and consider the instance / of random variables (X."...,, X²) with X.
ax M X, for all E [n]. We have that OPT(I*) = OPT(( and supA " = 2 supa E (I)). Therefore, using Inequality (17 with _ instead of / and
23

---

C = St. then dividing by OPT(1*) gives that M
E|ALG P= (I*)]
EIA
(T)
Doc (sk)
E X xx
CR R (ALG) v
sup
E ([OPT((A))
E
[(P((
[(OP((()
M
(T)
M
(8k)
B[x"Ix'sM
sup
E [(OPT(T)]
[[OPT(T))
E[OPT(T))
A
8k
and taking the limit + 0o, we obtain
E[A E[
CR Pa (ALG) sup
A [[OPT(/)) [[(OP([T)
and since X has finite expectation, taking the limit M + 00 gives
[[A
CR (ALG) S sup Finally, taking the infimum over all instances, we obtain that
A [[OPT(7))
CR (ALG) & sup (R)
As in the proof of Corollary 2.1.1 permuting inf, and SupA is possible because there is an algorithm (dynamic programming) achieving the supremum for any instance. By Lemma the inequality above holds for in particular for the optimal dynamic programming algorithm, which has maximal competitive ratio. Therefore, the inequality remains true for any other algorithm A, not necessarily rational.
B.3 Proof' of Proposition 3.3
Proof. Let us place ourselves in any order model or in the IID model. Since 7 inf Doo there exists sequence (sx)x21 of positive numbers such that lim
(==(+)) 56.
For the random variables XI...., taking values in {0, a, b} a.s., in any order model, it is clear that the optimal decision when observing 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 T be its stopping time. If T max X; and 0 otherwise. In particular, ALG is rational the ~ropprt inequality and we have by Lemma 3.1 that
1 then necessarily max4e(n) X; b, and the reward of ALG in that case is D (a) if
EAAGG P (1) EAALG 0 (Л) + D[D (max X,) 1==+1]
sE(n]
EEALG (1) + (a) Pr(T = n + max X; = a).
(18)
Consider now the instance _ of random variables (X+ ........... X²i where X 2 X, for all i [n]. 1 satisfies the same assumptions as with a = and b sub and we have E[OPT([*)]
* E [P)((T)), EJALG"((T)) <
* SUpA TEA (T)) and (max;e(M) X a²) = (max X,
a). It follows that
E[ALG P (7+)
SUPA | (T)
(so St E[(OPT(I)
Pr(r n 1, max X; a) iE|n
E[OPT(I*)]
E(OPT())
SupA E| (T)
Doc (8k)
a
+
Pr(r = n 1, max X; = a)
E[OPT([))
Sk
B[OPT(T))
iE(n
Taking the limit + do gives
SupA (T) ya Pr(r = + maxig(m) X; a)
CRD~(ALG) <
E [(OPT(I)
supa (E (1) + E (max X,) (
E[OPT(/))
24

---

ALG is also rational in the y-prophet inequality. Therefore, using Lemma 3.1
we deduce that
[LAG (T) sup [[OPT(
E (7)
CR (ALG)
(Z)
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 yo-ppophet inequality
C.1 Proof of Proposition 4.2
Proof. For the lower bound, suffices to consider the following trivial algorithm: if a > y then run Aa, and if y > then observe all the items then select the with maximum value.
For the upper bound, let = (Fi...., Fn)) be an instance of the problem and X; ~ F; for all i, [2) and let Bg supA E(OPT([)] Let A be any algorithm, its stopping time, and Y, max Xx()), where π is the observation order. With the previous notations, we can write that E[A = For any 2, y 2 the application y ~ max(x, YV) is convex on [0. 1]. hence it can be upper bounded by (1 7)x + max(2,, v). Therefore
E [[maa(Xxtr):>>23
((( S 7) 7) (n) + ( Y+)
- (1 >) [E (7) + [[(PP((
- ((1 7)33, + +>) E[)P((())
Therefore, (ALG) < ((1-7))) + 7). Taking the infimum over all the instances / gives the result. Indeed, we denote A, the optimal dynamic programming algorithm for the standard prophet inequality, then
E [ [PT
inf 31 = inf 1
CR CR 88.
C.2 Proofs for the adversarial order model
Proof. We first prove the upper bound, and then analyze the single threshold algorithm proposed in the theorem.
Upper bound Let E 7)) and let a = - (such that 1 (1 - --ya = a). Let X1, X₂ the two random variables defined by X1 almost surely and
w.p. w.p. 1-
X2 =
Stopping at the first step gives reward of while stopping at the second step gives
e)ya a hence the expected output of any algorithm is exactly equal to On the other hand E|max(XX (X,, X2)) + (1 E)a,
E7max(7a, X2)]
e) x ya
and we deduce that, for any algorithm ALG for the 7-prophet inequality, we have
CR(ALG) < E|ALG X2)]
E ma X1, X²)]
1+ E)a
and this is true for any (0, 7). thus taking + gives
CR(ALG) S
2 2-1
25

---

Lower bound Consider an algorithm with an acceptance threshold 6, i.c. that accepts the first value larger than I (Fi..... F......F.. be any instance, such that X; ~ F; for all i, and let us define X = maxie[n] X; and p = Pr(X* < 0). In the classical prophet inequality, if no value is larger than then the reward of the algorithm zero, and we have the classical lower bound
(T)) 2 (1 p)6 + p - 0)+},
For the 7-prophet, if no value is larger than (i.e X - 8), then the algorithm gains y instead of 0. Therefore, it holds that
B(ALG(())) = B[ALG" (T) + - x x
2 (1 r)0 p + sol
= (1 - ppp + p - - > 5x
= (1 -r) p( (1- p}0) - -
(L p)00 + pB[X Lx.>o] + +1E[x"1x-s0
and observing that
x00xx
P
we deduce the lower bound
1x.>0] +++ + y (1 (1-p) p))
E[ALG* 2 p
E
p
p.7+ (1 (1-p)
min
p E[X"
The right term is maximized for p satisfying p = + [1-p]²
that leads to
p
(1 (1-p)²
4 p² = + 2p 22
P
p= 2 2-7
Hence, by choosing threshold satisfying Pr(X- <0)
1 2-
obtain competitive ratio of
least 2-
C.3 Proofs for the random order model
We prove here the upper and lower bounds stated in Theorem 4.4
C.3.1 Proof of Theorem 4.4
Proof. We first prove the upper bound, and then derive the analysis for single threshold algorithms.
Upper bound Let > 0, and let XI,..., Xn+1 be independent random variables such that Xn+1 a a.s. and for 1 S Kish
X, n w.p. w.p. 1
R
Any reasonable algorithm skips zero values and stops when observing the value The only strategic decision to make is thus to stop or not when observing X,-1 = a. By analyzing the dynamic programming solution ALG, before a certain step j. and select it otherwise. The step j corresponds to the time when the expectation observed.
obtain that the optimal decision rule is to skip if it is observed
of the future reward is less than a. Let be the random order in which the variables Then, if न - + 1) < j, i.c. if the value a is observed before time j. X is not selected. The output of this algorithm is hence n if at least one random variable equals n, and ya otherwise. This leads to
(1- 1 1 (1-12)" $ + ya.
)2)") ra (1 (1- n
)
E[ALG;(X)) (n 1) <
26

---

where we used the inequality (1 21- 2
1. On the other hand, if ग (n)
2 J. then a is
ni selected if the value n has not been observed before it, hence for any 2 we have
i-1
(X) = =
1
1
n2
n²
+
we deduce that
n+1
i-1
S (1+ (1++))) Pr(p (n) 1)
Σ
+a
(n) =1)
n
j j-1 1
1
n+1
(1 70)
+ n 1
+
n+] 1
i=j
= (1 (1- _ 1
j
+
+ + o(1)
2
$ 1 2ya + (1 - 7)) ((1)
where the last inequality is obtained by maximizing over j/n. Finally, we directly obtain that
1 1 nz
( "
1 n2
E[max X.}
+ 1
=1 + o(1),
so for any algorithm ALG we obtain that
1 + 2na + - 7)
CR CR' (ALG) I (ALG.) =
1+a
The function above is minimized for a = / 1-7 - 1, which translates to (ALG)) <1 7) 3/2 (/33
v1 +
Lower bound We still denote by /= (Fi...., Fx) the input instance and X; ~ F. for all i E [m]. Let ALG be the algorithm with single threshold 0, then it is direct that
ALG = ALG" (1) + 1x
(19)
We start by giving a lower bound on E|ALG").. We use from Correa et al. 2021c] for any x it holds that
(Theorem 2.1) that
Pr(ALG (T) 2 x) = Pr(ALG (T) 2 0) = PP(X 2 0) = 1 - p,
and for A it holds that
1-P p Pr(X 2 x)
Pr(ALG (T) 20) - -logp
from which we deduce that
E|ALG* (I)] / Pr(AAG 2 x)dr
1-p 1 Pr(X* 2 x)dr.
(1 (1- -logp S
(20)
On the other hand, we obtain that
Pr(X"1xx<e 2 2)dx ( Pr(æ S X* < 0)dr
E [xxAxx=0l
(Pr(X*> > x) - -Pr(X 2 0))dz
/'" Pr(X* r)dr- (1 - p)0
(21)
27

---

Using 19
20 and 21
we deduce that
1-p P
/ Pr(X 2 x)do - 7(1 p)0
E|ALG' 2 (1 - pp0 + - -logp..
Pr(X 2)dr +
J0
/8
1-p
-) pp0 +2
Pr(X" x)dr
Pr(X" 2 2)d2
logp J
2 ((1 - 1)(1 - p) + +7) / Pr(X* 2 2)dr
1 1 000
+
Pr(X* 2 z)dr
loog p
1
Pr(X* 2 x)dx + / Pr(X* x)dr
min
(1 - (1 p) 7, logg
-in 1 (1 7)p 1- [[X]]
logp p
Finally, choosing p = Py gives the result.
C.3.2 Proof of Corollary 4.4.1
Proof. Forp 1-(1-1/0) have immediately that
1/e
-1-7)/e
- 11-1))p=1111 1-
1/e)r
and p E [1/e, 1] for any j0, 1]. Since the function x + (1 x log(1/2)) is concave, we can
e-1 which the line intersecting it in 1/e and 1. lower bound on [1/e, 1] by x 1 1/e+ z-1/e Therefore have
p 1/e
p 1/e =1 1- 1--1-1/44
(1 (1-7)/e
log p
e
Finally, using the previous theorem, this choice of guarantees competitive ratio of at least
1 1 p min {1 1- (1 (1-7)p1 -)pp
(1-7)/e
-logp 1 (1 1/e)y
C.4
Proofs for the IID model
Proof of Lemma
Proof of Lemma 4.5 Let F be the cumulative distribution function of X1, > 0 and ALG the algorithm with single threshold 0 such that F(0) a We denote X max4e(x] X,, As in the
previous proofs, we will begin by lower bounding ALG nF. For any i E [r+]. ALG stops at step i and only if X; and all the previous items were rejected, i... X2 S for all j Thus we can write
EAAL ( (F,n))
E.
Σ (X11 ( 1=1
- 1x,0
1=1
F(0)"
E 1 >o]
1 - F(8)
F(A)"
x nE X 1x,>0,,
(22)
28

---

where the second equality is true by the independence of the random variables (Xi); On the other hand, we can upper bound E >x+ follows
E 1 x - Pr(X > 6)0 [[(X 0)-
$ Pr(X > 8)8 + (X; - -0)+
Pr(X > > + (1 x - Pr(Xi >
010)
a) = - ((0) - = nE 1
Using the definition of the independence of (Xi): then Bernoulli's inequality have that
Pr(X 0) F(O)" =1 _ 1
9 =a
71
E[01x+ F(6)
Elx'Ix=sel F(0)"
and observing that /
we deduce that
1-a
B 1x 1x S
E[X* [x + nLE[X [x
F(O)a
by substituting into j2 we obtain
E/ALG" 2
1 F(0)"
E[X + (1 1
E 1(x'1x-50l)
F(0)²
a
Finally, the reward in the 7-prophet inequality is
EAALG" (F, E[ALG'
( (F, m)] + >E[X "XX"XLL co
- F(0)"
F(O)
1 1- a F(0)=
E E 1 xx +
+7)
-[x 1x-c0l
F( 1 - F(0)"
1 F(0)")
min
1-
+7 E E[Xx]
a
The equation 1-F(6)
1-F(0)"
[1
1-a Play"
+ y, is equivalent
a
1
) (1 (1-1)= 7
(23)
(1 a/n)n
and for any n 2 2 the function a + (7--))))" - (2 - 1) is decreasing on (0, 1] and goes from 1 to O, thus Equation (23) admits a unique solution dn,7, and taking a an,y guarantees reward of 1-F(0)" E[X*] Ope
E[X*].
Proof of Theorem 4.6
Proof. We first prove the upper bound, and then we give the tinglo-threshold algorithm satisfying the lower bound.
Upper bound We consider an instance similar to the one used in the proof of Theorem 4.4 Let a, x > 0, and let XI,..., X2 be IID random variables with the following the distribution F defined by
w.p.
X1
a
w.p.
w.p.
T2
reasonable algorithm would always reject the value and accept the value n. However, the algorithm faces an item with value it must decide to either accept it, or reject it with guarantee of recovering ya at the end. By analyzing the dynamic programming algorithm ALG,, we find that the optimal decision is reject if observed before a certain step j. and accept it otherwise. Let us denote r the stopping time of ALG.. By convention, we write n + to say that no value was selected by the algorithm, in which case the reward is y max4e[n] X,.
29

---

I S j - 1 then necessarily X, = n. because ALG, rejects the value a if it is met before step j. and if r n n+1 then |a X; E {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 is
< +
E|X;
T i] Pr(T = i)
+ Pr(T = n + 1, max = a)
(24)
iE/n|
Let us now compute the terms above one by one.
1-1 J-1
Pr(T < j) = Pr(3i E [j - 1] : X, = n) =1
(1
11-11
1
1
j
n²
n²
where we used Bernoulli's inequality (1 (1- 11-1/22)f-12 11 11
> 1 1. For i E [j....,n} n):
ALG, stops at if X; E {a. n) and if it has not stopped before, i.e. X E {0.a} for all & < j and
Xx = 0 for all & E (j...., - 13, hence
Pr(T = i) = Pr(vk- <j: Xx
o n and vjskgi-
1: Xx = 0 and X; #0)
1 1
1 I n
1 n
Pr(x,
n2
< (1 x '- Pr((X 0),
the second equality is true by independence, and the last inequality holds because 1- + S and
1
2 2/- By independence of the variables (Xx)a. we also have that
B[X,]
1 ax
E x[2 1-
X; + 0] Pr(X, + 0) Pr +
Finally, the event = 1, maxie(m) x;
= a) is equivalent (max:e)- X, = ak
0). In fact, the algorithm does not stop before + 1 if and only if Xx * for all ks < j and X2 = 0 for all j S k S n, and under these conditions, it holds that maX X; = max,el -1] X, Therefore
Pr(r = n + 1, max X₁ = a) = Pr( max X, = a, Ak 2 j Xx = 0) /E[m)
-E
1]
Pr( max
X; + 0) Pr(vk 21 j 00)
x
(1-
x 1 n-j
1
1
n
n n
zi (1))
+o(1)
(e zi - 1)e x + o(1)
All in all, we obtain by substituting into 24 that
EJALG]
<
+
+ ax
1
x i-s n
+ +ue (6 -1) + o()
n
imj
j
+ ax
1- (1 - x/ s/n) n-j11
+ -aae= 4 - 1) + o(1)
+
n
z/n
(1 - e x z
+o(1)) + yae - =c 22 - 1) + o())
+
+ a
( + (1 - -))a] - z1
+ + a 7aE + o())
1
x
< max
{s (1 + (1 7)a)
c c
+
1
+ (1 7/ 2 )a (1))
x
1
1
(log(1 + (1 - 7)xx)) + 1 x)
+
+ (1 7 = )a + o11)
I
x
1
log(1 + (1 - 7)ar)) + +++ + (1 - - - a =())
30

---

On the other hand, we have that
Pr(max X; - n) -1
112 )
+o(lnn)
1E|m)
Pr(max X; =0 - (1-0)))---1)) n² sEIn|
1
= = +0(1)
Pr(max X, = Pr(max X, = 0) Pr(max X₁ n) e- + o(1) sc/m]
kE/m
sc/m
therefore, the expected maximum value is
E[max X²] = Pr(max X, n1 + Pr(max X₁ a)
VE(N)
iE(n]
KE(n]
=1+ (1 - c a 0(1)
We deduce that
B[ALG] (F, n)]
log(1 + (1 - 7)ax) + 1 + (1 - "e )
<
+ o(1
(maxxee)) [n] X₂]
+ (1 - 6-2)
1 log(1 + (1 7) 7ax)) -10e o(1)
1+ - -==
Consequently, for any a, > 0 and for any algorithm ALG we have
CR(ALG) & CR(ALG.)
(FA,
< lim E [m X,]
$ log(1 + (1 )ar) (1 yaaz
I + (1 2)
In particular, for x = 2 and a
1-7/2 1-7
we find that
CR(ALG) s log(3 - -7) - (2 - -yye-
2+ 1-7 - 2)
1 (1 (1) e² log(33 -7) - (2 - 7) 2(2c2 1) - (3c2 1)
Uv)))
This proves the upper bound stated in the theorem, and we can verify that it is increasing, and satisfies (0)) T-2/e2 (()) =1
1-log 3
Lower 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 py, first introduced in Theorem 4.4, is the
unique solution of the equation (1 - (1-7))) 1_ y.
p. which is equivalent to L1 11-1 1) [og(1/p)
Let a, = - log(p.). It follows from the definition of p., that a, is the unique solution of the equation
(c" - 1 11) 7. For any n 2 2 and 2 0 we have that (1 - x z/n)" S e² hence, by definition
of an,y and a.y
1)
-1)
<
6 Bunn
Only
11
Un ym
On.y
7
1
-1 )
(1-1))
1
(25)
a
a
31

---

Moreover, the function I + (c" - 1)(1/x is decreasing on (0, 1). In fact its derivative at any point z (0,1) 1)
d
( - e e= -1 1) (= -1)
c² e
dr
x²
1
(1
x² (1 x){²
x22
1
x2 (1+ c²) <0.
It follows from (5 that a, On Finally, given that + I-c is non non-increasing (0, 1]. deduce that
anny
an,7
an,7
We deduce that the competitive ratio of the algorithm described in Theorem i.6 least 1-e
day
1-py [1/(1/P,]
1 (1 P-
D Random decay functions
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 steps with a probability Pj. this modeled by (x) = ε with E a Bernoulli random variable with parameter Pj- We explain in this section how the definitions and our results extend to this case.
Definition D.1 (Random process). Let X is non-empty set. A random process o X' is a collection of random variables (Zv)ee Two random processes Z { and Z' (ZZ}zex 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,) ] (Z IxEx" m are mutually independent for any Zm are mutually independent.
In E Ei I' E Xm, the random variables 7,)
Definition D.2 (Random decay functions). Let D (D1, D2....) be sequence of mutually independent random processes. We say that D is sequence of random decay functions if
1. Pr(D)(=) $ [0,z]) for any 2 and 1,
2. j N21 H (a) a) non-increasing for any x. 0,
3. x 0 Pr( 2 a) is non-decreasing for any j E N21 and a 2 0.
The second condition asserts that the random variable (x) has first-order stochastic dominance over (x). Along with the first condition, reflect that the distributions the rejected values become progressively smaller. The last condition indicates that for any integer j 2 1 and non-negative real numbers x < y, (y) has first-order stochastic dominance over Dr(r), which means that, as the value of increases, so does the potential recovered value after steps.
The decision-maker In the D-prophet inequality with deterministic decay functions, we assumed that the decisiinn-maees has full knowledge of the functions D1, D ..... In the randomized setting, we assume instead that the decision-make maker knows the distributions of the decay functions, i.e. knows the distribution of the random variables (z for all x 0 and > 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 each step, it observes a new item with value X,, and decides to stop or continue. Once they decide to stop at some time 7, they observe the values Di (X(,,)) ... (X,,) and then they choose the maximal one. As consequence, the stopping time is independent of the randomness induced by the decay functions. As in the deterministic case, the expected reward any algorithm ALG can be written as
BIALG (XI, Xx)] = max 0S
(X,
32

---

that 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 2 O that the random variables (a)( converge in distribution to some random variable Do (z). In fact, for any 2 0 and 2 O, the sequence (Pr(D, (2:) 2 a));21 is non-increasing and non-negative, thus it converges to some constant G(z,a) a). Given that + (z( 2 a) is non-decreasing for any j. we obtain by taking the limit - oo that I + G(z, a) is non-increasing. and with similar argument we obtain, for any x 2 O, that G(z, a) = for all a S and G(x, a) for all a > Therefore, + G(z,, a) defined the cumulative distribution of random variable Doo such that
x 1220- Pr(D (z) a) is non-decreasing for all 2 0,
. Pr((Doo( (x) [0, x|) for al 2 0.
Therefore, for all x 2 0, Doc (x) is the limit in distribution of (D) hence a sequence D' D2 of mutually independent random processes such that (z) Dz (2) for any j 2 and x 2 defines a sequence of decay functions. We say in this case that all the decay functions are identically distributed D Moreover, it holds for all Dx (x)] = limz-sx [xD = inl [x))
From there, all the proofs of Section P can be easily generalized to the case of random decay functions, and 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 (=) O. Similarly, using that the stopping time of the algorithm is independent of randomness induced by Doo, Proposition 3.3
remains true with y infz>0 [[]]
Lower bounds For establishing lower bounds, observe that, for any random decay functions D, we denote H, (x) DjD (x)] for all x, then H (H1 H2,..... defines a sequence of deterministic decay functions. Furthermore, for any instance XI.... Xn and any algorithm ALG, it holds that
E[ALG? (X1,.... X,)] = E
max
(D,(X--1))
05isT-1
E
E
max
(Di(X,-)) X Xul]
USiST-1
2
E
max
(E(D,(X,-)) X1, Xx,,...,,A.ll .xl..
OSsis-11
E
max
(H:(X+-))
Losisr-1
= E|ALG* (X,,.., X,)]]
follows that lower bounds established for deterministic decay functions can be extended random decay functions by considering their expectations.
With the previous observations, both the lower and upper bounds, depending on YD that we proved in the deterministic D-prophet inequality can be generalized to the random D-prophet inequality, by taking
Implications
BxD
YD inf inf #20j21
33

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the introduction, present the problem, and state the main contributions of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
The limitations are discussed in the conclusion.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
34

---

Justification:
All the assumptions are clearly stated, and full proofs are in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
35

---

Answer:
[NA]
Justification:
No experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ ccpppp.ccppulli//uuuiu wwwiii/gguie///eeeeeeeeic CoodeSubeiiieeee ssi wswonnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: No experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
36

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer:[NA)
Justification:
No experiments.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Question:
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics, and the paper conforms to it.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The contribution of the paper is theoretical. We do not feel there is major societal impact that needs to be discussed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
37

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is 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 being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there 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 monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
The contribution of the paper is mainly theoretical.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have 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 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 best faith effort.
12. Lieenses 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 any assets.
Guidelines:
The answer NA means that the paper does 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 URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.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, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of 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.
38

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not provide any assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No such experiments are included in the paper.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No such studies are included the paper.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
39


Reviews:
[{"review_id": "uWe0RGA2j8", "reviewer": "Reviewer_us2g", "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.\n\nThe 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\n1. establish an upper bound on the CR in the adversarial model, where a matching online algorithm is also proposed;\n2. 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\n3. design an algorithm in the iid case whose asymptotic CR is the same as that in the random order model.", "questions": "1. See Weakness 1\n2. '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": "Clearly stated", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1. The setup is new, and it looks to of importance.\n1. The paper is well-written so it is easy to get the intuitions behind the reductions.\n2. The result for adversarial case is optimal.", "weaknesses": "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)?\n2. For random order models and iid models, the algorithms designed are sub-optimal and cannot be implemented easily.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on our submission. Below we address the raised concerns and questions.\n### Weaknesses\n* **Other models.** We studied the models where the only decision made by the algorithm is the stopping time. The only model not included in our analysis is the \"order selection model\", where the decision-maker additionally decides in which order to observe the samples. To prove the reduction in that model, our intuition is that hard instances can be constructed using a trick similar to the one we used for the IID model, but then the optimal order in which the samples of these instances are observed should also be characterized. \n* **Optimality.** The algorithms we provide for the IID and random order models match the optimal single-threshold algorithms when $\\gamma = 0$. Better algorithms require using time-dependent thresholds, which are difficult to analyze even for $\\gamma = 0$. Multiple prior works on prophet inequalities have studied either the IID or the random order model (see the related work section), incrementally improving the lower and upper bounds. Moreover, finding an optimal algorithm in the prophet inequality with random order is still an open question. \n* **Implementation.** The algorithms we propose only require computing the solution $p$ of the equation $1-(1-\\gamma)p = \\frac{1-p}{-\\log p}$, which can be easily computed numerically with very high precision as explained in Line 307. The proposed threshold then depends on the distribution of the maximum reward, which is standard for prophet inequalities. Additionally, we give in Corollary 4.4.1 a simpler threshold that results in a slightly weaker competitive ratio.\n\n### Questions\n* **Separation between the IID and random order models.** For $\\gamma = 0$, the optimal single-threshold algorithm for both the iid and random order models has a competitive ratio of $1-1/e$. However, as mentioned in the related work section, using time-dependent thresholds enables a competitive ratio of $\\approx 0.745$ in the iid model, which is optimal. On the other hand, in the random order model, no algorithm has a competitive ratio better than  $\\sqrt{3}-1 \\approx 0.732$, which shows the separation between the best competitive ratios in both models.\n* **Generalizing the algorithms.** A key property satisfied by single-threshold algorithms is Equation $(4)$ in line 270, on which our analysis relies. For algorithms using time-dependent thresholds, this property is no longer true (see Line 272), and different analysis techniques must be used to generalize them. Studying such algorithms is difficult and very technical even for $\\gamma = 0$, and multiple separate works have focused either on the IID or the random order model to advance the analysis of such algorithms (see the related work section).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fWoiZj0svM", "reviewer": "Reviewer_Q5gj", "summary": "**Problem Studied**\n\nThis 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.\n\n**Main Results / Contributions**\n\nThe 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.", "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. \n\n2. 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.)\n\n3. 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$?\n\n4. There are several typos in the paper, notably in the title (\"Inequalitites\" -> \"Inequalities\").", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "The paper is generally well-written. The definitions and theorem statements are clear, and the proof sketches in the first 9 pages of the paper gives the reader a good intuition about why the statements are true. The paper introduces a new problem (lookback prophet inequalities), which to my knowledge has not be studied before. The problem definition is clean and I think it is a reasonably natural formulation.", "weaknesses": "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on our submission. Below we address the raised concerns and questions.\n\n### Weakness\nIndeed, many variants of the prophet inequality are used to model specific use cases. For example, 'Learning Online Algorithms with Distributional Advice' (ICML 2021) explores a situation where a decision-maker with access only to samples competes against an adversary with access to distributions, and 'Fairness and Bias in Online Selection' (ICML 2021) examines the case of items belonging to distinct, incomparable groups.\nOn the other hand, the model we study is a generalization of the prophet inequality, which removes the overly pessimistic assumption of irrevocable rejection decisions, and captures much more general and more realistic online selection problems, which is why believe it is a highly relevant model.\n\n### Questions\n* **Real estate example.** In the introduction, we use examples to illustrate that rejection decisions can often be reversed in practical scenarios. While we acknowledge the reviewer's point that the lookback prophet inequality does not perfectly model a real estate scenario, we believe it offers a more realistic representation than the standard prophet inequality, and constitutes an important step towards closing the gap between theory and practice in online selection problems.\n* **Restaurant example.** Imagine restaurants lined up along a street, with roughly equal distances between them. If there is a long distance between two consecutive restaurants, then it can be represented by empty restaurant spots, each with a zero reward. This can be modeled with decay functions of the form $D_j = cj$ with $c$ a constant. In a more general scenario, restaurants could be located anywhere on a map, which can be modeled as a decision-maker traversing a path in an arbitrary metric space. This problem is not captured by the lookback prophet inequality, and exploring it would be an interesting direction for future research.\n* **Competitive ratio for fixed $n$.** The competitive ratio is defined as the worst-case ratio over instances of all sizes, this is why considering arbitrarily large instances for proving upper bounds is not a limitation. Nonetheless, for the random order and IID models, we believe that better ratios are possible for a fixed $n$, as suggested for example in Lemma 4.5. Some prior works, such as \"Comparisons of stop rule and supremum expectations of iid random variables\", focused on characterizing the optimal ratios for fixed $n$ in the IID model. The authors use dynamic programming to give a recursive characterization of these ratios, but the computations are cumbersome and highly technical, and yet they fail to give closed-form expressions or precise estimations. Investigating this question in the Lookback Prophet inequality with arbitrary decay functions is surely a very interesting research direction, but also very challenging.\n* **Typos.** We thank the reviewer for their remark. We have reviewed the paper in detail and corrected all the typos.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WLPGRn19XQ", "reviewer": "Reviewer_g6ab", "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.", "questions": "1. What is the biggest technical challenge in the analysis?\n2. 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": "Yes.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper extends the standard prophet inequality to a more general and realistic form.\n2. This paper gives a general reduction that characterizes the property of decay functions.\n3. The competitive ratio for adversarial order is tight.", "weaknesses": "1. The analyses for random order and IID cases are not ideal. It seems neither upper nor lower bounds are tight for general $\\gamma$.\n2. I am not sure about the technical contribution of this paper. What is the biggest technical challenge in the analysis?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the time and effort spent on our submission. Below we address the raised concerns and questions.\n### Weaknesses\n* **Upper bounds.** The reduction from the $D_\\infty$- to the $\\gamma$-prophet inequality relies on using distributions with support {$0,a,b$}, which is a limitation. Proving better upper bounds would require improving the reduction itself. We are not sure if this is feasible with arbitrary decay functions\n* **Lower bounds.** The algorithms we provide for the IID and random order models match the optimal single-threshold algorithms for $\\gamma = 0$. Better algorithms require using time-dependent thresholds, which are technically difficult to analyze even for $\\gamma = 0$. Multiple prior works on prophet inequalities have studied either the IID or the random order model (see the related work section), incrementally improving the lower and upper bounds. Moreover, finding an optimal algorithm in the prophet inequality with random order is still an open question.\n\n### Questions\n* **Technical challenges.** The first big technical challenge lies in the reduction from the $\\mathcal{D}$- to the $D_\\infty$-prophet inequality, as we consider very general classes of decay functions with minimal assumptions. Moreover, the reduction relies on explicitly constructing hard instances for which the decay functions $\\mathcal{D}$ and $D_\\infty$ are equivalent, which requires very adequate concentration inequalities and rigorous tuning of the parameters in the construction. Moreover, a separate proof is given for each order model, as different arguments are required. The second big technical challenge lies in analyzing the algorithms for the $\\gamma$-prophet inequality. With single-threshold algorithms, as shown in Equation (4), there is an additional term of $E[\\gamma (\\max X_i) 1_{\\max X_i<\\theta}]$ compared to the case of $\\gamma=0$, which cannot be lower bounded by $c E[\\max X_i]$ for a universal constant $c$ independent of the distributions. Hence manipulating this term to improve upon the competitive ratio of the case $\\gamma = 0$ is challenging. Proving upper bounds is also more technical than the case $\\gamma = 0$.\n* **Statement of upper bounds in the $\\gamma$-prophet inequality.** We agree with the reviewer and thank them for the suggestion. There is a discussion on this point in Section 4.4. However, we will revise the statements of Theorems 4.3, 4.4, and 4.6 to place greater emphasis on this aspect.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: 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.
Decision: Accept (poster)