# Lookback Prophet Inequalities

Ziyad Benomar CREST, Ecole polytechnique, ENSAE, Fairplay joint team, Paris
Dorian Baudry Institut Polytechnique de Paris, ENSAE, Fairplay joint team,
Paris Vianney Perchet
CREST, ENSAE, Criteo AI LAB
Fairplay joint team, Paris

###### 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, rejected 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$.

##  1 Introduction

Optimal stopping problems constitute a classical paradigm of decision-making
under uncertainty (Dynkin, 1963) Typically, in online algorithms, these
problems are formalized as variations of the secretary problem (Lindley, 1961)
or the prophet inequality (Krengel and Sucheston, 1977). In the context of the
prophet inequality, the decision-maker observes a finite sequence of items,
each having a value drawn independently from a known probability distribution.
Upon encountering a new item, the decision-maker faces the choice of either
accepting it and concluding the selection process or irreversibly rejecting
it, with the objective of maximizing the value of the selected item. However,
while the prophet inequality problem is already used in scenarios such as
posted-price mechanism design (Hajiaghayi et al., 2007) or online auctions
(Syrgkanis, 2017), it might present a pessimistic model of real-world online
selection problems. Indeed, it is in general possible in practice to revisit
previously rejected items and potentially recover them or at least recover a
fraction of their value.

Consider for instance an individual navigating a city in search of a
restaurant. When encountering one, they have the choice to stop and dine at
this place, continue their search, or revisit a previously passed option,
incurring a utility cost that is proportional to the distance of backtracking.
In another example drawn from the real estate market, homeowners receive
offers from potential buyers. The decision to accept or reject an offer can be
revisited later, although buyer interest may have changed, resulting in a
potentially lower offer or even a lack of interest. Lastly, in the financial
domain, an agent may choose to sell an asset at its current price or opt for a
lookback put option, allowing them to sell at the asset’s highest price over a
specified future period. To make a meaningful comparison between the two, one
must account for factors such as discounting (time value of money) and the
cost of the option.

###  1.1 Formal problem and notation

To encompass diverse scenarios, we propose a general way to quantify the cost
incurred by the decision-maker for retrieving a previously rejected value.

######  Definition 1.1 (Decay functions).

Let $\mathcal{D}=(D_{1},D_{2},\ldots)$ be a sequence of non-negative functions
defined on $[0,\infty)$. It is a sequence of decay functions if

  1. (i)

$D_{1}(x)\leq x$ for all $x\geq 0$,

  2. (ii)

the sequence $(D_{j}(x))_{j\geq 1}$ is non-increasing for all $x\geq 0$,

  3. (iii)

the function $D_{j}$ is non-decreasing for all $j\geq 1$.

In the context of decay functions $\mathcal{D}$, if a value $x$ is rejected,
the algorithm can recover ${D}_{j}(x)$ after $j$ subsequent steps. The three
conditions defining decay functions serve as fundamental prerequisites for the
problem. The first and second conditions ensure that the recoverable value of
a rejected item can only diminish over time, while the final condition implies
that an increase in the observed value $x$ corresponds to an increase in the
potential recovered value. Although the non-negativity of the decay functions
is non-essential, we retain it for convenience, as we can easily revert to
this assumption by considering that the algorithm has a reward of zero by not
selecting any item.

The motivating examples that we introduced can be modeled respectively with
decay functions of the form $D_{j}(x)=x-c_{j}$ where $(c_{j})_{j\geq 1}$ is a
non-decreasing positive sequence, $D_{j}(x)=\xi_{j}x$ with
$\xi_{j}\sim\mathcal{B}(p_{j})$ and $(p_{j})_{j\geq 1}$ a non-increasing
sequence of probabilities, and $D_{j}(x)=\lambda^{j}x$ with $\lambda\in[0,1]$.
In one of these examples (housing market), the natural model is to use _random
decay functions_ : the buyer makes the same offer if they are still
interested, and offers $0$ otherwise. Definition 1.1 can be easily extended to
consider this case. However, to enhance the clarity of the presentation, we
only discuss the deterministic case in the rest of the paper. In Appendix D,
we explain how all the proofs and theorems can be generalized to that case.

##### The $\mathcal{D}$-prophet inequality

For any decay functions $\mathcal{D}$, we define the $\mathcal{D}$-prophet
inequality problem, where the decision maker, knowing $\mathcal{D}$, observes
sequentially the values $X_{1},\ldots,X_{n}$, with $X_{i}$ drawn from a known
distribution $F_{i}$ for all $i\in[n]$. If they decide to stop at some step
$\tau$, then instead of gaining $X_{\tau}$ as in the classical prophet
inequality, they can choose to select the current item $X_{\tau}$ and have its
full value, or select any item $X_{i}$ with $i<\tau$ among the rejected ones
but only recover a fraction $D_{\tau-i}(X_{i})\leq X_{i}$ of its value.
Therefore, if an algorithm ALG stops at step $\tau$ its reward is

$\displaystyle\textsf{ALG}^{\mathcal{D}}(X_{1},\ldots,X_{n})$
$\displaystyle=\max\\{X_{\tau},D_{1}(X_{\tau-1}),D_{2}(X_{\tau-2}),\ldots,D_{\tau-1}(X_{1})\\}$
$\displaystyle=\max_{0\leq i\leq\tau-1}\\{D_{i}(X_{\tau-i})\\}\;,$

with the convention $D_{0}(x)=x$. If the algorithm does not stop at any step
before $n$, then its reward is
$\textsf{ALG}^{\mathcal{D}}(X_{1},\ldots,X_{n})=\max_{1\leq i\leq
n}\\{D_{i}(X_{\pi(n-i+1)})\\}$, which corresponds to $\tau=n+1$.

######  Remark 1.1.

As in the standard prophet inequality, an algorithm is defined by its stopping
time, i.e., the rule set to decide whether to stop or not. Hence, if
$\mathcal{D}$ and $\mathcal{D}^{\prime}$ are two different sequences of decay
functions, any algorithm for the $\mathcal{D}$-prophet inequality, although
its stopping time might depend on the particular sequence of functions
$\mathcal{D}$, is also an algorithm for the $\mathcal{D}^{\prime}$-prophet
inequality. Consider for example an algorithm ALG with stopping time
$\tau(\mathcal{D})$ that depends on $\mathcal{D}$. Its reward in the
$\mathcal{D}^{\prime}$-prophet inequality is
$\textsf{ALG}^{\mathcal{D}^{\prime}}(X_{1},\ldots,X_{n})=\max_{0\leq
i\leq\tau-1}\\{D^{\prime}_{i}(X_{\tau(\mathcal{D})-i})\\}$.

##### Observation order

Several variants of the prophet inequality problem have been studied,
depending on the order of observations. The standard model is the adversarial
(or fixed) order: The instance of the distributions $F_{1},\dots,F_{n}$ is
chosen by an adversary, and the algorithm observes the samples $X_{1}\sim
F_{1},\ldots,X_{n}\sim F_{n}$ in this order (Krengel and Sucheston, 1977,
1978). In the random order model, the adversary can again choose the
distributions, but the algorithm observes the samples in a uniformly random
order. Another setting in which the observation order is no longer important
is the IID model (Hill and Kertz, 1982; Correa et al., 2021b), where all the
values are sampled independently from the same distribution $F$. The
$\mathcal{D}$-prophet inequality is well-defined in each of these different
order models: if the items are observed in the order
$X_{\pi(1)},\ldots,X_{\pi(n)}$ with $\pi$ a permutation of $[n]$, then the
reward of the algorithm is
$\textsf{ALG}^{\mathcal{D}}(X_{1},\ldots,X_{n})=\max_{0\leq
i\leq\tau-1}\\{D_{i}(X_{\pi(\tau-i)})\\}$. In this paper, we study the
$\mathcal{D}$-prophet inequality in the three models we presented, providing
lower and upper bounds in each of them.

##### Competitive ratio

In the $\mathcal{D}$-prophet inequality, an input instance $I$ is a finite
sequence of probability distributions $(F_{1},\ldots,F_{n})$. Thus, for any
instance $I$, we denote by $\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I)]$ the
expected reward of ALG given $I$ as input, and we denote by
$\mathbb{E}[\textsf{OPT}(I)]$ the expected maximum of independent random
variables $(X_{i})_{i\in[n]}$, where $X_{i}\sim F_{i}$. With these notations,
we define the competitive ratio, which will be used to measure the quality of
the algorithms.

######  Definition 1.2 (Competitive ratio).

Let $\mathcal{D}$ be a sequence of decay functions and ALG an algorithm. We
define the competitive ratio of ALG by

$\textsf{CR}^{\mathcal{D}}(\textsf{ALG})=\inf_{I}\frac{\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}\;,$

with the infimum taken over the tuples of all sizes of non-negative
distributions with finite expectation.

An algorithm is said to be $\alpha$-competitive if its competitive ratio is at
least $\alpha$, which means that for any possible instance $I$, the algorithm
guarantees a reward of at least $\alpha\mathbb{E}[\textsf{OPT}(I)]$. The
notion of competitive ratio is used more broadly in competitive analysis as a
metric to evaluate online algorithms (Borodin and El-Yaniv, 2005), as it lower
bounds their performance even in worst-case scenarios, when the input instance
is chosen adversarially.

###  1.2 Contributions

It is trivial that non-zero decay functions $\mathcal{D}$ guarantee a better
reward compared to the classical prophet inequality. However, in general, this
is not sufficient to conclude that the standard upper bounds or the
competitive ratio of a given algorithm can be improved. Hence, a first key
question is: what condition on $\mathcal{D}$ is necessary to surpass the
conventional upper bounds of the classical prophet inequality? Surprisingly,
the answer hinges solely on the constant $\gamma_{\mathcal{D}}$, defined as
follows,

$\gamma_{\mathcal{D}}=\inf_{x>0}\inf_{j\geq
1}\left\\{\frac{D_{j}(x)}{x}\right\\}\;.$ (1)

In the adversarial order model, we demonstrate that the optimal competitive
ratio achievable in the $\mathcal{D}$-prophet inequality is determined by the
parameter $\gamma_{\mathcal{D}}$ alone. Additionally, in both the random order
and IID models, we demonstrate the essential requirement of
$\gamma_{\mathcal{D}}>0$ for breaking the upper bounds of the classical
prophet inequality. In particular, this implies that no improvement can be
made with decay functions of the form $D_{j}(x)=x-c_{j}$ with $c_{j}>0$, or
$D_{j}(x)=\lambda^{j}x$ with $\lambda\in[0,1)$. Subsequently, we develop
algorithms and provide upper bounds in the $\mathcal{D}$-prophet inequality,
uniquely dependent on the parameter $\gamma_{\mathcal{D}}$. We illustrate them
in Figure 1, comparing them with the identity function $\gamma\mapsto\gamma$,
which is a trivial lower bound.

Figure 1: Lower and upper bounds on the competitive ratio in the
$\mathcal{D}$-prophet inequality depending on $\gamma_{\mathcal{D}}$, in the
adversarial order (Thm 4.3), random order (Thm 4.4) and IID (Thm 4.6) models

###  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 a more comprehensive and historical overview, we refer
the interested reader to surveys on the problem such as (Lucier, 2017; Correa
et al., 2019). Prophet inequalities have immediate applications in mechanism
design (Hajiaghayi et al., 2007; Deng et al., 2022; Psomas et al., 2022; Makur
et al., 2024), auctions (Syrgkanis, 2017; Dütting et al., 2020), resource
management (Sinclair et al., 2023), and online matching (Cohen et al., 2019;
Ezra et al., 2020; Jiang et al., 2021; Papadimitriou et al., 2021; Brubach et
al., 2021). Many variants and related problems have been studied, including,
for example, the matroid prophet inequality (Kleinberg and Weinberg, 2012;
Feldman et al., 2016), prophet inequality with advice (Diakonikolas et al.,
2021), and variants with fairness considerations (Correa et al., 2021a;
Arsenis and Kleinberg, 2022).

##### Random order and IID models

Esfandiari et al. (2017) introduced the prophet secretary problem, where items
are observed in a uniformly random order, and they proved a
$(1-\frac{1}{e})$-competitive algorithm. Correa et al. (2021c) showed later a
competitive ratio of $0.669$, which currently stands as the best-known
solution for the problem. They also proved an upper bound of
$\sqrt{3}-1\approx 0.732$, which was improved to $0.7254$ in (Bubna and
Chiplunkar, 2023). Addressing the gap between the lower and upper bound
remains an engaging and actively pursued open question. On the other hand, the
study of prophet inequalities with IID random variables dates back to papers
such as (Hill and Kertz, 1982; Kertz, 1986), demonstrating guarantees on the
dynamic programming algorithm. The problem was completely solved in (Correa et
al., 2021b), where the authors show that the competitive ratio of the dynamic
programming algorithm is $0.745$, thus it constitutes an upper bound on the
competitive ratio of any algorithm, and they give a simpler adaptive threshold
algorithm matching it. Another setting that we do not study in this paper, is
the order selection model, where the decision-maker can choose the order in
which the items are observed, knowing their distributions (Chawla et al.,
2010; Beyhaghi et al., 2021; Peng and Tang, 2022).

##### Beyond the worst-case

In recent years, there has been increasing interest in exploring ways to
exceed the worst-case upper bounds of online algorithms by providing the
decision-maker with additional capabilities. A notable research avenue is
learning-augmented algorithms (Lykouris and Vassilvtiskii, 2018), which equip
the decision-maker with predictions about unknown variables of the problem.
Multiple problems have been studied in this framework, such as scheduling
(Purohit et al., 2018; Lassota et al., 2023; Merlis et al., 2023; Benomar and
Perchet, 2024b), matching (Antoniadis et al., 2020; Dinitz et al., 2021; Chen
et al., 2022), caching (Antoniadis et al., 2023; Chlkedowski et al., 2021;
Christianson et al., 2023), and in particular, online selection problems
(Dütting et al., 2021; Sun et al., 2021; Benomar and Perchet, 2024a;
Diakonikolas et al., 2021). More related to our setting, the ability to
revisit items in online selection has been studied in problems such as the
multiple-choice prophet inequality, where the algorithm can select up to $k$
items and its reward is the maximum selected value (Assaf and Samuel-Cahn,
2000). This allows for revisiting up to $k$ items, chosen during the
execution, for final acceptance or rejection decisions. Similarly, in
Pandora’s box problem (Weitzman, 1978; Kleinberg et al., 2016) and its
variants (Esfandiari et al., 2019; Gergatsouli and Tzamos, 2022; Atsidakou et
al., 2024; Gergatsouli and Tzamos, 2024; Berger et al., 2024), the decision
maker decides the observation order of the items, but a cost $c_{i}$ is paid
for observing each value $X_{i}$, with the gain being the maximum observed
value minus the total opening costs. A very recent work investigates a
scenario closely related to the lookback prophet inequality (Ekbatani et al.,
2024) where, upon selecting a candidate $X_{i}$, the decision-maker has the
option to discard it and choose a new value $X_{j}$ at any later step $j$, at
a buyback cost of $f\times X_{i}$, where $f>0$. The authors present an optimal
algorithm for the case when $f\geq 1$, although the problem remains open for
$f\in(0,1)$.

##  2 From $\mathcal{D}$-prophet to the $D_{\infty}$-prophet inequality

Let us consider a sequence $\mathcal{D}$ of decay functions. By Definition
1.1, for any $x\in[0,\infty]$ the sequence $(D_{j}(x))_{j\geq 1}$ converges,
since it is non-increasing and non-negative. Hence, there exists a mapping
$D_{\infty}$ such that for any $x\geq 0$,
$\lim_{j\to\infty}D_{j}(x)=D_{\infty}(x)$. Furthermore, we can easily verify
that $D_{\infty}$ is non-decreasing and satisfies $D_{\infty}(x)\in[0,x]$ for
all $x\geq 0$.

Thanks to these properties, we obtain that $(D_{\infty})_{j\geq 1}$ also
satisfies Definition 1.1, and is hence a valid sequence of decay functions. We
thus refer to the corresponding problem as the $D_{\infty}$-prophet
inequality. Since $D_{j}\geq D_{\infty}$ for any $j\geq 1$, it is
straightforward that the stopping problem with the decay functions
$D_{\infty}$ would be less favorable to the decision-maker. More precisely,
for any random variables $X_{1},\ldots,X_{n}$, observation order $\pi$, and
algorithm ALG with stopping time $\tau$, it holds that

$\textsf{ALG}^{\mathcal{D}}(X_{1},\ldots,X_{n})\coloneqq\max\\{X_{\pi(\tau)},\max_{i<\tau}D_{\tau-i}(X_{\pi(i)})\\}\geq\max\\{X_{\pi(\tau)},\max_{i<\tau}D_{\infty}(X_{\pi(i)})\\}\;,$

which corresponds to the output of ALG (with the same decision rule) when all
the decay functions are equal to $D_{\infty}$. Therefore, any guarantees
established for algorithms in the $D_{\infty}$-prophet inequality naturally
extend to the $\mathcal{D}$-prophet inequality. However, it remains uncertain
whether the $\mathcal{D}$-prophet inequality can yield improved competitive
ratios compared to the $D_{\infty}$-prophet inequality. In the following, we
prove that this is not the case, for all the order models presented in Section
1.

######  Theorem 2.1.

Let $D_{\infty}$ be the pointwise limit of the sequence of decay functions
$\mathcal{D}=(D_{j})_{j\geq 1}$. Then for any instance
$I=(F_{1},\ldots,F_{n})$ of non-negative distributions, in the adversarial
order and the random order models it holds that

$\forall\textsf{ALG}:\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\leq\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}\;,$
(2)

where the supremum is taken over all the online algorithms A. In the IID
model, the same inequality holds with an additional $O(n^{-1/3})$ term, which
depends only on the size $n$ of the instance.

The main implication of Theorem 2.1 is the following corollary.

######  Corollary 2.1.1.

In the adversarial order and the random order models, if $\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern 1.5mu_{\infty}$ is an
optimal algorithm for the $D_{\infty}$-prophet inequality, i.e. with maximal
competitive ratio, then $\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern 1.5mu_{\infty}$ is
also optimal for the $\mathcal{D}$-prophet inequality. Moreover, it holds that

$\textsf{CR}^{\mathcal{D}}(\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern
1.5mu_{\infty})=\textsf{CR}^{D_{\infty}}(\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern 1.5mu_{\infty})\;.$

A direct consequence of this result is that, in the adversarial and the random
order models, the asymptotic decay $D_{\infty}$ entirely determines the
competitive ratio that is achievable and the upper bounds for the
$\mathcal{D}$-prophet inequality. Therefore, we can restrict our analysis to
algorithms designed for the problem with identical decay function. In the IID
model, the same conclusion holds if the worst-case instances are arbitrarily
large, making the additional $O(n^{-1/3})$ term vanish. This is the case in
particular in the classical IID prophet inequality (Hill and Kertz, 1982).

###  2.1 Sketch of the proof of Theorem 2.1

While we use different techniques for each order model considered, all the
proofs share the same underlying idea. Given any instance $I$ of non-negative
distributions, we build an alternative instance $J$ such that the reward of
any algorithm on $I$ with decay functions $\mathcal{D}=(D_{j})_{j}$ it at most
its reward on $J$ with decay functions all equal to $D_{\infty}$. To do this,
we essentially introduce an arbitrarily large number of zero values between
two successive observations drawn from distributions belonging to $I$. Hence,
under $J$ the algorithm cannot recover much more than a fraction
$D_{\infty}(X)$ for any past observation $X$ collected from $F\in I$.

In the adversarial case, implementing this idea is straightforward, since
nature can build $J$ by directly inserting $m$ zeros between each pair of
consecutive values, and the result is obtained by making $m$ arbitrarily
large. For the random order model, we use the same instance $J$, but extra
steps are needed to prove that the number of steps between two non-zero values
is very large with high probability.

Moving to the IID model, an instance $I$ is defined by a pair $(F,n)$, where
$F$ is a non-negative distribution, and $n$ is the size of the instance. In
this scenario, we consider an instance consisting of $m>n$ IID random
variables $(Y_{i})_{i\in[m]}$, each sampled from $F$ with probability $n/m$,
and equal to zero with the remaining probability. We again achieve the desired
result by letting $m$ be arbitrarily large compared to $n$. However, the
number of variables sampled from $F$ is not fixed; it follows a Binomial
distribution with parameters $(m,n/m)$. We control this variability by using
concentration inequalities, which causes the additional term $O(n^{-1/3})$.

##  3 From $D_{\infty}$-prophet to the $\gamma_{\mathcal{D}}$-prophet
inequality

As discussed in Section 2, Theorem 2.1 implies that, for either establishing
upper bounds or guarantees on the competitive ratios of algorithms, it is
sufficient to study the $D_{\infty}$-prophet inequality, where all the decay
functions are equal to $D_{\infty}$. The remaining question is then to
determine which functions $D_{\infty}$ 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_{\infty}$-prophet
inequality.

In the $D_{\infty}$-prophet inequality, it is always possible to have a reward
of $D_{\infty}(\max_{i\in[n]}X_{i})$ by rejecting all the items and then
selecting the maximum by the end. Thus, there is no advantage in stopping at
step $i$ where $X_{i}\leq D_{\infty}(\max_{j<i}X_{j})$. An algorithm
respecting this decision rule is called rational.

######  Lemma 3.1.

For any rational algorithm ALG in the $D_{\infty}$-prophet inequality, if we
denote $\tau$ its stopping time, then for any instance
$I=(F_{1},\ldots,F_{n})$ and $X_{i}\sim F_{i}$ for all $i\in[n]$ we have

$\textsf{ALG}^{D_{\infty}}(X_{1},\ldots,X_{n})=\textsf{ALG}^{0}(X_{1},\ldots,X_{n})+D_{\infty}\big{(}\max_{i\in[n]}X_{i}\big{)}\mathbbm{1}_{\tau=n+1}\;.$

Moreover, the optimal dynamic programming algorithm in the
$D_{\infty}$-prophet inequality is rational.

The best competitive ratio in the $D_{\infty}$-prophet inequality is achieved,
possibly among others, by the optimal dynamic programming algorithm, which is
a rational algorithm by the previous Lemma. Hence, by the previous Lemma, it
suffices to prove it on rational algorithms. We use this observation to prove
the next propositions.

######  Proposition 3.2.

In the $D_{\infty}$-prophet inequality, if
$\inf_{x>0}\frac{D_{\infty}(x)}{x}=0$, then it holds, in any order model, that

$\forall\textsf{ALG}:\textsf{CR}^{D_{\infty}}(\textsf{ALG})\leq\sup_{\textsf{A}}\textsf{CR}^{0}(\textsf{A})\;,$
(3)

where the supremum is taken over all the online algorithms A.

Proposition 3.2 implies that if $\inf_{x>0}\frac{D_{\infty}(x)}{x}=0$, then,
in any order model, any upper bound on the competitive ratios of all
algorithms in the classical prophet inequality is also an upper bound on the
competitive ratios of all algorithm in the $D_{\infty}$-prophet inequality.
Consequently, for surpassing the upper bounds of the classical prophet
inequality, it is necessary to have, for some $\gamma>0$, that
$D_{\infty}(x)\geq\gamma x$ for all $x\geq 0$. Furthermore, the next
Proposition allows giving upper bounds in the $D_{\infty}$-prophet inequality
that depend only on $\inf_{x>0}\frac{D_{\infty}(x)}{x}$.

######  Proposition 3.3.

Let $\gamma=\inf_{x>0}D_{\infty}(x)/x$, and $0<a<b$. Consider an instance $I$
of distributions with support in $\\{0,a,b\\}$, then in any order model and
for any algorithm ALG we have that

$\textsf{CR}^{D_{\infty}}(\textsf{ALG})\leq\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{\gamma}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}\;,$

where $\mathbb{E}[\textsf{A}^{\gamma}(I)]$ is to the reward of A if all the
decay functions were equal to $x\mapsto\gamma x$.

The core idea for proving this proposition is that rescaling an instance, i.e.
considering $(rX_{i})_{i\in[n]}$ instead of $(X_{i})_{i\in[n]}$, has no impact
in the classical prophet inequality. However, in the $D_{\infty}$-prophet
inequality, rescaling can be exploited to adjust the ratio
$\frac{D_{\infty}(rx)}{rx}$. By considering instances with random variables
taking values in $\\{0,a,b\\}$ almost surely, where $a<b$, a reasonable
algorithm facing such an instance would never reject the value $b$.
Consequently, the value it recovers from rejected items is either
$D_{\infty}(0)=0$ or $D_{\infty}(a)$. Rescaling this instance by a factor
$r=s/a$ and taking the ratio to the expected maximum, the ratio
$\frac{D_{\infty}(s)}{s}$ appears, with $s$ a free parameter that can be
chosen to satisfy
$\frac{D_{\infty}(s)}{s}\to\inf_{x>0}\frac{D_{\infty}(x)}{x}=\gamma_{\mathcal{D}}$.

As a consequence, if $\inf_{x>0}\frac{D_{\infty}(x)}{x}=\gamma$, then any
upper bound obtained in the $\gamma$-prophet inequality (when the decay
functions are all equal to $x\mapsto\gamma x$) using instances of random
variables $(X_{1},\ldots,X_{n})$ satisfying $X_{i}\in\\{0,a,b\\}$ a.s. for all
$i$, is also an upper bound in the $D_{\infty}$-prophet inequality.

##### Implication

Let us consider any sequence $\mathcal{D}$ of decay functions, and define

$\gamma_{\mathcal{D}}:=\inf_{x>0}\left\\{\frac{D_{\infty}(x)}{x}\right\\}=\inf_{x>0}\inf_{j\geq
1}\left\\{\frac{D_{j}(x)}{x}\right\\}\;.$

For any $x>0$ and $j\geq 1$ it holds that $D_{j}(x)\geq\gamma_{\mathcal{D}}x$,
therefore, any guarantees on the competitive ratio of an algorithm in the
$\gamma_{\mathcal{D}}$-prophet inequality are valid in the
$\mathcal{D}$-prophet inequality, under any order model. Furthermore,
combining Theorem 2.1 and Proposition 3.3, we obtain that for any instance $I$
of random variables taking values in a set $\\{0,a,b\\}$ it holds that

$\forall\textsf{ALG}:\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\leq\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{\gamma_{\mathcal{D}}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}\;,$

with an additional term of order $O(n^{-1/3})$ in the IID model. In the
particular case where $\gamma_{\mathcal{D}}=0$, Proposition 3.3 with Theorem
2.1 give a stronger result, showing that no algorithm can surpass the upper
bounds of the classical prophet inequality. This is true also for the IID
model since the instances used to prove the tight upper bound of $\approx
0.745$ are of arbitrarily large size (Hill and Kertz, 1982).

Therefore, by studying the $\gamma$-prophet inequality for $\gamma\in[0,1]$,
we can prove upper bounds and lower bounds on the $\mathcal{D}$-prophet
inequality for any sequence $\mathcal{D}$ of decay functions.

##  4 The $\gamma$-prophet inequality

We study in this section the $\gamma$-prophet inequality, where all the decay
functions are equal to $x\mapsto\gamma x$, for some $\gamma\in[0,1]$. For any
algorithm ALG with stopping time $\tau$ and random variables
$X_{1},\ldots,X_{n}$, if the observation order is $\pi$, we use the notation

$\textsf{ALG}^{\gamma}(X_{1},\ldots,X_{n})=\max\\{X_{\pi(\tau)},\gamma
X_{\pi(\tau-1)},\ldots,\gamma X_{\pi(1)}\\}\;.$

and we denote by $\textsf{CR}^{\gamma}(\textsf{ALG})$ the competitive ratio of
ALG in this setting. In the following, we provide theoretical guarantees for
the $\gamma$-prophet inequality. For each observation order, we first derive
upper bounds on the competitive ratio of any algorithm, depending on $\gamma$,
using only hard instances satisfying the condition in Proposition 3.3. This
would guarantee that the upper bounds extend to the $\mathcal{D}$-prophet
inequality if $\gamma_{\mathcal{D}}=\gamma$. We also design single-threshold
algorithms with well-chosen thresholds depending on $\gamma$ and the
distributions, with competitive ratios improving with $\gamma$. A crucial
property of single-threshold algorithms, which we use to estimate their
competitive ratios, is that their reward satisfies

$\textsf{ALG}^{\gamma}(X_{1},\ldots,X_{n})=\textsf{ALG}^{0}(X_{1},\ldots,X_{n})+(\max_{i}X_{i})\mathbbm{1}_{(\max_{i}X_{i}<\theta)}\;.$
(4)

The additional term appearing due to $\gamma$ depends only on
$\max_{i\in[n]}X_{i}$, which is the reward of the prophet against whom we
compete. This property is not satisfied by more general class of algorithms
such as multiple-threshold algorithms, where each observation $X_{\pi(i)}$ is
compared with a threshold $\theta_{i}$.

######  Remark 4.1.

We only consider instances with continuous distributions in the proofs of
lower bounds. The thresholds $\theta$ considered are such that
$\Pr(\max_{i\in[n]}X_{i}\geq\theta)=g(\gamma,n,\pi)$, with $g$ depending on
$\gamma$, the order model $\pi$ and the size of the instance $n$. Such a
threshold is always guaranteed to exist when the distributions are continuous.
However, as in the prophet inequality, the algorithms can be easily adapted to
non-continuous distributions by allowing stochastic tie-breaking. A detailed
strategy for doing this can be found for example in (Correa et al., 2021c).

Before delving into the study of the different models, we provide generic
lower and upper bounds, which depend solely on the bounds of the classical
prophet inequality and $\gamma$.

######  Proposition 4.2.

In any order model, if $\alpha$ is a lower bound in the classical prophet
inequality, and $\beta$ an upper bound, then, in the $\gamma$-prophet
inequality

  1. (i)

there exists a trivial algorithm with a competitive ratio of at least
$\max\\{\gamma,\alpha\\}$,

  2. (ii)

the competitive ratio of any algorithm is at most $(1-\gamma)\beta+\gamma$.

###  4.1 Adversarial order

We first consider the adversarial order model, and prove the upper bound of
$\frac{1}{2-\gamma}$. Then, we provide a single-threshold algorithm with a
competitive ratio matching this upper bound, hence fully solving the
$\gamma$-prophet inequality in this adversarial order model.

######  Theorem 4.3.

In the adversarial order model, the competitive ratio of any algorithm for the
$\gamma$-prophet inequality is at most $\frac{1}{2-\gamma}$. Furthermore,
there exists a single threshold algorithm with a competitive ratio of at least
$\frac{1}{2-\gamma}$: given any instance $(F_{1},\dots,F_{n})$, this result is
achieved with the threshold $\theta$ satisfying $\Pr_{X_{1}\sim
F_{1},\dots,X_{n}\sim
F_{n}}(\max_{i\in[n]}X_{i}\leq\theta)=\frac{1}{2-\gamma}$.

###  4.2 Random order

Consider now that the items are observed in a uniformly random order
$X_{\pi(1)},\ldots,X_{\pi(n)}$, and $X^{*}=\max_{i\in[n]}X_{i}$. As for the
adversarial model, we first prove an upper bound on the competitive ratio as a
function of $\gamma$, and then prove a lower bound for a single-threshold
algorithm. However, for this model, there is a gap between the two bounds, as
illustrated in Figure 1.

We first prove an upper bound that depends on $\gamma$, matching the upper
bound $\sqrt{3}-1$ of Correa et al. (2021c) when $\gamma=0$ and equal to $1$
when $\gamma=1$. Our single-threshold algorithm has a competitive ratio of at
least $(1-\frac{1}{e})$ when $\gamma=0$, which is the best competitive ratio
of a single threshold algorithm in the prophet inequality (Esfandiari et al.,
2017; Correa et al., 2021c), and equal to $1$ for $\gamma=1$.

######  Theorem 4.4.

The competitive ratio of any algorithm ALG in the $\gamma$-prophet inequality
with random order satisfies

$\textsf{CR}^{\gamma}(\textsf{ALG})\leq(1-\gamma)^{3/2}(\sqrt{3-\gamma}-\sqrt{1-\gamma})+\gamma\;.$

Furthermore, denoting by $p_{\gamma}$ is the unique solution to the equation
$1-(1-\gamma)p=\frac{1-p}{-\log p}$, the single-threshold algorithm
$\textsf{ALG}_{\theta}$ with $\Pr_{X_{1}\sim F_{1},\dots,X_{n}\sim
F_{n}}(\max_{i\in[n]}X_{i}\leq\theta)=p_{\gamma}$ satisfies

$\textsf{CR}^{\gamma}(\textsf{ALG})\geq 1-(1-\gamma)p_{\gamma}\;.$

While the equation defining $p_{\gamma}$ cannot be solved analytically, the
solution can easily be computed numerically for any $\gamma\in[0,1]$. Before
moving to the IID case, we propose in the following a more explicit lower
bound derived from Theorem 4.4.

######  Corollary 4.4.1.

In the random order model, the single threshold algorithm with a threshold
$\theta$ satisfying
$\Pr(\max_{i\in[n]}\geq\theta)=\frac{1/e}{1-(1-1/e)\gamma}$ has a competitive
ratio of at least $1-\frac{(1-\gamma)/e}{1-(1-1/e)\gamma}$.

###  4.3 IID Random Variables

In the classical IID prophet inequality, Hill and Kertz (1982) showed that the
competitive ratio of any algorithm is at most $\approx 0.745$. The proof of
this upper bound is hard to generalize for the IID $\gamma$-prophet
inequality. As an alternative, we prove a weaker upper bound, which equals
$\approx 0.778$ for $\gamma=0$ and $1$ for $\gamma=1$, and the prove relies on
instances of arbitrarily large size satisfying the condition of Proposition
3.3, hence the lower bound can be extended to the $\mathcal{D}$-prophet
inequality.

Subsequently, we present a single-threshold algorithm with the same
competitive ratio as the random order algorithm. However, the proof is
different, leveraging the fact that the variables are identically distributed.
More precisely, we introduce a single-threshold algorithm with guarantees that
depend on the size $n$ of the instance, then we show that its competitive
ratio is at least that of the algorithm presented in Theorem 4.4, with
equality when $n$ approaches infinity.

Although it might look surprising that the obtained competitive ratio in the
IID model is not better than that of the random-order model, the same behavior
occurs in the classical prophet inequality. Indeed, Li et al. (2022)
established that no single-threshold algorithm can achieve a competitive ratio
better than $1-1/e$ in the standard prophet inequality with IID random
variables, which is also the best possible with a single-threshold algorithm
in the random order. However, considering larger classes of algorithms, the
competitive ratios achieved in the IID model are better than those of the
random order model.

We describe the algorithm and give a first lower bound on its reward depending
on the size of the instance in the following lemma.

######  Lemma 4.5.

Let $a_{n,\gamma}$ be the unique solution of the equation
$\left(\frac{1}{(1-a/n)^{n}}-1\right)\left(\frac{1}{a}-1\right)=\gamma$, then
for any IID instance $X_{1},\ldots,X_{n}$, the algorithm with threshold
$\theta$ satisfying $\Pr(X_{1}>\theta)=\frac{a_{n,\gamma}}{n}$ has a reward of
at least

$\frac{1}{a_{n,\gamma}}\left(1-\Big{(}1-\frac{a_{n,\gamma}}{n}\Big{)}^{n}\right)\mathbb{E}[\max_{i\in[n]}X_{i}]\;.$

We can prove that the reward presented in the Lemma above is strictly better
than that of the reward in the case of the random order model. However, both
are asymptotically equal as we show in the following theorem, thus yielding
the same theorem.

######  Theorem 4.6.

The competitive ratio of any algorithm in the IID $\gamma$-prophet inequality
is at most

$U(\gamma)=1-(1-\gamma)\frac{e^{2}\log(3-\gamma)-(2-\gamma)}{2(2e^{2}-1)-(3e^{2}-1)\gamma}\;.$

In particular, $U$ is increasing, $U(0)=\frac{4-\log
3}{2(2-\frac{1}{e}^{2})}\approx 0.778$ and $U(1)=1$. Furthermore, there exists
a single-threshold algorithm $\textsf{ALG}_{\theta}$ satisfying

$\textsf{CR}^{\gamma}(\textsf{ALG}_{\theta})\geq 1-(1-\gamma)p_{\gamma}\;,$

where $p_{\gamma}$ is defined in Theorem 4.4.

###  4.4 Extension to the $\mathcal{D}$-prophet inequality

As detailed in the previous sections, all the competitive ratios proved in the
case of the $\gamma$-prophet inequality remain true in the $D_{\infty}$\- and
the $\mathcal{D}$-prophet inequality for $\gamma=\gamma_{\mathcal{D}}$.

Moreover, Proposition 3.2 shows that upper bounds that are demonstrated
through instances of random variables taking values in some set $\\{0,a,b\\}$
a.s. remain true in the $D_{\infty}$-prophet inequality and consequently also
in the $\mathcal{D}$-prophet inequality by Theorem 2.1. Since we restricted
ourselves to using such instances for proving upper bounds in the
$\gamma$-prophet inequality, they all remain also true in the
$\mathcal{D}$-prophet inequality for $\gamma=\gamma_{\mathcal{D}}$.

##  5 Conclusion

In this paper, we addressed the $\mathcal{D}$-prophet inequality problem,
which models a very broad spectrum of online selection scenarios,
accommodating various observation order models and allowing to revisit
rejected candidates at a cost. The problem extends the classic prophet
inequality, corresponding to the special case where all decay functions are
zero. The main result of the paper is a reduction from the general
$\mathcal{D}$-prophet inequality to the $\gamma$-prophet inequality, where all
the decay functions equal to $x\mapsto\gamma x$ for some constant
$\gamma\in[0,1]$. Subsequently, we provide algorithms and upper bounds for the
$\gamma$-prophet inequality, which remain valid, by the previous reduction, in
the $\mathcal{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

##### Better upper bounds in the $D_{\infty}$-prophet inequality

Proposition 3.3 establishes that upper bounds proved in the $\gamma$-prophet
inequality using instances of random variables with support in some set
$\\{0,a,b\\}$ remain true in the $D_{\infty}$-prophet inequality, and hence in
the $\mathcal{D}$-prophet inequality, by Theorem 2.1, for
$\gamma=\gamma_{\mathcal{D}}$. This is enough to establish a tight upper bound
in the adversarial order model, but not in the random order and IID models. An
interesting question to explore is if more general upper bounds can be
extended, or not, from the $\gamma$\- to the $\mathcal{D}$-prophet inequality.

##### Algorithms for the $\gamma$-prophet inequality

As explained in Section 4, our analysis of the competitive ratio of single-
threshold algorithms relies on the identity (4), which is not satisfied for
instance by multiple-threshold algorithms. In the adversarial order model, we
proved that the optimal competitive ratio $1/(2-\gamma)$ can be achieved with
a single-threshold algorithm. However, this is not the case in the random
order or IID models. An open research avenue is to study other classes of
algorithms in the $\gamma$-prophet inequality.

## References

  * Antoniadis et al. [2020] Antonios Antoniadis, Themis Gouleakis, Pieter Kleer, and Pavel Kolev.  Secretary and online matching problems with machine learned advice.  _Advances in Neural Information Processing Systems_ , 33:7933–7944, 2020.
  * Antoniadis et al. [2023] Antonios Antoniadis, Joan Boyar, Marek Eliás, Lene Monrad Favrholdt, Ruben Hoeksma, Kim S Larsen, Adam Polak, and Bertrand Simon.  Paging with succinct predictions.  In _International Conference on Machine Learning_ , pages 952–968. PMLR, 2023.
  * Arsenis and Kleinberg [2022] 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.
  * Assaf and Samuel-Cahn [2000] David Assaf and Ester Samuel-Cahn.  Simple ratio prophet inequalities for a mortal with multiple choices.  _Journal of applied probability_ , 37(4):1084–1091, 2000.
  * Atsidakou et al. [2024] 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.
  * Benomar and Perchet [2024a] Ziyad Benomar and Vianney Perchet.  Advice querying under budget constraint for online algorithms.  _Advances in Neural Information Processing Systems_ , 36, 2024a.
  * Benomar and Perchet [2024b] Ziyad Benomar and Vianney Perchet.  Non-clairvoyant scheduling with partial predictions.  _arXiv preprint arXiv:2405.01013_ , 2024b.
  * Berger et al. [2024] Ben Berger, Tomer Ezra, Michal Feldman, and Federico Fusco.  Pandora’s problem with deadlines.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 38, pages 20337–20343, 2024.
  * Beyhaghi et al. [2021] Hedyeh Beyhaghi, Negin Golrezaei, Renato Paes Leme, Martin Pál, and Balasubramanian Sivan.  Improved revenue bounds for posted-price and second-price mechanisms.  _Operations Research_ , 69(6):1805–1822, 2021.
  * Borodin and El-Yaniv [2005] Allan Borodin and Ran El-Yaniv.  _Online computation and competitive analysis_.  cambridge university press, 2005.
  * Brubach et al. [2021] 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:27184–27195, 2021.
  * Bubna and Chiplunkar [2023] 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.
  * Chawla et al. [2010] Shuchi Chawla, Jason D Hartline, David L Malec, and Balasubramanian Sivan.  Multi-parameter mechanism design and sequential posted pricing.  In _Proceedings of the forty-second ACM symposium on Theory of computing_ , pages 311–320, 2010.
  * Chen et al. [2022] 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.
  * Chlkedowski et al. [2021] Jakub Chlkedowski, Adam Polak, Bartosz Szabucki, and Konrad Tomasz .Zolna.  Robust learning-augmented caching: An experimental study.  In _International Conference on Machine Learning_ , pages 1920–1930. PMLR, 2021.
  * Christianson et al. [2023] Nicolas Christianson, Junxuan Shen, and Adam Wierman.  Optimal robustness-consistency tradeoffs for learning-augmented metrical task systems.  In _International Conference on Artificial Intelligence and Statistics_ , pages 9377–9399. PMLR, 2023.
  * Cohen et al. [2019] Alon Cohen, Avinatan Hassidim, Haim Kaplan, Yishay Mansour, and Shay Moran.  Learning to screen.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Correa et al. [2019] Jose Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld.  Recent developments in prophet inequalities.  _ACM SIGecom Exchanges_ , 17(1):61–70, 2019.
  * Correa et al. [2021a] Jose Correa, Andres Cristi, Paul Duetting, and Ashkan Norouzi-Fard.  Fairness and bias in online selection.  In _International conference on machine learning_ , pages 2112–2121. PMLR, 2021a.
  * Correa et al. [2021b] 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):1452–1478, 2021b.
  * Correa et al. [2021c] Jose Correa, Raimundo Saona, and Bruno Ziliotto.  Prophet secretary through blind strategies.  _Mathematical Programming_ , 190(1-2):483–521, 2021c.
  * Deng et al. [2022] 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.
  * Diakonikolas et al. [2021] Ilias 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.
  * Dinitz et al. [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.
  * Dütting et al. [2020] 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–37, 2020.
  * Dütting et al. [2021] 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.
  * Dynkin [1963] Evgenii Borisovich Dynkin.  The optimum choice of the instant for stopping a markov process.  _Soviet Mathematics_ , 4:627–629, 1963.
  * Ekbatani et al. [2024] Farbod Ekbatani, Rad Niazadeh, Pranav Nuti, and Jan Vondrák.  Prophet inequalities with cancellation costs.  _arXiv preprint arXiv:2404.00527_ , 2024.
  * Esfandiari et al. [2017] Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh.  Prophet secretary.  _SIAM Journal on Discrete Mathematics_ , 31(3):1685–1701, 2017.
  * Esfandiari et al. [2019] Hossein Esfandiari, MohammadTaghi HajiAghayi, Brendan Lucier, and Michael Mitzenmacher.  Online pandora’s boxes and bandits.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pages 1885–1892, 2019.
  * Ezra et al. [2020] 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.
  * Feldman et al. [2016] 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.
  * Gergatsouli and Tzamos [2022] Evangelia Gergatsouli and Christos Tzamos.  Online learning for min sum set cover and pandora’s box.  In _International Conference on Machine Learning_ , pages 7382–7403. PMLR, 2022.
  * Gergatsouli and Tzamos [2024] Evangelia Gergatsouli and Christos Tzamos.  Weitzman’s rule for pandora’s box with correlations.  _Advances in Neural Information Processing Systems_ , 36, 2024.
  * Hajiaghayi et al. [2007] Mohammad Taghi Hajiaghayi, Robert Kleinberg, and Tuomas Sandholm.  Automated online mechanism design and prophet inequalities.  In _AAAI_ , volume 7, pages 58–65, 2007.
  * Hill and Kertz [1982] Theodore P Hill and Robert P Kertz.  Comparisons of stop rule and supremum expectations of iid random variables.  _The Annals of Probability_ , pages 336–345, 1982.
  * Jiang et al. [2021] 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.
  * Kertz [1986] Robert P 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.
  * Kleinberg and Weinberg [2012] Robert Kleinberg and Seth Matthew Weinberg.  Matroid prophet inequalities.  In _Proceedings of the forty-fourth annual ACM symposium on Theory of computing_ , pages 123–136, 2012.
  * Kleinberg et al. [2016] Robert Kleinberg, Bo Waggoner, and E Glen Weyl.  Descending price optimally coordinates search.  _arXiv preprint arXiv:1603.07682_ , 2016.
  * Krengel and Sucheston [1977] Ulrich Krengel and Louis Sucheston.  Semiamarts and finite values.  1977\.
  * Krengel and Sucheston [1978] Ulrich Krengel and Louis Sucheston.  On semiamarts, amarts, and processes with finite value.  _Probability on Banach spaces_ , 4:197–266, 1978.
  * Lassota et al. [2023] Alexandra Anna Lassota, Alexander Lindermayr, Nicole Megow, and Jens Schlöter.  Minimalistic predictions to schedule jobs with online precedence constraints.  In _International Conference on Machine Learning_ , pages 18563–18583. PMLR, 2023.
  * Li et al. [2022] Bo Li, Xiaowei Wu, and Yutong Wu.  Query efficient prophet inequality with unknown iid distributions.  _arXiv preprint arXiv:2205.05519_ , 2022.
  * Lindley [1961] Denis V Lindley.  Dynamic programming and decision theory.  _Journal of the Royal Statistical Society: Series C (Applied Statistics)_ , 10(1):39–51, 1961.
  * Lucier [2017] Brendan Lucier.  An economic view of prophet inequalities.  _ACM SIGecom Exchanges_ , 16(1):24–47, 2017.
  * Lykouris and Vassilvtiskii [2018] Thodoris Lykouris and Sergei Vassilvtiskii.  Competitive caching with machine learned advice.  In _International Conference on Machine Learning_ , pages 3296–3305. PMLR, 2018.
  * Makur et al. [2024] 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.
  * Merlis et al. [2023] Nadav Merlis, Hugo Richard, Flore Sentenac, Corentin Odic, Mathieu Molina, and Vianney Perchet.  On preemption and learning in stochastic scheduling.  In _International Conference on Machine Learning_ , pages 24478–24516. PMLR, 2023.
  * Papadimitriou et al. [2021] Christos Papadimitriou, Tristan Pollner, Amin Saberi, and David Wajc.  Online stochastic max-weight bipartite matching: Beyond prophet inequalities.  In _Proceedings of the 22nd ACM Conference on Economics and Computation_ , pages 763–764, 2021.
  * Peng and Tang [2022] 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.
  * Psomas et al. [2022] Alexandros Psomas, Ariel Schvartzman Cohenca, and S Weinberg.  On infinite separations between simple and optimal mechanisms.  _Advances in Neural Information Processing Systems_ , 35:4818–4829, 2022.
  * Purohit et al. [2018] Manish Purohit, Zoya Svitkina, and Ravi Kumar.  Improving online algorithms via ml predictions.  _Advances in Neural Information Processing Systems_ , 31, 2018.
  * Samuel-Cahn [1984] Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  _the Annals of Probability_ , pages 1213–1216, 1984.
  * Sinclair et al. [2023] Sean R 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 31877–31914. PMLR, 2023.
  * Sun et al. [2021] Bo Sun, Russell Lee, Mohammad Hajiesmaili, Adam Wierman, and Danny Tsang.  Pareto-optimal learning-augmented algorithms for online conversion problems.  _Advances in Neural Information Processing Systems_ , 34:10339–10350, 2021.
  * Syrgkanis [2017] Vasilis Syrgkanis.  A sample complexity measure with applications to learning optimal auctions.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Weitzman [1978] Martin Weitzman.  _Optimal search for the best alternative_ , volume 78.  Department of Energy, 1978.

##  Appendix A From $\mathcal{D}$-prophet to the $D_{\infty}$-prophet
inequality

In this section, we prove the reduction from the $\mathcal{D}$-prophet to the
$D_{\infty}$-prophet inequality problem in the adversarial and random order
models, and the reduction up to an additional $O(n^{-1/3})$ term in the IID
model. First, we prove Corollary 2.1.1, which is the principal implication of
Theorem 2.1.

###  A.1 Proof of Corollary 2.1.1

###### Proof.

Let us denote $\textsf{A}_{*,\infty}$ the algorithm taking optimal decisions
for any instance in the $D_{\infty}$-prophet inequality (obtained via dynamic
programming). Then, by Theorem 2.1 we obtain for the adversarial and random
order models that

$\sup_{\textsf{ALG}}\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\leq\inf_{I}\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}=\inf_{I}\frac{\mathbb{E}[\textsf{A}_{*,\infty}^{D_{\infty}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}=\textsf{CR}^{D_{\infty}}(\textsf{A}_{*,\infty})=\sup_{\textsf{A}}\textsf{CR}^{D_{\infty}}(\textsf{A})\;.$
(5)

Since
$\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\geq\textsf{CR}^{D_{\infty}}(\textsf{ALG})$
for any algorithm, we deduce that (5) is an equality. If we consider now any
algorithm $\mkern 1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern
1.5mu_{\infty}$ that is optimal for the $D_{\infty}$-prophet inequality, not
necessarily $\textsf{A}_{*,\infty}$, then Equation (5) provides

$\textsf{CR}^{\mathcal{D}}(\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern
1.5mu_{\infty})\geq\textsf{CR}^{D_{\infty}}(\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern
1.5mu_{\infty})=\sup_{\textsf{ALG}}\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\;.$

The previous inequality is again an equality, and it implies that
$\bar{\textsf{A}}_{\infty}$ is also optimal, in the sense of the competitive
ratio, for the $\mathcal{D}$-prophet inequality, and

$\textsf{CR}^{\mathcal{D}}(\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern
1.5mu_{\infty})=\textsf{CR}^{D_{\infty}}(\mkern
1.5mu\overline{\mkern-2.0mu\textsf{A}\mkern-1.5mu}\mkern 1.5mu_{\infty})\;.$

∎

###  A.2 Auxilary Lemma

The efficiency of the proof scheme introduced in Section 2.1 relies on the
following key argument: if $(D_{j})_{j\geq 1}$ converges pointwise to
$D_{\infty}$, then for any algorithm A and any instance $I$, the output of A
when all the decay functions are equal to $D_{m}$ converges to its output when
all the decay functions are equal to $D_{\infty}$. If $X_{1},\ldots,X_{n}$ are
the realizations of $I$ observed by A and if $\sigma$ is the order in which
they are observed, then denoting $\tau$ the stopping time of A we can write
that

$\displaystyle\mathbb{E}[\textsf{A}^{D_{m}}$
$\displaystyle(I)]-\mathbb{E}[\textsf{A}^{D_{\infty}}(I)]$
$\displaystyle=\mathbb{E}[\max\\{X_{\sigma(\tau)},D_{m}(\max_{i<\tau}X_{\sigma(i)})\\}]-\mathbb{E}[\max\\{X_{\sigma(\tau)},D_{\infty}(\max_{i<\tau}X_{\sigma(i)})\\}]$
$\displaystyle\leq\max_{\begin{subarray}{c}\pi\in\mathcal{S}_{n}\\\
q\in[n]\end{subarray}}\left\\{\mathbb{E}[\max\\{X_{\pi(q)},D_{m}(\max_{i<q}X_{\pi(i)})\\}]-\mathbb{E}[\max\\{X_{\pi(q)},D_{\infty}(\max_{i<q}X_{\pi(i)})\\}]\right\\}\;,$

where $\mathcal{S}_{n}$ is the set of all permutations of $[n]$. The latter
upper bound is independent of $\sigma$ and A. We show in the following lemma
that it converges to $0$ when $m\to\infty$.

######  Lemma A.1.

Let $\mathcal{S}_{n}$ be the set of all permutations of $[n]$. For any fixed
instance $I=(F_{1},\ldots,F_{n})$, considering $X_{i}\sim F_{i}$ for all
$i\in[n]$, define for all $m\geq 1$

$\epsilon_{m}(I)=\max_{\begin{subarray}{c}\pi\in\mathcal{S}_{n}\\\
q\in[n]\end{subarray}}\left\\{\mathbb{E}[\max\\{X_{\pi(q)},D_{m}(\max_{i<q}X_{\pi(i)})\\}]-\mathbb{E}[\max\\{X_{\pi(q)},D_{\infty}(\max_{i<q}X_{\pi(i)})\\}]\right\\}\;.$

If $\mathbb{E}[\max_{i\in[n]}X_{i}]<\infty$, then
$\lim\limits_{m\to\infty}\epsilon_{m}(I)=0$.

###### Proof.

Let us denote $f_{1},\ldots,f_{n}$ the respective probability density
functions of $X_{1},\ldots,X_{q}$. For any $q\in[n]$ and
$\pi\in\mathcal{S}_{n}$, let us define for all $m\geq 0$ the function
$\varphi^{\pi,q}_{m}:[0,\infty)^{q}\to[0,\infty)$ by
$\varphi^{\pi,q}_{m}(x_{1},\ldots,x_{q})=\max\\{x_{\pi(q)},D_{m}(\max_{i<q}x_{\pi(i)})\\}-\max\\{x_{\pi(q)},D_{\infty}(\max_{i<q}x_{\pi(i)})\\}$.
$\varphi^{\pi,q}_{m}$ is positive because $D_{m}\geq D_{\infty}$. The sequence
$(\varphi^{\pi,q}_{m})_{m}$ is non-increasing, converges to $0$ pointwise, and
is dominated by $(x_{1},\ldots,x_{q})\mapsto\max_{i\in[q]}x_{i}$, which is
integrable with respect to the probability measure
$(x_{1},\ldots,x_{q})\mapsto\prod_{i=1}^{q}f(x_{i})$. Therefore, using the
dominated convergence theorem, we deduce that
$\lim_{m\to\infty}\mathbb{E}[\varphi^{\pi,q}_{m}(X_{1},\ldots,X_{q})]=0$. It
follows that

$\lim_{m\to\infty}\epsilon_{m}(I)=\lim_{m\to\infty}\Big{(}\max_{\begin{subarray}{c}\pi\in\mathcal{S}_{n}\\\
q\in[n]\end{subarray}}\mathbb{E}[\varphi^{\pi,q}_{m}(X_{1},\ldots,X_{q})]\Big{)}=0\;.$

∎

###  A.3 Proof of Theorem 2.1

###### Proof of Theorem 2.1.

We provide a separate proof for each of the adversarial order, random order
and IID models.

##### Adversarial order

Let $I=(F_{1},\ldots,F_{n})$ be any instance and $X_{i}\sim F_{i}$ for all
$i\in[n]$. Consider the instance $I_{m}=(Y_{1},\ldots,Y_{mn})$, where
$Y_{km}\sim F_{k}$ for any $k\in[n]$ and $Y_{i}=0$ a.s. for all
$i\notin\\{m,2m,\ldots,mn\\}$. It is clear that no reasonable algorithm would
stop at a zero value: if the current observation is $0$ it is preferable to
wait for a non-null value, or it would have been preferable to stop at the
previous non-null value. Hence, $\tau$ is a multiple of $m$: $\tau=\rho m$ for
some $\rho\in\mathbb{N}^{\star}$. Given that $D_{j}(0)=0$ for all $j$ and the
sequence $(D_{j})_{j}$ is non-increasing, we have that

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})]$
$\displaystyle=\mathbb{E}[\max_{i\leq\tau}D_{\tau-i}(Y_{i})]$
$\displaystyle=\mathbb{E}[\max_{k\leq\rho}D_{\tau-km}(Y_{km})]$
$\displaystyle=\mathbb{E}[\max_{k\leq\rho}D_{\rho m-km}(X_{k})]$
$\displaystyle=\mathbb{E}[\max\\{X_{\rho},\max_{k<\rho}D_{(\rho-k)m}(X_{k})\\}]$
$\displaystyle\leq\mathbb{E}[\max\\{X_{\rho},\max_{k<\rho}D_{m}(X_{k})\\}]$
$\displaystyle\leq\mathbb{E}[\max\\{X_{\rho},\max_{k<\rho}D_{\infty}(X_{k})\\}]+\epsilon_{m}(I)\;,$

where $\epsilon_{m}(I)$ is defined in Lemma A.1. We can then use that the
first right-hand term is the output of some other algorithm that would choose
a stopping time $\rho$ when facing $I$ in the context of the
$D_{\infty}$-prophet inequality. More precisely, consider the algorithm
$\textsf{A}_{m}$ which, given any instance $I=(F_{1},\ldots,F_{n})$, simulates
the behavior of ALG facing the sequence $I_{m}$, where at each step $i\in[mn]$

  * •

if $i\notin\\{m,\ldots,nm\\}$: ALG observes $Y_{i}=0$,

  * •

otherwise, if $i=km$ for some $k\in[n]$: $\textsf{A}_{m}$ observes $X_{k}$ and
ALG observes $Y_{km}=X_{k}$

  * •

if ALG stops on $Y_{\rho m}$, then $\textsf{A}_{m}$ also stops, and its reward
is $X_{\rho}$.

$\textsf{A}_{m}(X_{1},\ldots,X_{n})$ stops at the same value as
$\textsf{ALG}(Y_{1},\ldots,Y_{m})$, their reward in the $D_{\infty}$-prophet
inequality is the same, and since $\max_{i\in[n]}X_{i}=\max_{i\in[mn]}Y_{i}$
this yields to

$\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\leq\frac{\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})]}{\mathbb{E}[\textsf{OPT}(I_{m})]}\leq\frac{\mathbb{E}[\textsf{A}_{m}^{D_{\infty}}(I)]+\epsilon_{m}(I)}{\mathbb{E}[\textsf{OPT}(I)]}\leq\sup_{\textsf{A}:\text{
algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}+\frac{\epsilon_{m}(I)}{\mathbb{E}[\textsf{OPT}(I)]}\;,$

and taking the limit when $m\to\infty$ gives the result, by making the second
term vanish.

##### Random order

Let $I=(F_{1},\dots,F_{n})$ be an instance of distributions and $X_{i}\sim
F_{i}$ for $i\in[n]$. Using the notation $\delta_{0}$ for the Dirac
distribution in $0$, we consider
$I_{m}=(F_{1},\ldots,F_{n},\delta_{0},\ldots,\delta_{0})$ containing $m$
copies of $\delta_{0}$ so that the observations from this instance always
contain at least $m$ null values. Let $Y_{1},\ldots,Y_{m}$ be a realization of
this instance. For simplicity, say that $Y_{i}=X_{i}$ for $i\in[n]$, and
$Y_{i}=0$ for $i>n$.

We first show that when $m\to\infty$, since the observation order is drawn
uniformly at random, the algorithm observes a large number of zeros between
every two random variables drawn from $(F_{1},\dots,F_{n})$. Let us denote by
$\pi$ the uniformly random order in which the observations are received, i.e.
the algorithms observes $Y_{\pi(1)},Y_{\pi(2)},\ldots$, and let $\ell\geq 1$
be some positive integer, and $t_{1},\dots,t_{n}$ be the increasing indices in
which the variables $Y_{1},\ldots,Y_{n}$ are observed, i.e.
$t_{1}<\ldots<t_{n}$ and $\\{t_{1},\ldots
t_{n}\\}=\\{\pi^{-1}(1),\ldots,\pi^{-1}(n)\\}$. Therefore, any observation
outside $\\{Y_{\pi(t_{1})},\ldots,Y_{\pi(t_{1})}\\}$ is zero. Using the
notation $L=\min_{i\in[n-1]}|t_{i+1}-t_{i}|$, we obtain that

$\displaystyle\Pr(L\leq\ell)$
$\displaystyle=\Pr(\cup_{i=1}^{n-1}\left\\{t_{i+1}-t_{i}\leq\ell\right\\})$
$\displaystyle=\Pr\left(\cup_{k=1}^{n}\cup_{j=1}^{k-1}\left\\{|\pi^{-1}(k)-\pi^{-1}(j)|\leq\ell\right\\}\right)$
$\displaystyle\leq\frac{n(n-1)}{2}\Pr(|\pi^{-1}(1)-\pi^{-1}(2)|\leq\ell)$
$\displaystyle=\frac{n(n-1)}{2}\Pr(\big{(}\cup_{k=1}^{n+m}(\pi^{-1}(1)=k,\pi^{-1}(2)\in\\{k-\ell,\ldots,k+\ell\\}\setminus\\{k\\})$
$\displaystyle\leq\frac{n(n-1)}{2}\times(n+m)\times\frac{1}{n+m}\times\frac{2\ell}{n+m-1}$
$\displaystyle\leq\frac{n^{2}\ell}{m}\;.$

Taking $\ell=\sqrt{m}$, we find that $\Pr(L\leq\ell)\leq n^{2}/\sqrt{m}$.
Therefore, for any algorithm ALG, observing that the reward of
$\textsf{ALG}^{D}$ is at most $\max_{i\in[n]}X_{i}$ a.s., and by independence
of $\max_{i\in[n]}X_{i}$ and $L$, we deduce that

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})]$
$\displaystyle=\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})\mathbbm{1}_{L>\ell}]+\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})\mathbbm{1}_{L\leq\ell}]$
$\displaystyle\leq\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})\mid
L>\ell]+\mathbb{E}[(\max_{i\in[n]}X_{i})\mathbbm{1}_{L\leq\ell}]$
$\displaystyle\leq\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})\mid
L>\ell]+\mathbb{E}[\max_{i\in[n]}X_{i}]\frac{n^{2}}{\sqrt{m}}\;.$ (6)

Let us denote $\tau$ the stopping time of ALG and
$t_{\rho}=\max_{j\in[n]}\\{t_{j}:t_{j}\leq\tau\\}$ the last time when a
variable $(X_{j})_{j\in[n]}$ was observed by ALG. The sequence of functions
$(D_{j})_{j\geq 1}$ is non-increasing, hence

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})\mid L>\ell]$
$\displaystyle=\mathbb{E}[\max_{i\in[\tau]}D_{\tau-i}(Y_{\pi(i)})\mid L>\ell]$
$\displaystyle=\mathbb{E}[\max_{j\leq i}D_{\tau-t_{j}}(Y_{\pi(t_{j})})\mid
L>\ell]$ (7) $\displaystyle\leq\mathbb{E}[\max_{j\leq
i}D_{t_{\rho}-t_{j}}(Y_{\pi(t_{j})})\mid L>\ell]$ (8)
$\displaystyle=\mathbb{E}[\max\big{\\{}Y_{\pi(t_{\rho})},\max_{j<\rho}D_{t_{\rho}-t_{j}}(Y_{\pi(t_{j})})\big{\\}}\mid
L>\ell]$
$\displaystyle\leq\mathbb{E}[\max\big{\\{}Y_{\pi(t_{\rho})},\max_{j<\rho}D_{\ell}(Y_{\pi(t_{j})})\big{\\}}]\;,$
(9)

Equation (7) holds because the only non-zero values up to step $\tau$ are
$(Y_{\pi(t_{j})})_{j\in[\rho]}$. Inequality (8) uses that the sequence
$(D_{j})_{j\geq 1}$ is non-increasing, and (9) uses, in addition to that, the
independence of $L$ and $(Y_{\pi(t_{j})})_{j\in[n]}$. We now argue that the
term
$\mathbb{E}[\max\big{\\{}Y_{\pi(t_{\rho})},\max_{j<\rho}D_{\ell}(Y_{\pi(t_{j})})\big{\\}}]$
is the expected reward of an algorithm in the $D_{\ell}$-inequality. Given
that $\pi$ is a uniform random permutation of $[n+m]$ and by definition of
$t_{1},\ldots,t_{n}$, the application $\sigma:k\in[n]\mapsto\pi(t_{k})$ is a
random permutation of $[n]$. Therefore we consider the algorithm
$\textsf{A}_{m}$ that receives as input the instance $I=(F_{1},\ldots,F_{n})$,
then considers the array $u=(1,\ldots,1,0,\ldots,0)$ composed of $n$ values
equal to $1$ and $m$ zero values, and a uniformly random permutation $\pi$ of
$[n+m]$, then simulates $\textsf{ALG}^{D}(I_{m})$ as follows: at each step
$j\in[n+m]$

  * •

if $u_{\pi(j)}=0$, then ALG observes the value $Y_{\pi(j)}=0$,

  * •

if $u_{\pi(j)}=1$, then $\textsf{A}_{m}$ observes the next value
$X_{\sigma(k)}$, and ALG observes $Y_{\pi(j)}=X_{\sigma(k)}$,

  * •

when ALG decides to stop, $\textsf{A}_{m}$ also stops, and its reward is the
current value $X_{\sigma(k)}$.

With this construction, $(Y_{j})_{j\in[n+m]}$ is indeed a realization of the
instance $I_{m}$, and $\textsf{A}_{m}$ stops on the last value sampled from
$F_{1},\ldots,F_{n}$ observed by ALG. Therefore, denoting $\rho$ the stopping
time of $\textsf{A}_{m}$, and $\epsilon_{\ell}(I)$ as defined in Lemma A.1, we
have

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})\mid L>\ell]$
$\displaystyle\leq\mathbb{E}[\max\big{\\{}Y_{\pi(t_{\rho})},\max_{j<\rho}D_{\ell}(Y_{\pi(t_{j})})\big{\\}}]$
$\displaystyle=\mathbb{E}[\max\big{\\{}X_{\sigma(\rho)},\max_{j<\rho}D_{\ell}(X_{\sigma(t_{j})})\big{\\}}]$
$\displaystyle=\mathbb{E}[\textsf{A}^{D_{\ell}}_{m}(I)]$
$\displaystyle\leq\mathbb{E}[\textsf{A}^{D_{\infty}}_{m}(I)]+\epsilon_{\ell}(I)$
$\displaystyle\leq\sup_{\textsf{A}:\text{algo}}\mathbb{E}[\textsf{A}^{D_{\infty}}(I)]+\epsilon_{\ell}(I)\;.$

Taking $\ell=\sqrt{m}$ and substituting into Equation (6), then observing that
$\mathbb{E}[\textsf{OPT}(I)]=\mathbb{E}[\textsf{OPT}(I_{m})]$, gives that

$\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\leq\frac{\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(I_{m})]}{\mathbb{E}[\textsf{OPT}(I_{m})]}\leq\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}+\frac{\epsilon_{\sqrt{m}}(I)}{\mathbb{E}[\textsf{OPT}(I)]}+\frac{n^{2}}{\sqrt{m}}\;.$

Finally, taking $m\to\infty$ and using Lemma A.1, we deduce that

$\textsf{CR}^{\mathcal{D}}(\textsf{ALG})\leq\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}\;,$

which completes the proof for the random order.

##### IID random variables

For any probability distribution $F$ on $[0,\infty)$ and for any $n\geq 1$ we
denote $\mathbb{E}[\textsf{OPT}(F,n)]$ the expected maximum of $n$ independent
random variables drawn from $F$, and for any algorithm ALG we denote
$\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(F,n)]$ its expected output when given
$n$ IID variable sampled from $F$ as input. The proof of Theorem 2.1 for this
last model is much more technical than for previous models, so we first prove
several auxiliary results that we will later use to provide a concise proof of
the last part of the theorem.

######  Lemma A.2.

For any probability distribution $F$ and $n\geq 1,\Delta\geq 0$, we have

$\mathbb{E}[\textsf{OPT}(F,n+\Delta)]\leq\left(1+\frac{\Delta}{n}\right)\mathbb{E}[\textsf{OPT}(F,n)]\;.$

###### Proof.

We first write

$\displaystyle\Pr(\textsf{OPT}(F,n+\Delta)>x)$
$\displaystyle=1-F(x)^{n+\Delta}$
$\displaystyle=\left(1+F(x)^{n}\frac{1-F(x)^{\Delta}}{1-F(x)^{n}}\right)(1-F(x)^{n})$
$\displaystyle=\left(1+F(x)^{n}\frac{1-F(x)^{\Delta}}{1-F(x)^{n}}\right)\Pr(\textsf{OPT}(F,n)>x)\;,$

and then use that

$F(x)^{\Delta}=e^{\Delta\log(F(x))}\geq
1+\Delta\log(F(x))=1-\frac{\Delta}{n}\log(1/F(x)^{n})\geq
1-\frac{\Delta}{n}\left(\frac{1-F(x)^{n}}{F(x)^{n}}\right)\;,$

so we directly obtain

$F(x)^{n}\frac{1-F(x)^{\Delta}}{1-F(x)^{n}}\leq\frac{\Delta}{n}\;,$

which gives that

$\Pr(\textsf{OPT}(F,n+\Delta)>x)\leq\left(1+\frac{\Delta}{n}\right)\Pr(\textsf{OPT}(F,n)>x)\;.$

As we consider non-negative random variables, it follows directly that

$\mathbb{E}(\textsf{OPT}(F,n+\Delta))\leq\left(1+\frac{\Delta}{n}\right)\mathbb{E}(\textsf{OPT}(F,n))\;.$

∎

######  Lemma A.3.

Let $N\sim\mathcal{B}(m,\varepsilon)$ and let $n:=\mathbb{E}[N]=\varepsilon
m$, then we have

$\displaystyle\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq n+n^{2/3}}]$
$\displaystyle\leq\frac{6}{n^{1/3}}\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]\;,$
$\displaystyle\mathbb{E}[\textsf{OPT}(F,N)]$
$\displaystyle\leq\left(1+\frac{3}{n^{1/3}}\right)\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]\;.$

###### Proof.

Let $\Delta,s>0$ such that $\Delta\leq s$. For any $k\geq 1$ let
$W_{k}=[s+(k-1)\Delta,s+k\Delta)$. $(W_{k})_{k\geq 1}$ is a partition of
$[s,\infty)$, thus we have

$\displaystyle\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq s}]$
$\displaystyle=\sum_{k=1}^{\infty}\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\in
W_{k}}]$
$\displaystyle\leq\sum_{k=1}^{\infty}\mathbb{E}[\textsf{OPT}(F,s+k\Delta)\mathbbm{1}_{N\in
W_{k}}]$
$\displaystyle=\sum_{k=1}^{\infty}\mathbb{E}[\textsf{OPT}(F,s+k\Delta)]\Pr(N\in
W_{k})$
$\displaystyle\leq\sum_{k=1}^{\infty}\left(1+\frac{k\Delta}{s}\right)\mathbb{E}[\textsf{OPT}(F,s)]\Pr(N\in
W_{k})$ $\displaystyle=\left(\Pr(N\geq
s)+\frac{\Delta}{s}\sum_{k=1}^{\infty}k\Pr(N\in
W_{k})\right)\mathbb{E}[\textsf{OPT}(F,s)]\;,$

and observing that

$\sum_{k=1}^{\infty}k\Pr(N\in
W_{k})=\sum_{k=1}^{\infty}\sum_{\ell=0}^{k-1}\Pr(N\in
W_{k})=\sum_{\ell=0}^{\infty}\sum_{k=\ell+1}^{\infty}\Pr(N\in
W_{k})=\sum_{\ell=0}^{\infty}\Pr(N\geq s+\ell\Delta)\;,$

we obtain, given $\Delta\leq s$, that

$\displaystyle\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq s}]$
$\displaystyle\leq\left(\Pr(N\geq
s)+\frac{\Delta}{s}\sum_{k=0}^{\infty}\Pr(N\geq
s+k\Delta)\right)\mathbb{E}[\textsf{OPT}(F,s)]$ (10)
$\displaystyle\leq\left(2\sum_{k=0}^{\infty}\Pr(N\geq s+k\Delta)\right)\;.$
(11)

$N$ is a Bernoulli random variable with expectation $n$. Therefore, Chernoff’s
inequality gives for any $\delta\geq 0$ that

$\Pr(N\geq(1+\delta)n)\leq\exp\left(-\frac{\delta^{2}n}{2+\delta}\right)\leq\exp\left(-\frac{\min(\delta,\delta^{2})n}{3}\right)\;,$

where the second inequality can be derived by treating separately $\delta<1$
and $\delta\geq 1$. In particular, for any $k\geq 1$, taking
$\delta=\frac{k\Delta}{n}$ such that $\Delta\leq n$ yields

$\Pr(N\geq
n+k\Delta)\leq\exp\left(-\frac{\min(k\Delta,k^{2}\Delta^{2}/n)}{3}\right)\leq\exp\left(-\frac{k\min(\Delta,\Delta^{2}/n)}{3}\right)=\exp\left(-\frac{k\Delta^{2}}{3n}\right)\;.$

Substituting this Inequality into (11) with $s=n+\Delta$, we obtain

$\displaystyle\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq n+\Delta}]$
$\displaystyle\leq\left(2\sum_{k=1}^{\infty}\Pr(N\geq
n+k\Delta)\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]$
$\displaystyle\leq\left(2\sum_{k=1}^{\infty}\exp\left(-\frac{k\Delta^{2}}{3n}\right)\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]$
$\displaystyle=\frac{2}{\exp\left(\frac{\Delta^{2}}{3n}\right)-1}\mathbb{E}[\textsf{OPT}(F,n+\Delta)]$
$\displaystyle\leq\frac{6n}{\Delta^{2}}\mathbb{E}[\textsf{OPT}(F,n+\Delta)]\;,$

and taking $\Delta=n^{2/3}$ proves the first inequality of the lemma.

Let us move now to the second inequality. We have

$\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N<s}]\leq\mathbb{E}[\textsf{OPT}(F,s)\mathbbm{1}_{N<s}]=\mathbb{E}[\textsf{OPT}(F,s)]\Pr(N<s)\;,$

and thus, using Inequality (10), again with $s=n+\Delta$ and $\Delta=n^{2/3}$,
it follows that

$\displaystyle\mathbb{E}[\textsf{OPT}(F,N)]$
$\displaystyle=\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N<s}]+\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq
s}]$ $\displaystyle\leq\left(1+\frac{\Delta}{s}\sum_{k=0}^{\infty}\Pr(N\geq
s+k\Delta)\right)\mathbb{E}[\textsf{OPT}(F,s)]$
$\displaystyle\leq\left(1+\sum_{k=1}^{\infty}\Pr(N\geq
n+k\Delta)\right)\mathbb{E}[\textsf{OPT}(F,s)]$
$\displaystyle\leq\left(1+\frac{3}{n^{1/3}}\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]\;.$

∎

######  Lemma A.4.

Let
$\delta_{1},\ldots,\delta_{m}\overset{\text{iid}}{\sim}\mathcal{B}(\varepsilon)$,
$N=\sum_{i=1}^{m}\delta_{i}$, $n=\mathbb{E}[N]=\varepsilon m$ and
$L=\min_{i\neq j}\\{|i-j|:\delta_{i}=1,\delta_{j}=1\\}$, then for any
$\ell\geq 0$ we have

$\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{L\leq\ell}]\leq\frac{4m\ell\varepsilon^{2}}{(1-\varepsilon)^{2}}\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]\;.$

###### Proof.

The random variables $N$ and $L$ are not independent, thus we need to
adequately compute the distribution of $L$ conditional to $N$. For any
$\ell\geq 0$ and $k\geq 2$ we have

$\displaystyle\Pr(L\leq\ell,N=s)$
$\displaystyle=\Pr\Big{(}L\leq\ell,\sum_{i=1}^{m}\delta_{k}=s\Big{)}$
$\displaystyle=\Pr\Big{(}\cup_{i=1}^{m}\cup_{j=\max(1,i-\ell)}^{i-1}\big{(}\delta_{i}=\delta_{j}=1,\sum_{i=1}^{m}\delta_{k}=s\big{)}\Big{)}$
$\displaystyle\leq
m\ell\Pr\big{(}\delta_{1}=\delta_{2}=1,\sum_{i=3}^{m}\delta_{k}=s\big{)}$
$\displaystyle=m\ell\varepsilon^{2}{m-2\choose
s}\varepsilon^{s}(1-\varepsilon)^{m-s-2},$

therefore

$\displaystyle\Pr(L\leq\ell\mid N=s)$
$\displaystyle=\frac{\Pr(L\leq\ell,N=s)}{\Pr(N=s)}$
$\displaystyle\leq\frac{m\ell\varepsilon^{2}{m-2\choose
s}\varepsilon^{s}(1-\varepsilon)^{m-s-2}}{{m\choose
s}\varepsilon^{s}(1-\varepsilon)^{m-s}}$
$\displaystyle\leq\frac{m\ell\varepsilon^{2}}{(1-\varepsilon)^{2}}\;.$

Using this inequality and Lemma A.3, we deduce that

$\displaystyle\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{L\leq\ell}]$
$\displaystyle=\mathbb{E}[\textsf{OPT}(F,N)\Pr(L\leq\ell\mid N)]$
$\displaystyle\leq\frac{m\ell\varepsilon^{2}}{(1-\varepsilon)^{2}}\mathbb{E}[\textsf{OPT}(F,N)]$
$\displaystyle\leq\frac{m\ell\varepsilon^{2}}{(1-\varepsilon)^{2}}\left(1+\frac{3}{n^{1/3}}\right)\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]$
$\displaystyle\leq\frac{4m\ell\varepsilon^{2}}{(1-\varepsilon)^{2}}\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]\;.$

∎

Using the previous lemmas, we can now prove the theorem. Let $m>n\geq 1$,
$\Delta=n^{2/3}$, $\varepsilon=n/m$ and let $Q$ be the probability
distribution of a random variable that is equal to $0$ with probability
$1-\varepsilon$, and drawn from $F$ with probability $\varepsilon$.

Let us consider $m$ i.i.d. variables $Y_{1},\ldots,Y_{m}\sim Q$, and for each
$i\in[m]$ we denote by $\delta_{i}$ the indicator that $Y_{i}$ is drawn from
$F$. Define $N=\sum_{i=1}^{m}\delta_{i}\sim\mathcal{B}(m,\varepsilon)$ the
number of random variables $Y_{i}$ drawn from the distribution $F$. In the
following, we upper bound the competitive ratio of any algorithm by analyzing
its ratio on this particular instance. For this, we first provide a lower
bound on $\mathbb{E}[\textsf{OPT}(Q,m)]$ using Lemma A.2, and obtain

$\mathbb{E}[\textsf{OPT}(F,n-\Delta)]\geq\frac{1}{1+\frac{2\Delta}{n}}\mathbb{E}[\textsf{OPT}(F,n+\Delta)]\geq\left(1-\frac{2\Delta}{n}\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]\;,$

thus we have

$\displaystyle\mathbb{E}[\textsf{OPT}(Q,m)]$
$\displaystyle=\mathbb{E}[\textsf{OPT}(F,N)]$
$\displaystyle\geq\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq n-\Delta}]$
$\displaystyle\geq\mathbb{E}[\textsf{OPT}(F,n-\Delta)\mathbbm{1}_{N\geq
n-\Delta}]$ $\displaystyle=\mathbb{E}[\textsf{OPT}(F,n-\Delta)]\Pr(N\geq
n-\Delta)$ $\displaystyle\geq\left(1-\frac{2\Delta}{n}\right)\Pr(N\geq
n-\Delta)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]$
$\displaystyle\geq\left(1-\frac{2\Delta}{n}-\Pr(N<n-\Delta)\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]$
$\displaystyle\geq\left(1-2n^{-1/3}-\exp(-n^{1/3}/2)\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]$
$\displaystyle\geq\left(1-4n^{-1/3}\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]\;,$
(12)

where, for the last three inequalities, we used respectively Bernoulli’s
inequality, Chernoff bound, then $e^{-y}\leq 1/y$.

Then, we upper bound the reward of any algorithm given the instance $(Q,m)$ as
input. Let $L=\min_{i\neq j}\\{|i-j|:\delta_{i}=1,\delta_{j}=1\\}$ the
smallest gap between two successive variables $Y_{i}$ drawn from $F$, and let
$t_{1}<\ldots<t_{N}$ the indices for which $\delta_{i}=1$. We have for any
algorithm ALG and positive integer $\ell$ that

$\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)]=\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)\mathbbm{1}_{N\geq
n+\Delta\text{ or
}L\leq\ell}]+\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)\mathbbm{1}_{N<n+\Delta,L>\ell}]\;.$
(13)

Using Lemma A.3 and Lemma A.4, the first term can be bounded as follows

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)\mathbbm{1}_{N\geq
n+\Delta\text{ or }L\leq\ell}]$
$\displaystyle\leq\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq
n+\Delta\text{ or }L\leq\ell}]$
$\displaystyle\leq\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{N\geq
n+\Delta}]+\mathbb{E}[\textsf{OPT}(F,N)\mathbbm{1}_{L\leq\ell}]$
$\displaystyle\leq\left(\frac{6}{n^{1/3}}+\frac{4m\ell\varepsilon^{2}}{(1-\varepsilon)^{2}}\right)\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]\;.$

Considering that $m\geq 2n$ (i.e. $\varepsilon=n/m\leq 1/2$) and taking
$\ell=\sqrt{m}$, we obtain

$\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)\mathbbm{1}_{N\geq n+\Delta\text{
or
}L\leq\ell}]\leq\left(\frac{6}{n^{1/3}}+\frac{16n^{2}}{m}\right)\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]\;.$
(14)

Regarding the second term in Equation (13), let $\tau$ be the stopping time of
ALG and $t_{\rho}=\max\\{j\leq\tau:\delta_{j}=1\\}$ the last value sampled
from $F$ and observed by ALG before it stops. We have

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)\mathbbm{1}_{N<n+\Delta,L>\ell}]$
$\displaystyle\leq\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)\mid
N<n+\Delta,L>\ell]$
$\displaystyle=\mathbb{E}[\max_{i\in[\tau]}D_{\tau-i}(Y_{i})\mid
N<n+\Delta,L>\ell]$ $\displaystyle=\mathbb{E}[\max_{j\in[\rho]}D_{\tau-
t_{j}}(Y_{i})\mid N<n+\Delta,L>\ell]$
$\displaystyle\leq\mathbb{E}[\max_{j\in[\rho]}D_{t_{\rho}-t_{j}}(Y_{i})\mid
N<n+\Delta,L>\ell]$
$\displaystyle=\mathbb{E}[\max\big{\\{}Y_{t_{\rho}},\max_{j<\rho}D_{t_{\rho}-t_{j}}(Y_{t_{j}})\big{\\}}\mid
N<n+\Delta,L>\ell]$
$\displaystyle\leq\mathbb{E}[\max\big{\\{}Y_{t_{\rho}},\max_{j<\rho}D_{\ell}(Y_{t_{j}})\big{\\}}\mid
N<n+\Delta]\;.$

We then prove that the last term is the reward of an algorithm
$\textsf{A}_{m}$ in the $D_{\ell}$-prophet inequality. Let us $\textsf{A}_{m}$
be the algorithm that takes as input an instance $X_{1},\ldots,X_{n+\Delta-1}$
of $n+\Delta$ IID random variables, then simulates
$\textsf{ALG}^{\mathcal{D}}(Q,m)\mid N<n+\Delta$ as follows: let
$\delta_{1},\ldots,\delta_{m}\overset{\text{iid}}{\sim}\mathcal{B}(n/m)$ set
$N_{\textsf{A}}=0$ and for each $i\in[m]$

  * •

if $\delta_{i}=0$: ALG observes the value $Y_{i}=0$,

  * •

if $\delta_{i}=1$: increment $N$, then $\textsf{A}_{m}$ observes the next
value $X_{k}$, and ALG observes $Y_{i}=X_{k}$,

  * •

if $N_{\textsf{A}}=n+\Delta-1$ or ALG stops, then $\textsf{A}_{m}$ also stops.

When ALG decides to stop, the current value observed by $\textsf{A}_{m}$ is
$X_{\rho}$: the last value $Y_{t_{\rho}}$ observed by ALG such that
$\delta_{t_{\rho}}=0$. Observe that stopping when $N_{\textsf{A}}=n+\Delta+1$,
is equivalent to letting ALG observe zero values until the end, and stopping
when ALG stops. Hence, the variables $Y_{1},\ldots,Y_{m}$ have the same
distribution as $m$ IID samples from $Q$ conditional to $N<n+\Delta$. Denoting
$\rho$ the stopping time of $\textsf{A}_{m}$ and $\epsilon_{\ell}(F,n+\Delta)$
as defined in Lemma A.1, we deduce that

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)\mid
N<n+\Delta,L>\ell]$
$\displaystyle\leq\mathbb{E}[\max\big{\\{}Y_{t_{\rho}},\max_{j<\rho}D_{\ell}(Y_{t_{j}})\big{\\}}\mid
N<n+\Delta]$
$\displaystyle=\mathbb{E}[\max\big{\\{}X_{\rho},\max_{j<\rho}D_{\ell}(X_{j})\big{\\}}]$
$\displaystyle=\mathbb{E}[\textsf{A}_{m}^{D_{\ell}}(F,n+\Delta)]$
$\displaystyle\leq\mathbb{E}[\textsf{A}_{m}^{D_{\infty}}(F,n+\Delta)]+\epsilon_{\ell}(F,n+\Delta)\;.$
(15)

Substituting (14) and (15) in (13), with $\ell=\sqrt{m}$, yields

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)]\leq\left(\frac{6}{n^{1/3}}+\frac{16n^{2}}{m}\right)\mathbb{E}[\textsf{OPT}(F,n+\Delta)]+\mathbb{E}[\textsf{A}_{m}^{D_{\infty}}(F,n+\Delta)]+\epsilon_{\sqrt{m}}(F,n+\Delta)\;,$

and using Inequality 12, it follows that

$\displaystyle\textsf{CR}^{\mathcal{D}}(\textsf{ALG})$
$\displaystyle\leq\frac{\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(Q,m)]}{\mathbb{E}[\textsf{OPT}(Q,m)]}$
$\displaystyle\leq\frac{\frac{6}{n^{1/3}}+\frac{16n^{2}}{m}}{1-\frac{4}{n^{1/3}}}+\frac{\mathbb{E}[\textsf{A}_{m}^{D_{\infty}}(F,n+\Delta)]+\epsilon_{\sqrt{m}}(F,n+\Delta)}{(1-\frac{4}{n^{1/3}})\mathbb{E}[\textsf{OPT}(F,n+\Delta)]}$
$\displaystyle\leq\frac{\frac{6}{n^{1/3}}+\frac{16n^{2}}{m}}{1-\frac{4}{n^{1/3}}}+\frac{1}{1-\frac{4}{n^{1/3}}}\left(\frac{\epsilon_{\sqrt{m}}(F,n+\Delta)}{\mathbb{E}[\textsf{OPT}(F,n+\Delta)]}+\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(F,n+\Delta)]}{\mathbb{E}[\textsf{OPT}(F,n+\Delta)]}\right)\;,$

taking the limit $m\to\infty$ and using Lemma A.1 gives

$\displaystyle\textsf{CR}^{\mathcal{D}}(\textsf{ALG})$
$\displaystyle\leq\frac{\frac{6}{n^{1/3}}}{1-\frac{4}{n^{1/3}}}+\frac{1}{1-\frac{4}{n^{1/3}}}\left(\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(F,n+\Delta)]}{\mathbb{E}[\textsf{OPT}(F,n+\Delta)]}\right)$
$\displaystyle=\frac{6}{n^{1/3}-4}+\left(1+\frac{4}{n^{1/3}-4}\right)\left(\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(F,n+\Delta)]}{\mathbb{E}[\textsf{OPT}(F,n+\Delta)]}\right)$
$\displaystyle\leq\frac{10}{n^{1/3}-4}+\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(F,n+n^{2/3})]}{\mathbb{E}[\textsf{OPT}(F,n+n^{2/3})]}\;.$

where the last inequality holds because
$\mathbb{E}[\textsf{A}^{D_{\infty}}(F,n+\Delta)]\leq\mathbb{E}[\textsf{OPT}(F,n+\Delta)]$
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\geq(n+n^{2/3})/2=k/2$, thus
$n^{1/3}\geq k^{1/3}/2$, and we obtain

$\displaystyle\textsf{CR}^{\mathcal{D}}(\textsf{ALG})$
$\displaystyle\leq\frac{20}{k^{1/3}-8}+\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(F,k)]}{\mathbb{E}[\textsf{OPT}(F,k)]}$
$\displaystyle=\sup_{\textsf{A}:\text{algo}}\frac{\mathbb{E}[\textsf{A}^{D_{\infty}}(F,k)]}{\mathbb{E}[\textsf{OPT}(F,k)]}+O\left(\frac{1}{k^{1/3}}\right)\;.$

∎

##  Appendix B From $D_{\infty}$-prophet to the $\gamma_{\mathcal{D}}$-prophet
inequality

###  B.1 Proof of Lemma 3.1

###### Proof.

Let ALG be any rational algorithm in the $D_{\infty}$-prophet inequality. If
ALG stops at some step $\tau\in[n]$, then by definition we have that
$X_{\tau}>D_{\infty}(\max_{j<\tau}X_{j})$, and thus
$\textsf{ALG}^{D_{\infty}}(X_{1},\ldots,X_{n})=\textsf{ALG}^{0}(X_{1},\ldots,X_{n})$.
Otherwise, if it stops at $\tau=n+1$, then its reward is
$\max_{i\in[n]}D_{\infty}(X_{i})=D_{\infty}(\max_{i\in[n]}X_{i})$, because
$D_{\infty}$-is non increasing.

On the other hand, let $\textsf{A}_{*}$ be the optimal dynamic programming
algorithm for the $D_{\infty}$-prophet inequality. At any step $i$, if
$X_{i}<D_{\infty}(\max_{j<i}X_{j})$, then stopping at $i$ gives a reward of
$D_{\infty}(\max_{j<i}X_{j})$, while by rejecting $X_{i}$, the final reward is
guaranteed to be at least $D_{\infty}(\max_{j<i}X_{j})$. Thus rejecting
$X_{i}$ 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
$\inf_{x>0}\frac{D_{\infty}(x)}{x}=0$, then there exist a sequence
$(s_{k})_{k\geq 1}$ such that
$\lim_{k\to\infty}\frac{D_{\infty}(s_{k})}{s_{k}}=0$.

Let $I=(F_{1},\ldots,F_{n})$ an instance of non-negative random variables with
finite expectation, and $X_{i}\sim F_{i}$ for all $i\in[n]$. Let ALG be a
rational algorithm for the $D_{\infty}$-prophet inequality and let us denote
$\tau$ its stopping time. Denoting $X^{*}:=\max_{i\in[n]}X_{i}$ and using
Lemma 3.1, we have for any constant $C>0$ that that

$\displaystyle\mathbb{E}[\textsf{ALG}^{D_{\infty}}(I)]$
$\displaystyle=\mathbb{E}[\textsf{ALG}^{0}(I)\mathbbm{1}_{\tau\leq
n}]+\mathbb{E}[D_{\infty}(X^{*})\mathbbm{1}_{\tau=n+1}]$
$\displaystyle\leq\mathbb{E}[\textsf{ALG}^{0}(I)]+\mathbb{E}[D_{\infty}(C)]+\mathbb{E}[D_{\infty}(X^{*})\mathbbm{1}_{X^{*}>C}]$
$\displaystyle\leq\sup_{\textsf{A}}\mathbb{E}[\textsf{A}^{0}(I)]+\mathbb{E}[D_{\infty}(C)]+\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>C}]\;.$
(16)

Let $k\geq 1$ a positive integer, $M$ a positive constant, and consider the
instance $I^{k}$ of random variables $(X_{1}^{k},\ldots,X_{n}^{k})$ with
$X_{i}^{k}\sim\frac{s_{k}}{M}X_{i}$ for all $i\in[n]$. We have that
$\textsf{OPT}(I^{k})=\frac{s_{k}}{M}\textsf{OPT}(I)$ and
$\mathbb{E}[\textsf{A}^{0}(I^{k})]=\frac{s_{k}}{M}\mathbb{E}[\textsf{A}^{0}(I)]$
for any algorithm A. Therefore, using Inequality (16) with $I^{k}$ instead of
$I$ and $C=\frac{s_{k}}{M}$, then dividing by $\textsf{OPT}(I^{k})$ gives that

$\displaystyle\textsf{CR}^{D_{\infty}}(\textsf{ALG})\leq\frac{\mathbb{E}[\textsf{ALG}^{D_{\infty}}(I^{k})]}{\mathbb{E}[\textsf{OPT}(I^{k})]}$
$\displaystyle\leq\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}+\frac{D_{\infty}(s_{k})}{\frac{s_{k}}{M}\mathbb{E}[\textsf{OPT}(I)]}+\frac{\mathbb{E}[\frac{s_{k}}{M}X^{*}\mathbbm{1}_{X^{*}>M}]}{\frac{s_{k}}{M}\mathbb{E}[\textsf{OPT}(I)]}$
$\displaystyle=\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}+\left(\frac{M}{\mathbb{E}[\textsf{OPT}(I)]}\right)\frac{D_{\infty}(s_{k})}{s_{k}}+\frac{\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>M}]}{\mathbb{E}[\textsf{OPT}(I)]}\;,$

and taking the limit $k\to\infty$, we obtain

$\textsf{CR}^{D_{\infty}}(\textsf{ALG})\leq\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}+\frac{\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>M}]}{\mathbb{E}[\textsf{OPT}(I)]}\;,$

and since $X^{*}$ has finite expectation, taking the limit $M\to\infty$ gives

$\textsf{CR}^{D_{\infty}}(\textsf{ALG})\leq\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}\;.$

Finally, taking the infimum over all instances, we obtain that

$\textsf{CR}^{D_{\infty}}(\textsf{ALG})\leq\sup_{\textsf{A}}\textsf{CR}^{0}(\textsf{A})\;.$

As in the proof of Corollary 2.1.1, permuting $\inf_{I}$ and
$\sup_{\textsf{A}}$ is possible because there is an algorithm (dynamic
programming) achieving the supremum for any instance. By Lemma 3.1, the
inequality above holds for in particular for the optimal dynamic programming
algorithm, which has a maximal competitive ratio. Therefore, the inequality
remains true for any other algorithm A, not necessarily rational. ∎

###  B.3 Proof of Proposition 3.3

###### Proof.

Let us place ourselves in any order model or in the IID model. Since
$\gamma=\inf_{x>0}\frac{D_{\infty}(x)}{x}$, there exists a sequence
$(s_{k})_{k\geq 1}$ of positive numbers such that
$\lim_{k\to\infty}\frac{D_{\infty}(s_{k})}{s_{k}}=\gamma$.

For the random variables $X_{1},\ldots,X_{n}$ taking values in $\\{0,a,b\\}$
a.s., in any order model, it is clear that the optimal decision when observing
a zero value is to reject it, and when observing the value $b$ is to accept
it. Let ALG be an algorithm satisfying this property and let $\tau$ be its
stopping time. If $\tau=n+1$ then necessarily $\max_{i\in[n]}X_{i}\neq b$, and
the reward of ALG in that case is $D_{\infty}(a)$ if $\max_{i\in[n]}X_{i}$ and
$0$ otherwise. In particular, ALG is rational in the $D_{\infty}$-prophet
inequality and we have by Lemma 3.1 that

$\displaystyle\mathbb{E}[\textsf{ALG}^{D_{\infty}}(I)]$
$\displaystyle=\mathbb{E}[\textsf{ALG}^{0}(I)]+\mathbb{E}[D_{\infty}(\max_{i\in[n]}X_{i})\mathbbm{1}_{\tau=n+1}]$
$\displaystyle=\mathbb{E}[\textsf{ALG}^{0}(I)]+D_{\infty}(a)\Pr(\tau=n+1,\max_{i\in[n]}X_{i}=a)\;.$
(17)

Consider now the instance $I^{k}$ of random variables
$(X_{1}^{k},\ldots,X_{n}^{k})$ where $X_{i}^{k}=\frac{s_{k}}{a}X_{i}$ for all
$i\in[n]$. $I^{k}$ satisfies the same assumptions as $I$ with $a^{k}=s_{k}$
and $b^{k}=\frac{s_{k}b}{a}$, and we have
$\mathbb{E}[\textsf{OPT}(I^{k})]=\frac{s_{k}}{a}\mathbb{E}[\textsf{OPT}(I)]$,
$\mathbb{E}[\textsf{ALG}^{0}(I^{k})]=\frac{s_{k}}{a}\mathbb{E}[\textsf{ALG}^{0}(I)]$
and $(\max_{i\in[n]}X^{k}_{i}=a^{k})\iff(\max_{i\in[n]}X_{i}=a)$. It follows
that

$\displaystyle\frac{\mathbb{E}[\textsf{ALG}^{D_{\infty}}(I^{k})]}{\mathbb{E}[\textsf{OPT}(I^{k})]}$
$\displaystyle=\frac{\mathbb{E}[\textsf{ALG}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}+\frac{D_{\infty}(s_{k})}{\frac{s_{k}}{a}\mathbb{E}[\textsf{OPT}(I)]}\Pr(\tau=n+1,\max_{i\in[n]}X_{i}=a)$
$\displaystyle=\frac{\mathbb{E}[\textsf{ALG}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}+\left(\frac{D_{\infty}(s_{k})}{s_{k}}\right)\frac{a}{\mathbb{E}[\textsf{OPT}(I)]}\Pr(\tau=n+1,\max_{i\in[n]}X_{i}=a)\;.$

Taking the limit $k\to\infty$ gives

$\displaystyle\textsf{CR}^{D_{\infty}}(\textsf{ALG})$
$\displaystyle\leq\frac{\mathbb{E}[\textsf{ALG}^{0}(I)]+\gamma
a\Pr(\tau=n+1,\max_{i\in[n]}X_{i}=a)}{\mathbb{E}[\textsf{OPT}(I)]}$
$\displaystyle=\frac{\mathbb{E}[\textsf{ALG}^{0}(I)]+\mathbb{E}[\gamma(\max_{i\in[n]}X_{i})\mathbbm{1}_{\tau=n+1}]}{\mathbb{E}[\textsf{OPT}(I)]}\;.$

ALG is also reasonable in the $\gamma$-prophet inequality. Therefore, using
Lemma 3.1, we deduce that

$\textsf{CR}^{D_{\infty}}(\textsf{ALG})\leq\frac{\mathbb{E}[\textsf{ALG}^{\gamma}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}\leq\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{\gamma}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}.$

This upper bound is true for the optimal dynamic programming algorithm, since
it rejects all zeros and accepts $b$, therefore the upper bound also holds for
any other algorithm. ∎

##  Appendix C The $\gamma_{\mathcal{D}}$-prophet inequality

###  C.1 Proof of Proposition 4.2

###### Proof.

For the lower bound, it suffices to consider the following trivial algorithm:
if $\alpha>\gamma$ then run $\textsf{A}_{\alpha}$, and if $\gamma>\alpha$ then
observe all the items then select the one with maximum value.

For the upper bound, let $I=(F_{1},\ldots,F_{n})$ be an instance of the
problem and $X_{i}\sim F_{i}$ for all $i$, and let
$\beta_{I}:=\sup_{\textsf{A}}\frac{\mathbb{E}[\textsf{A}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}$.
Let A be any algorithm, $\tau$ its stopping time, and
$Y_{\tau}=\max_{i<\tau}{X_{\pi(i)}}$, where $\pi$ is the observation order.
With the previous notations, we can write that
$\mathbb{E}[\textsf{A}^{\gamma}(I)]=\mathbb{E}[\max(X_{\pi(\tau)},\gamma
Y_{\tau})]$. For any $x,y\geq 0$, the application $\gamma\mapsto\max(x,\gamma
y)$ is convex on $[0,1]$, hence it can be upper bounded by
$(1-\gamma)x+\gamma\max(x,y)$. Therefore

$\displaystyle\mathbb{E}[\textsf{A}^{\gamma}(I)]$
$\displaystyle\leq(1-\gamma)\mathbb{E}[X_{\pi(\tau)}]+\gamma\mathbb{E}[\max(X_{\pi(\tau)},Y_{\tau})]$
$\displaystyle\leq(1-\gamma)\mathbb{E}[\textsf{A}^{0}(I)]+\gamma\mathbb{E}[\textsf{OPT}(I)]$
$\displaystyle\leq\big{(}(1-\gamma)\beta_{I}+\gamma\big{)}\mathbb{E}[\textsf{OPT}(I)]\;.$

Therefore,
$\textsf{CR}^{\gamma}(\textsf{ALG})\leq((1-\gamma)\beta_{I}+\gamma)$. Taking
the infimum over all the instances $I$ gives the result. Indeed, if we denote
$\textsf{A}_{*}$ the optimal dynamic programming algorithm for the standard
prophet inequality, then

$\inf_{I}\beta_{I}=\inf_{I}\frac{\mathbb{E}[\textsf{A}_{*}^{0}(I)]}{\mathbb{E}[\textsf{OPT}(I)]}=\textsf{CR}^{0}(\textsf{A}_{*})\leq\beta\;.$

∎

###  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 $\varepsilon\in(0,1-\gamma)$, and let
$a=\frac{1}{1-(1-\varepsilon)\gamma}$ (such that $1+(1-\varepsilon)\gamma
a=a$). Let $X_{1},X_{2}$ the two random variables defined by $X_{1}=a$ almost
surely and

$X_{2}=\left\\{\begin{array}[]{ll}\frac{1}{\varepsilon}&\mbox{w.p.
}\varepsilon\\\ 0&\mbox{w.p. }1-\varepsilon\end{array}\right.\;.$

Stopping at the first step gives a reward of $a$, while stopping at the second
step gives

$\mathbb{E}[\max(\gamma
a,X_{2})]=\varepsilon\times\frac{1}{\varepsilon}+(1-\varepsilon)\times\gamma
a=1+(1-\varepsilon)\gamma a=a\;,$

hence the expected output of any algorithm is exactly equal to $a$. On the
other hand

$\mathbb{E}[\max(X_{1},X_{2})]=1+(1-\varepsilon)a\;,$

and we deduce that, for any algorithm ALG for the $\gamma$-prophet inequality,
we have

$\textsf{CR}(\textsf{ALG})\leq\frac{\mathbb{E}[\textsf{ALG}(X_{1},X_{2})]}{\mathbb{E}[\max(X_{1},X_{2})]}=\frac{a}{1+(1-\varepsilon)a}\;,$

and this is true for any $\varepsilon\in(0,1-\gamma)$, thus taking
$\varepsilon\to 0$ gives

$\textsf{CR}(\textsf{ALG})\leq\frac{\frac{1}{1-\gamma}}{1+\frac{1}{1-\gamma}}=\frac{1}{2-\gamma}\;.$

##### Lower bound

Consider an algorithm with an acceptance threshold $\theta$, i.e. that accepts
the first value larger than $\theta$. Let $I=(F_{1},\ldots,F_{n})$ be any
instance, such that $X_{i}\sim F_{i}$ for all $i$, and let us define
$X^{*}=\max_{i\in[n]}X_{i}$ and $p=\Pr(X^{*}\leq\theta)$. In the classical
prophet inequality, if no value is larger than $\theta$ then the reward of the
algorithm is zero, and we have the classical lower bound

$\mathbb{E}[\textsf{ALG}^{0}(I)]\geq(1-p)\theta+p\mathbb{E}[(X^{*}-\theta)_{+}],$

For the $\gamma$-prophet, if no value is larger than $\theta$ (i.e
$X^{*}\leq\theta$), then the algorithm gains $\gamma X^{*}$ instead of $0$.
Therefore, it holds that

$\displaystyle\mathbb{E}[\textsf{ALG}^{\gamma}(I)]$
$\displaystyle=\mathbb{E}[\textsf{ALG}^{0}(I)]+\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]$
$\displaystyle\geq(1-p)\theta+p\mathbb{E}[(X^{*}-\theta)_{+}]+\gamma\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]$
$\displaystyle=(1-p)\theta+p\mathbb{E}[(X^{*}-\theta)\mathbbm{1}_{X^{*}>\theta}]+\gamma\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]$
$\displaystyle=(1-p)\theta+p(\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]-(1-p)\theta)+\gamma\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]$
$\displaystyle=(1-p)^{2}\theta+p\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]+\gamma\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]\;,$

and observing that

$\theta=\frac{\mathbb{E}[\theta\mathbbm{1}_{X^{*}\leq\theta}]}{p}\geq\frac{\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]}{p}\;,$

we deduce the lower bound

$\displaystyle\mathbb{E}[\textsf{ALG}^{\gamma}(I)]$ $\displaystyle\geq
p\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]+\left(\gamma+\frac{(1-p)^{2}}{p}\right)\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]$
$\displaystyle\geq\min\left\\{p,\gamma+\frac{(1-p)^{2}}{p}\right\\}\mathbb{E}[X^{*}]\;.$

The right term is maximized for $p$ satisfying $p=\gamma+\frac{(1-p)^{2}}{p}$,
that leads to

$\displaystyle p=\gamma+\frac{(1-p)^{2}}{p}$ $\displaystyle\iff p^{2}=\gamma
p+1-2p+p^{2}$ $\displaystyle\iff p=\frac{1}{2-\gamma}\;.$

Hence, by choosing a threshold $\theta$ satisfying
$\Pr(X^{*}\leq\theta)=\frac{1}{2-\gamma}$ we obtain a competitive ratio of at
least $\frac{1}{2-\gamma}$. ∎

###  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 $a>0$, and let $X_{1},\ldots,X_{n+1}$ be independent random variables such
that $X_{n+1}=a$ a.s. and for $1\leq i\leq n$

$X_{i}\sim\left\\{\begin{array}[]{ll}n&\mbox{w.p. }\frac{1}{n^{2}}\\\
0&\mbox{w.p. }1-\frac{1}{n^{2}}\end{array}\right.\;.$

Any reasonable algorithm skips zero values and stops when observing the value
$n$. The only strategic decision to make is thus to stop or not when observing
$X_{n+1}=a$. By analyzing the dynamic programming solution
$\textsf{ALG}_{\star}$ we obtain that the optimal decision rule is to skip $a$
if it is observed before a certain step $j$, and select it otherwise. The step
$j$ corresponds to the time when the expectation of the future reward is less
than $a$. Let $\pi$ be the random order in which the variables are observed.
Then, if $\pi^{-1}(n+1)<j$, i.e. if the value $a$ is observed before time $j$,
$X_{n=1}$ is not selected. The output of this algorithm is hence $n$ if at
least one random variable equals $n$, and $\gamma a$ otherwise. This leads to

$\displaystyle\mathbb{E}[\textsf{ALG}^{\gamma}_{\star}(X)\mid\pi^{-1}(n+1)<j]$
$\displaystyle=n\left(1-\left(1-\frac{1}{n^{2}}\right)^{n}\right)+\gamma
a\left(1-\frac{1}{n^{2}}\right)^{n}$ $\displaystyle\leq 1+\gamma a\;,$

where we used the inequality $\left(1-\frac{1}{n^{2}}\right)^{n}\geq
1-\frac{1}{n}$. On the other hand, if $\pi^{-1}(n)\geq j$, then $a$ is
selected if the value $n$ has not been observed before it, hence for any
$i\geq j$ we have

$\displaystyle\mathbb{E}[\textsf{ALG}^{\gamma}_{\star}(X)\mid\pi^{-1}(n+1)=i]$
$\displaystyle=n\left(1-\left(1-\frac{1}{n^{2}}\right)^{i-1}\right)+a\left(1-\frac{1}{n^{2}}\right)^{i-1}$
$\displaystyle\leq\frac{i-1}{n}+a\;,$

we deduce that

$\displaystyle\mathbb{E}[\textsf{ALG}^{\gamma}_{\star}(X)]$
$\displaystyle\leq(1+\gamma a)\Pr(\pi^{-1}(n)\leq
j-1)+\sum_{i=j}^{n+1}\left(\frac{i-1}{n}+a\right)\Pr(\pi^{-1}(n)=i)$
$\displaystyle=\frac{j-1}{n+1}(1+\gamma
a)+\frac{1}{n+1}\sum_{i=j}^{n+1}\left(\frac{i-1}{n}+a\right)$
$\displaystyle=(1-(1-\gamma)a)\frac{j}{n}-\frac{1}{2}\left(\frac{j}{n}\right)^{2}+\frac{1}{2}+a+o(1)$
$\displaystyle\leq 1+2\gamma a+(1-\gamma)^{2}a^{2}+o(1)\;,$

where the last inequality is obtained by maximizing over $j/n$. Finally, we
directly obtain that

$\displaystyle\mathbb{E}[\max_{i}X_{i}]$
$\displaystyle=n\left(1-\left(1-\frac{1}{n^{2}}\right)^{n}\right)+a\left(1-\frac{1}{n^{2}}\right)^{n}$
$\displaystyle=1+a+o(1)\;,$

so for any algorithm ALG we obtain that

$\textsf{CR}^{\gamma}(\textsf{ALG})\leq\textsf{CR}^{\gamma}(\textsf{ALG}_{\star})\leq\frac{1+2\gamma
a+(1-\gamma)^{2}a^{2}}{1+a}\;.$

The function above is minimized for $a=\sqrt{\frac{3-\gamma}{1-\gamma}}-1$,
which translates to

$\textsf{CR}^{\gamma}(\textsf{ALG})\leq(1-\gamma)^{3/2}(\sqrt{3-\gamma}-\sqrt{1-\gamma})+\gamma\;.$

##### Lower bound

We still denote by $I=(F_{1},\ldots,F_{n})$ the input instance and $X_{i}\sim
F_{i}$ for all $i\in[n]$. Let ALG be the algorithm with single threshold
$\theta$, then it is direct that

$\textsf{ALG}^{\gamma}(I)=\textsf{ALG}^{0}(I)+\gamma
X^{*}\mathbbm{1}_{X^{*}<\theta}\;.$ (18)

We start by giving a lower bound on $\mathbb{E}[\textsf{ALG}^{0}]$. We use
from [Correa et al., 2021c] (Theorem 2.1) that for any $x<\theta$ it holds
that

$\Pr(\textsf{ALG}^{0}(I)\geq
x)=\Pr(\textsf{ALG}^{0}(I)\geq\theta)=\Pr(X^{*}\geq\theta)=1-p\;,$

and for $x\geq\theta$ it holds that

$\Pr(\textsf{ALG}^{0}(I)\geq x)\geq\frac{1-p}{-\log p}\Pr(X^{*}\geq x)\;,$

from which we deduce that

$\displaystyle\mathbb{E}[\textsf{ALG}^{0}(I)]$
$\displaystyle=\int_{0}^{\infty}\Pr(\textsf{ALG}^{0}(I)\geq x)dx$
$\displaystyle\geq(1-p)\theta+\frac{1-p}{-\log
p}\int_{\theta}^{\infty}\Pr(X^{*}\geq x)dx\;.$ (19)

On the other hand, we obtain that

$\displaystyle\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}<\theta}]$
$\displaystyle=\int_{0}^{\infty}\Pr(X^{*}\mathbbm{1}_{X^{*}<\theta}\geq
x)dx=\int_{0}^{\infty}\Pr(x\leq X^{*}<\theta)dx$
$\displaystyle=\int_{0}^{\theta}(\Pr(X^{*}>x)-\Pr(X^{*}\geq\theta))dx$
$\displaystyle=\int_{0}^{\theta}\Pr(X^{*}>x)dx-(1-p)\theta\;.$ (20)

Using (18), (19) and (20) we deduce that

$\displaystyle\mathbb{E}[\textsf{ALG}^{\gamma}(I)]$
$\displaystyle\geq(1-p)\theta+\frac{1-p}{-\log
p}\int_{\theta}^{\infty}\Pr(X^{*}\geq
x)dx+\gamma\int_{0}^{\theta}\Pr(X^{*}\geq x)dx-\gamma(1-p)\theta$
$\displaystyle=(1-\gamma)(1-p)\theta+\gamma\int_{0}^{\theta}\Pr(X^{*}\geq
x)dx+\frac{1-p}{-\log p}\int_{\theta}^{\infty}\Pr(X^{*}\geq x)dx$
$\displaystyle\geq((1-\gamma)(1-p)+\gamma)\int_{0}^{\theta}\Pr(X^{*}\geq
x)dx+\frac{1-p}{-\log p}\int_{\theta}^{\infty}\Pr(X^{*}\geq x)dx$
$\displaystyle\geq\min\left\\{(1-\gamma)(1-p)+\gamma\,,\,\frac{1-p}{-\log
p}\right\\}\left(\int_{0}^{\theta}\Pr(X^{*}\geq
x)dx+\int_{\theta}^{\infty}\Pr(X^{*}\geq x)dx\right)$
$\displaystyle=\min\left\\{1-(1-\gamma)p\,,\,\frac{1-p}{-\log
p}\right\\}\mathbb{E}[X^{*}]\;.$

Finally, choosing $p=p_{\gamma}$ gives the result. ∎

####  C.3.2 Proof of Corollary 4.4.1

###### Proof.

For $p=\frac{1/e}{1-(1-1/e)\gamma}$, we have immediately that

$1-(1-\gamma)p=1-\frac{(1-\gamma)/e}{1-(1-1/e)\gamma}\;,$

and $p\in[1/e,1]$ for any $\gamma\in[0,1]$. Since the function
$x\mapsto(1-x)/\log(1/x)$ is concave, we can lower bound it on $[1/e,1]$ by
$x\mapsto 1-1/e+\frac{x-1/e}{e-1}$, which is the line intersecting it in $1/e$
and $1$. Therefore we have

$\frac{1-p}{-\log p}\geq
1-1/e+\frac{p-1/e}{e-1}=1-\frac{(1-\gamma)/e}{1-(1-1/e)\gamma}\;.$

Finally, using the previous theorem, this choice of $p$ guarantees a
competitive ratio of at least

$\min\left\\{1-(1-\gamma)p\,,\,\frac{1-p}{-\log
p}\right\\}=1-\frac{(1-\gamma)/e}{1-(1-1/e)\gamma}\;.$

∎

###  C.4 Proofs for the IID model

#### Proof of Lemma 4.5

###### Proof of Lemma 4.5.

Let $F$ be the cumulative distribution function of $X_{1}$, $a>0$ and ALG the
algorithm with single threshold $\theta$ such that $1-F(\theta)=\frac{a}{n}$.
We denote $X^{*}=\max_{i\in[n]}X_{i}$. As in the previous proofs, we will
begin by lower bounding $\textsf{ALG}^{0}(F,n)$. For any $i\in[n]$, ALG stops
at step $i$ if and only if $X_{i}>\theta$ and all the previous items were
rejected, i.e. $X_{j}\leq\theta$ for all $j<i$. Thus we can write

$\displaystyle\mathbb{E}[\textsf{ALG}^{0}(F,n)]$
$\displaystyle=\mathbb{E}\Big{[}\sum_{i=1}^{n}(X_{i}\mathbbm{1}_{X_{i}>\theta})\mathbbm{1}_{\forall
j<i:X_{j}\leq\theta}\Big{]}$
$\displaystyle=\sum_{i=1}^{n}F(\theta)^{i-1}\mathbb{E}[X_{i}\mathbbm{1}_{X_{i}>\theta}]$
$\displaystyle=\frac{1-F(\theta)^{n}}{1-F(\theta)}\mathbb{E}[X_{1}\mathbbm{1}_{X_{1}>\theta}]$
$\displaystyle=\frac{1-F(\theta)^{n}}{a}\times
n\mathbb{E}[X_{1}\mathbbm{1}_{X_{1}>\theta}]\;,$ (21)

where the second equality is true by the independence of the random variables
$(X_{i})_{i}$. On the other hand, we can upper bound
$\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]$ as follows

$\displaystyle\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]$
$\displaystyle\leq\Pr(X^{*}>\theta)\theta+\mathbb{E}[(X^{*}-\theta)_{+}]$
$\displaystyle\leq\Pr(X^{*}>\theta)\theta+\mathbb{E}\Big{[}\sum_{i=1}^{n}(X_{i}-\theta)_{+}\Big{]}$
$\displaystyle=\Pr(X^{*}>\theta)\theta+n\big{(}\mathbb{E}[X_{1}\mathbbm{1}_{X_{1}>\theta}]-\Pr(X_{1}>\theta)\theta\big{)}$
$\displaystyle=(1-F(\theta)^{n}-a)\theta+n\mathbb{E}[X_{1}\mathbbm{1}_{X_{1}>\theta}]\;.$

Using the definition of $\theta$, the independence of $(X_{i})_{i}$ then
Bernoulli’s inequality we have that

$\Pr(X^{*}>\theta)=1-F(\theta)^{n}=1-\left(1-\frac{a}{n}\right)^{n}\leq
1-(1-n\times\frac{a}{n})=a\;,$

and observing that
$\theta=\frac{\mathbb{E}[\theta\mathbbm{1}_{X^{*}\leq\theta}]}{F(\theta)^{n}}\geq\frac{\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]}{F(\theta)^{n}}$,
we deduce that

$\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]\leq-\left(1-\frac{1-a}{F(\theta)^{n}}\right)\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]+n\mathbb{E}[X_{1}\mathbbm{1}_{X_{1}>\theta}]\;.$

by substituting into (21), we obtain

$\mathbb{E}[\textsf{ALG}^{0}(F,n)]\geq\frac{1-F(\theta)^{n}}{a}\left(\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]+\left(1-\frac{1-a}{F(\theta)^{n}}\right)\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}\leq\theta}]\right)\;.$

Finally, the reward in the $\gamma$-prophet inequality is

$\displaystyle\mathbb{E}[\textsf{ALG}^{\gamma}(F,n)]$
$\displaystyle=\mathbb{E}[\textsf{ALG}^{0}(F,n)]+\gamma\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}<\theta}]$
$\displaystyle\geq\frac{1-F(\theta)^{n}}{a}\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}>\theta}]+\left(\frac{1-F(\theta)^{n}}{a}\left(1-\frac{1-a}{F(\theta)^{n}}\right)+\gamma\right)\mathbb{E}[X^{*}\mathbbm{1}_{X^{*}<\theta}]$
$\displaystyle\geq\min\left\\{\frac{1-F(\theta)^{n}}{a},\frac{1-F(\theta)^{n}}{a}\left(1-\frac{1-a}{F(\theta)^{n}}\right)+\gamma\right\\}\mathbb{E}[X^{*}]\;.$

The equation
$\frac{1-F(\theta)^{n}}{a}=\frac{1-F(\theta)^{n}}{a}\left(1-\frac{1-a}{F(\theta)^{n}}\right)+\gamma$,
is equivalent to

$\left(\frac{1}{(1-a/n)^{n}}-1\right)\left(\frac{1}{a}-1\right)=\gamma\;,$
(22)

and for any $n\geq 2$ the function
$a\mapsto\big{(}\frac{1}{(1-a/n)^{n}}-1\big{)}\big{(}\frac{1}{a}-1\big{)}$ is
decreasing on $(0,1]$ and goes from $1$ to $0$, thus Equation (22) admits a
unique solution $a_{n,\gamma}$, and taking $a=a_{n,\gamma}$ guarantees a
reward of
$\frac{1-F(\theta)^{n}}{a_{n,\gamma}}\mathbb{E}[X^{*}]=\frac{1-(1-\frac{a_{n,\gamma}}{n})^{n}}{a_{n,\gamma}}\mathbb{E}[X^{*}]$.
∎

#### Proof of Theorem 4.6

###### Proof.

We first prove the upper bound, and then we give the single-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 $X_{1},\ldots,X_{n}$ be IID random variables with the
following the distribution $F$ defined by

$X_{1}\sim\left\\{\begin{array}[]{ll}n&\mbox{w.p. }\frac{1}{n^{2}}\\\
a&\mbox{w.p. }\frac{x}{n}\\\ 0&\mbox{w.p.
}1-\frac{x}{n}-\frac{1}{n^{2}}\end{array}\right.\;.$

A reasonable algorithm would always reject the value $0$ and accept the value
$n$. However, if the algorithm faces an item with value $a$, it must decide to
either accept it, or reject it with a guarantee of recovering $\gamma a$ at
the end. By analyzing the dynamic programming algorithm
$\textsf{ALG}_{\star}$, we find that the optimal decision is to reject $a$ if
observed before a certain step $j$, and accept it otherwise. Let us denote
$\tau$ the stopping time of $\textsf{ALG}_{\star}$. By convention, we write
$\tau=n+1$ to say that no value was selected by the algorithm, in which case
the reward is $\gamma\max_{i\in[n]}X_{i}$.
If $\tau\leq j-1$ then necessarily $X_{\tau}=n$, because
$\textsf{ALG}_{\star}$ rejects the value $a$ if it is met before step $j$, and
if $\tau=n+1$ then $\max_{i\in[n]}X_{i}\in\\{0,a\\}$, because otherwise the
algorithm would have selected the value $n$ and stopped earlier. It follows
that the expected output of $\textsf{ALG}_{\star}$ on this instance is

$\displaystyle\mathbb{E}[\textsf{ALG}_{\star}^{\gamma}(F,n)]=$ $\displaystyle
n\Pr(\tau<j)+\sum_{i=j}^{n}\mathbb{E}[X_{i}\mid\tau=i]\Pr(\tau=i)$
$\displaystyle+\gamma a\Pr(\tau=n+1,\max_{i\in[n]}X_{i}=a)\;.$ (23)

Let us now compute the terms above one by one.

$\Pr(\tau<j)=\Pr(\exists
i\in[j-1]:X_{i}=n)=1-\left(1-\frac{1}{n^{2}}\right)^{j-1}\leq\frac{j}{n^{2}}\;,$

where we used Bernoulli’s inequality $(1-1/n^{2})^{j-1}\geq
1-\frac{j-1}{n^{2}}>1-\frac{j}{n^{2}}$. For $i\in\\{j,\ldots,n\\}$,
$\textsf{ALG}_{\star}$ stops at $i$ if $X_{i}\in\\{a,n\\}$ and if it has not
stopped before, i.e. $X_{k}\in\\{0,a\\}$ for all $k<j$ and $X_{k}=0$ for all
$k\in\\{j,\ldots,i-1\\}$, hence

$\displaystyle\Pr(\tau=i)$ $\displaystyle=\Pr(\forall k<j:X_{k}\neq n\text{
and }\forall j\leq k\leq i-1:X_{k}=0\text{ and }X_{i}\neq 0)$
$\displaystyle=\left(1-\frac{1}{n^{2}}\right)^{j-1}\left(1-\frac{x}{n}-\frac{1}{n^{2}}\right)^{i-j}\Pr(X_{i}\neq
0)$ $\displaystyle\leq\left(1-\frac{x}{n}\right)^{i-j}\Pr(X_{i}\neq 0)\;,$

the second equality is true by independence, and the last inequality holds
because $1-\frac{1}{n^{2}}\leq 1$ and $1-\frac{x}{n}-\frac{1}{n^{2}}\leq
1-\frac{x}{n}$. By independence of the variables $(X_{k})_{k}$, we also have
that

$\mathbb{E}[X_{i}\mid\tau=i]=\mathbb{E}[X_{i}\mid X_{i}\neq
0]=\frac{\mathbb{E}[X_{i}]}{\Pr(X_{i}\neq 0)}=\frac{1+ax}{n\Pr(X_{i}\neq
0)}\;.$

Finally, the event $(\tau=n+1,\max_{i\in[n]}X_{i}=a)$ is equivalent
$(\max_{i\in[j-1]}X_{i}=a,\forall k\geq j:X_{k}=0)$. In fact, the algorithm
does not stop before $n+1$ if and only if $X_{k}\neq n$ for all $k<j$ and
$X_{k}=0$ for all $j\leq k\leq n$, and under these conditions, it holds that
$\max_{i\in[n]}X_{i}=\max_{i\in[j-1]}X_{i}$. Therefore

$\displaystyle\Pr(\tau=n+1,\max_{i\in[n]}X_{i}=a)$
$\displaystyle=\Pr(\max_{i\in[j-1]}X_{i}=a,\forall k\geq j:X_{k}=0)$
$\displaystyle\leq\Pr(\max_{i\in[j-1]}X_{i}\neq 0)\Pr(\forall k\geq
j:X_{k}=0)$
$\displaystyle=\left(1-\left(1-\frac{x}{n}-\frac{1}{n^{2}}\right)^{j-1}\right)\left(1-\frac{x}{n}-\frac{1}{n^{2}}\right)^{n-j}$
$\displaystyle=\big{(}1-e^{-\frac{xj}{n}}+o(1)\big{)}\big{(}e^{-x+\frac{xj}{n}}+o(1)\big{)}$
$\displaystyle=\big{(}e^{\frac{xj}{n}}-1\big{)}e^{-x}+o(1)\;.$

All in all, we obtain by substituting into 23 that

$\displaystyle\mathbb{E}[\textsf{ALG}_{\star}^{\gamma}(F,n)]$
$\displaystyle\leq\frac{j}{n}+\left(\frac{1+ax}{n}\right)\sum_{i=j}^{n}\left(1-\frac{x}{n}\right)^{i-j}+\gamma
ae^{-x}\big{(}e^{\frac{xj}{n}}-1\big{)}+o(1)$
$\displaystyle=\frac{j}{n}+\left(\frac{1+ax}{n}\right)\frac{1-(1-x/n)^{n-j+1}}{x/n}+\gamma
ae^{-x}\big{(}e^{\frac{xj}{n}}-1\big{)}+o(1)$
$\displaystyle=\frac{j}{n}+\left(\frac{1}{x}+a\right)\big{(}1-e^{-x+\frac{xj}{n}}+o(1)\big{)}+\gamma
ae^{-x}\big{(}e^{\frac{xj}{n}}-1\big{)}+o(1)$
$\displaystyle=\frac{j}{n}-\Big{[}\big{(}\tfrac{1}{x}+(1-\gamma)a\big{)}\Big{]}e^{\frac{xj}{n}}+\frac{1}{x}+a-\gamma
ae^{-x}+o(1)$
$\displaystyle\leq\max\limits_{s>0}\left\\{s-\Big{[}\big{(}\tfrac{1}{x}+(1-\gamma)a\big{)}\Big{]}e^{xs}\right\\}+\frac{1}{x}+(1-\gamma
e^{-x})a+o(1)$
$\displaystyle=-\frac{1}{x}\big{(}\log(1+(1-\gamma)ax)+1-x\big{)}+\frac{1}{x}+(1-\gamma
e^{-x})a+o(1)$ $\displaystyle=-\frac{1}{x}\log(1+(1-\gamma)ax)+1+(1-\gamma
e^{-x})a+o(1)\;.$

On the other hand, we have that

$\Pr(\max_{i\in[n]}X_{i}=n)=1-\left(1-\frac{1}{n^{2}}\right)^{n}=\frac{1}{n}+o(1/n)\;,$
$\Pr(\max_{i\in[n]}X_{i}=0)=\left(1-\frac{x}{n}-\frac{1}{n^{2}}\right)=e^{-x}+o(1)\;,$
$\Pr(\max_{i\in[n]}X_{i}=a)=1-\Pr(\max_{i\in[n]}X_{i}=0)-\Pr(\max_{i\in[n]}X_{i}=n)=1-e^{-x}+o(1)\;,$

therefore, the expected maximum value is

$\displaystyle\mathbb{E}[\max_{i\in[n]}X_{i}]$
$\displaystyle=n\Pr(\max_{i\in[n]}X_{i}=n)+a\Pr(\max_{i\in[n]}X_{i}=a)$
$\displaystyle=1+\big{(}1-e^{-x}\big{)}a+o(1)\;.$

We deduce that

$\displaystyle\frac{\mathbb{E}[\textsf{ALG}_{\star}^{\gamma}(F,n)]}{\mathbb{E}[\max_{i\in[n]}X_{i}]}$
$\displaystyle\leq\frac{-\frac{1}{x}\log(1+(1-\gamma)ax)+1+(1-\gamma
e^{-x})a}{1+\big{(}1-e^{-x}\big{)}a}+o(1)$
$\displaystyle=1-\frac{\frac{1}{x}\log(1+(1-\gamma)ax)-(1-\gamma)ae^{-x}}{1+\big{(}1-e^{-x}\big{)}a}+o(1)\;.$

Consequently, for any $a,x>0$ and for any algorithm ALG we have

$\displaystyle\textsf{CR}(\textsf{ALG})$
$\displaystyle\leq\textsf{CR}(\textsf{ALG}_{\star})$
$\displaystyle\leq\lim_{n\to\infty}\frac{\mathbb{E}[\textsf{ALG}_{\star}^{\gamma}(F,n)]}{\mathbb{E}[\max_{i\in[n]}X_{i}]}$
$\displaystyle\leq
1-\frac{\log(1+(1-\gamma)ax)-(1-\gamma)axe^{-x}}{x+\big{(}1-e^{-x}\big{)}ax}\;.$

In particular, for $x=2$ and $a=\frac{1-\gamma/2}{1-\gamma}$ we find that

$\displaystyle\textsf{CR}(\textsf{ALG})$ $\displaystyle\leq
1-\frac{\log(3-\gamma)-(2-\gamma)e^{-2}}{2+\frac{2-\gamma}{1-\gamma}(1-e^{-2})}$
$\displaystyle=1-(1-\gamma)\frac{e^{2}\log(3-\gamma)-(2-\gamma)}{2(2e^{2}-1)-\gamma(3e^{2}-1)}$
$\displaystyle=U(\gamma)\;.$

This proves the upper bound stated in the theorem, and we can verify that it
is increasing, and satisfies $U(0)=\frac{4-\log 3}{4-2/e^{2}}$ $U(1)=1$

##### 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-\gamma)p_{\gamma})$, where $p_{\gamma}$, first
introduced in Theorem 4.4, is the unique solution of the equation
$(1-(1-\gamma)p)=\frac{1-p}{-\log p}$, which is equivalent to
$\big{(}\frac{1}{p}-1\big{)}\big{(}\frac{1}{\log(1/p)}-1\big{)}=\gamma$.

Let $a_{\gamma}=-\log(p_{\gamma})$. It follows from the definition of
$p_{\gamma}$ that $a_{\gamma}$ is the unique solution of the equation
$(e^{a}-1)(\frac{1}{a}-1)=\gamma$. For any $n\geq 2$ and $x\geq 0$ we have
that $(1-x/n)^{n}\leq e^{-x}$, hence, by definition of $a_{n,\gamma}$ and
$a_{\gamma}$

$\displaystyle\left(\frac{1}{e^{-a_{n,\gamma}}}-1\right)\left(\frac{1}{a_{n,\gamma}}-1\right)$
$\displaystyle\leq\left(\frac{1}{(1-\frac{a_{n,\gamma}}{n})^{n}}-1\right)\left(\frac{1}{a_{n,\gamma}}-1\right)$
$\displaystyle=\gamma$
$\displaystyle=\left(\frac{1}{e^{-a_{\gamma}}}-1\right)\left(\frac{1}{a_{\gamma}}-1\right)\;.$
(24)

Moreover, the function $x\mapsto(e^{x}-1)(1/x-1)$ is decreasing on $(0,1)$. In
fact its derivative at any point $x\in(0,1)$ is

$\displaystyle\frac{d}{dx}\left[\left(\frac{1}{e^{-x}}-1\right)\left(\frac{1}{x}-1\right)\right]$
$\displaystyle=\left(\frac{1}{x}-1\right)e^{x}-\frac{e^{x}-1}{x^{2}}$
$\displaystyle=\frac{1}{x^{2}}\left(1-x^{2}-(1-x)e^{x}\right)$
$\displaystyle=\frac{1-x}{x^{2}}(1+x-e^{x})<0\;.$

It follows from (24) that $a_{\gamma}\leq a_{n,\gamma}$. Finally, given that
$x\mapsto\frac{1-e^{-x}}{x}$ is non-increasing on $(0,1]$, we deduce that

$\frac{1-(1-\frac{a_{n,\gamma}}{n})^{n}}{a_{n,\gamma}}\geq\frac{1-e^{-a_{n,\gamma}}}{a_{n,\gamma}}\geq\frac{1-e^{-a_{\gamma}}}{a_{\gamma}}\;.$

We deduce that the competitive ratio of the algorithm described in Theorem 4.6
is at least
$\frac{1-e^{-a_{\gamma}}}{a_{\gamma}}=\frac{1-p_{\gamma}}{\log(1/p_{\gamma})}=1-(1-\gamma)p_{\gamma}$.

∎

##  Appendix 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 $j$ steps with a probability
$p_{j}$, this is modeled by $D_{j}(x)=\xi_{j}x$ with $\xi_{j}$ a Bernoulli
random variable with parameter $p_{j}$. We explain in this section how the
definitions and our results extend to this case.

######  Definition D.1 (Random process).

Let $\mathcal{X}$ is a non-empty set. A random process o $\mathcal{X}$ is a
collection of random variables $\\{Z_{x}\\}_{x\in\mathcal{X}}$. Two random
processes $\mathcal{Z}=\\{Z_{x}\\}_{x\in\mathcal{X}}$ and
$\mathcal{Z}^{\prime}=\\{Z^{\prime}_{x}\\}_{x\in\mathcal{X}^{\prime}}$ are
independent if any finite sub-process of $\mathcal{Z}$ is independent of any
sub-process of $\mathcal{Z}^{\prime}$. For simplicity, let us say that the
random processes
$\\{Z^{1}_{x}\\}_{x\in\mathcal{X}^{1}},\ldots,\\{Z^{m}_{x}\\}_{x\in\mathcal{X}^{m}}$
are mutually independent if, for any
$x_{1}\in\mathcal{X}_{1},\ldots,x_{m}\in\mathcal{X}_{m}$, the random variables
$Z^{1}_{x_{1}},\ldots,Z^{m}_{x_{m}}$ are mutually independent.

######  Definition D.2 (Random decay functions).

Let $\mathcal{D}=(D_{1},D_{2},\ldots)$ be a sequence of mutually independent
random processes. We say that $\mathcal{D}$ is a sequence of random decay
functions if

  1. 1.

$\Pr(D_{j}(x)\notin[0,x])=0$ for any $x\geq 0$ and $j\geq 1$,

  2. 2.

$j\in\mathbb{N}_{\geq 1}\mapsto\Pr(D_{j}(x)\geq a)$ is non-increasing for any
$x,a\geq 0$,

  3. 3.

$x\geq 0\mapsto\Pr(D_{j}(x)\geq a)$ is non-decreasing for any
$j\in\mathbb{N}_{\geq 1}$ and $a\geq 0$.

The second condition asserts that the random variable $D_{j-1}(x)$ has first-
order stochastic dominance over $D_{j}(x)$. Along with the first condition,
reflect that the distributions of the rejected values become progressively
smaller. The last condition indicates that for any integer $j\geq 1$ and non-
negative real numbers $x<y$, $D_{j}(y)$ has a first-order stochastic dominance
over $D_{j}(x)$, which means that, as the value of $x$ increases, so does the
potential recovered value after $j$ steps.

##### The decision-maker

In the $\mathcal{D}$-prophet inequality with deterministic decay functions, we
assumed that the decision-maker has full knowledge of the functions
$D_{1},D_{2}\ldots$. In the randomized setting, we assume instead that the
decision-maker knows the distributions of the decay functions, i.e. knows the
distribution of the random variables $D_{j}(x)$ for all $x\geq 0$ and $j\geq
1$. However, they do not observe their values until they decide to stop. The
online selection process is therefore as follows: the algorithm knows
beforehand the distributions of the decay functions, then at each step, it
observes a new item with value $X_{i}$, and decides to stop or continue. Once
they decide to stop at some time $\tau$, they observe the values
$D_{1}(X_{\tau-1}),\ldots,D_{\tau}(X_{1})$ and then they choose the maximal
one. As a consequence, the stopping time $\tau$ is independent of the
randomness induced by the decay functions. As in the deterministic case, the
expected reward of any algorithm ALG can be written as

$\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(X_{1},\ldots,X_{n})]=\mathbb{E}[\max_{0\leq
i\leq\tau-1}\\{D_{i}(X_{\tau-i})\\}]\;.$

##### The limit decay

A key result in our paper is the reduction of the problem to the case where
all the decay functions are identical, and we prove this reduction by
considering the pointwise limit of the decay functions. In the case of random
decay functions, instead of the pointwise convergence, it holds for all $x\geq
0$ that the random variables $(D_{j}(x))_{j}$ converge in distribution to some
random variable $D_{\infty}(x)$. In fact, for any $x\geq 0$ and $a\geq 0$, the
sequence $(\Pr(D_{j}(x)\geq a))_{j\geq 1}$ is non-increasing and non-negative,
thus it converges to some constant $G(x,a)$. Given that
$x\mapsto\Pr(D_{j}(x)\geq a)$ is non-decreasing for any $j$, we obtain by
taking the limit $j\to\infty$ that $x\mapsto G(x,a)$ is non-increasing, and
with similar argument we obtain, for any $x\geq 0$, that $G(x,a)=1$ for all
$a\leq 0$ and $G(x,a)=0$ for all $a>x$. Therefore, $a\mapsto 1-G(x,a)$ defined
the cumulative distribution of a random variable $D_{\infty}$ such that

  * •

$x\geq 0\mapsto\Pr(D_{\infty}(x)\geq a)$ is non-decreasing for all $a\geq 0$,

  * •

$\Pr(D_{\infty}(x)\notin[0,x])=0$ for al $x\geq 0$.

Therefore, for all $x\geq 0$, $D_{\infty}(x)$ is the limit in distribution of
$(D_{j}(x))_{j}$, hence a sequence
$\mathcal{D}^{\prime}=(D_{1}^{\prime},D_{2}^{\prime},\ldots)$ of mutually
independent random processes such that $D^{\prime}_{j}(x)\sim D_{\infty}(x)$
for any $j\geq 1$ and $x\geq 0$ defines a sequence of decay functions. We say
in this case that all the decay functions are identically distributed as
$D_{\infty}$. Moreover, it holds for all $x\geq 0$ that
$\mathbb{E}[D_{\infty}(x)]=\lim_{j\to\infty}\mathbb{E}[D_{j}(x)]=\inf_{j\geq
1}\mathbb{E}[D_{j}(x)]$

From there, all the proofs of Section 2 can be easily generalized to the case
of random decay functions, and it follows that we can restrict ourselves to
studying identically distributed decay functions. Moreover, Proposition 3.2
can be generalized to the case of random decay functions, and the necessary
condition for surpassing $1/2$ becomes
$\inf_{x>0}\frac{\mathbb{E}[D_{\infty}(x)]}{x}>0$. Similarly, using that the
stopping time $\tau$ of the algorithm is independent of randomness induced by
$D_{\infty}$, Proposition 3.3 remains true with
$\gamma=\inf_{x>0}\frac{\mathbb{E}[D_{\infty}(x)]}{x}$.

##### Lower bounds

For establishing lower bounds, observe that, for any random decay functions
$\mathcal{D}$, if we denote $H_{j}(x)=\mathbb{E}[D_{j}(x)]$ for all $x$, then
$\mathcal{H}=(H_{1},H_{2},\ldots)$ defines a sequence of deterministic decay
functions. Furthermore, for any instance $X_{1},\ldots,X_{n}$ and any
algorithm ALG, it holds that

$\displaystyle\mathbb{E}[\textsf{ALG}^{\mathcal{D}}(X_{1},\ldots,X_{n})]$
$\displaystyle=\mathbb{E}[\max_{0\leq i\leq\tau-1}\\{D_{i}(X_{\tau-i})\\}]$
$\displaystyle=\mathbb{E}\Big{[}\mathbb{E}[\max_{0\leq
i\leq\tau-1}\\{D_{i}(X_{\tau-i})\\}\mid\tau,X_{1},\ldots,X_{n}]\Big{]}$
$\displaystyle\geq\mathbb{E}\Big{[}\max_{0\leq
i\leq\tau-1}\big{\\{}\mathbb{E}[D_{i}(X_{\tau-i})\mid\tau,X_{1},\ldots,X_{n}]\big{\\}}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\max_{0\leq
i\leq\tau-1}\\{H_{i}(X_{\tau-i})\\}\Big{]}$
$\displaystyle=\mathbb{E}[\textsf{ALG}^{\mathcal{H}}(X_{1},\ldots,X_{n})].$

It follows that lower bounds established for deterministic decay functions can
be extended to random decay functions by considering their expectations.

##### Implications

With the previous observations, both the lower and upper bounds, depending on
$\gamma_{\mathcal{D}}$ that we proved in the deterministic
$\mathcal{D}$-prophet inequality can be generalized to the random
$\mathcal{D}$-prophet inequality, by taking

$\gamma_{\mathcal{D}}=\inf_{x>0}\inf_{j\geq
1}\frac{\mathbb{E}[D_{j}(x)]}{x}\;.$