# Prophet Secretary Against the Online Optimal

Paul Dütting
Google Research
<EMAIL_ADDRESS>Evangelia Gergatsouli
University of Wisconsin-Madison
<EMAIL_ADDRESS>Rojin Rezvan
University of Texas at Austin
<EMAIL_ADDRESS>Yifeng Teng
Google Research
<EMAIL_ADDRESS>Alexandros Tsigonias-Dimitriadis
Universidad de Chile
<EMAIL_ADDRESS>
We study the prophet secretary problem, a well-studied variant of the classic
prophet inequality, where values are drawn from independent known
distributions but arrive in uniformly random order. Upon seeing a value at
each step, the decision-maker has to either select it and stop or irrevocably
discard it. Traditionally, the chosen benchmark is the expected reward of the
prophet, who knows all the values in advance and can always select the maximum
one. In this work, we study the prophet secretary problem against a less
pessimistic but equally well-motivated benchmark; the _online_ optimal. Here,
the main goal is to find polynomial-time algorithms that guarantee near-
optimal expected reward. As a warm-up, we present a quasi-polynomial time
approximation scheme (QPTAS) achieving a $(1-\varepsilon)$-approximation in
$O(n^{\text{poly}\log n\cdot f(\varepsilon)})$ time through careful
discretization and non-trivial bundling processes. Using the toolbox developed
for the QPTAS, coupled with a novel _frontloading_ technique that enables us
to reduce the number of decisions we need to make, we are able to remove the
dependence on $n$ in the exponent and obtain a polynomial time approximation
scheme (PTAS) for this problem.

##  1 Introduction

The prophet inequality problem is a central problem in the field of optimal
stopping theory. In the classic version of this problem, a gambler faces a
sequence of $n$ variables $X_{i}$, each drawn independently from a known
distribution $\mathcal{D}_{i}$, which are presented to him one by one. The
gambler’s goal is to decide, at each step, whether to keep the value realized
from the distribution or continue and irrevocably discard it, in order to
maximize the value obtained. The optimal online policy can be found (in poly-
time) using backward induction. The classic benchmark for the classic problem
is the all-knowing _prophet_ , who can see the future values and select the
maximum. The celebrated result of Krengel and Sucheston (1977, 1978); Samuel-
Cahn (1984) shows that using a simple threshold policy, the gambler can obtain
an expected value that is at least 1/2 of the expected value of the prophet,
and that this is best possible among all online policies. Prophet inequalities
are of special interest in algorithmic game theory too, due to their strong
connections to sequential posted pricing mechanisms. In fact, we know from
Hajiaghayi et al. (2007); Chawla et al. (2010); Correa et al. (2019a) that
designing posted-price mechanisms is equivalent to finding (threshold)
stopping rules in the related prophet inequality setting.

Motivated in part by this connection to sequential posted pricing, prophet
inequalities have been studied for a broad range of combinatorial settings
such as matroids (Kleinberg and Weinberg, 2012; Alaei, 2011; Feldman et al.,
2016), bipartite and non-bipartite matching with vertex or edge arrivals
(Gravin and Wang, 2019; Ezra et al., 2020, 2022), or combinatorial auctions
(Feldman et al., 2015; Dütting et al., 2017, 2020).

A fundamental variant of the classic prophet inequality problem is the prophet
secretary problem (Esfandiari et al., 2015; Correa et al., 2017; Azar et al.,
2018; Correa et al., 2019b), where the variables arrive in uniformly random
order instead of adversarially. In the original formulation of this problem,
we compete again with the _prophet_. In this case, it was shown that there
exists a $0.669$-approximation (Correa et al., 2019b) while no algorithm can
achieve an approximation better than $0.7254$ (Bubna and Chiplunkar, 2022).
Closing this gap is an important open problem in the prophet inequalities
community. Another exciting property of the prophet secretary problem is that
unlike in the classic prophet inequality problem, the dynamic program for
solving the optimal online policy is of exponential size.

In this work, we study the prophet secretary problem against the _online
optimal_. This benchmark does not assume any prior knowledge of the future; we
compete against an algorithm that has the same information as we do at every
step, but infinite computation power. This way, we measure the potential loss
that arises due to computational limitations, rather than quantifying the loss
that’s due to the fact that the algorithm has to make decisions online. Our
work is the first to provide algorithms for prophet secretary against the
online optimal. We design both a quasi-polynomial time approximation scheme
(QPTAS) and a polynomial time approximation scheme (PTAS), showing that we can
obtain an arbitrarily good approximation against the online optimal. Our
algorithmic results uncover important structural properties of the prophet
secretary problem and near-optimal (threshold-based) stopping decisions.

###  1.1 Our Contribution & Techniques

We show how to approximate the expected value of the online optimal to within
a factor of $1-\varepsilon$; this immediately translates into an algorithm
that achieves a $1-\varepsilon$ approximation.

Our starting point is a simple observation, which states that if one groups
“similar” variables into $g$ groups and treats variables in each group in the
same way, then one can write a dynamic program that tracks the number of
variables in each group, with complexity exponential in $g$. This reduces the
problem to showing that there is a succinct grouping that obtains a
$(1-\varepsilon)$-approximation. For the QPTAS it suffices to give a grouping
of size $\text{polylog}(n)$, for the PTAS we need to further reduce this to
$O(1)$.

First result: QPTAS. We give the intuition underlying the grouping of size
$\text{polylog}(n)$ for a special case that captures most of the solution
idea. The special case is that each random variable has binary support as
follows: variable $X_{i}$ is either $v_{i}$ or zero, with probabilities
$p_{i}$ and $1-p_{i}$.

First, we argue that we can scale the values appropriately so that OPT falls
into some small constant interval $[c,1]$. Afterward, we show that we don’t
lose more than $O(\varepsilon)$ if we ignore variables with low value
($v_{i}\leq\varepsilon$) or low expected value
($v_{i}p_{i}\leq\varepsilon/n$). For the remaining variables whose value is
very high ($v_{i}\geq 1/\varepsilon^{2}$), we show how to compress them by
adjusting their values so that they all have the same value and their
probabilities fall in a $O(\text{poly}~{}n)$ range. We then discretize the
variables with small values (from $\varepsilon$ to $1/\varepsilon^{2}$) and
their respective probabilities which range from $\varepsilon^{3}/n$ to $1$, to
powers of $(1+\varepsilon)$. We also round the probabilities (which are also
in a $\text{poly}(n,\varepsilon)$ range) of the variables with the same high
value to powers of $(1+\varepsilon)$.

This construction readily generalizes to the constant-size support case (by
treating the O(1) high realizations as we did before for the single one). An
additional ingredient that is needed for the case where the support is not
necessarily of constant size, is an argument for collapsing all high
realizations (those above OPT) of a variable into a single point. Together
with a discretization of the low realizations of a variable (from
$\varepsilon$ to 1), we are back to the constant-size support case.

######  Theorem 1.1 (QPTAS, informal).

There exists a $(1-\varepsilon)$-approximation algorithm for computing the
optimal reward of the prophet secretary problem in time
$n^{\text{polylog}~{}n\cdot f(\varepsilon)}$.

Second result: PTAS. Similar to the case of the QPTAS, the case where all
variables are binary is descriptive of the idea behind the PTAS for the
general case. Starting off from the discretizations done in the QPTAS, what we
need to take care of are variables with realization probability that are each
individually small ($<poly(\epsilon))$, but that still cannot be ignored as
there may be enough of them to contribute considerably to optimal reward. This
step is crucial to reduce the number of possible probabilities to
$\text{poly}(\frac{1}{\varepsilon})$.

In order to do so, we propose the novel technique of “frontloading”. The idea
is as follows. Fix a support value $v$, and consider the variables of interest
(those with neither high nor low probabilities) with that support. If it is
the case that $k$ many of these variables have a total realization probability
that is not very high, then we claim that imagining these $k$ variables as a
single box, with the total realization probability equal to that of the $k$
boxes, and as an ”outside option” always available through the interval where
these variables arrive, does not affect the reward much. This makes us capable
of reducing the number of different probabilities we need to track for the
dynamic program that finds the optimal.

In order to generalize this to variables with support size more than one, we
show that we can imagine a variable with multiple support values, as multiple
binary variables (each of them having one of the support values with its
corresponding probability that is not too high, and the remaining probability
on value $0$) and an additional variable with high probability for each
support value that arrives after each other. This brings us back to the binary
case, as there are not many types of variables with a larger probability on
each support value and they can be treated differently.

######  Theorem 1.2 (PTAS, informal).

There exists a $(1-\varepsilon)$-approximation algorithm for computing the
optimal reward of the prophet secretary problem in time $n^{f(\varepsilon)}$.

The above theorem shows that the optimal reward OPT of any prophet secretary
instance can be efficiently approximated. Observe that given an efficient
oracle that always returns a value between $(1-\varepsilon)\text{OPT}$ and
OPT, we can use it to construct an efficient algorithm for the prophet
secretary problem with an expected reward at least
$(1-\varepsilon)\text{OPT}$. In particular, at each step, the algorithm
queries the oracle on the remaining instance to obtain a threshold to make the
decision on the current variable. See Lemma 2.1 for more discussion. Then we
not only have a PTAS for computing the approximately optimal reward of the
prophet secretary problem, but also obtain an efficient strategy with almost
optimal reward.

######  Corollary 1.3 (PTAS Algorithm, informal).

There exists a $(1-\varepsilon)$-approximation strategy for the prophet
secretary problem against the online optimal that runs in time
$n^{f(\varepsilon)}$.

###  1.2 Related Work

Classic prophet inequality and prophet secretary. There is a vast literature
on the topic of prophet inequalities, starting with the classic, fixed order
prophet inequality studied first in Krengel and Sucheston (1977, 1978), who
obtained a tight 0.5 approximation for the problem. Another remarkable result
came a bit later from Samuel-Cahn (1984), who showed that the tight bound can
be achieved by using a single-threshold algorithm (a different well-known
single-threshold algorithm was also shown in Kleinberg and Weinberg (2012)).
For a comprehensive treatment of the subject, we refer the reader to the
earlier survey by Hill and Kertz (1992) and the more recent ones by Lucier
(2017); Correa et al. (2018).

In this paper, we focus on one of the most well-established variants, which is
a natural combination of the secretary problem and the classic prophet
inequality, introduced by Esfandiari et al. (2015) as the prophet secretary
problem. Their main result was to show that a non-adaptive multi-threshold
algorithm achieves a $\left(1-\frac{1}{e}\right)$-approximation to the prophet
benchmark. A bit later, Ehsani et al. (2018) and Correa et al. (2017) arrived
to the same approximation guarantee by using different threshold-based
algorithms. The first algorithm breaking this $\left(1-\frac{1}{e}\right)$
barrier by a tiny fraction came from Azar et al. (2018) and was subsequently
improved by Correa et al. (2019b) to $0.669$, which is the currently best-
known bound. Obtaining a tight answer for this problem remains a very
interesting open question, since the best-known hardness result is $0.7254$,
as shown very recently in Bubna and Chiplunkar (2022).

The exploration of the optimal online algorithm as a benchmark has been
pioneered in Niazadeh et al. (2018) and Papadimitriou et al. (2021); Braverman
et al. (2022) as well as Anari et al. (2019). Niazadeh et al. (2018) study the
power of single-threshold algorithms when competing with the online optimal.
Papadimitriou et al. (2021), Braverman et al. (2022), and Naor et al. (2023)
consider this benchmark for the online stochastic maximum-weight matching
problem under vertex arrivals,111Note that the online rounding scheme for
fractional bipartite matchings of Saberi and Wajc (2021) also improved and
generalized the result of Papadimitriou et al. (2021). and Anari et al. (2019)
for an online pricing problem with laminar matroid constraints.

The free-order model. Apart from the fixed and the random arrival order
models, another setting that has received a lot of attention is the one where
the decision-maker can freely choose the order. For the optimal ordering
problem, where the goal of the decision-maker is to compute (or approximate)
the optimal order of inspection using efficient algorithms, Agrawal et al.
(2020) showed that it is NP-hard and provided an FPTAS for distributions of
support size $3$. Fu et al. (2018) proved, among other results, that for
distributions with constant support size, the problem admits a PTAS. Earlier,
Chakraborty et al. (2010) gave a PTAS for general distributions for the
problem of revenue maximization in sequential posted-price mechanisms;
combined with the result of Correa et al. (2019a), they automatically obtain a
PTAS for the optimal ordering problem as well. Finally, Liu et al. (2021)
designed an EPTAS using a new decomposition technique for random variables. An
EPTAS was also independently obtained by Segev and Singla (2021). A remaining
open question is whether there can be an FPTAS.

When competing with the prophet benchmark, called the order selection problem,
until very recently the best-known bound was $0.669$ coming from the work of
Correa et al. (2019b) for the random order model. Very recently, Peng and Tang
(2022) was the first to beat this bound and obtain a (much-improved)
0.7251-competitive algorithm, which was further improved to 0.7258 by Bubna
and Chiplunkar (2022) shortly thereafter. Since no separation is known between
the i.i.d. prophet inequality and the order selection problem, the upper bound
of $0.745$ follows from the work of Hill and Kertz (1982). Showing or
disproving that the i.i.d. case is the worst-case for free-order remains an
intriguing open problem.

The Pandora’s Box problem. A similar setting, where there is additional
exploration cost for the variables but the decision-maker does not have to
make immediate and irrevocable decisions, is the Pandora’s box problem, first
defined more than four decades ago by Weitzman (1979). A recent line of work
extended the original model in various directions (see, e.g., Guha et al.
(2008); Doval (2018); Beyhaghi and Kleinberg (2019); Boodaghians et al.
(2020); Chawla et al. (2020, 2021)), where in all cases the goal is either to
maximize or minimize the objective function against the online optimal.

In particular, the setting of non-obligatory inspection has been thoroughly
explored from an algorithmic point of view, and the question of whether there
exists any polynomial-time algorithm to compute the optimal policy remained
open until very recently. Guha et al. (2008) provided the first constant-
factor approximation to the problem. Note that their paper deals with
information acquisition in multichannel wireless networks, but their model
turns out to correspond exactly to the Pandora’s box problem with non-
obligatory inspection. Doval (2018) introduced the problem in the economics
literature some years later. Beyhaghi and Kleinberg (2019) revived it in the
EconCS community; their main result was to introduce a simple policy that also
guarantees a constant-factor approximation (albeit worse than the one of Guha
et al. (2008)). Only very recently Fu et al. (2022) showed that the problem is
NP-hard and provided a PTAS. In a concurrent and independent work, Beyhaghi
and Cai (2022) also obtained a PTAS for the problem.

Finally, in the interesting problem termed Pandora’s box with commitment, in
which the decision-maker now has to decide immediately and irrevocably whether
to stop or continue, Fu et al. (2018) first gave a PTAS and later Segev and
Singla (2021) developed an EPTAS for this problem, as part of a general
framework that works in different classes of stochastic combinatorial
optimization problems.

#### Organization.

In Section 2, we define the optimal objective and state a dynamic program to
compute it, together with some structural lemmas that compare the optimal
reward of instances with similar variables. In Section 3, we first describe
the QPTAS strategy for a special case of two-point distributions and later
extend it to the general case. Finally, in Section 4, we describe the PTAS
strategy again for two-point distributions. In the interest of space, the
proofs for the general case of PTAS have been moved to the Appendix. Omitted
proofs of Sections 2, 3, and 4 can be found in Appendices B, C, and D,
respectively.

##  2 Preliminaries

Let $X_{1},\ldots,X_{n}$ be $n$ independent non-negative random variables
drawn from known distributions $\mathcal{D}_{1},\ldots,\mathcal{D}_{n}$. To
simplify the presentation, we focus on the case of discrete distributions. We
remark that all of our results hold also for continuous distributions; we
discuss this further at the corresponding technical sections. We denote the
product distribution by
$\mathcal{D}=\mathcal{D}_{1}\times\ldots\mathcal{D}_{n}$ and the support of
each variable $X_{i}$ by $\text{supp}(X_{i})$. We are sequentially presented
with the variables in a uniformly random order and need to decide at every
step to either keep the value realized from the distribution, or irrevocably
discard it. The goal of the algorithm is to maximize the expected value
chosen.

As a benchmark we adopt the _online optimal_ , i.e., the expected value
achievable by an algorithm that has infinite computational resources but no
knowledge of the future.

The online optimal can be expressed as a dynamic program, as shown in equation
(1). We denote by $\text{OPT}(X|\mathcal{B})$ the recursive solution when the
current variable has value $X$ and the set of variables remaining is
$\mathcal{B}$.

$\text{OPT}(X|\mathcal{B})=\begin{cases}\mathbb{E}_{\mathcal{D}}\left[X\right]&\text{if
}\mathcal{B}=\emptyset\\\
\mathbb{E}_{\mathcal{D}}\left[\max\left(X,\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\text{OPT}(X_{i}|\mathcal{B}\setminus\\{i\\})\right)\right]&\text{else.}\end{cases}$
(1)

Observe that the optimal strategy is a series of (adaptive and decreasing)
thresholds; in every step we only continue if the current value obtained is
less than the expected optimal of the subproblem, with one less box. We denote
the threshold of $|\mathcal{B}|=n$ variables by

$\theta_{n}=\frac{1}{|\mathcal{B}|}\sum_{i\in\mathcal{B}}\text{OPT}(X_{i}|\mathcal{B}\setminus\\{i\\}).$

We also denote by $X_{-i}$ all variables $X_{1},\ldots,X_{n}$ except the
variable $X_{i}$ and by $Y_{k:n}$ (resp. $X_{k:n})$ for all $k\in[n]$ the
remaining instance starting at index $k$. For the instance we want to solve,
i.e. $Y_{1:n}$ (resp. $X_{1:n}$), we drop the subscript and simply write $Y$
(resp. $X$). Similarly, $\text{OPT}_{\ell:k}$ is the optimal solution for the
sub-instance $X_{\ell},\ldots X_{k}$.

Our ultimate goal is to find a poly-time algorithm that achieves a
$1-\varepsilon$ approximation to the online optimal. Following, we give the
definitions of QPTAS and PTAS in the context of maximization problems.

######  Definition 1 (QPTAS).

For every fixed $\varepsilon>0$, there is a $(1-\varepsilon)$-approximation
algorithm that runs in time $O\left(n^{\text{polylog}\ n}\right)$.

######  Definition 2 (PTAS).

For every fixed $\varepsilon>0$, there is a $(1-\varepsilon)$-approximation
algorithm that runs in time polynomial in $n$.

###  2.1 From reward approximation oracle to efficient strategy

Lemma 2.1 shows that if we can calculate thresholds that are always within
$(1-\varepsilon)$ of those that the DP calculates, then the error does not
propagate and we will lose in expectation at most $(1-\varepsilon)$. The proof
appears in Section B of the Appendix. The lemma can transform any efficient
approximation algorithm on the optimal reward of the prophet secretary
algorithm to an efficient strategy for the prophet secretary game with
approximately optimal reward.

######  Lemma 2.1.

For any prophet secretary instance $X_{1},\cdots,X_{n}$, let
$\text{OPT}^{\prime}(X)$ be an algorithm such that given input $X$ returns a
value $\text{OPT}^{\prime}(X)\in[(1-\varepsilon)\text{OPT}(X),\text{OPT}(X)]$.
Consider an algorithm ALG for the prophet secretary problem such that at any
step, the algorithm uses $\text{OPT}^{\prime}($on the remaining variables$)$
as a threshold for the current variable. Then

$\text{ALG}(X)\geq(1-\varepsilon)\text{OPT}(X).$

###  2.2 Grouping in the DP

Since the dynamic program given above can be exponential in size, a general
tool that we will employ is to group variables into a smaller number of
groups, and treat all variables in a group in the same way.

Specifically, given a collection of $g$ groups of variables, we only need to
keep track of the number of variables in each group. Denote by $k_{i}$ the
size of group $i$, and by $K=\sum_{i}k_{i}$ the total number of groups
remaining. Then we can write the optimal DP as follows

$\text{OPT}(X,k_{1},\ldots,k_{g})=\begin{cases}\mathbb{E}_{\mathcal{D}}\left[X\right]&\text{if
}K=0,\\\
\mathbb{E}_{\mathcal{D}}\left[\max\left(X,\frac{1}{K}\sum\limits_{i\in[g]}k_{i}\text{OPT}(X_{i},k_{1},\ldots,k_{i-1},k_{i}\text{-}1,k_{i+1}\ldots,k_{g})\right)\right]&\text{else.}\end{cases}$
(2)

A simple observation now is that the size of the optimal online, using
formulation (2), is exponential in the number of different groups. The proof
of this claim is deferred to Section B of the appendix.

######  Claim 1.

The size of the dynamic program of (2), given $g$ different non-empty groups,
is at most $\left\lceil\frac{n}{g}\right\rceil^{g}$, where $n$ is the number
of variables.

With this observation at hand, it suffices to find a grouping of the variables
into $\text{polylog}~{}n$ groups for a QPTAS and into a constant number of
groups for a PTAS, such that the online optimal on the groups is
$1-\varepsilon$ close to the online optimal.

###  2.3 Structural lemmas

We next present two structural lemmas, which will be useful in our analysis.
Lemma 2.2 shows that if we perturb the values that the random variables can
take a bit, then the solution to the DP does not change by much. Lemma 2.3
shows that this is also true for probabilities. Their proof is deferred to
section B of the Appendix.

######  Lemma 2.2.

Let $\text{OPT}_{1:n}$ be the optimal online solution to prophet secretary on
variables $X_{1},\ldots X_{n}$, and $\text{OPT}^{\prime}_{1:n}$ the optimal
online solution on an instance where each value $v\in\text{supp}(X_{i})$ is
replaced by $v^{\prime}$ s.t. $v^{\prime}\leq v\leq\gamma\cdot v^{\prime}$
then it holds that

$\text{OPT}^{\prime}_{1:n}\geq\frac{\text{OPT}_{1:n}}{\gamma}.$

Similarly, if $v^{\prime}\leq v\leq v^{\prime}+\gamma$ for some $\gamma>1$
then $\text{OPT}^{\prime}_{1:n}\geq\text{OPT}_{1:n}-\gamma$.

######  Lemma 2.3.

Let $\text{OPT}_{1:n}$ be the optimal online solution to prophet secretary on
variables $X_{1},\ldots X_{n}$, and $\text{OPT}^{\prime}_{1:n}$ the optimal
online solution on an instance where each probability
$p_{v}=\textbf{Pr}_{\mathcal{D}_{i}}\left[X_{i}=v\right]$ for
$v\in\text{supp}(X_{i})$ is replaced by $p_{v}^{\prime}$ s.t.
$p_{v}^{\prime}\leq p_{v}\leq\gamma\cdot p_{v}^{\prime}$ then it holds that

$\text{OPT}^{\prime}_{1:n}\geq\frac{\text{OPT}_{1:n}}{\gamma}.$

##  3 Warm-up: QPTAS

We begin by presenting a QPTAS for approximating the optimal reward of the
prophet secretary problem. By Claim 1, our goal is to show that there is a
grouping of the variables into $\text{polylog}(n)$ groups such that the online
optimal on the groups achieves a ($1-\varepsilon$)-approximation.

The key insights that will enable this are: for each variable, we can collapse
values and probabilities of all realizations above OPT into a single point.
Moreover, we can compress the support of the probabilities of these points
into a $\text{poly}(n)$ range by moving all their values to a single value
that we choose.

######  Remark.

Very simple ideas, like grouping according to the mean and variance of each
distribution fail. For more details see Section A of the Appendix.

###  3.1 QPTAS for constant-size support

We start by solving the case where each random variable comes from a
distribution with constant support size, as this already captures some of the
key ideas of the construction. Any proof not included in this section is
deferred to Section C.1 of the Appendix.

A variable $X_{i}$ (with with $\mathbb{E}\left[X_{i}\right]<\infty$) has
support size at most $c$, for some constant $c$, if it is of the form

$X_{i}=\begin{cases}v_{1}&\text{w.p. }p_{1}\\\ v_{2}&\text{w.p. }p_{2}\\\
\ldots&\\\ v_{\kappa}&\text{w.p. }p_{\kappa},\\\ \end{cases}$

where $\kappa\leq c$ is the size of the support. Next, we state the main
result of this section.

######  Theorem 3.1.

[QPTAS for constant size support] There exists a
$(1-\varepsilon)$-approximation algorithm for the prophet secretary problem
against the online optimal that runs in time
$O\left(\left(\frac{n}{g}\right)^{g}\right)$ for
$g=O\left(\frac{\log^{2c}n/\varepsilon}{(c-1)!\log^{2c}(1+\varepsilon)}\right)$.
In the special case of $c=2$, for 2-point distributions with $v_{1}=0$ and
$v_{2}>0$ we can get running time of
$O\left(\left(\frac{n}{g}\right)^{g}\right)$ for
$g=O\left(\frac{\log^{2}n/\varepsilon}{\log^{2}(1+\varepsilon)}\right)$.

In what follows, we give a proof for the special case of two-point
distributions, each supported on one zero and one non-zero value, as it
contains most of the important ideas that we need to prove the theorem. At the
end of this subsection, we describe the small extra step we need to do to
obtain the result for the constant-size support case, and we defer the rest of
the necessary adjustments to the appendix. After this, we will move on to the
case of general distributions. Thus, from now on we consider random variables
$X_{i}$ of the form

$X_{i}=\begin{cases}v_{i}&\text{, w.p. }p_{i}\\\ 0&\text{, w.p.
}1-p_{i}.\end{cases}$

Preprocessing: Before describing our discretization process, we do some
preprocessing steps, starting by scaling the optimal such that the following
claim holds.

######  Claim 2.

WLOG we can normalize the values s.t. $\text{OPT}\in[0.669,1]$.

This holds since we can normalize the values in order to have
$\mathbb{E}_{\mathcal{D}}\left[\max_{i}X_{i}\right]=1$. Using Theorem 1.1 from
Correa et al. (2019b) we know that the online OPT will be in $[0.669,1]$
(since they give a $0.669$ approximation to the prophet). Following this, for
the variables where $v_{i}\leq\varepsilon$ or $v_{i}p_{i}\leq\varepsilon/n$ we
set $v_{i}^{\prime}=0$ and keep $p_{i}^{\prime}=p_{i}$.

The following claim shows that grounding to $0$ the point masses $v_{i}$ with
$v_{i}\cdot p_{i}\leq\frac{\varepsilon}{n}$ does not incur more that
$O(\varepsilon)$ loss for OPT.

######  Claim 3.

Let $X_{1},\ldots,X_{n}$ be two-point random variables. If for every variable
$X_{i}$ for which $\mathbb{E}\left[X_{i}\right]=v_{i}\cdot
p_{i}\leq\frac{\varepsilon}{n}$ we move all mass to $0$, (i.e.,
$v^{\prime}_{i}=0$ with $p^{\prime}_{i}=1$) then we lose at most
$1.5\varepsilon\cdot\text{OPT}$.

Dealing with high values: Before proceeding to the discretization, and since
we did not make any assumptions on the upper bound of the support of every
distribution, we need to treat separately the points with “high” values. Here
by “high” values we mean those variables that have a point with
$v_{i}\in[1/\varepsilon^{2},\infty)$ and $p_{i}\in(0,\varepsilon^{2}]$. In
particular, we need to compress their values or their probabilities in a
$\text{poly}(n)$-range support (in values / probability) so that we can
perform afterwards the careful discretization process. We achieve that by
performing the following expectation-preserving transformation. Let $v_{\max}$
be the largest support value in the input. We set all such points to have
equal value $v_{i}^{\prime}=v_{\max}$ and rescale the initial probabilities to
$p_{i}^{\prime}\leftarrow\frac{v_{i}p_{i}}{v_{\max}}$, to maintain the same
expected reward from this support value (i.e.,
$v_{i}^{\prime}p^{\prime}_{i}=v_{i}p_{i}$). Let $p^{o}$ be the largest
$p^{\prime}_{i}$ from this transformation, we can ensure that
$p_{i}^{\prime}\in[\frac{\varepsilon}{n}p^{o},p^{o}]$ for each
$i\in\mathcal{B}$ by removing all variables with
$p^{\prime}_{i}<\frac{\varepsilon}{n}$ losing at most $O(\varepsilon)$
fraction of the optimal reward due to Claim 3.

We claim that this transformation does not cause more than
$O(\varepsilon^{2})$ multiplicative loss.

######  Claim 4.

Let $X_{1},\ldots,X_{n}$ be an instance of prophet secretary such that each
variable $X_{i}$ has at most one support value $>1$, and $Y_{1},\ldots Y_{n}$
the instance where we change the variables $X_{i}$ to variable $Y_{i}$, where
the support value $v_{i}>1/\varepsilon^{2}$ with probability $p_{i}$ is
changed to $v_{\max}$ with probability $\frac{v_{i}p_{i}}{v_{\max}}$, where
$v_{\max}$ is the largest support value of all variables. Then

$\text{OPT}(X)\leq\text{OPT}(Y)\leq(1+\varepsilon^{2})\text{OPT}(X).$

The proofs of Claim 4 and Claim 3 are deferred to Appendix C.1.

Discretization: We now define the steps in our discretization process.

######  Definition 3 (Discretization).

Given a set of $n$ variables, each of which is a two point distribution giving
$v_{i}$ w.p. $p_{i}$ and $0$ otherwise we define the following discretization
process.

  * •

Step 1: round down all $v_{i}$’s to the nearest $(1+\varepsilon)^{k}$, for
$k\in\mathbb{Z}$.

  * •

Step 2: round down all $p_{i}$’s to the nearest $(1+\varepsilon)^{k}$, for
$k\in\mathbb{Z}$.

We discretize each group of variables differently, based on the values of
$v_{i}$ and $p_{i}$ of each variable. The different discretization cases are
also presented in Figure 1.

  * •

Case 1: variables that have $v_{i}\in[\varepsilon,1/\varepsilon^{2}]$ and
$p_{i}\in[\varepsilon^{3}/n,1]$. We use the discretization of Definition 3,
based on both value and probability.

  * •

Case 2: variables that have $v_{i}\in[1/\varepsilon^{2},\infty)$ and
$p_{i}\in(0,\varepsilon^{2}]$. Here, we have performed the expectation-
preserving transformation described above and then we use again the
discretization of Definition 3, based on both value and probability.

Observe also that variables that have $v_{i}>1/\varepsilon^{2}$ and
$p_{i}\in(\varepsilon^{2},1]$ cannot exist, since in this case the optimal
would not be $\text{OPT}\leq 1$.

$\varepsilon$$1/\varepsilon^{2}$$v_{i}$$p_{i}$$\varepsilon^{3}/n$$\varepsilon^{2}$PreprocessingCase
1Case 2Cannot Exist Figure 1: Different cases for discretization for the
$2$-point case. In case 2, we only consider the variables with
$v_{i}p_{i}>\varepsilon/n$. Preprocessing here refers to all the value-
probability pairs that we omit from the instance.

#### Proof of Theorem 3.1 (for 2-point distributions).

We separately bound the error and calculate the number of groups resulting
from our discretization process.

_Bounding the error:_ In our preprocessing phase, we move all mass to value
$0$ for the following two types of variables: when $v_{i}<\varepsilon$ (step
1), and when $v_{i}p_{i}<\varepsilon/n$ (step 2). Denote by
$\text{OPT}^{\prime}$ and $\text{OPT}^{\prime\prime}$ the optimal value after
each of the preprocessing steps.

  * •

Variables with $v_{i}<\varepsilon$: note that each of the variables in Step 1
contributes at most $\varepsilon$ and $\text{OPT}\leq 1$ from Assumption 2.
Denote by $A=\\{X_{i}:v_{i}>\varepsilon\\}$ and we write OPT as

OPT $\displaystyle=\mathbb{E}\left[\text{gain}|\text{select }b\in
A\right]\textbf{Pr}\left[\text{select }b\in
A\right]+\mathbb{E}\left[\text{gain}|\text{select }b\not\in
A\right]\textbf{Pr}\left[\text{select }b\not\in A\right]$
$\displaystyle\leq\mathbb{E}\left[\text{gain}|\text{select }b\in
A\right]\textbf{Pr}\left[\text{select }b\in
A\right]+\frac{\varepsilon}{0.669}\text{OPT}$
$\displaystyle\leq\text{OPT}^{\prime}+1.5\varepsilon\text{OPT},$

from which we get $\text{OPT}^{\prime}\geq(1-1.5\varepsilon)\text{OPT}$.

  * •

Variables with $v_{i}p_{i}<\varepsilon/n$: denote by
$A=\\{X_{i}:v_{i}p_{i}\geq\varepsilon/n\\}$, then we write
$\text{OPT}^{\prime}$ as

$\displaystyle\text{OPT}^{\prime}$
$\displaystyle=\mathbb{E}\left[\text{gain}|\text{select }b\in
A\right]\textbf{Pr}\left[\text{select }b\in
A\right]+\mathbb{E}\left[\text{gain}|\text{select }b\not\in
A\right]\textbf{Pr}\left[\text{select }b\not\in A\right]$
$\displaystyle\leq\mathbb{E}\left[\text{gain}|\text{select }b\in
A\right]\textbf{Pr}\left[\text{select }b\in
A\right]+\mathbb{E}\left[\max_{i\not\in A}X_{i}\right]$
$\displaystyle\leq\mathbb{E}\left[\text{gain}|\text{select }b\in
A\right]\textbf{Pr}\left[\text{select }b\in
A\right]+1.5\varepsilon\text{OPT}^{\prime}$
$\displaystyle=\text{OPT}^{\prime\prime}+1.5\varepsilon\text{OPT}^{\prime},$

where in the last inequality we used Claim 3.

Combining these two steps, we get that
$\text{OPT}^{\prime\prime}\geq(1-1.5\varepsilon)^{2}\text{OPT}$. We move on to
bound the loss incurred by the two different discretization cases.

  * •

Case 1: Lemmas 2.2 and 2.3 hold with $\gamma=(1+\varepsilon)$, therefore we
only lose a factor of $(1+\varepsilon)^{2}$, by applying first Lemma 2.2 for
the discretization in the values, and then Lemma 2.3 for the discretization in
the probabilities.

  * •

Case 2: Combining Claim 4 and Lemma 2.3 for $\gamma=(1+\varepsilon)$, we
transform all variables with support value $>1/\varepsilon^{2}$ and discretize
the probabilities to powers of $(1+\varepsilon)$, losing $O(\varepsilon)$
fraction of optimal reward.

Combining all the above together, we get $O(\varepsilon)$ multiplicative loss
by the preprocessing and the discretization.

_Counting the groups:_ Observe that from the preprocessing phase all variables
will belong to one group, i.e. the group where $v_{i}=0$ w.p. $1$.

  * •

Case 1: using the discretization described in Definition 3, we have
$O\left(\frac{\log n/\varepsilon}{\log(1+\varepsilon)}\right)$ different
values for $p_{i}$ and $O\left(\frac{\log
1/\varepsilon}{\log(1+\varepsilon)}\right)$ different values for $v_{i}$.
Therefore creating one group for each pair of values we have
$O\left(\frac{\log 1/\varepsilon\cdot\log
n/\varepsilon}{\log^{2}(1+\varepsilon)}\right)$ different groups in total.

  * •

Case 2: since all variables have the same value, we need to count the
different groups from the discretization of the probabilities in range
$\left[\frac{\varepsilon}{n}p^{o},p^{o}\right]$. Recall that we discretize all
probabilities by rounding them down to the nearest $(1+\varepsilon)^{k}$. The
number of different $k$ values is $O\left(\frac{\log
n+\log(1/\varepsilon)}{\log(1+\varepsilon)}\right)$.

Therefore the total number of groups is
$O\left(\frac{\log^{2}n/\varepsilon}{\log^{2}(1+\varepsilon)}\right)$.

This concludes the proof of the case of two-point variables. We describe next
the extra step required to generalize the above arguments to the case of
constant support size. We defer the discussion on the minor adjustments in the
previous lemmas and claims that give the slightly different error bound for
the constant size support (it now depends also on $c$) to Appendix C.1.

#### Counting the groups in the case of constant size support

Observe that now _groups_ are defined differently than in the two-point case.
In particular, to say that two random variables are in the same group in the
DP, we need that they have the same distribution after discretization. This
implies (1) that they end up with the same number of points after
discretization, and (2) that the points fall in the exact same groups.

Suppose that after discretizing the values can take $k_{1}$ and the
probabilities $k_{2}$ different values. Let us denote $k=k_{1}\cdot k_{2}$ the
different value-probability pairs that arise and by $\mathcal{D}^{\prime}_{i}$
the distribution of $X_{i}$ after the discretization. Assume for now that
$|\text{supp}(\mathcal{D}^{\prime}_{i})|=c$ for every $X_{i}$ and that also
$|\text{supp}(\mathcal{D}^{\prime}_{i})|=c$ (i.e., no two points of the
support collapse to the same one). To count the number of different
distributions that arise for support size $c$ we need a balls-into-bins
argument, where the bins are the value-probability pairs and the balls are the
points in the support. Then ${k\choose c}$ is the number of different
distributions and two variables $X_{i},X_{j}$ must have
$\mathcal{D}^{\prime}_{i}=\mathcal{D}^{\prime}_{j}$ to be in the same group.

We now have to count all the different possibilities. Note that after
discretization for every $X_{i}$ we have that
$|\text{supp}(\mathcal{D}^{\prime}_{i})|\in[1,c]$. For each of the possible
support sizes, we count the emerging groups and add them to find the total
number of groups. We, thus, obtain

$\sum_{i=1}^{c}\binom{k}{i}\leq c\cdot\binom{k}{c}\leq\frac{k^{c}}{(c-1)!},$

where the first inequality holds because the binomial is increasing in the
interval $[1,c]$ for some constant $c$ (assuming $c=o(k)$), and the last
inequality holds for every binomial coefficient by using Stirling’s
approximation. Since we follow the same discretization process as for two-
point distributions, we know from Theorem 3.1 that
$k=O\left(\frac{\log^{2}n/\varepsilon}{\log^{2}(1+\varepsilon)}\right)$, and
the desired result follows. Putting it all together, the number of groups is
$g=O\left(\frac{\log^{2c}n/\varepsilon}{(c-1)!\log^{2c}(1+\varepsilon)}\right)$.

###  3.2 QPTAS for general distributions

Moving on to the QPTAS for the general case, observe that the techniques used
for the constant support case cannot work when the support size of a
distribution is arbitrary. For instance, the transformation in the case of
dealing with high values from before will not work now, because Claim 4 cannot
be applied when a variable can have multiple large support values
$>1/\varepsilon^{2}$. However, we are still able to obtain a QPTAS (Theorem
3.2): using the fact that whenever any (optimal) algorithm encounters a value
$X_{i}>1$ it will accept it, we are able to reduce the size of the support
significantly, using a new _bundling_ technique.

The second step involves the rest of the points with values in
$[\varepsilon,1]$. These can possibly be arbitrarily many, but their range is
constant, so we can discretize to powers of $(1+\varepsilon)$ as before. After
doing that, we know that each $X_{i}$ has at most one point with $v_{i}>1$
(which can also be possibly unbounded) and a constant number of points in
$[\varepsilon,1]$. Thus, we can employ the discretization process for the
distributions with constant-size support and the main difference will now be
that the support size $c$ depends on the fixed $\varepsilon$.

######  Theorem 3.2.

There exists a $(1-\varepsilon)$-approximation algorithm for the prophet
secretary problem against the online optimal that runs in time
$O\left(\left(\frac{n}{g}\right)^{g}\right)$ for
$g=O\left(\frac{\log^{2c}n/\varepsilon}{(c-1)!\log^{2c}(1+\varepsilon)}\right)$
where $c=O\left(\frac{\log 1/\varepsilon}{\log(1+\varepsilon)}\right)$.

#### Bundling & Discretization:

recall that the normalized optimal satisfies $\text{OPT}\leq 1$ (from Claim
2). For each variable $X_{i}$ we create a transformed variable
$X^{\prime}_{i}$ that is exactly the same as $X_{i}$ for values less than $1$,
but we collapse the mass above $1$ to a single point with value the mean value
of $X_{i}$ above $1$. Formally

$X^{\prime}_{i}=\begin{cases}x&\text{when }x\leq 1,\text{ w.p.
}\textbf{Pr}_{X_{i}\sim\mathcal{D}_{i}}\left[X_{i}=x\right]\\\
\mathbb{E}_{X_{i}\sim\mathcal{D}_{i}}\left[X_{i}|X_{i}>1\right]&\text{w.p.
}\textbf{Pr}_{X_{i}\sim\mathcal{D}_{i}}\left[X_{i}>1\right].\end{cases}$ (3)

The following claim formalizes the key observation that this bundling uses in
order to avoid losing any gain, and Lemma 3.4 shows that this bundling does
not change the value of the optimal DP.

######  Fact 3.3.

The optimal DP for prophet secretary OPT, will not set a threshold more than
OPT at any step.

To see why this holds, observe that at any point the threshold is the expected
gain in the subproblem with one less variable. If this threshold was more than
OPT, it would imply that the subproblem obtained a value higher than OPT.

######  Lemma 3.4.

Using the bundling described in (3), the value of the optimal DP solution does
not change.

We defer the proof of the Lemma to Section C.2 of the Appendix. After
transforming the variables as described above, for each variable, we use the
following discretization process.

  * •

Step 1: We make $0$ all the values of the support that are
$v_{i}<\varepsilon$.

  * •

Step 2: We discretize to powers of $(1+\varepsilon)$ all values in
$v_{i}\in[\varepsilon,1/\varepsilon^{2}]$.

###### Proof of Theorem 3.2.

This case is reduced to the constant support size case of Theorem 3.1 after
the above steps.

#### Bounding the error:

Observe initially that from Lemma 3.4 there is no loss incurred from the
bundling process. Using the same argument as Case 2 in the 2-point case, we
can discard all values at most $\varepsilon$. Through this process, we only
lose $O(\varepsilon)\text{OPT}$. For step 2, using Lemma 2.2 we again incur
loss of $O(\varepsilon)$.

#### Counting the support:

From our discretization process, Step 2 creates $\frac{\log
1/\varepsilon}{\log(1+\varepsilon)}$ different values.

Therefore each variable can have a support of size at most $\frac{\log
1/\varepsilon}{\log(1+\varepsilon)}+2$, where the extra $2$ is from the point
of mass above $1$ and Case 1 (if the initial variable did not have $0$ in the
support). Now using Theorem 3.1 with $c=O\left(\frac{\log
1/\varepsilon}{\log(1+\varepsilon)}\right)$ we get the theorem. ∎

Observe at this point that the techniques used also hold for continuous
distributions. In particular, steps 1 and 2 from above are well-defined for
continuous distributions. By applying these preprocessing steps, we have
transformed the continuous distribution to a discrete one with constant
support size. Moreover, it is easy to check that the same arguments as in the
case of discrete distributions apply for bounding the error. Then, we can
continue with the steps in the constant-support case (see section 3.1) and
obtain the same approximation guarantee. Since in the PTAS we start from the
discretization done in the QPTAS, it is immediate that the PTAS results and
techniques also hold for continuous distributions.

##  4 PTAS

In this section, we propose a PTAS for calculating an approximation of the
optimal reward of the prophet secretary problem. In the QPTAS algorithm, we
discretized the probabilities (and values) of the supports of each random
variable to powers of $(1+\varepsilon)$. However, even after the “bundling”
(via rounding) process, for each random variable the number of possible
realization probabilities of each support value can be $\Omega(\log n)$, and
the support size of each variable can be a constant. Thus, the total number of
variable groups can be $\text{polylog}(n)$ and there can be more than
$\text{poly}(n)$ states in the dynamic program, which means that a polynomial
time approximation scheme is not possible with only the discretization in
previous sections. In particular, we need to deal with the variables with
realization probabilities that are small (say $\text{poly}(\varepsilon)$), but
that there could be enough of them to make a non-negligible contribution to
the optimal reward. This is problematic even in a simple setting where each
variable is drawn from a two point distribution.

To solve this, we observe that for a sequence of random variables with small
realization probability, if their total realization probability is small
($O(\varepsilon^{2})$), we can make a decision for the sequence as a whole:
even if we have seen the realization of all such random variables, we do not
gain much compared to the original game where we need to make a decision at
the arrival of each variable. This technique, called _frontloading_ is the key
for our proof, and allows us to obtain a PTAS for the general Prophet
Secretary problem.

######  Theorem 4.1.

[PTAS for constant size support] There exists a
$(1-\varepsilon)$-approximation algorithm for the prophet secretary problem
against the online optimal that runs in time
$O(n^{(1/\varepsilon)^{\text{poly}(1/\varepsilon)}})$. In the special case of
2-point distributions with $v_{1}=0$ and $v_{2}>0$, we can get running time of
$O(n^{poly(\frac{1}{\varepsilon})})$.

In the following sections, we formally show our main theorem. There is a
summary of our notations in Table 1 in the Appendix for convenience.

###  4.1 A PTAS for binary distributions

We start with a simpler but representative case, where each variable’s
distribution $\mathcal{D}_{i}$ is again defined as

$X_{i}=\begin{cases}v_{i}&\text{, w.p. }p_{i}\\\ 0&\text{, w.p.
}1-p_{i}.\end{cases}$

Using QPTAS transformations, we can assume:

Normalization.  Every $X_{i}$ either has $v_{i}\leq 1/\varepsilon^{2}$, or
$v_{i}=v_{\max}$, where $v_{\max}$ is the largest possible support value of
the original instance. Additionally, we may assume $\text{OPT}\in[0.669,1]$ (
Claim 2).

Discretization.  There are only $\tilde{O}(1/\varepsilon)$ different values of
$v_{i}$ being either $v_{\max}$ or powers of $(1+\varepsilon)$ between
$\varepsilon$ and $1/\varepsilon^{2}$, losing at most $\varepsilon$ fraction
of optimal reward (Lemma 2.2). We can also assume that every $p_{i}$ is a
power of $(1+\varepsilon)$ (Lemma 2.3).

For every $v\in\mathbb{R}$, let $\mathbf{X}_{v}$ denote the set of random
variables with the two support values being $0$ and $v$. Some of the proofs in
this section are deferred to Section D.1 of the Appendix.

Small probability variables and special variables. We group random variables
that have “small realization probabilities”. Let $q_{i}=-\ln(1-p_{i})$. For
any set of random variables
$\mathbf{X}^{\prime}_{v}=\\{X_{i_{1}},X_{i_{2}},\cdots,X_{i_{k}}\\}\subseteq\mathbf{X}_{v}$,
the probability that $v$ gets realized from one of the random variables is
exactly

$1-\prod_{i_{j}}(1-p_{i_{j}})=1-\exp\left(\sum_{i_{j}}\ln(1-p_{i_{j}})\right)=1-\exp\left(-\sum_{i_{j}}q_{i_{j}}\right).$

Although $q_{i}$ is not the true probability of realization, when $p_{i}$ is
small enough, $q_{i}$ is a good approximation of $p_{i}$, and for any set
$\mathbf{X}^{\prime}_{v}$, $\sum_{i}q_{i}$ is a good approximation of the
probability that $v$ gets realized in one of the variables in
$\mathbf{X}^{\prime}_{v}$. This is because for any $p_{i}<\varepsilon$ we have
that $p_{i}<q_{i}<p_{i}(1+\varepsilon).$ This holds by writing down the Taylor
series of $q_{i}$ based on $p_{i}$.

#### First Preprocessing.

We initially split the variables into different groups, shown in Figure 2. For
each different support value $v$, the variables in $\mathbf{X}_{v}^{*}$ are
ignored if their total probability is at most $\varepsilon^{10}$. Variables in
$\mathbf{X}_{v}^{+}$ are discretized and treated like separate variables.

Specifically, for each support value $v\leq 1/\varepsilon^{2}$, define a set
of “small probability variables” $\mathbf{X}^{*}_{v}$ as

$\mathbf{X}^{*}_{v}=\\{X_{i}|X_{i}\in\mathbf{X}_{v},\ s.t.\
q_{i}<\varepsilon^{20}\\}.$

In other words, $\mathbf{X}^{*}_{v}$ contains all random variables $X_{i}$
with support values $0$ and $v$, such that $q_{i}<\varepsilon^{20}$. Since the
probabilities of realization have been discretized to powers of
$(1+\varepsilon)$, the number of distinct $p_{i}$ with
$-\ln(1-p_{i})=q_{i}\geq\varepsilon^{20}$ is only a constant (actually
$\tilde{O}(1/\varepsilon)$). Define
$\mathbf{X}^{+}_{v}=\mathbf{X}_{v}\setminus\mathbf{X}^{*}_{v}$, then it
contains only $\tilde{O}(1/\varepsilon)$ distinct random variables. We call
$\mathbf{X}^{+}_{v}$ “special variables with support $v$”, and
$\mathbf{X}^{+}=\bigcup_{v}\mathbf{X}^{+}_{v}$ the set of all special
variables. There are only a constant number of distinct random variables in
$\mathbf{X}^{+}$. Let
$\overline{Q}^{*}_{v}=\sum_{X_{i}\in\mathbf{X}^{*}_{v}}q_{i}$ denote the sum
of $q_{i}$ for all small-probability random variables with support values $0$
and $v$. Finally, let $Q_{\max}=\sum_{i:X_{i}\in X_{v_{\max}}}q_{i}$ and
$\mathbf{X}^{*}_{v_{\max}}=\\{X_{i}|X_{i}\in\mathbf{X}_{v_{max}},\ s.t.\
q_{i}<\varepsilon^{20}Q_{\max}\\}$.

######  Lemma 4.2.

For $v\leq 1/\varepsilon^{2}$, if $\overline{Q}^{*}_{v}<\varepsilon^{10}$ and
for $v_{max}\geq\varepsilon^{-2}$, if
$\overline{Q}^{*}_{v_{max}}<\varepsilon^{10}Q_{max}$, then ignoring the
variables in $\mathbf{X}^{*}_{v}$ reduces the optimal reward by at most
$\varepsilon^{8}$.

Using the above lemma, we can replace all variables in $\mathbf{X}^{*}_{v}$ to
zero values, where $\overline{Q}^{*}_{v}<\varepsilon^{10}$. Since there are
only $\tilde{O}(1/\varepsilon)$ distinct support values, the total loss in
reward is negligible. From now on we assume
$\overline{Q}^{*}_{v}\geq\varepsilon^{10}$ for every $v\leq 1/\varepsilon^{2}$
and that $\overline{Q}^{*}_{v_{max}}\geq\varepsilon^{10}Q_{max}$.

$v_{\max}$$1/\varepsilon^{2}$$(1+\varepsilon)^{k}=v_{i}$$\varepsilon$$Y_{2},Y_{6}$$Y_{42},Y_{8},Y_{9}$${\Big{\\}}}\mathbf{X}_{v_{i}}$$v$$p$$\varepsilon^{20}$$1$$\mathbf{X}^{*}_{v_{i}}$$\mathbf{X}^{+}_{v_{i}}$
Figure 2: First preprocessing of PTAS. In this example, variables
$Y_{2},Y_{6},Y_{42},Y_{8}$ and $Y_{9}$ have support value
$v_{i}=(1+\varepsilon)^{k}$, while $Y_{2}$ and $Y_{6}$ have probability of
being non-zero at most $\varepsilon^{20}$. If the total probability of
variables in $\mathbf{X}_{v_{i}}^{*}$ is at most $\varepsilon^{10}$, the
variables are ignored for the rest of the game.

#### Second Preprocessing.

Of the variables in $\mathbf{X}_{v}^{*}$ that remained we will split them in
blocks according to their probability as shown in Figure 3. We begin by
introducing some notation; we define
$Q^{*}_{v}=\min(\varepsilon^{-1},\overline{Q}^{*}_{v})$ and
$Q^{o}_{v}=\varepsilon^{4}Q^{*}_{v}$, and finally
$\delta_{v}=\frac{Q^{o}_{v}}{\overline{Q}^{*}_{v}}$.

Let $Y_{1},Y_{2},\ldots,Y_{n}$ be the random realization of all variables,
with $Y_{i}$ being the $i$’th random variable that arrives. For each support
value $v>0$, partition all random variables to $\varepsilon^{-4}+1$ blocks
$\mathbf{B}^{v}_{0},\mathbf{B}^{v}_{1},\ldots,\mathbf{B}^{v}_{\varepsilon^{-4}}$
such that each block contains a sequence of consecutive variables. In
particular, $\mathbf{B}^{v}_{0}$ contains the first
$n\left(1-\frac{Q^{*}_{v}}{\overline{Q}^{*}_{v}}\right)=n-\delta_{v}n/\varepsilon^{4}$
arrived variables (when $Q^{*}_{v}=\overline{Q}^{*}_{v}$ we have
$\mathbf{B}^{v}_{0}=\emptyset$); each of
$\mathbf{B}^{v}_{1},\ldots,\mathbf{B}^{v}_{\varepsilon^{-4}}$ contains
$\delta_{v}n$ consecutive variables.

Support value
$\mathbf{v}$$\mathbf{B}_{0}^{\mathbf{v}}$$\mathbf{B}_{1}^{\mathbf{v}}$$\dots$$\mathbf{B}_{\varepsilon^{-4}}^{\mathbf{v}}$$n\text{-}\delta_{v}n/\varepsilon^{4}$$\delta_{v}/n$$\delta_{v}/n$
Figure 3: Second Preprocessing of the PTAS. For each support value
$\mathbf{v}$ we split the variables into blocks $\mathbf{B}^{v}_{i}$. If
$\mathbf{B}^{v}_{0}$ is not empty, we ignore it at game $G_{3}$.

The intuition behind this partition is as follows. For all variables in
$\mathbf{X}^{*}_{v}$, the total $q_{i}$ of all variables in the last
$\varepsilon^{-4}$ blocks is roughly $Q^{*}_{v}$ with high probability, thus
all variables in the first block $\mathbf{B}^{v}_{0}$ with small realization
probability and support value 0 and $v$ can be ignored. Furthermore, for each
block $\mathbf{B}^{v}_{k}$, the total $q_{i}$ of variables in
$\mathbf{X}^{*}_{v}$ is roughly $\varepsilon^{4}Q^{*}_{v}$, which is small.
This means that even if all variables with small realization probability and
support value $0$ or $v$ in each block are realized together, it does not
influence the decision with high probability. This way, the small probability
random variables are grouped, and we don’t have to remember the identity of
each individual random variable. For different $v$, the partition of the
blocks can be different.

High level proof sketch. After performing the two preprocessing steps. the
main idea for our proof is to reduce our original prophet secretary problem to
a problem with a smaller optimal DP solution, without losing too much. Our
process is the following.

  1. 1.

Game $G_{1}$. We begin our reduction process, starting by game $G_{1}$ which
corresponds to the original Prophet Secretary problem. The whole reduction
process is shown in Figure 4.

  2. 2.

Game $G_{2}$. In this game we remove the high variance variables.
Specifically, we make sure that the realization prob of all variables in a
block is always within ($1\pm\varepsilon)$ of their expectation.

  3. 3.

Game $G_{3}$. We remove the small variables of block
$\mathbf{B}_{0}^{\mathbf{v}}$ for each support value $v$. This will not
decrease the reward by a factor more than $\epsilon$ of optimal, because by
game $G_{2}$ we know that the probability of realization of a variable within
the blocks except block zero is still considerable. This step is important, as
it gives us an interval in which the realization probability of $v$ will be.

  4. 4.

Game $G_{4}$. This is potentially the most crucial step, called
_frontloading_. In each block, and for each different support value $v$ we
“move” the uncertainty of the corresponding variables to the beginning of the
block. Specifically, we flip a coin at the beginning of a new block, and if
the flip succeeded we keep the value as an outside option.

  5. 5.

Game $G_{5}$. all outside options for $v$ have the same probability of
realization. By doing this, we do not have to keep track of different
probabilities for each outside option.

$G_{1}$$G_{2}$$G_{3}$$G_{4}$$G_{5}$$(1-\varepsilon)\leq$$(1-\varepsilon)\leq$$\leq$$(1-\varepsilon)\leq$$\geq$$\geq$$\geq
1/(1+\varepsilon)$$\geq$Lem 4.3Lem 4.4Lem 4.6Lem 4.7 Figure 4: Series of
reductions we use to prove Theorem 4.1. $G_{1}$ is the original Prophet
Secretary game, and $G_{5}$ is a new game that can be solved in polynomial
time.

Original prophet secretary game $G_{1}$. There are $n$ random variables
$X_{1},X_{2},\ldots,X_{n}$ arriving in random order. When each variable
arrives, the gambler observes the realized value and decides whether to take
it. If the gambler decides not to take the realized value, the value cannot be
taken later.

Prophet secretary game $G_{2}$ with possible failure. The gambler plays
prophet secretary game $G_{1}$, but the reward is set to $0$ if there exists a
possible support value $v$ and a block $\mathbf{B}^{v}_{k}$ such that for the
variables
$X_{i_{1}},X_{i_{2}},\ldots,X_{i_{\ell}}\in\mathbf{B}^{v}_{k}\cap\mathbf{X}^{*}_{v}$
we have that
$\sum_{X_{i_{j}}\in\mathbf{B}^{v}_{k}}q_{i_{j}}\not\in[(1-\varepsilon)Q^{o}_{v},(1+\varepsilon)Q^{o}_{v}]$.
In other words, when the realization probability of $v$ of all variables with
a small probability in a block is far from their expectation, no reward is
given to the gambler.

######  Lemma 4.3.

$(1-\varepsilon)\text{OPT}(G_{1})\leq\text{OPT}(G_{2})\leq\text{OPT}(G_{1})$.

###### Proof.

First, we show the following claim.

######  Claim 5.

Suppose we have $n$ non-negative real numbers $A_{1},\cdots,A_{n}$ with
$A_{i}\leq\varepsilon^{10}\delta A$ for some $\delta<1$ where
$A:=\sum_{i}A_{i}$. If we sample $m=\delta n$ numbers $Y_{1},\cdots,Y_{m}$
uniformly at random and without replacement, then

$\textbf{Pr}\left[|Y-\mathbb{E}\left[Y\right]|\geq\varepsilon\mathbb{E}\left[Y\right]\right]<\varepsilon^{8}.$

Now fix a block $\mathbf{B}^{v}_{k}$. In the lemma above, let $n$ be the total
number of variables, $A=\overline{Q}^{*}_{v}$ and $\delta=\delta_{v}$. Finally
let $A_{i}=q_{i}$ for each variable $X_{i}\in\mathbf{X}^{*}_{v}$. Note that
the expectation of the sum of small probability variables is $Q^{o}_{v}$.
Therefore, using the above lemma we conclude that the probability that the sum
of $q_{i}$’s for small probability variables in a block (which corresponds to
the $Y_{i}$’s) deviates from their expectation by more than a multiplicative
factor of $\varepsilon$ is at most $\varepsilon^{8}$. Now there are
$\varepsilon^{-4}$ many blocks, and there are at most
$\tilde{O}(1/\varepsilon)<\varepsilon^{-2}$ many different support values.
Using union bound, we can conclude that the event that prompts the gambler not
to get any award in $G_{2}$ happens with probability at most
$\varepsilon^{8}\cdot\varepsilon^{-4}\cdot\varepsilon^{-2}=\varepsilon^{2}$.
This concludes the proof of the lemma. ∎

Prophet secretary game $G_{3}$ with lazy decision. The gambler plays game
$G_{2}$. However, every variable with support $0$ and $v$ and small
realization probability in $\mathbf{X}^{*}_{v}\cap\mathbf{B}^{v}_{0}$ is not
realized.

######  Lemma 4.4.

$(1-\varepsilon)\text{OPT}(G_{2})\leq\text{OPT}(G_{3})\leq\text{OPT}(G_{2})$.

Before moving onto the proof of the lemma, we state an observation used in the
proof.

######  Observation 4.5.

Let $Q^{*}_{v}=\min(\varepsilon^{-1},\overline{Q}^{*}_{v})$. If we encounter a
variable $X_{i}\in\mathbf{X}^{*}_{v}$ while the remaining variables in
$\mathbf{X}^{*}_{v}$ have total $q_{i}$ more than $Q^{*}_{v}$, then ignoring
$X_{i}$ decreases the reward of the algorithm by a factor of at most
$\varepsilon$.

###### Proof of Lemma 4.4.

By the definition of $G_{2}$, we know that the effective sum222Here by
effective sum we mean that the cases explained in $G_{2}$ are ignored. of $q$
values of $X_{i}$ variables in $\mathbf{B}^{v}_{k}\cap\mathbf{X}^{*}_{v}$ for
any $k$ is in the interval
$[(1-\varepsilon)Q^{o}_{v},(1+\varepsilon)Q^{o}_{v}]$. The total number of
blocks, other than the first one, is $\varepsilon^{-4}$. This means the total
sum of $q$ values of these variables is in the interval
$\varepsilon^{-4}[(1-\varepsilon)Q^{o}_{v},(1+\varepsilon)Q^{o}_{v}]=Q^{*}_{v}[(1-\varepsilon),(1+\varepsilon)]$.
Now using Observation 4.5, since we know that if we skip block
$\mathbf{B}^{v}_{0}$, the sum of $q_{i}$s of the remaining variables is at
least $(1-\varepsilon)Q^{*}_{v}$, the loss in reward can be at most
$\varepsilon(1-\varepsilon)=O(\varepsilon^{2})$. This concludes the proof. ∎

Prophet secretary game $G_{4}$ with lazy decision and outside option. The
gambler plays prophet secretary game $G_{3}$. However, in each block
$\mathbf{B}^{v}_{k}$ with $k\geq 1$, the realization of variables with small
probability in $\mathbf{X}^{*}_{v}\cap\mathbf{B}^{v}_{k}$ is different. In
particular, all variables in $\mathbf{X}^{*}_{v}\cap\mathbf{B}^{v}_{k}$ are
realized at the beginning of $\mathbf{B}^{v}_{k}$ (and not later), and kept as
an outside option $Z_{v}$. Whenever the gambler decides to accept a variable
$Y_{i}$ in $\mathbf{B}^{v}_{k}$, the gambler can choose to replace $Y_{i}$ by
$Z_{v}$. At the end of $\mathbf{B}^{v}_{k}$, the gambler can take $Z_{v}$ and
stop. If the gambler decides to take nothing and continue the game, the
outside option $Z_{v}$ is cleared.

######  Lemma 4.6.

$\text{OPT}(G_{3})\leq\text{OPT}(G_{4})\leq(1+\varepsilon)\text{OPT}(G_{3})$.

###### Proof of Lemma 4.6.

We prove this lemma by induction on the number of support values that have
been grouped. For any set $\mathbf{V}$ of support values, let the game
$G_{3}(\mathbf{V})$ be $G_{3}$ in which only variables with support values
$v\in\mathbf{V}$ are grouped. Then $G_{4}=G_{3}(\\{\textrm{all support
values}\\})$. First, we show that
$\text{OPT}(G_{3})\leq\text{OPT}(G_{3}(\\{v\\}))\leq(1+O(\varepsilon^{3}))\text{OPT}(G_{3})$
(base case). Notice that the exact same proof works for showing that for any
$\mathbf{V}$,
$\text{OPT}(G_{3}(\mathbf{V}))\leq\text{OPT}(G_{3}(\mathbf{V}\cup\\{v^{\prime}\\}))\leq(1+O(\varepsilon^{3}))\text{OPT}(G_{3}(\mathbf{V}))$
when an additional support value $v^{\prime}$ is grouped (inductive step).
Then by induction
$\text{OPT}(G_{3})\leq\text{OPT}(G_{4})\leq(1+\varepsilon)\text{OPT}(G_{3})$,
as there are only $\tilde{O}(1/\varepsilon)<1/\varepsilon^{2}$ distinct
discretized support values.

Denote $G_{3}^{v}=G_{3}(\\{v\\})$. Notice that the gambler in game $G_{3}$ has
strictly less information than the gambler in game $G_{3}^{v}$: in any block
$\mathbf{B}^{v}_{k}$ in $G_{3}^{v}$, compared to $G_{3}$, the variables with
small probability and support value $v$ are front-loaded and realized together
at the beginning of the block, and exist as an outside option throughout the
entire block. Thus the optimal reward of $G_{3}^{v}$ is always at least the
optimal reward of $G_{3}$, i.e. $\text{OPT}(G_{3})\leq\text{OPT}(G_{3}^{v})$.
In the remainder of the proof, we show that
$\text{OPT}(G_{3}^{v})\leq(1+O(\varepsilon^{3}))\text{OPT}(G_{3})$. In
particular, we show how to transform an optimal algorithm $\mathcal{A}_{v}$ of
Game $G_{3}^{v}$ to an algorithm $\mathcal{A}$ of Game $G_{3}$, while the
reward is almost unchanged. As the optimal decision of $G_{3}^{v}$ can be
calculated via a dynamic program, we can assume without loss of generality
that $\mathcal{A}_{v}$ is a threshold-based algorithm (using the optimal
online reward of the remaining instance at each step), with the threshold
being non-increasing over time.

Coupling. We consider the decision trees of the two games. For each node in
the decision tree of $G_{3}$, there is a corresponding node in the decision
tree of $G_{3}^{v}$, where the realization histories of all variables are
identical. We completely couple the randomness of the two games, so that when
we analyze the decision trees of the two games, the arrival order of the
variables and the realized value of each variable are the same.

Building $\mathcal{A}$ from $\mathcal{A}_{v}$.

  1. 1.

On block $\mathbf{B}^{v}_{0}$, algorithm $\mathcal{A}$ makes exactly the same
decision in $G_{3}$ as the algorithm $\mathcal{A}_{v}$ in game $G_{3}^{v}$.
The expected reward from $\mathbf{B}^{v}_{0}$ in the two games will be the
same. This is because in going from game $G_{2}$ to $G_{3}$, we made the
assumption that the reward from all the small probability variables of support
$v$ in $\mathbf{B}^{v}_{0}$ are zeroed out.

  2. 2.

On block $\mathbf{B}^{v}_{k}$, consider any node $N_{v}$ in the decision tree
when the gambler reaches $\mathbf{B}^{v}_{k}$ and let $N$ be the corresponding
node in the decision tree of $G_{3}$. Depending on how $\mathcal{A}_{v}$
performs, we define $\mathcal{A}$:

Case 1. In $\mathcal{A}_{v}$, after the gambler reaches decision node $N_{v}$,
she always wants to accept $v$ whenever it is available in
$\mathbf{B}^{v}_{k}$. Consider the following algorithm $\mathcal{A}$ for
$G_{3}$:

  * •

Whenever the gambler observes $v$ realized by a variable in
$\mathbf{X}^{*}_{v}$, the algorithm accepts it;

  * •

Whenever the gambler observes a realized value not in $\mathbf{X}^{*}_{v}$,
the gambler makes the same decision as in the corresponding node in
$G_{3}^{v}$, that if the $\mathcal{A}_{v}$ accepts the same value (possibly
changed to an outside option $v$) in $G_{3}^{v}$, $\mathcal{A}$ also accepts
the variable in $G_{3}$; if $\mathcal{A}_{v}$ does not accept the same value
in the corresponding node in $G_{3}^{v}$, $\mathcal{A}$ also rejects the
variable.

Analysis. We analyze how much reward difference the two algorithms have in
$\mathbf{B}^{v}_{k}$.

  1. (a)

Since $\mathcal{A}_{v}$ always accepts outside option $v$ at the end of block
$\mathbf{B}^{v}_{k}$, the probability that $\mathcal{A}_{v}$ accepts some
variable in $\mathbf{B}^{v}_{k}$ is identical to the probability that
$\mathcal{A}$ accepts some variable in $\mathbf{B}^{v}_{k}$.

  2. (b)

Any time $\mathcal{A}_{v}$ accepts some variable $X_{i}$ before the end of
$\mathbf{B}^{v}_{k}$ in $G_{3}^{v}$, $\mathcal{A}$ either accepts $X_{i}$ in
the corresponding node in $G_{3}$, or it accepts $v$ from a variable in
$\mathbf{X}^{*}_{v}$ before reaching the node (and at the same time
$\mathcal{A}_{v}$ can accept $\max(v,X_{i})$). This happens with probability
at most $(1+\varepsilon)Q^{o}_{v}<2Q^{o}_{v}<2\varepsilon^{3}$, as the total
$q_{i}$ of all variables in $\mathbf{X}^{*}_{v}$ in $\mathbf{B}^{v}_{k}$ is at
most $(1+\varepsilon)Q^{o}_{v}$.

  3. (c)

Any time $\mathcal{A}_{v}$ accepts the outside option $v$ at the end of
$\mathbf{B}^{v}_{k}$ in $G_{3}^{v}$, $\mathcal{A}$ accepts $v$ in $G_{3}$.

This way, we have coupled the reward of the two algorithms in the two games,
such that whenever $\mathcal{A}_{v}$ accepts some value, $\mathcal{A}$ accepts
a possibly different value with probability at most $2\varepsilon^{3}$. Thus
the reward of $\mathcal{A}$ in block $\mathbf{B}^{v}_{k}$ in Game $G_{3}$ is
at least $(1-2\varepsilon^{3})$ fraction of the reward of $\mathcal{A}_{v}$ in
block $\mathbf{B}^{v}_{k}$ in Game $G_{3}^{v}$, starting from corresponding
nodes $N$ and $N_{v}$ in the two decision trees.
Case 2. If in $\mathcal{A}_{v}$, after the gambler reaches decision node
$N_{v}$ the gambler does not always want to accept $v$ whenever it is
available in $\mathbf{B}^{v}_{k}$. Consider the following algorithm
$\mathcal{A}$ for $G_{3}$:

  * •

Whenever the gambler observes $v$ realized by a variable in
$\mathbf{X}^{*}_{v}$, the algorithm rejects it;

  * •

whenever the gambler observes a realized value not in $\mathbf{X}^{*}_{v}$,
the gambler makes the same decision as in the corresponding node in
$G_{3}^{v}$ in a way the same as Case 1.

Analysis. The following cases may occur:

  1. (a)

When a variable $X_{i}$ not in $\mathbf{X}^{*}_{v}$ arrives in $G_{3}^{v}$,
and $\mathcal{A}_{v}$ decides to accept it, $\mathcal{A}$ also accepts $X_{i}$
in $G_{3}$ with the same value. Since with probability at most
$(1+\varepsilon)Q^{o}_{v}<2Q^{o}_{v}<2\varepsilon^{3}$, the value accepted by
$\mathcal{A}_{v}$ is replaced by $\max(v,G_{v})$, we have coupled the two
games such that the reward of $\mathcal{A}$ is at least $(1-2\varepsilon^{3})$
fraction of the reward of $\mathcal{A}_{v}$.

  2. (b)

When $\mathcal{A}_{v}$ reaches the end of the block $\mathbf{B}^{v}_{k}$ at
some decision node $N_{v,1}$, and $\mathcal{A}_{v}$ decides to accept the
outside option whenever it is $v$, $\mathcal{A}$ does not accept any variable
in $\mathbf{B}^{v}_{k}$. Therefore, the reward loss from $\mathcal{A}$ in
$G_{3}$ is $v$ with probability at most $2Q^{o}_{v}$, conditioned on that
$\mathcal{A}_{v}$ reaches decision node $N_{v,1}$. In the future, as
$\mathcal{A}_{v}$ already decides to accept $v$ at $N_{v,1}$, it will always
decide to accept $v$ whenever available in the decision tree rooted at
$N_{v,1}$, since the optimal threshold based algorithm always sets non-
increasing thresholds. Thus in the decision tree rooted at the corresponding
node of $N_{v,1}$ in $G_{3}$, this case will not be discussed, which means
that any decision node like $N_{v,1}$ discussed in this case cannot be the
ancestor of another such node.

  3. (c)

When $\mathcal{A}_{v}$ reaches the end of the block $\mathbf{B}^{v}_{k}$ at
some decision node $N_{v,2}$, and $\mathcal{A}_{v}$ decides not to accept the
outside option even if it is $v$, both algorithms do not accept any variable
in $\mathbf{B}^{v}_{k}$, thus both have reward 0.

Now we are ready to analyze the reward of $\mathcal{A}$ in
$\mathbf{B}^{v}_{k}$ of $G_{3}$. It is at least $(1-2\varepsilon^{3})$ times
the reward of $\mathcal{A}_{v}$ in $\mathbf{B}^{v}_{k}$ of $G_{3}^{v}$, minus
$\textbf{Pr}\left[\mathcal{A}_{v}\textrm{ reaches a node like }N_{v,1}\textrm{
in Case 2(b)}\right]\cdot 2Q^{o}_{v}\cdot v$. Thus summing the reward for all
of the blocks, we have

$ALG(\mathcal{A},G_{3})\geq(1-2\varepsilon^{3})\text{OPT}(G_{3}^{v})-\sum_{k}\sum_{N_{v,1}}\textbf{Pr}\left[\mathcal{A}_{v}\textrm{
reaches }N_{v,1}\textrm{ in Case 2(b) in }\mathbf{B}^{v}_{k}\right]\cdot
2Q^{o}_{v}v.$

As we discussed in Case 2(b), no decision node like $N_{k,1}$ is the ancestor
of another decision node in Case 2(b) in later blocks. Thus
$\sum_{k}\sum_{N_{v,1}}\textbf{Pr}\left[\mathcal{A}_{v}\textrm{ reaches
}N_{v,1}\textrm{ in Case 2(b) in }\mathbf{B}^{v}_{k}\right]\leq 1$, which
implies

$ALG(\mathcal{A},G_{3})\geq(1-2\varepsilon^{3})\text{OPT}(G_{3}^{v})-2Q^{o}_{v}v.$
(4)

Now we bound $Q^{o}_{v}v$. Observe that if an algorithm only accepts realized
value $v$ from $\mathbf{X}^{*}_{v}$, as the realization probability of $v$ is
at least $(1-e^{-Q^{*}_{v}})$, its reward is at least $(1-e^{-Q^{*}_{v}})v$.
Thus $(1-e^{-Q^{*}_{v}})v\leq\text{OPT}(G_{3}).$ Also notice that when $1\leq
Q^{*}_{v}\leq 1/\varepsilon$, $1-e^{-Q^{*}_{v}}\geq 1-e^{-1}$, while
$Q^{o}_{v}=\varepsilon^{4}Q^{*}_{v}\leq\varepsilon^{3}$, thus
$Q^{o}_{v}v\leq\frac{e}{e-1}\varepsilon^{3}\text{OPT}(G_{3})$; when
$Q^{*}_{v}<1$, $1-e^{-Q^{*}_{v}}>\frac{1}{2}Q^{*}_{v}$, thus
$Q^{o}_{v}v=\varepsilon^{4}Q^{*}_{v}v<2\varepsilon^{4}\text{OPT}(G_{3})$.
Therefore, $Q^{o}_{v}v=O(\varepsilon^{3})\text{OPT}(G_{3})$ always holds, so
by (4) we have

$\text{OPT}(G_{3})\geq
ALG(\mathcal{A},G_{3})\geq(1-O(\varepsilon^{3}))\text{OPT}(G_{3}^{v}),$

which completes the proof. ∎

Prophet secretary game $G_{5}$ with perturbed outside option. The gambler
plays the prophet secretary game $G_{4}$. However, in each block
$\mathbf{B}^{v}_{k}$ with $k\geq 1$, the outside option $Z_{v}$ is set to $v$
with a fixed probability $1-e^{-(1-\varepsilon)Q^{o}_{v}}$.

######  Lemma 4.7.

$(1-\varepsilon)\text{OPT}(G_{4})\leq\text{OPT}(G_{5})\leq\text{OPT}(G_{4})$.

The proof of this lemma can be found in D.5, and is identical to the proof of
the similar lemma for the general distribution case.

Combining Lemmas 4.3, 4.4, 4.6 and 4.7 above, we get the following corollary,
showing that Game $G_{5}$ obtains almost the same optimal reward as the
original prophet secretary problem.

######  Corollary 4.8.

$(1-O(\varepsilon))\text{OPT}(G_{1})\leq\text{OPT}(G_{5})\leq(1+O(\varepsilon))\text{OPT}(G_{1})$.

######  Theorem 4.9.

Prophet secretary game $G_{5}$ can be optimally solved in time
$n^{\text{poly}(\frac{1}{\varepsilon})}$.

###### Proof of Theorem 4.9.

We propose a dynamic program that solves $G_{5}$ in
$n^{\text{poly}(\frac{1}{\varepsilon})}$ time.

First, recall our assumption that for any value $v$ in support of some
variable, we have $\varepsilon\leq v\leq\varepsilon^{-2}$. Moreover, we
discretized the space, so that there are only
$\tilde{O}(\frac{1}{\varepsilon})$ different values of $v$, and that all
probabilities $p_{i}$ are powers of $(1+\varepsilon)$ and belong in
$[\varepsilon^{20},1]$ for $v_{i}\leq 1/\varepsilon^{2}$, and
$p_{i}\in[\varepsilon^{20}Q_{\max}/(1+\varepsilon),Q_{\max}]$ where
$Q_{\max}=\sum_{i:X_{i}\in X_{v_{\max}}}q_{i}$. At any point in the sequence,
let $n_{v,p}$ be the number of remaining variables with support value $v$ and
probability of realization of $p$. We claim that the information the optimal
algorithm needs to make a decision at each point is the value of $n_{v,p}$ for
all $v$ and $p$, and the values of $Z_{v}$, the outside option of the current
block of $v$, for every value $v$. This is because if the algorithm is facing
variable $X$, and it is of the group $(v,p)$, then the choice it makes depends
on the realized value of $X$ (whether it is $0$ or $v$), the outside option
$Z_{v}$, and the expected optimal value of the future, given that the number
of variables of group $(v,p)$ is one less than before. So if
$\mathcal{N}=\\{n_{v,p}\\}_{\forall v,\forall p}$ and
$\mathcal{Z}=\\{Z_{v}\\}_{\forall v}$, then one can define

$\text{OPT}(\mathcal{N},\mathcal{Z})=\sum_{v,p}\textbf{Pr}\left[\textrm{next
variable is
X=(v,p)}\right]\cdot\mathbb{E}_{X}\left[\max(X,\max_{v}Z_{v},\text{OPT}(\mathcal{N}_{v,p},\mathcal{Z}^{\prime}))\right]$

where $\mathcal{N}_{v,p}$ is the same as $\mathcal{N}$, only that its
corresponding value for $n_{v,p}$ is deducted by 1. Moreover,
$\mathcal{Z}^{\prime}$ is the same as $\mathcal{Z}$, unless we are at a
”critical point”, where we get inside the next block $\mathbf{B}^{v}_{k}$ for
some support value $v$. In order to obtain $\mathcal{Z}^{\prime}$ from
$\mathcal{Z}$ we do the following; (1) if there’s no new group starting it
remains the same (2) if there is a new group starting, we change the outside
option of the group that ended to $0$, and flip again the coin to see if we
still have the variable $v$ available.

Size of the DP:  The total number of values in support is at most $\frac{\log
1/\varepsilon}{\log(1+\varepsilon)}=\tilde{O}{(1/\varepsilon)}$ and the total
number of possible probabilities is at most $20\frac{\log
1/\varepsilon}{\log(1+\varepsilon)}=\tilde{O}{(1/\varepsilon)}$. Moreover, for
all $v$ and $p$, $0\leq n_{v,p}\leq n$, and the value of $Z_{v}$ is either $0$
or $v$. This means the first component $\mathcal{N}$ of DP has at most
$n^{\text{poly}(\frac{1}{\varepsilon})}$ possible choices, and the second
component $\mathcal{Z}$ has $2^{\tilde{O}(1/\varepsilon)}$ possibilities. If
at the beginning of the sequence, the values are stored in $\mathcal{N}_{0}$
and $\mathcal{Z}_{0}$, then finding
$\text{OPT}(\mathcal{N}_{0},\mathcal{Z}_{0})$ gives us the optimal answer.
This takes time at most $O(n^{\text{poly}(1/\varepsilon)})$, yielding a PTAS.
∎

######  Corollary 4.10.

There exists a PTAS algorithm for the prophet secretary game $G_{1}$. This is
a direct result of Corollary 4.8 and Theorem 4.9.

######  Remark.

The main idea in generalizing this scheme to general distributions is that we
transform each distribution with support of size $k>2$, to $k$ distributions
in the 2 point form, where each is one of the support values with its
corresponding probability and the rest of the mass is on zero. These
distributions arrive sequentially.

## References

  * Agrawal et al. (2020) Shipra Agrawal, Jay Sethuraman, and Xingyu Zhang.  On optimal ordering in the optimal stopping problem.  In _EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary_ , pages 187–188, 2020.
  * Alaei (2011) Saeed Alaei.  Bayesian combinatorial auctions: Expanding single buyer mechanisms to many buyers.  In _FOCS’11: The 52nd IEEE Symposium on Foundations of Computer Science, Palm Springs, CA, USA_ , pages 512–521, 2011.
  * Anari et al. (2019) Nima Anari, Rad Niazadeh, Amin Saberi, and Ali Shameli.  Nearly optimal pricing algorithms for production constrained and laminar bayesian selection.  In _EC’19: The 20th ACM Conference on Economics and Computation, Phoenix, AZ, USA_. ACM, 2019.
  * Azar et al. (2018) Yossi Azar, Ashish Chiplunkar, and Haim Kaplan.  Prophet secretary: Surpassing the 1-1/e barrier.  In _EC’18: The 19th ACM Conference on Economics and Computation, Ithaca, NY, USA_ , pages 303–318, 2018.
  * Beyhaghi and Cai (2022) Hedyeh Beyhaghi and Linda Cai.  Pandora’s problem with nonobligatory inspection: Optimal structure and a PTAS.  _CoRR_ , abs/2212.01524, 2022.  URL https://doi.org/10.48550/arXiv.2212.01524.
  * Beyhaghi and Kleinberg (2019) Hedyeh Beyhaghi and Robert Kleinberg.  Pandora’s problem with nonobligatory inspection.  In _EC’19: The 20th ACM Conference on Economics and Computation, Phoenix, AZ, USA_ , pages 131–132, 2019.
  * Boodaghians et al. (2020) Shant Boodaghians, Federico Fusco, Philip Lazos, and Stefano Leonardi.  Pandora’s box problem with order constraints.  In _EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary_ , pages 439–458, 2020.
  * Braverman et al. (2022) Mark Braverman, Mahsa Derakhshan, and Antonio Molina Lovett.  Max-weight online stochastic matching: Improved approximations against the online benchmark.  In _EC’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA_ , page 967–985, 2022.
  * Bubna and Chiplunkar (2022) Archit Bubna and Ashish Chiplunkar.  Prophet inequality: Order selection beats random order.  _CoRR_ , abs/2211.04145, 2022.  doi: 10.48550/arXiv.2211.04145.  URL https://arxiv.org/pdf/2211.04145.pdf.
  * Chakraborty et al. (2010) Tanmoy Chakraborty, Eyal Even-Dar, Sudipto Guha, Yishay Mansour, and S. Muthukrishnan.  Approximation schemes for sequential posted pricing in multi-unit auctions.  In _WINE’10: The Sixth International Workshop on Internet and Network Economics, Stanford, CA, USA_ , pages 158–169. 2010.
  * Chawla et al. (2010) Shuchi Chawla, Jason D. Hartline, David L. Malec, and Balasubramanian Sivan.  Multi-parameter mechanism design and sequential posted pricing.  In _STOC ’10: The Forty-Second ACM Symposium on Theory of Computing, Cambridge, MA, USA_ , page 311–320, 2010.
  * Chawla et al. (2020) Shuchi Chawla, Evangelia Gergatsouli, Yifeng Teng, Christos Tzamos, and Ruimin Zhang.  Pandora’s box with correlations: Learning and approximation.  In _FOCS’20: 61st IEEE Annual Symposium on Foundations of Computer Science, Durham, NC, USA_ , pages 1214–1225, 2020.
  * Chawla et al. (2021) Shuchi Chawla, Evangelia Gergatsouli, Jeremy McMahan, and Christos Tzamos.  Approximating pandora’s box with correlations.  _CoRR_ , abs/2108.12976, 2021.  URL https://arxiv.org/abs/2108.12976.
  * Correa et al. (2017) José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld.  Posted price mechanisms for a random stream of customers.  In _EC’17: The 18th ACM Conference on Economics and Computation, Cambridge, MA, USA_ , pages 169–186, 2017.
  * Correa et al. (2018) José R. Correa, Patricio Foncea, Ruben Hoeksma, Tim Oosterwijk, and Tjark Vredeveld.  Recent developments in prophet inequalities.  _SIGecom Exchanges_ , 17(1):61–70, 2018.
  * Correa et al. (2019a) José R. Correa, Patricio Foncea, Dana Pizarro, and Victor Verdugo.  From pricing to prophets, and back!  _Operations Research Letters_ , 47(1):25–29, 2019a.
  * Correa et al. (2019b) José R. Correa, Raimundo Saona, and Bruno Ziliotto.  Prophet secretary through blind strategies.  In _SODA’19: The 30th ACM-SIAM Symposium on Discrete Algorithms, San Diego, California, USA_ , pages 1946–1961, 2019b.
  * Doval (2018) Laura Doval.  Whether or not to open pandora’s box.  _Journal of Economic Theory_ , 175:127–158, 2018.
  * Dütting et al. (2017) Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier.  Prophet inequalities made easy: Stochastic optimization by pricing non-stochastic inputs.  In _FOCS’17: The 58th IEEE Symposium on Foundations of Computer Science, Berkeley, CA, USA_ , pages 540–551, 2017.
  * Dütting et al. (2020) Paul Dütting, Thomas Kesselheim, and Brendan Lucier.  An O(log log m) prophet inequality for subadditive combinatorial auctions.  In _FOCS’20: The 61st IEEE Symposium on Foundations of Computer Science, Durham, NC, USA_ , pages 306–317, 2020.
  * Ehsani et al. (2018) Soheil Ehsani, MohammadTaghi Hajiaghayi, Thomas Kesselheim, and Sahil Singla.  Prophet secretary for combinatorial auctions and matroids.  In _SODA’18: The 29th Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, USA_ , pages 700–714, 2018.
  * Esfandiari et al. (2015) Hossein Esfandiari, MohammadTaghi Hajiaghayi, Vahid Liaghat, and Morteza Monemizadeh.  Prophet secretary.  In _ESA’15: The 23rd European Symposium on Algorithms Algorithms, Patras, Greece_ , pages 496–508, 2015.
  * 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 _EC ’20: The 21st ACM Conference on Economics and Computation, Virtual Event, Hungary_ , pages 769–787, 2020.
  * Ezra et al. (2022) Tomer Ezra, Michal Feldman, Nick Gravin, and Zhihao Gavin Tang.  General graphs are easier than bipartite graphs: Tight bounds for secretary matching.  In _EC ’22: The 23rd ACM Conference on Economics and Computation, Boulder, CO, USA_ , pages 1148–1177, 2022.
  * Feldman et al. (2015) Michal Feldman, Nick Gravin, and Brendan Lucier.  Combinatorial auctions via posted prices.  In _SODA’15: The 26th Annual ACM-SIAM Symposium on Discrete Algorithms, San Diego, CA, USA_ , pages 123–135, 2015.
  * Feldman et al. (2016) Moran Feldman, Ola Svensson, and Rico Zenklusen.  Online contention resolution schemes.  In _SODA’16:The 27th ACM-SIAM Symposium on Discrete Algorithms, Arlington, VA, USA_ , pages 1014–1033, 2016.
  * Fu et al. (2018) Hao Fu, Jian Li, and Pan Xu.  A PTAS for a Class of Stochastic Dynamic Programs.  In _ICALP’18: 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic_ , pages 56:1–56:14, 2018.
  * Fu et al. (2022) Hu Fu, Jiawei Li, and Daogao Liu.  Pandora box problem with nonobligatory inspection: Hardness and improved approximation algorithms.  _CoRR_ , abs/2207.09545, 2022.  doi: 10.48550/arXiv.2207.09545.  URL https://doi.org/10.48550/arXiv.2207.09545.
  * Gravin and Wang (2019) Nikolai Gravin and Hongao Wang.  Prophet inequality for bipartite matching: Merits of being simple and non adaptive.  In _Proceedings of the 2019 ACM Conference on Economics and Computation, EC 2019, Phoenix, AZ, USA, June 24-28, 2019_ , pages 93–109. ACM, 2019.  doi: 10.1145/3328526.3329604.  URL https://doi.org/10.1145/3328526.3329604.
  * Guha et al. (2008) Sudipto Guha, Kamesh Munagala, and Saswati Sarkar.  Information acquisition and exploitation in multichannel wireless networks.  _CoRR_ , abs/0804.1724, 2008.  URL https://arxiv.org/abs/0804.1724.
  * Hajiaghayi et al. (2007) Mohammad Taghi Hajiaghayi, Robert D. Kleinberg, and Tuomas Sandholm.  Automated online mechanism design and prophet inequalities.  In _AAAI’07: The 22nd AAAI Conference on Artificial Intelligence, Vancouver, British Columbia, Canada_ , pages 58–65, 2007.
  * Hill and Kertz (1982) T. P. Hill and Robert P. Kertz.  Comparisons of stop rule and supremum expectations of i.i.d. random variables.  _The Annals of Probability_ , 10(2), 1982.  doi: 10.1214/aop/1176993861.
  * Hill and Kertz (1992) Theodore P. Hill and Robert P. Kertz.  A survey of prophet inequalities in optimal stopping theory.  _Contemporary Mathematics_ , 125, 1992.
  * Kleinberg and Weinberg (2012) Robert Kleinberg and S. Matthew Weinberg.  Matroid prophet inequalities.  In _STOC’12: The 44th Symposium on Theory of Computing Conference, New York, NY, USA_ , pages 123–136, 2012.
  * Krengel and Sucheston (1977) Ulrich Krengel and Louis Sucheston.  Semiamarts and finite values.  _Bulletin of the American Maththematical Society_ , 83(4):745–747, 07 1977.  URL https://projecteuclid.org:443/euclid.bams/1183538915.
  * Krengel and Sucheston (1978) Ulrich Krengel and Louis Sucheston.  On semiamarts, amarts, and processes with finite value.  _Advances on Probabilty and Related Topics_ , 4:197–266, 1978.
  * Liu et al. (2021) Allen Liu, Renato Paes Leme, Martin Pál, Jon Schneider, and Balasubramanian Sivan.  Variable decomposition for prophet inequalities and optimal ordering.  In _EC’21: The 22nd ACM Conference on Economics and Computation_ , page 692, 2021.
  * Lucier (2017) Brendan Lucier.  An economic view of prophet inequalities.  _SIGecom Exchanges_ , 16(1):24–47, 2017.
  * Naor et al. (2023) Joseph Naor, Aravind Srinivasan, and David Wajc.  Online dependent rounding schemes.  _CoRR_ , abs/2301.08680, 2023.  URL https://doi.org/10.48550/arXiv.2301.08680.
  * Niazadeh et al. (2018) Rad Niazadeh, Amin Saberi, and Ali Shameli.  Prophet inequalities vs. approximating optimum online.  In _WINE’18: 14th Conference on Web and Internet Economics, Oxford, UK_ , pages 356–374, 2018.
  * Papadimitriou et al. (2021) Christos Papadimitriou, Tristan Pollner, Amin Saberi, and David Wajc.  Online stochastic max-weight bipartite matching: Beyond prophet inequalities.  In _EC’22: The 22nd ACM Conference on Economics and Computation, Phoenix, AZ, USA_ , page 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 _FOCS’22: The 63rd IEEE Symposium on Foundations of Computer Science, Denver, CO, USA_ , 2022.
  * Saberi and Wajc (2021) Amin Saberi and David Wajc.  The Greedy Algorithm is _not_ Optimal for On-Line Edge Coloring.  In _ICALP’21: 48th International Colloquium on Automata, Languages, and Programming, Glasgow, Scotland_ , pages 109:1–109:18, 2021.
  * Samuel-Cahn (1984) Ester Samuel-Cahn.  Comparison of threshold stop rules and maximum for independent nonnegative random variables.  _Annals of Probability_ , 12(4):1213–1216, 11 1984.  doi: 10.1214/aop/1176993150.
  * Segev and Singla (2021) Danny Segev and Sahil Singla.  Efficient approximation schemes for stochastic probing and prophet problems.  In _EC ’21: The 22nd ACM Conference on Economics and Computation, Budapest, Hungary_ , pages 793–794, 2021.
  * Weitzman (1979) Martin L Weitzman.  Optimal Search for the Best Alternative.  _Econometrica_ , 47(3):641–654, May 1979.

##  Appendix A Why Simple Grouping Ideas Fail

Our initial idea for grouping “similar” variables was to group the ones that
have similar (within $\varepsilon$) expected value and variance, to obtain the
groups shown in the grid shown in Figure 5. Ideally grouping the variables
like that, and treating variables that “fall” in the same square of the grid
as the same will not cost more than $O(\varepsilon)$ in the optimal DP.

$\mathbb{E}\left[X\right]$$\text{Var}[X]$$X_{1}$$X_{2}$$\varepsilon$$\varepsilon$
Figure 5: Simple grouping according to mean and variance that does not work.

However consider the following example; there are two variables $X_{A}$ and
$X_{B}$ defined as follows.

$X_{A}=\begin{cases}3/4,&\text{w.p. }1/2\\\ 1/4,&\text{w.p.
}1/2\end{cases},\hskip 5.69046ptX_{B}=\begin{cases}1,&\text{w.p. }1/8\\\
1/2,&\text{w.p. }3/4\\\ 0,&\text{w.p. }1/8\end{cases}$

and observe that
$\mu=\mathbb{E}\left[X_{A}\right]=\mathbb{E}\left[X_{B}\right]=1/2$ and
$\text{Var}(X_{A})=\text{Var}(X_{B})=1/16$, therefore they would be treated as
the same.

In an instance with 2 variables only, if we calculate the DP solutions of
having a $X_{A}$ variable first and having a $X_{B}$ variable first we get
$\mathbb{E}\left[\text{OPT}(X_{A},\mu)\right]=\mathbb{E}\left[\text{OPT}(X_{A},1/2)\right]=5/8=0.625$
while
$\mathbb{E}\left[\text{OPT}(X_{B},\mu)\right]=\mathbb{E}\left[\text{OPT}(X_{B},1/2)\right]=9/16\approx
0.563$. These solutions differ by a constant even though the gap of the mean
and variance of the variables is $0$, therefore we cannot hope for any
qptas/ptas algorithm.

##  Appendix B Proofs from Section 2

See 2.1

###### Proof.

We prove this using induction on the number of variables. When there is a
single variable, then ALG and OPT both use $0$ as the threshold for $X_{1}$,
thus having the same reward. Suppose that there are $k+1$ variables, and
without loss of generality assume the first variable arrived is $X_{1}$.
Notice that ALG uses $\text{OPT}^{\prime}(X_{>1})$ from the remaining
variables $X_{>1}$ as the threshold for $X_{1}$. Then we can calculate the
reward of ALG as follows:

$\displaystyle\text{ALG}(X_{1},X_{>1})$ $\displaystyle=$
$\displaystyle\text{ALG}(X_{>1})\textbf{Pr}\left[X_{1}<\text{OPT}^{\prime}(X_{>1})\right]$
$\displaystyle+\mathbb{E}[X_{1}|\text{OPT}^{\prime}(X_{>1})\leq
X_{1}<\text{OPT}(X_{>1})]\cdot\textbf{Pr}\left[\text{OPT}^{\prime}(X_{>1})\leq
X_{1}<\text{OPT}(X_{>1})\right]$
$\displaystyle+\mathbb{E}[X_{1}|X_{1}\geq\text{OPT}(X_{>1})]\cdot\textbf{Pr}\left[X_{1}\geq\text{OPT}(X_{>1})\right]$
$\displaystyle\geq$
$\displaystyle(1-\varepsilon)\text{OPT}(X_{>1})\textbf{Pr}\left[X_{1}<\text{OPT}^{\prime}(X_{>1})\right]$
$\displaystyle+\text{OPT}^{\prime}(X_{>1})\cdot\textbf{Pr}\left[\text{OPT}^{\prime}(X_{>1})\leq
X_{1}<\text{OPT}(X_{>1})\right]$
$\displaystyle+\mathbb{E}[X_{1}|X_{1}\geq\text{OPT}(X_{>1})]\cdot\textbf{Pr}\left[X_{1}\geq\text{OPT}(X_{>1})\right]$
$\displaystyle\geq$
$\displaystyle(1-\varepsilon)\text{OPT}(X_{>1})\textbf{Pr}\left[X_{1}<\text{OPT}(X_{>1})\right]$
$\displaystyle+\mathbb{E}[X_{1}|X_{1}\geq\text{OPT}(X_{>1})]\cdot\textbf{Pr}\left[X_{1}\geq\text{OPT}(X_{>1})\right]$
$\displaystyle\geq$ $\displaystyle(1-\varepsilon)\text{OPT}(X_{1},X_{>1}).$

Here the first line is true by discussing the expected reward in different
cases of $X_{1}$; the second line is true since by induction on $k$ remaining
variables $X_{>1}$, $\text{ALG}(X_{>1})\geq(1-\varepsilon)\text{OPT}(X_{>1})$;
the third line is true since
$\text{OPT}^{\prime}(X_{>1})\geq(1-\varepsilon)\text{OPT}(X_{>1})$. The last
line is true since the optimal algorithm sets $\text{OPT}(X_{>1})$ as the
threshold for $X_{1}$. Thus by induction
$\text{ALG}(X)\geq(1-\varepsilon)\text{OPT}(X)$ holds for any number of
variables.

∎

See 1

###### Proof of Claim 1.

The way we defined the DP, the decision tree has one vertex for each
combination of the number of remaining variables within each group. Let
$S_{i}:=[0,|G_{i}|]$, i.e., $S_{i}$ contains all possible values for the
cardinality of the yet unobserved variables of a group during a run of the DP.
Note that for the set of vertices (or the size of the DP) $V$ we have
$|V|=\prod_{i=1}^{g}|S_{i}|$. Therefore, we want to split our $n$ variables
into those $g$ groups. If at step $j$ we observe a variable
$X_{j}\in\mathcal{G}_{i}$, then the next state has
$|\mathcal{G}_{i}^{j+1}|:=|\mathcal{G}_{i}^{j}-1|$, where
$\mathcal{G}_{i}^{j}$ denotes the set of yet unobserved random variables
belonging to the group before time $j$. When no variables remain in a group
$\mathcal{G}_{i}$, it is simply the empty set.

Now we show that $|V|$ is maximized when the variables are split equally among
the groups, meaning that $|S_{i}|=\left\lceil\frac{n}{g}\right\rceil$ for all
$i$. Assume that $|V|$ is maximized for some other split of the variables
which will result in some other values $|\mathcal{G}^{\prime}_{i}|,i\in[n]$.
Start again from the configuration where all groups have the same cardinality.
Pick any pair $\mathcal{G}_{j},\mathcal{G}_{k}$ and move $\ell$ variables from
one group to the other, so that now
$|\mathcal{G}^{\prime}_{j}|=\left\lceil\frac{n}{g}\right\rceil-\ell$ and
$|\mathcal{G}^{\prime}_{k}|=\left\lceil\frac{n}{g}\right\rceil+\ell$, for some
$\ell\in\mathbb{N}$. Then
$|V|=\left\lceil\frac{n}{g}\right\rceil^{g-2}\left(\left\lceil\frac{n}{g}\right\rceil-\ell\right)\left(\left\lceil\frac{n}{g}\right\rceil+\ell\right)<\left\lceil\frac{n}{g}\right\rceil^{g}$,
which is a contradiction. ∎

See 2.2

###### Proof of Lemma 2.2.

We use induction on the number of variables that remain in the game, and show
the lemma for the multiplicative case. The additive case follows exactly the
same steps.

For the base case, let $X$ be the variable that is currently instantiated, and
$Y$ the single variable that remains. Recall that OPT stops when
$X\geq\mathbb{E}\left[Y\right]=\sum_{i}v_{i}\textbf{Pr}\left[Y=v_{i}\right]$,
and similarly $\text{OPT}^{\prime}$ stops when
$X\geq\mathbb{E}\left[Y^{\prime}\right]=\sum_{i}v^{\prime}_{i}\textbf{Pr}\left[Y=v^{\prime}_{i}\right]$.
Since $v^{\prime}_{i}\leq v_{i}\leq\gamma\cdot v^{\prime}_{i}$ for every
$v_{i}\in\text{supp}(Y)$ it holds that

$\frac{\mathbb{E}\left[Y\right]}{\gamma}\leq\mathbb{E}\left[Y^{\prime}\right]\leq\mathbb{E}\left[Y\right].$
(5)

We distinguish in the following cases.

  * •

Cases 1 & 2 : $\text{OPT}_{1}$ and $\text{OPT}_{1}^{\prime}$ either both stop
and take $X$ or both continue and take $Y$, in which case their values are the
same.

  * •

Case 3: $\text{OPT}_{1}^{\prime}$ stops and takes $X$, while $\text{OPT}_{1}$
continues and gets $\mathbb{E}\left[Y\right]$. Using equation (5) we have that
$\text{OPT}_{1}^{\prime}=X\geq\mathbb{E}\left[Y^{\prime}\right]\geq\frac{\mathbb{E}\left[Y\right]}{\gamma}=\text{OPT}_{1}/\gamma$.

  * •

Case 4: $\text{OPT}^{\prime}$ continues and receives
$\mathbb{E}\left[Y\right]$ while $\text{OPT}_{1}$ stops and receives $X$. Then
$\text{OPT}^{\prime}_{1}=\mathbb{E}\left[Y\right]\geq\mathbb{E}\left[Y^{\prime}\right]\geq
X=\text{OPT}_{1}$, where we used that since $\text{OPT}^{\prime}_{1}$
continued it holds that $\mathbb{E}\left[Y^{\prime}\right]\geq X$.

For the induction, we assume the claim holds for at most $n$ variables, and
show it for $n+1$. Let $X_{1}$ be the variable that is currently instantiated.
We distinguish in the following cases.

  * •

Cases 1 & 2: $\text{OPT}_{1:n+1}$ and $\text{OPT}_{1:n+1}^{\prime}$ either
both stop and take $X_{1}$ or both continue and take $\text{OPT}_{2:n+1}$, in
which case their values are the same.

  * •

Case 3: $\text{OPT}_{1:n+1}^{\prime}$ stops and takes $X_{1}$, while
$\text{OPT}_{1:n+1}$ continues and gains $\text{OPT}_{2:n+1}$ on expectation,
then we get that

$\displaystyle\text{OPT}_{1:n+1}^{\prime}$ $\displaystyle=X_{1}$
$\displaystyle\text{since }\text{OPT}^{\prime}\text{ stopped}$
$\displaystyle\geq\text{OPT}^{\prime}_{2:n+1}$
$\displaystyle\text{OPT}^{\prime}\text{ is a threshold policy}$
$\displaystyle=\frac{1}{n}\sum_{i\in[n]}\text{OPT}^{\prime}(X_{i}|X_{-i})$
$\displaystyle\text{Def. of }\text{OPT}^{\prime}\eqref{eq:DP}$
$\displaystyle\geq\frac{1}{\gamma}\cdot\frac{1}{n}\sum_{i\in[n]}\text{OPT}(X_{i}|X_{-i})$
Induction hypothesis
$\displaystyle=\frac{\text{OPT}_{2:n+1}}{\gamma}=\frac{\text{OPT}_{1:n+1}}{\gamma}$
Def (1) and OPT stops

  * •

Case 4: $\text{OPT}^{\prime}_{1:n+1}$ continues while $\text{OPT}_{1:n+1}$
stops and receives $X_{1}$. Since $\text{OPT}^{\prime}_{1:n+1}$ continues we
have that
$\text{OPT}^{\prime}_{1:n+1}=\frac{1}{n}\sum_{i\in[n]}\text{OPT}^{\prime}(X_{i}|X_{-i})\geq
X_{1}=\text{OPT}_{1:n+1}$.

∎

See 2.3

###### Proof of Lemma 2.3.

Observe that in the proof of Lemma 2.2 holds using exactly the same steps for
the main induction. The only step that uses the fact that we have different
values is the base case, which holds the same when the guarantee holds for
$p_{i}^{\prime}$ instead of $v_{i}^{\prime}$. ∎

##  Appendix C Proofs from Section 3

###  C.1 Proofs from Section 3.1

See 3

###### Proof of Claim 3.

We will try to bound the expected contribution of these variables in the DP.
The worst case will be if every $X_{i}$ has
$\mathbb{E}\left[X_{i}\right]\leq\frac{\varepsilon}{n}$ and we have to
transform all of them. We assume wlog that we arrange the variables by
decreasing $v_{i}$, i.e. $v_{i}\geq v_{2}\geq\ldots\geq v_{n}$. Then the
contribution of an instance with $n$ such variables to the optimal, denoted by
$\text{OPT}^{\text{small}}$, is

$\displaystyle\text{OPT}^{\text{small}}\leq\mathbb{E}\left[\max_{i\in[n]}X_{i}\right]=\sum_{i=1}^{n}\left(v_{i}p_{i}\prod_{j<i}(1-p_{j})\right)\leq\frac{\varepsilon}{n}\cdot
n<1.5\varepsilon\cdot\text{OPT},$

where the second inequality holds because the expression is maximized when
$p_{i}$ tends to 1 for every $i$ (and we have also assumed that $v_{i}\cdot
p_{i}\leq\frac{\varepsilon}{n}$) and the last one because we have normalized
OPT (see Claim 2).

∎

See 4

###### Proof of Claim 4.

We show the two inequalities separately.

#### For $\text{OPT}(X)\leq\text{OPT}(Y)$:

Assume that only one variable in the instance falls in Case 2, thus it is the
only one that we change.

  * •

_Base case_ : we have 2 variables $X_{1},X_{2}$ in the original instance, and
$X_{1},Y_{2}$ in the changed instance. Since the order is random, there are
two cases by coupling the arrival orders of the two instances. If $X_{1}$
arrives first, both $\text{OPT}(X)$ and $\text{OPT}(Y)$ see the same
realization and the same threshold, and therefore have the same gain. If
$Y_{2}$ (resp. $X_{2}$) arrives first then

$\displaystyle\text{OPT}(Y)$
$\displaystyle=\mathbb{E}\left[\max(Y_{2},\mathbb{E}\left[X_{1}\right])\right]$
$\displaystyle=v^{\prime}_{2}p^{\prime}_{2}+(1-p^{\prime}_{2})\mathbb{E}\left[X_{1}\right]$
$\displaystyle\geq v_{2}p_{2}+(1-p_{2})\mathbb{E}\left[X_{1}\right]$
$\displaystyle=\mathbb{E}\left[\max(X_{2},\mathbb{E}\left[X_{1}\right])\right]$
$\displaystyle=\text{OPT}(X),$

where the inequality holds because from the transformation we always have
$p^{\prime}_{2}\leq p_{2}$.

  * •

_Induction_ : assume that the inequality holds for at most $n-1$ variables,
and that the only changed variable is $Y_{j}$. Then, for $n$ variables we
distinguish in the following cases:

    * –

Case 1: variable $Y_{j}$ (resp. $X_{j}$) arrives first. Then we have

$\displaystyle\text{OPT}(Y)$
$\displaystyle=v^{\prime}_{j}p^{\prime}_{j}+(1-p^{\prime}_{j})\text{OPT}(Y_{2:n})$
$\displaystyle\geq v_{j}p_{j}+(1-p_{j})\text{OPT}(X_{2:n})$
$\displaystyle=\text{OPT}(X),$

where the inequality holds since $p^{\prime}_{j}\leq p_{j}$ and from the
induction hypothesis.

    * –

Case 2: any of the non-changed variables $Y_{k}$ (resp. $X_{k}$) for some
$k\neq j$ arrives first. Then, from the induction hypothesis we get

$\displaystyle\text{OPT}(Y)$
$\displaystyle=\mathbb{E}\left[\max(Y_{k},\text{OPT}(Y_{2:n})\right]$
$\displaystyle\geq\mathbb{E}\left[\max(X_{k},\text{OPT}(X_{2:n}))\right]$
$\displaystyle=\text{OPT}(X).$

If there are $\ell\in[n]$ variables in Case 2, we can apply the
transformations sequentially: At each time, pick at random a variable in Case
2 and transform it. Repeat until all $\ell$ random variables are transformed.
By applying multiple times the arguments above, we know that we end up with
the instance $Y$, for which it holds that $\text{OPT}(X)\leq\text{OPT}(Y)$.

#### For $\text{OPT}(X)\geq\left(1-\varepsilon^{2}\right)\text{OPT}(Y)$:

To start, assume that we have again only one changed variable. We define an
algorithm $\text{ALG}^{\prime}$ as follows: $\text{ALG}^{\prime}$ is given an
instance $Z$ and, by coupling the realizations with instance $Y$, it simply
always stops at the same index that OPT stops at $Y$. 333Note that this is no
longer a threshold algorithm, since the decision to stop in the instance $Z$
is based on the realizations of another instance $Y$ i.e. we might have
($Z<$threshold) but still stop. Observe that
$\text{ALG}^{\prime}(Y)=\text{OPT}(Y)$ (since they make the exact same
decisions) and that $\text{OPT}(X)\geq\text{ALG}^{\prime}(X)$.

We now define a new algorithm $\text{ALG}^{\prime\prime}$ for instance $X$:
$\text{ALG}^{\prime\prime}$ stops on $X$ at the same index (and, thus, at the
same variable when it is not the changed one) as $\text{ALG}^{\prime}$ on
instance $Y$, except in the case that $\text{ALG}^{\prime}$ stops at the
transformed variable $Y_{i}$. In this case, $\text{ALG}^{\prime\prime}$ stops
at the corresponding original variable $X_{i}$ whenever it is realized, that
is, with an additional probability of $p_{i}-p^{\prime}_{i}$ compared to
$\text{ALG}^{\prime}(Y)$. Coupling the realizations of the two instances,
observe that $\text{ALG}^{\prime}(Y)$ and $\text{ALG}^{\prime\prime}(X)$
obtain the same reward when they stop with a random variable before the
transformed one. When they encounter the transformed variable $Y_{i}$ (resp.
the original variable $X_{i}$), $\text{ALG}^{\prime}(Y)$ and
$\text{ALG}^{\prime\prime}(X)$ stop with different probabilities. But since
the transformation is expectation-preserving, $\text{ALG}^{\prime}$ and
$\text{ALG}^{\prime\prime}$ get the same expected reward from the transformed
and the original variable, respectively. But now with an additional
probability of $p_{i}-p^{\prime}_{i}$ we have that
$\text{ALG}^{\prime\prime}(X)$ stops but $\text{ALG}^{\prime}(Y)$ continues.
Therefore, when this occurs, $\text{ALG}^{\prime}(Y)$ receives an additional
reward. Let us write $Y_{\text{rest}}$ for the remaining instance in this
case. Then we have that

$\displaystyle\text{OPT}(X)$
$\displaystyle\geq\mathbb{E}\left[\text{ALG}^{\prime\prime}(X)\right]$
$\displaystyle=\mathbb{E}\left[\text{ALG}^{\prime}(Y)\right]-\left(p_{i}-p^{\prime}_{i}\right)\mathbb{E}\left[\text{ALG}^{\prime}(Y_{\text{rest}})\right]$
$\displaystyle\geq\mathbb{E}\left[\text{ALG}^{\prime}(Y)\right]-p_{i}\mathbb{E}\left[\text{ALG}^{\prime}(Y)\right]$
$\displaystyle=\left(1-p_{i}\right)\text{OPT}(Y),$

where the second inequality holds since
$\text{ALG}^{\prime}(Y)\geq\text{ALG}^{\prime}(Y_{\text{rest}})$. If we again
have more variables to transform, we apply the changes sequentially and we get
the

$\text{OPT}(X)\geq\prod_{i}(1-p_{i})\text{OPT}(Y)$

where the product is taken over all variables with support value
$>\frac{1}{\varepsilon^{2}}$. Observe that the probability that at least one
of the variables get realized is $1-\prod_{i}(1-p_{i})\leq\varepsilon^{2}$,
otherwise the gambler can obtain at least 1 reward in expectation from these
variables with support value $>\frac{1}{\varepsilon^{2}}$. Thus
$\text{OPT}(X)\geq(1-\varepsilon^{2})\text{OPT}(Y)$. ∎

See 3.1

###### Continued proof of Theorem 3.1.

We conclude the proof of Theorem 3.1 by showing how to bound the error for the
constant size support case.

#### Bounding the error:

We demonstrate here how the proofs of the arguments for the 2-point
distributions can be adapted in order to give a similar error for the constant
size support for each case. For the preprocessing note that the difference now
is that for every variable $X_{i}$, for every point
$v_{i}\in\text{supp}\left(\mathcal{D}_{i}\right)$ that satisfies either
$v_{i}\cdot p_{i}<\frac{\varepsilon}{cn}$ or $v_{i}<\varepsilon$, we move all
their mass to value $0$. In the case of variables with points of value
$v_{i}<\varepsilon$, we will still lose in the worst case
$1.5\varepsilon\text{OPT}$ in our single-choice objective by removing them
all. For the variables with points that satisfy
$v_{i}p_{i}<\frac{\varepsilon}{cn}$ the following change occurs in the proof
of Claim 3: instead of now summing over $n$ points (one per random variable),
we will now have to consider at most $n\cdot c$ such points in the summation.
But since we scaled down the bound of $v_{i}p_{i}$ by a factor of $c$ we still
have a multiplicative loss of $(1-1.5c\varepsilon)$. For the Case 1 variables,
Lemmas 2.2 and 2.3 hold for general distributions; as a result, the
multiplicative error here remains $(1+\varepsilon)^{2}$. For the points in
Case 2, as Claim 4 still holds, we do not need to make any changes to the
case. ∎

###  C.2 Proofs from Section 3.2

See 3.4

###### Proof of Lemma 3.4.

We show that if one variable changes, then the optimal thresholds remain the
same, and the lemma follows by applying this process as many times as the
number of variables.

Assume only one variable changes, we show the lemma using induction in the
total number of variables of the instance. For the base case, there is only
one variable remaining, $X$ in the original instance and $X^{\prime}$ in the
transformed one. Thresholds therefore are
$\theta_{1}=\mathbb{E}_{\mathcal{D}}\left[X\right]=\mathbb{E}_{\mathcal{D}^{\prime}}\left[X^{\prime}\right]=\theta^{\prime}_{1}$.

We now assume the lemma holds for at most $n-1$ variables, and there are $n$
variables $X_{1},\ldots,X_{n}$, where the transformed instance has a variable
$X_{1}^{\prime}$ transformed according to the bundling 3 and denote by
$\mathcal{D}^{\prime}$ the product distribution of all initial variables and
$X^{\prime}_{1}$. Then we have the following

$\displaystyle\theta^{\prime}_{1:n}$
$\displaystyle=\mathbb{E}_{\mathcal{D}^{\prime}}\left[\frac{1}{n}\left(\text{OPT}(X^{\prime}_{1}|X_{-1})+\sum_{i=2}^{n}\text{OPT}(X_{i}|X_{-i})\right)\right]$
$\displaystyle\text{Definition of }\theta’$
$\displaystyle=\frac{1}{n}\left(\mathbb{E}_{\mathcal{D}^{\prime}}\left[\max(X^{\prime}_{1},\theta_{-1})\right]+\mathbb{E}_{\mathcal{D}}\left[\sum_{i=2}^{n}\text{OPT}(X_{i}|\theta^{\prime}_{-i})\right]\right)$
$\displaystyle=\frac{1}{n}\left(\vphantom{\sum_{i}^{n}}\mathbb{E}_{\mathcal{D}^{\prime}}\left[\max(X^{\prime}_{1},\theta_{-1})|X^{\prime}_{1}<1\right]\textbf{Pr}\left[X^{\prime}_{1}<1\right]\right.$
$\displaystyle\left.\hskip
56.9055pt+\mathbb{E}_{\mathcal{D}^{\prime}}\left[X^{\prime}_{1}|X^{\prime}_{1}>1\right]\textbf{Pr}\left[X^{\prime}_{1}>1\right]+\mathbb{E}_{\mathcal{D}}\left[\sum_{i=2}^{n}\text{OPT}(X_{i}|\theta_{-i})\right]\right)$
Ind. hyp. & Fact 3.3
$\displaystyle=\frac{1}{n}\left(\vphantom{\sum_{i}^{n}}\mathbb{E}_{\mathcal{D}}\left[\max(X_{1},\theta_{-1})|X_{1}<1\right]\textbf{Pr}\left[X_{1}<1\right]\right.$
$\displaystyle\left.\hskip
56.9055pt+\mathbb{E}_{\mathcal{D}}\left[X_{1}|X_{1}>1\right]\textbf{Pr}\left[X_{1}>1\right]+\mathbb{E}_{\mathcal{D}}\left[\sum_{i=2}^{n}\text{OPT}(X_{i}|\theta_{-i})\right]\right)$
Definition of bundling $\displaystyle=\theta_{1:n}$

∎

##  Appendix D Proofs from Section 4

###  D.1 Proofs from Section 4.1

See 4.2

###### Proof.

Notice that the probability that at least one of the variables in
$\mathbf{X}^{*}_{v}$ gets realized with value $v$ is at most
$1-e^{-\overline{Q}^{*}_{v}}<\overline{Q}^{*}_{v}$. Thus in the optimal
solution, the total contribution from the variables in $\mathbf{X}^{*}_{v}$
with value $v$ is:

  * •

At most $\varepsilon^{10}v\leq\varepsilon^{8}$ for $v\leq\varepsilon^{-2}$.

  * •

At most $\overline{Q}^{*}_{v}\cdot v<\varepsilon^{10}\cdot Q_{max}\cdot v$ for
$v\geq\varepsilon^{-2}$. Note that since $\text{OPT}\leq 1$, it has to be that
$Q_{max}\cdot v_{max}\leq 1$. Therefore the total loss in this case is at most
$\varepsilon^{10}$.

Therefore, removing those variables lead to at most $\varepsilon^{8}$ loss in
total reward. ∎

See 4.5

###### Proof of Observation 4.5.

If $Q^{*}_{v}=\overline{Q}^{*}_{v}$, then nothing is changed. Otherwise, note
that the probability that $v$ is realized in the remaining variables is at
least

$1-\prod_{X_{j}\textrm{ in the remaining of
}\mathbf{X}_{v}^{*}}(1-p_{i})=1-\exp\left(-\sum_{X_{j}\textrm{ in the
remaining of }\mathbf{X}_{v}^{*}}q_{j}\right)\geq
1-e^{-1/\varepsilon}>1-\varepsilon.$

Therefore even after ignoring $X_{i}$, the probability that $v$ is realized is
at least $1-\varepsilon$. Thus, for any strategy that wants to accept
$X_{i}=v$, the gambler can instead ignore it and accept the first realized $v$
later. The gambler fails to accept the same reward $v$ with probability at
most $\varepsilon$.

∎

See 5

###### Proof of Claim 5.

By Chebyshev’s inequality we have,

$\textbf{Pr}\left[|Y-\mathbb{E}\left[Y\right]|\geq\varepsilon\delta
A\right]\leq\frac{\text{Var}[Y]}{(\varepsilon\delta A)^{2}}.$

Before bounding $\text{Var}[Y]$, we first bound a few useful terms.

$\mathbb{E}\left[Y\right]=\varepsilon\mathbb{E}\left[X\right]=\delta A$
$\displaystyle\mathbb{E}\left[\sum_{i<j}2Y_{i}Y_{j}\right]$ $\displaystyle=$
$\displaystyle
m(m-1)\mathbb{E}\left[Y_{1}Y_{2}\right]=\frac{m(m-1)}{n(n-1)}\sum_{i<j}2A_{i}A_{j}$
$\displaystyle=$
$\displaystyle\frac{m(m-1)}{n(n-1)}\left(\left(\sum_{i}A_{i}\right)^{2}-\sum_{i}A_{i}^{2}\right)<\delta^{2}\left(A^{2}-\sum_{i}A_{i}^{2}\right)$

Now we bound $\text{Var}[Y]$. By the definition of variance,

$\displaystyle\text{Var}[Y]$ $\displaystyle=$
$\displaystyle\mathbb{E}\left[Y^{2}\right]-(\mathbb{E}\left[Y\right])^{2}$
$\displaystyle=$
$\displaystyle\mathbb{E}\left(\sum_{i}Y_{i}\right)^{2}-\delta^{2}A^{2}$
$\displaystyle=$
$\displaystyle\sum_{i}\mathbb{E}\left[Y_{i}^{2}\right]+2\sum_{1\leq i<j\leq
m}\mathbb{E}\left[Y_{i}Y_{j}\right]-\delta^{2}A^{2}$ $\displaystyle<$
$\displaystyle\delta\sum_{i\leq
n}A_{i}^{2}+\delta^{2}\left(A^{2}-\sum_{i}A_{i}^{2}\right)-\delta^{2}A^{2}$
$\displaystyle=$ $\displaystyle(\delta-\delta^{2})\sum_{i\leq n}A_{i}^{2}$
$\displaystyle<$ $\displaystyle\delta\sum_{i\leq
n}A_{i}^{2}\leq\delta\max_{i}A_{i}\sum_{i\leq
n}A_{i}\leq\delta^{2}\varepsilon^{10}A^{2}.$

The lemma follows immediately from Chebyshev’s inequality. ∎

###  D.2 A PTAS for general distributions

When the support size of each random variable can be more than 1, suppose that
each variable $X_{i}$ is drawn from a distribution, that for each possible
support value $v$ (being a power of $(1+\varepsilon)$ between $\varepsilon$
and $1/\varepsilon^{2}$ or $v_{\max}$), $X_{i}=v$ with probability
$p^{v}_{i}$. Define $q^{v}_{i}=-\ln(1-p^{v}_{i})$. We observe that when
$p^{v}_{i}<\varepsilon$, if $\varepsilon$ is small enough,
$p^{v}_{i}<q^{v}_{i}<p^{v}_{i}+(p^{v}_{i})^{2}$. Thus $q^{v}_{i}$ is a
$(1+\varepsilon)$-approximation of $p^{v}_{i}$ when $p^{v}_{i}$ is small
enough.

#### First Preprocessing.

For each support value $v\leq 1/\varepsilon^{2}$, similar to the case with
binary distribution define $\mathbf{X}^{*}_{v}$ to be the set of variables
with small probabilities on support $v$:

$\mathbf{X}^{*}_{v}=\\{X_{i}|X_{i}\in\mathbf{X}_{v},\ s.t.\
q^{v}_{i}<\varepsilon^{20}\\}.$

Let $\overline{Q}^{*}_{v}=\sum_{X_{i}\in\mathbf{X}^{*}_{v}}q^{v}_{i}$ denote
the sum of $q^{v}_{i}$ for all random variables with support values $v$ being
realized with small probabilities. If $\overline{Q}^{*}_{v}<\varepsilon^{10}$,
it is safe to ignore the support $v$ of all variables in $\mathbf{X}^{*}_{v}$,
as they contribute less than $\varepsilon^{4}\text{OPT}$ in the optimal
selection. To be more precise, for a variable $X_{i}\in\mathbf{X}^{*}_{v}$, it
is safe to replace $X_{i}$ with $X_{i}^{\prime}$ which is defined by moving
all probability mass on $v$ to $0$:
$\textbf{Pr}\left[X^{\prime}_{i}=v\right]=0$, and
$\textbf{Pr}\left[X^{\prime}_{i}=v^{\prime}\right]=\textbf{Pr}\left[X_{i}=v\right]$
for every $v^{\prime}\neq v$. Thus later in the section, we assume that
$\overline{Q}^{*}_{v}>\varepsilon^{10}$.

Let $Q^{*}_{v}=\min(\varepsilon^{-1},\overline{Q}^{*}_{v})$. The same as in
the binary distribution case, whenever the gambler encounters a variable
$X_{i}\in\mathbf{X}^{*}_{v}$, while the remaining variables in
$\mathbf{X}^{*}_{v}$ have a total $q^{v}_{i}$ more than $Q^{*}_{v}$, it is
safe to ignore this variable $X_{i}$ if the realized value is $v$. We again
define $Q^{o}_{v}=\varepsilon^{4}Q^{*}_{v}$, and
$\delta_{v}=\frac{Q^{o}_{v}}{\overline{Q}^{*}_{v}}$.

For each variable $X_{i}$, define its “special truncation” $X^{+}_{i}$ as
follows: for each support value $v>0$,
$\textbf{Pr}\left[X^{+}_{i}=v\right]=0$, if $q^{v}_{i}<\varepsilon^{20}$;
$\textbf{Pr}\left[X^{+}_{i}=v\right]=p^{v}_{i}$, if
$q^{v}_{i}>\varepsilon^{20}$. All the removed probability masses are moved to
$q^{0}_{i}=\textbf{Pr}\left[X^{+}_{i}=0\right]$. In other words, the small
probability part of the variable is truncated. As there are only
$\tilde{O}(1/\varepsilon)$ different possible discretized probabilities for
each support value, and $\tilde{O}(1/\varepsilon)$ distinct discretized
support values, thus there are only $\text{poly}(1/\varepsilon)$ distinct
truncated variables. For support value $v=v_{\max}$, similar to the binary
distribution case we define the changes to the definitions above.
$\mathbf{X}^{*}_{v}$ is defined by $\\{X_{i}|X_{i}\in\mathbf{X}_{v},\ s.t.\
q^{v}_{i}<\varepsilon^{20}Q_{\max}\\}$. Support $v$ of all variables in
$\mathbf{X}^{*}_{v}$ can be ignored if
$\overline{Q}^{*}_{v}<\varepsilon^{10}Q_{\max}$. The “special truncation”
$X_{i}^{+}$ removes the probability mass on $v$ for each variable $X_{i}$ with
$q^{v}_{i}<\varepsilon^{20}Q_{\max}$.

#### Second Preprocessing.

Now we are ready to propose variants of online selection games, which all have
a similar optimal reward to the original prophet secretary game. Again, let
$Y_{1},Y_{2},\ldots,Y_{n}$ be the random realization of all variables, with
$Y_{i}$ being the $i$th random variable that arrives. For each support value
$v>0$, partition all random variables to $\varepsilon^{-4}+1$ blocks
$\mathbf{B}^{v}_{0},\mathbf{B}^{v}_{1},\ldots,\mathbf{B}^{v}_{\varepsilon^{-4}}$
such that each block contains a sequence of consecutive variables. In
particular, $\mathbf{B}^{v}_{0}$ contains the first
$n\left(1-\frac{Q^{*}_{v}}{\overline{Q}^{*}_{v}}\right)=n-\delta_{v}n/\varepsilon^{4}$
arrived variables; each of
$\mathbf{B}^{v}_{1},\ldots,\mathbf{B}^{v}_{\varepsilon^{-4}}$ contains
$\delta_{v}n$ consecutive variables. We now redefine different versions of
prophet secretary games in the binary distribution case to the general
setting.

$G_{1}$$G_{2}$$G_{3}$$G_{3}^{*}$$G_{4}$$G_{5}$$(1-\varepsilon)\leq$$(1-\varepsilon)\leq$$(1-\varepsilon)\leq$$\leq$$(1-\varepsilon)\leq$$\geq$$\geq$$\geq$$\geq
1/(1+\varepsilon)$$\geq$Lem D.1Lem D.2Lem D.3Lem D.4Lem D.5 Figure 6: Series
of reductions we use to prove Theorem D.7. The games in grey are mostly the
same as the binary case, while game $G^{*}_{3}$ is a new addition to handle
the general case.

#### Original prophet secretary game $G_{1}$.

There are $n$ random variables $X_{1},X_{2},\ldots,X_{n}$ arriving in random
order. At each time, when a variable arrives, the gambler observes the
realized value and decides whether to take it. If the play decides not to take
the realized value, the value cannot be taken later.

Prophet secretary game $G_{2}$ with possible failure. The gambler plays
prophet secretary game $G_{1}$, but the reward is set to 0 if there exists a
possible support value $v$ and a block $\mathbf{B}^{v}_{k}$ such that for the
variables
$X_{i_{1}},X_{i_{2}},\ldots,X_{i_{\ell}}\in\mathbf{B}^{v}_{k}\cap\mathbf{X}^{*}_{v}$,
$\sum_{X_{i_{j}}\in\mathbf{B}^{v}_{k}}q^{v}_{i_{j}}\not\in[(1-\varepsilon)Q^{o}_{v},(1+\varepsilon)Q^{o}_{v}]$.
In other words, if the realization probability of $v$ of all variables with a
small probability in a block is far from expectation, no reward is given to
the gambler. The same as in the binary distribution case, we have the
following lemma.

######  Lemma D.1.

$(1-\varepsilon)\text{OPT}(G_{1})\leq\text{OPT}(G_{2})\leq\text{OPT}(G_{1})$.

Prophet secretary game $G_{3}$ with lazy decision. The gambler plays prophet
secretary game $G_{2}$. However, for every variable $Y_{i}$ in
$\mathbf{X}^{*}_{v}\cap\mathbf{B}^{v}_{0}$, whenever its realized value is
$v$, the variable is removed and cannot be accepted by the gambler. Or
equivalently, $Y_{i}$ is replaced by variable $Y_{i}^{\prime}$ such that for
every positive support value $v^{\prime}\neq v$,
$\textbf{Pr}\left[Y_{i}^{\prime}=v^{\prime}\right]=\textbf{Pr}\left[Y_{i}=v^{\prime}\right]$;
for support value $v$, $\textbf{Pr}\left[Y^{\prime}_{i}=v\right]=0$. The same
as in the binary case, we have the following lemma.

######  Lemma D.2.

$(1-\varepsilon)\text{OPT}(G_{2})\leq\text{OPT}(G_{3})\leq\text{OPT}(G_{2})$.

Now we introduce a slightly different version of Game $G_{3}$ to reduce the
correlation between the realization of each possible support value. In
particular, for each $X_{i}$ with more than 1 positive support values, if
support values $v_{1},v_{2},\ldots,v_{k}$ are not in the “special truncation”
$X^{+}_{i}$ of $X_{i}$, then $X_{i}$ is replaced with a sequence of random
variables
$\mathbf{X}_{i}=(X_{i,v_{1}},X_{i,v_{2}},\ldots,X_{i,v_{k}},X^{+}_{i})$ that
always come together one by one, where $X_{i,v_{j}}$ is a variable drawn from
binary distribution:

$X_{i,v_{j}}=\begin{cases}v_{j},&\text{w.p. }p_{i}^{v_{j}}\\\ 0,&\text{w.p.
}1-p_{i}^{v_{j}}\end{cases}$

A nice property of the new game is that for each variable, the small-
probability parts of the variable is separated from the large-probability part
of the variable. The intuition behind this separation is that in later
versions of the game, we can group all variables with binary distribution the
same as in the previous section, and the remaining special variables can be
treated separately via dynamic programs.

Perturbed prophet secretary game $G_{3}^{*}$ with lazy decision. The gambler
plays prophet secretary game $G_{3}$. However, when each variable $X_{i}$
arrives, it is replaced by a bundle of variables $\mathbf{X}_{i}$ that arrives
consecutively.

######  Lemma D.3.

$(1-\varepsilon)\text{OPT}(G_{3})\leq\text{OPT}(G_{3}^{*})\leq\text{OPT}(G_{3})$.

###### Proof of Lemma D.3.

Notice that $\max\\{x\in\mathbf{X}_{i}\\}$ is stochastically dominated by
$X_{i}$: for any support value $v>0$,
$\textbf{Pr}\left[\max\\{X\in\mathbf{X}_{i}\\}=v\right]\leq\textbf{Pr}\left[\exists
X\in\mathbf{X}_{i}\textrm{ s.t. }X=v\right]=\textbf{Pr}\left[X_{i}=v\right]$.
This means that after replacing each $X_{i}$ with a bundle of variables
$\mathbf{X}_{i}$, even if the gambler is allowed to take the maximum of all
variables in $\mathbf{X}_{i}$ when $\mathbf{X}_{i}$ arrives, the optimal
reward of the new game is upper bounded by the original game, thus
$\text{OPT}(G_{3}^{*})\leq\text{OPT}(G_{3})$.

Now consider any optimal online algorithm for $G_{3}$. We assume that the
algorithm is threshold-based, where the threshold at any step is determined by
the optimal reward of the remaining game. At any node of the decision tree for
$G_{3}$, there is a corresponding node in the decision tree for $G_{3}^{*}$
with the same history (i.e. whenever a variable $X_{j}$ arrives in $G_{3}$ at
the $k$th step, a bundle of variables $\mathbf{X}_{j}$ arrives in $G_{3}^{*}$
at the $k$th step). Suppose that at a node of the decision tree for $G_{3}$,
$X_{i}$ arrives, while the optimal algorithm sets the threshold to be $t$. If
in the corresponding node in $G^{*}_{3}$ the gambler also sets the threshold
to be $t$ at the corresponding node when
$\mathbf{X}_{i}=(X_{i,v_{1}},X_{i,v_{2}},\ldots,X_{i,v_{k}},X^{+}_{i})$
arrives, we show that such an algorithm in $G^{*}_{3}$ obtains at least
$(1-\varepsilon)$ fraction of the reward obtained in $\text{OPT}(G_{3})$.

Firstly, the probability that the decision tree of $G^{*}_{3}$ reaches this
node is larger than the probability that the decision tree of $G_{3}$ reaches
the corresponding node, as in each of the previous steps in the decision
trees, the probability of stopping in $G^{*}_{3}$ is always upper bounded by
the probability of stopping in $G_{3}$, since both algorithms use the same
threshold at each step, and $\max\\{x\in\mathbf{X}_{j}\\}$ is stochastically
dominated by $X_{j}$ in each node of the tree.

Secondly, conditioned on both decision trees reach the corresponding nodes,
for every possible threshold $t$ and support value $v\geq t$, the probability
that $G_{3}$ accepts $X_{i}$ with $X_{i}=v$ is $p_{i}^{v}$. We now analyze
what’s the probability that $G^{*}_{3}$ accepts $\mathbf{X}_{i}$ with value
$v$. If $v$ is a support value of $X^{+}_{i}$, then $v$ is accepted with
probability $p_{i}^{v}$ at $X^{+}_{i}$ if non of $X_{i,v_{j}}$ arrives, which
happens with probability
$1-\prod_{j}{(1-p_{i}^{v_{j}})}=1-e^{\sum_{i_{j}}q_{i}^{v_{j}}}>1-\varepsilon$
when
$\sum_{i_{j}}q_{i}^{v_{j}}<\tilde{O}(1/\varepsilon)\varepsilon^{20}<\varepsilon^{18}.$
If $v=v_{j}$ is a support value with small probability in $X_{i}$, then $v$ is
accepted with probability $p_{i}^{v}$ at $X^{+}_{i}$ if non of
$X_{i,v_{\ell}}$ (with $\ell\neq j$) arrives, which happens with probability
at least $1-\prod_{j}{(1-p_{i}^{v_{j}})}>1-\varepsilon$. Therefore, for every
support value $v$, the probability that at a node of the decision tree of
$G^{*}_{3}$ accepts a variable with value $v$, is at least $(1-\varepsilon)$
times the probability that in the corresponding node of the decision tree of
$G_{3}$ of the optimal algorithm accepts a variable with value $v$. Thus by
coupling the randomness of the two decision trees, we have an algorithm with a
reward at least $(1-\varepsilon)\text{OPT}(G_{3})$ in Game $G^{*}_{3}$, which
means that $\text{OPT}(G_{3}^{*})\geq(1-\varepsilon)\text{OPT}(G_{3})$. This
concludes the proof of the lemma. ∎

Prophet secretary game $G_{4}$ with lazy decision and outside option. The
gambler plays prophet secretary game $G^{*}_{3}$. However, in each block
$\mathbf{B}^{v}_{k}$ with $k\geq 1$, the realization of $v$ for variables with
small probability in $\mathbf{X}^{*}_{v}\cap\mathbf{B}^{v}_{k}$ is different.
In particular, for all variables in
$\mathbf{X}^{*}_{v}\cap\mathbf{B}^{v}_{k}$, the realization of $v$ is put
together to the beginning of $\mathbf{B}^{v}_{k}$ (and not later), and kept as
an outside option $Z_{v}$. Whenever the gambler decides to accept a variable
$X_{i}^{+}$ in $\mathbf{B}^{v}_{k}$, the gambler can choose to replace
$X_{i}^{+}$ by $Z_{v}$. At the end of $\mathbf{B}^{v}_{k}$, the gambler can
take $Z_{v}$ and stop. If the gambler decides to take nothing and continue the
game, the outside option $Z_{v}$ is cleared.

######  Lemma D.4.

$\text{OPT}(G^{*}_{3})\leq\text{OPT}(G_{4})\leq(1+\varepsilon)\text{OPT}(G^{*}_{3})$.

###### Proof of Lemma D.4.

After we have replaced each $X_{i}$ with a sequence of variables
$\mathbf{X}_{i}$ where all support values with small probabilities are
extracted as binary variables, the proof of Lemma 4.6 completely goes through
in this case, as that proof does not require the special variables with large
support probabilities to be binary, and also does not require the variables in
each block $\mathbf{B}^{v}_{k}$ to arrive in random order. ∎

Prophet secretary game $G_{5}$ with perturbed outside option. The gambler
plays prophet secretary game $G_{4}$. However, in each block
$\mathbf{B}^{v}_{k}$ with $k\geq 1$, the outside option $Z_{v}$ is set to $v$
with a fixed probability $1-e^{(1-\varepsilon)Q^{o}_{v}}$. The same as in the
binary distribution setting, we have the following lemma.

######  Lemma D.5.

$(1-\varepsilon)\text{OPT}(G_{4})\leq\text{OPT}(G_{5})\leq\text{OPT}(G_{4})$.

###### Proof.

Fix some value $v$. Note that the effect of the outside option on the reward
is that we consider the maximum between that value and the value we get from
the current variable. Even if in this maximum $v$ always wins, by making this
change we have reduced this probability by at most
$e^{-(1-\varepsilon)Q^{o}_{v}}-e^{-(1+\varepsilon)Q^{o}_{v}}=O(\varepsilon^{3})$.
Moreover, there are at most $\tilde{O}(1/\varepsilon)$ many different values.
This means that the contribution of this change to $\text{OPT}(G_{5})$ is at
most $\varepsilon\text{OPT}(G_{4})$.

Finally, comparing $G_{3}$ and $G_{4}$, we are reducing probabilities in the
latter. So its optimal is always at most that of $G_{3}$. This concludes the
proof.

∎

Combining all the lemmas above, we get the following corollary, showing that
Game $G_{5}$ obtains almost the same optimal reward as the original prophet
secretary problem.

######  Corollary D.6.

$(1-O(\varepsilon))\text{OPT}(G_{1})\leq\text{OPT}(G_{5})\leq(1+O(\varepsilon))\text{OPT}(G_{1})$.

To approximately solve $\text{OPT}(G_{1})$, it suffices to solve
$\text{OPT}(G_{5})$. In the following theorem, we show that
$\text{OPT}(G_{5})$ can be efficiently computed.

######  Theorem D.7.

Prophet secretary game $G_{5}$ can be optimally solved in time
$n^{(1/\varepsilon)^{\text{poly}(1/\varepsilon)}}$.

###### Proof.

In the binary distribution case, we proposed a dynamic program that runs in
$n^{\text{poly}(1/\varepsilon)}$ time. The same dynamic program still works
for $G_{5}$ for general distribution, and the only difference is the size of
the DP. Notice that previously in the binary case there are at most 2 support
values for each variable, and now in the general case each variable has
support size $\tilde{O}(1/\varepsilon)$. This means that the number of
distinct “special variables” with large probabilities for each support value
is $\tilde{O}{(1/\varepsilon)}^{\tilde{O}(1/\varepsilon)}$, since each support
value has $\tilde{O}(1/\varepsilon)$ different discretized probabilities. The
running time of the dynamic program is now
$n^{(1/\varepsilon)^{\text{poly}(1/\varepsilon)}}$, which means that the
dynamic program is still a PTAS. ∎

######  Corollary D.8.

There exists a PTAS algorithm for the prophet secretary game $G_{1}$. This is
a direct result of Corollary D.6 and Theorem D.7.

Symbol | Definition |  Explanation
---|---|---
$\mathbf{X}_{v}$ | $\\{X_{i}:supp(X_{i})\in\\{0,v\\}\\}$ |  Variables with support $0$ and $v$.
$\mathbf{X}^{*}_{v}$ |  $\\{X_{i}|X_{i}\in\mathbf{X}_{v},\ s.t.\ q_{i}<\varepsilon^{20}\\}$ for $v\leq 1/\varepsilon^{2}$ |  Variables with support $0$ and $v$ and $q_{i}<\varepsilon^{20}$
$\mathbf{X}^{*}_{v_{\max}}$ | $\\{X_{i}|X_{i}\in\mathbf{X}_{v_{\max}},\ s.t.\ q_{i}<\varepsilon^{20}\sum_{X_{j}\in\mathbf{X}_{v_{\max}}}q_{j}\\}$ |  Variables with support $0$ and $v_{\max}$ and $q_{i}<\varepsilon^{20}\sum_{X_{j}\in\mathbf{X}_{v_{\max}}}q_{j}$
$\mathbf{X}^{+}_{v}$ | $\mathbf{X}^{+}_{v}=\mathbf{X}_{v}\setminus\mathbf{X}^{*}_{v}$ |  Special variables with support $v$
$\mathbf{X}^{+}$ | $\mathbf{X}^{+}=\bigcup_{v}\mathbf{X}^{+}_{v}$ |  All special variables
$\overline{Q}^{*}_{v}$ | $\overline{Q}^{*}_{v}=\sum_{X_{i}\in\mathbf{X}^{*}_{v}}q_{i}$ |  Total mass of small-probability variables with support $0$ and $v$
$Q^{*}_{v}$ | $Q^{*}_{v}=\min(\overline{Q}^{*}_{v},1/\varepsilon)$ |  Total mass of small-probability variables with support $0$ and $v$, capped at $1/\varepsilon$.
$Q^{o}_{v}$ | $\varepsilon^{4}Q^{*}_{v}$ |  The average mass of small probability variables in each block
$\delta_{v}$ | $Q^{o}_{v}/\overline{Q}^{*}_{v}$ |  The number of variables in each block $\mathbf{B}^{v}_{k}$ is $\delta_{v}$ fraction of total variables
$\mathbf{B}^{v}_{i}$ |  |  $i$’th block of the partition of all variables defined by support value $v$. Different support values create different partitions.
$Z_{v}$ |  |  Outside option for a block with support $v$
Table 1: Notation cheatsheet for binary distribution case.