Stochastic Input Models in Online Computing

arXiv:1709.07601v1 [cs.DS] 22 Sep 2017

Yasushi Kawase∗
Tokyo Institute of Technology, Tokyo, Japan
kawase.y.ab@m.titech.ac.jp

Abstract
In this paper, we study twelve stochastic input models for online problems and reveal the relationships
among the competitive ratios for the models. The competitive ratio is defined as the worst ratio between
the expected optimal value and the expected profit of the solution obtained by the online algorithm where
the input distribution is restricted according to the model. To handle a broad class of online problems, we
use a framework called request-answer games that is introduced by Ben-David et al. The stochastic input
models consist of two types: known distribution and unknown distribution. For each type, we consider
six classes of distributions: dependent distributions, deterministic input, independent distributions, identical independent distribution, random order of a deterministic input, and random order of independent
distributions. As an application of the models, we consider two basic online problems, which are variants
of the secretary problem and the prophet inequality problem, under the twelve stochastic input models.
We see the difference of the competitive ratios through these problems.

1

Introduction

In online computing, we are given a sequence of requests, and we need to choose an action in each step
based on the current information without knowing the full information which will be completely obtained in
the future [6, 25]. Since an online algorithm is forced to make decisions without knowing the entire inputs,
they may later turn out not to be optimal. The quality of an online algorithm is usually measured by the
competitive ratio [35], which is the worst ratio between the optimal value and the profit of the solution
obtained by the online algorithm. However, for practical application, it is too pessimistic because the worstcases rarely occur in real-world. Thus, an average-case analysis is more suitable than the worst one in such a
situation. In order to analyze average performance, we need to assume some distribution of inputs. Hence, in
this paper, we consider stochastic input models. In 2004, Hajiaghayi, Kleinberg, and Parkes [16] studied the
case where requests are drawn independently from some unknown distribution and the case where the requests
sequence is determined by picking a multi-set of requests and then permuting them randomly. However, we
can define various stochastic input models, and we need to consider which should we use depending on
analysis objective.
Various studies related to online problems with a stochastic input have been extensively conducted on
statistics literature. A most famous example of the problems is secretary problem [14, 15, 34]. In the
(classical) secretary problem, a decision-maker is willing to hire the best secretary out of n applicants that
arrive in a random order, and the goal is to maximize the probability of choosing the best applicant. As
each applicant appears, it must be either selected or rejected, and the decision is irrevocable. It is assumed
that the decision must be based only on the relative ranks (without ties) of the applicants seen so far and
the number of applicants n. It is well known that one can succeed with the optimal probability 1/e by the
following algorithm: observe the first n/e applicants without selecting, and then select the next applicant
who is the best among the observed applicants [12].
∗ Supported

by a Grant-in-Aid for Young Scientists (B) (No. 16K16005).

1

The above setting is also referred to the no-information case because there is no information about the
value of applicants. When the decision-maker is allowed to observe the actual values of the applicants, the
problem is called the full-information secretary problem if the values are chosen independently and identically
from a known distribution. Also, if the values are chosen independently and identically from a distribution
with an unknown parameter, it is called the partial-information secretary problem. Moreover, when the
values are chosen independently from known (not necessarily identical) distributions, the problem is studied
as prophet inequality. Krengel, Sucheston, and Garling [27] provided a tight 2-competitive algorithm: select
the first value that is at least half of the expected maximum.
There are also a huge number of researches on the stochastic input models in online learning literature, such
as online (convex) optimization, online prediction, online classification, and multi-armed bandit [10, 9, 18].
In many studies in the literature, it is assumed that input is drawn from an unknown distribution and one
repeatedly performs the same task.
The main purpose of this paper is to compare stochastic input models in the sense of competitive ratios.
As a previous result, Mehta [32] provided a relation between four models: unknown deterministic input,
random order of an unknown deterministic input, unknown i.i.d., and known i.i.d. However, he considered
only the online allocation problems. On the other hand, this paper studies a more general form of online
problems through request-answer games.

Our results
In this paper, we provide twelve stochastic input models for online problems and reveal the relationships
among the competitive ratios for the models. The models consist of two types: known distribution and
unknown distribution. For each type, we consider six classes of distributions: dependent distributions (dep),
deterministic input (det), independent distributions (ind), identical independent distribution (i.i.d.), random
order of a deterministic input (r.d.), and random order of independent distributions (r.i.). The competitive
ratio is defined as the worst ratio between the expected optimal value and the expected profit of the solution
obtained by the online algorithm where the input (request) distribution is restricted according to the model.
We will denote by CRmodel (resp. CRmodel ) the competitive ratio with unknown (resp. known) distribution
model. For example, CRdet , CRr.d. , CRi.i.d. , CRi.i.d. represent competitive ratios for unknown deterministic
input, random order of an unknown deterministic input, unknown i.i.d., and known i.i.d., respectively. Then,
our results can be summarized as Figure 1.
CRind
CRdep
CRdet
CRdet

CRi.i.d.

CRi.i.d.
CRr.d.

CRr.d.

CRr.i.

CRr.i.

CRind
CRdep

Figure 1: The relationships of the competitive ratios. Each arrow represents an inequality (the value at the
head of each arrow is at most the one at its tail) and ratios in the same region have the same value.

Related work
Ben-David et al. [5] introduced a general framework of online problems, which is called request-answer games.
They compared oblivious, adaptive-online, and adaptive-offline adversaries. The request-answer games can
be seen as the following two-person zero-sum games. The first player seeks an online algorithm that minimizes

2

the competitive ratio; the second player seeks a request sequence that maximizes the competitive ratio. We
can view a randomized online algorithm as a mixed strategy of the first player. By using von Neumann’s
minimax theorem [38] and Loomis’s lemma [29], we can get a technique to obtain an upper bound of the
competitive ratio. This technique is called Yao’s principle [39] and used for various online problems.
Many generalizations of the secretary problem, i.e., problems in the random order model, have been studied in the competitive analysis literature. As a natural generalization, Hajiaghayi, Kleinberg, and Parkes [16]
introduced the multiple-choice secretary problem and Kleinberg [23] provided an asymptotically optimal
competitive algorithm when the objective is to maximize the sum of the k choices. Babaioff, Immorlica, and
Kleinberg [4] introduced the matroid secretary problem. In this model, the set of selected applicants must
be an independent set in an underlying matroid. Lachish [28] provided O(log log r)-competitive algorithm
where r is the rank of given matroid. Korula and Pál [26] presented 8-competitive algorithm for bipartite
matching and then Kesselheim et al. [22] provide a tight e-competitive algorithm. Babaioff et al. [2] introduced knapsack secretary problem and proposed 10e-competitive algorithm. For more details, see Dinitz [11]
and Babaioff et al. [3].
There are also a number of researches for generalizations of prophet inequalities. Hajiaghayi, Kleinberg,
and Sandholm [17] considered multiple-choice variant and they provided a prophet inequality when the objective is to maximize the sum of the k choices. Kleinberg and Weinberg [24] studied the matroid constrained
version and gave a tight 2-competitive algorithm. Rubinstein and Singla [33] introduced framework for combinatorial valuation functions. Moreover, Esfandiari et al. [13] introduced a prophet secretary problem, which
is a natural combination of the prophet inequality problem and the secretary problem. In their setting, the
values are chosen independently from known (not necessarily identical) distributions but arrive in a random
order.

Paper Organization
Section 2 describes formal definitions of our models via request-answer games. Section 3 discusses some
variants of the secretary problem and the prophet inequality problem for our models. In Section 4, we give
the proof of our results shown in Figure 1 and show that we cannot simplify the relations.

2

Model

In this section, we introduce request-answer games with stochastic input models.
A request-answer system is a tuple (R, A, f, n) where each component is defined as follows. There is a set
of requests R and a set of answers A. Throughout the paper, we assume that the sets R and A are finite. A
positive integer n represents the number of rounds. Let f : Rn × An → R+ denote a utility function, where
R+ is the set of nonnegative real numbers.
A deterministic online algorithm ALG is a sequence of functions gi : Ri → A (i = 1, 2, . . . , n). Given a
deterministic online algorithm ALG = (g1 , . . . , gn ) and a request sequence r = (r1 , . . . , rn ) ∈ Rn , the output
is an answer sequence ALG[r] = (a1 , . . . , an ) ∈ An where ai = gi (r1 , . . . , ri ) for i = 1, . . . , n. The utility
incurred by ALG on r, denoted by ALG(r) is defined as
ALG(r) = f (r, ALG[r]).
A randomized online algorithm ALG is defined as a probability distribution over the set of all deterministic
online algorithms A = {(g1 , . . . , gn ) | gi : Ri → A (i = 1, . . . , n)}. The utility incurred by ALG on r, denoted
by ALG(r) is defined as
ALG(r) = Ex [f (r, ALGx [r])]
where we use Ex to denote the expectation with respect to the distribution over the set A = {ALGx }, which
defines ALG. We will denote by A the set of randomized algorithms. We remark that A is a convex compact
set since A is a finite set by the assumption that R and A are finite.
3

The performance of an online algorithm is measured by the competitive ratio—the ratio between its value
and the optimal value for the worst request sequence. Note that we only discuss in this paper the oblivious
adversary, i.e., the request sequence does not depend on the randomized results of the algorithm. This is
because we want to consider weaker adversaries than the standard model and the adaptive adversary and
stochastic input models are incompatible in most cases.
Given a request sequence r ∈ Rn , the optimal offline utility on r is defined as
OPT(r) = max{f (r, a) | a ∈ An }.
Let Sn be the set of permutations of [n], where [n] = {1, . . . , n}. For a permutation σ ∈ Sn and a sequence
x = (x1 , . . . , xn ), let us denote xσ = (xσ(1) , . . . , xσ(n) ).
Definition 2.1 (Competitive Ratios). For a request-answer game (R, A, f, n), a randomized online algorithm
ALG ∈ A is ρ-competitive for a distribution D over the request sequences Rn if
Er∼D [OPT(r)] ≤ ρ · Er∼D [ALG(r)].
Let D be a compact subset1 of the distributions over the request sequences Rn .
We define the competitive ratio of (R, A, f, n) for unknown distribution in D as
CRD (R, A, f, n) =

inf

sup

ALG∈A D∈D

Er∼D [OPT(r)]
Er∼D [ALG(r)]

(1)

where we define 0/0 = 1. In other words, there exists a randomized online algorithm that is CRD (R, A, f, n)competitive for any D ∈ D, and this is best possible. Similarly, we define the competitive ratio of (R, A, f, n)
for known distribution in D as
Er∼D [OPT(r)]
.
D∈D ALG∈A Er∼D [ALG(r)]

CRD (R, A, f, n) = sup

inf

(2)

Namely, for any D ∈ D, there exists a CRD (R, A, f, n)-competitive algorithm, and this is best possible. We
often omit the argument (R, A, f, n) if there is no confusion.
The value of the competitive ratio is at least 1 and smaller is better. It should be noted that, for
minimization problems, a randomized online algorithm ALG is ρ-competitive for a distribution D over the
request sequences Rn if
Er∼D [ALG(r)] ≤ ρ · Er∼D [OPT(r)].
We can also define the competitive ratio of a minimization version of request-answer games in the same
manner.
By the max-min inequality, the following inequality holds.
Lemma 2.2. For any request-answer game (R, A, f, n) and a set of distributions D over the request sequences
Rn , we have
CRD (R, A, f, n) ≥ CRD (R, A, f, n).
Moreover, if D is a compact convex set, the equality in the above inequality holds.
Lemma 2.3. For any request-answer game (R, A, f, n) and a compact convex set of distributions D over the
request sequences Rn , we have
CRD (R, A, f, n) = CRD (R, A, f, n).
1 We

assume compactness to simplify the exposition.

4

Proof. Since CRD (R, A, f, n) ≥ CRD (R, A, f, n) holds by Lemma 2.2, it is sufficient to prove CRD (R, A, f, n) ≤
CRD (R, A, f, n). Let c = CRD (R, A, f, n) and let h(D, ALG) = Er∼D [OPT(r) − c · ALG(r)]. Since
[OPT(r)]
, it holds that for any ALG ∈ A there exists D ∈ D
c = CRD (R, A, f, n) = inf ALG∈A supD∈D EEr∼D
r∼D [ALG(r)]
such that h(D, ALG) ≥ 0. Thus we have
inf

sup h(D, ALG) ≥ 0.

ALG∈A D∈D

Moreover, by von Neumann’s minimax theorem [38], we have
sup h(D, ALG) = sup

inf

ALG∈A D∈D

inf

h(D, ALG)

D∈D ALG∈A

since A and D are compact convex sets, and h(D, ALG) is linear by the linearity of expectations. Thus,
supD∈D inf ALG∈A h(D, ALG) ≥ 0 and hence there exists D∗ ∈ D such that h(D∗ , ALG) ≥ 0 for any ALG ∈ A.
Therefore, we obtain
Er∼D [OPT(r)]
D∈D ALG∈A Er∼D [ALG(r)]
Er∼D∗ [OPT(r)]
≥ inf
ALG∈A Er∼D∗ [ALG(r)]

CRD (R, A, f, n) = sup

inf

≥ c = CRD (R, A, f, n),
which proves the lemma.
P
A distribution over a (finite) domain Ω is a function D : Ω → [0, 1] such that x∈Ω D(x) = 1. We denote
by ∆(Ω) the set of all such distributions. For x ∈ Ω, let δx be a distribution such that δx (x) = 1 and δx (y) = 0
for any x, y ∈ Ω such that y 6= x. In this paper, we consider the following six classes of distributions.
1. Dependent distribution:
∆dep (Rn ) = ∆(Rn ).
2. Deterministic input :
∆det (Rn ) = {δr | r ∈ Rn }.
3. Independent distribution:
∆ind (Rn ) =

(

D ∈ ∆(Rn ) D(r) =

4. Identical independent distribution:
(
n

∆i.i.d.(R ) =

n

D ∈ ∆(R ) D(r) =

n
Y

i=1

)

Di (ri ), Di ∈ ∆(R) .

n
Y

i=1

′

′

)

D (ri ), D ∈ ∆(R) .

5. Random order of deterministic input :
∆r.d. (Rn ) = {ψr | r ∈ Rn }
where ψr ∈ ∆(Rn ) (r ∈ Rn ) is a distribution such that ψr (r ′ ) = |{σ ∈ Sn | r ′ = r σ }|/n! for r ′ ∈ Rn .
Here, recall that r σ = (rσ(1) , . . . , rσ(n) ).
6. Random order of independent distribution:
(
n

∆r.i. (R ) =

n

D ∈ ∆(R ) D(r) =
5

n
X Y

σ∈Sn i=1

)

Dσ(i) (ri )/n!, Di ∈ ∆(R) .

We will omit the argument Rn when no confusion can arise. In addition, we abbreviate CR∆dep (Rn ) (R, A, f, n)
to CRdep and also we abbreviate the other competitive ratios in the same way.
Now, we can formally state our main results, which was depicted in Figure 1.
Theorem 2.4. For any request-answer game (R, A, f, n), we have
CRdet ≤ CRi.i.d. ≤ CRi.i.d. ≤ CRr.d. = CRr.i. ≤ CRdep = CRdet = CRind = CRdep ,
CRdet ≤ CRr.d. ≤ CRr.i. ≤ CRr.i. ,

(4)

CRi.i.d. ≤ CRind ≤ CRdep .

(6)

CRi.i.d. ≤ CRr.i. ,

3

(3)
(5)

Examples of the Stochastic Input Models

Before proving our main results, we see some examples of the stochastic input models.

3.1

Online selection problem

Suppose that a decision-maker sequentially observes a sequence of random variables X1 , X2 , . . . , Xn and is
allowed to choose only one number, which can be done only upon receiving that number. The goal is to
maximize the expectation of the chosen value. We formalize the problem as a request-answer game. Let
Rm = {0, 1, . . . , m} (where m is a sufficiently large integer), A = {0, 1}, and
(
ri∗ (if {i∗ } = {i | ai = 1}),
f (r, a) =
0
(otherwise).
ai = 1 (resp. ai = 0) represents that the decision-maker selects (resp. rejects) ith value.
The problem in the known independent distributions model is introduced by Krengel and Sucheston,
and it is eagerly studied under the name of the prophet inequalities. It is well known that this problem is
2-competitive when n ≥ 2, i.e., lim supm→∞ CR∆ind (Rnm ) = 2 for any n ≥ 2 [21]. Hill and Kertz [19] gave a
better upper bound of the competitive ratio in the known i.i.d. model and the current best upper bound is
1.354 [1].
For the known dependent distributions model, Hill and Kertz [20] proved that there exists no constant
competitive algorithm, i.e., lim supn,m→∞ CR∆dep (Rnm ) = ∞. By Theorem 2.4, this implies that
lim sup CR∆dep (Rnm ) = lim sup CR∆ind (Rnm ) = lim sup CR∆det (Rnm ) = ∞.
n,m→∞

n,m→∞

n,m→∞

For random order of known independent distributions model (prophet secretary problem), Esfandiari
et al. [13] provided e/(e − 1)-competitive algorithm and there is no online algorithm that can achieve a
competitive ratio better than 15/11. Hence, it holds that 15/11 ≤ lim supn,m→∞ CR∆r.i. (Rnm ) ≤ e/(e − 1).
When the given input is random order or i.i.d. distribution, it is easy to see that the secretary algorithm
is e-competitive. On the other hand, Stewart [36] proves that no algorithm can select the best number with
probability 1/e − o(1) when X1 , X2 , . . . , Xn are chosen i.i.d. from a uniform distribution on the interval (α, β)
and (α, β) is chosen from a certain Pareto distribution. Transforming the variables Xi to M Xi , where M is
a sufficient large number, implies that there is no online algorithm that is better than e-competitive. Thus
we have lim supn,m→∞ CR∆r.d. (Rnm ) = lim supn,m→∞ CR∆r.i. (Rnm ) = lim supn,m→∞ CR∆i.i.d. (Rnm ) = e.
For the other models, we can easily check that CR∆r.d. (Rnm ) = CR∆det (Rnm ) = 1 for any n, m because we
can deterministically pick the maximum number.

6

3.2

Odds problem

We show that the odds problem—a generalization of the classical secretary problem—can be formulated as the
known identical distribution model. In the odds problem, a decision-maker sequentially observes a sequence
of independent 0/1 random variables X1 , X2 , . . . , Xn , where Pr[Xi = 1] = pi (1) and Pr[Xi = 0] = pi (0) (=
1 − pi (1)). We say success if Xi = 1 and failure if Xi = 0. The goal is to find an optimal stopping rule to
maximize the probability of win—the probability of obtaining the last success. Note that the special case
pi = 1/i corresponds to the classical secretary problem and several generalizations of the odds problem have
been studied [8, 37, 30, 31].
Let us consider a request-answer game (R, A, f, n) where R = {0, 1}, A = {0, 1}, and
(
1 (if r = (0, . . . , 0) or {i | ai = 1} = arg max{i | ri = 1}),
f (r, a) =
0 (otherwise).
Qn
Then, for a distribution D∗ such that D∗ (r) = i=1 pi (ri ), the expected value Er∼D∗ [ALG(r)] is the probability of win2 . Note that OPT(r) = 1 for any r ∈ Rn and hence the competitive ratio is the inverse value
of the probability of win.
Bruss [7] proved that ALG∗ = (g1∗ , . . . , gn∗ ) is e-competitive when
(
Pn
pj (1)
1 (ri = 1 and
j=i+1 pj (0) < 1),
∗
gi (r1 , . . . , ri ) =
0 (otherwise)
and this is asymptotically best possible. Moreover, no online algorithm can achieve a competitive ratio better
than e even if the input is a known i.i.d. distribution when n goes to infinity (see Lemma A.1 in Appendix).
Namely, we can conclude that
lim sup CRind = lim sup CRi.i.d. = e.
n→∞

n→∞

Next, let us consider the following distribution D∗ :


. . . , 1, 0, . . . , 0), i = 1, 2, . . . , n),
1/n (r = (1,
| {z } | {z }
∗
D (r) =
i
n−i

0
(otherwise).

Then, it is easy to see that any algorithm wins with probability at most 1/n. On the other hand, selecting
a variable uniformly at random is an n-competitive algorithm. Thus, we obtain CRdep = CRdet = CRind =
CRdep = n.
For known deterministic inputs or known random order distribution, it holds that CRdet = CRr.d. = 1
because the algorithm can distinguish whether a current success is the last one or not.
For the other models CRi.i.d. , CRr.d. , CRr.i. , and CRr.i. , we can observe, by Theorem 2.4, that the values
are at least e when n goes to infinity and they are at most n. However, any good bounds are not known, to
the best of the author’s knowledge.

4

Relating the Competitive Ratios

In this section, we give the proof of Theorem 2.4 and we show that the relations (3)–(6) cannot be merged
into one sequence.
2 More

precisely, we add extra probability Pr[r = (0, . . . , 0)] to simplify later discussion.

7

4.1

Proof of Theorem 2.4

Let us start with an easy part.
Lemma 4.1. For any request-answer game (R, A, f, n), we have
CR∆det (Rn ) = 1.
Proof. As the online algorithm knows the whole request sequence in advance, it can output the optimal
answer sequence. More precisely, we get
CRdet =

Er′ ∼δr [OPT(r ′ )]
′
δr ∈∆det (Rn ) ALG∈A Er ′ ∼δr [ALG(r )]
sup

inf

OPT(r)
ALG(r)
maxa∈An f (r, a)
= sup
r∈Rn maxALG∈A ALG(r)

= sup

inf

r∈Rn ALG∈A

= sup
r∈Rn

maxa∈An f (r, a)
= 1.
maxa∈An f (r, a)

As the competitive ratios are at least 1, the lemma implies that CRdet is the smallest one.
We use the convex hull of a set of distributions to prove the rest part of the theorem. For a set of
distributions D, the convex hull is the set
(
)
X
X
conv(D) =
λD · D
λD = 1 and λD ≥ 0 (∀D ∈ D) .
D∈D

D∈D

The following lemma connects the unknown distribution model and the known distribution model.

Lemma 4.2. For any compact set of distributions D, we have
CRD = CRconv(D) = CRconv(D) .
Proof. CRconv(D) = CRconv(D) holds by Lemma 2.3 since conv(D) is a compact convex set.
Since D ⊆ conv(D), we have
inf

sup

ALG∈A D∈D

Er∼D [OPT(r)]
Er∼D [OPT(r)]
≤ inf
.
sup
Er∼D [ALG(r)] ALG∈A D∈conv(D) Er∼D [ALG(r)]

(7)

Thus, it is sufficient to prove the reverse inequality of (7).
Let us fix ALG ∈ A. Let D1 , D2 , · · · ∈ conv(D) be a sequence of distributions satisfying
lim

i→∞

Er∼Di [OPT(r)]
Er∼D [OPT(r)]
.
=
sup
Er∼Di [ALG(r)] D∈conv(D) Er∼D [ALG(r)]

By the definition
for each i ∈ {1, 2, . . . },there exist coefficients λiD such that Di =
P of thei convex closure,
P
i
i
D∈D λD = 1, and λD ≥ 0 (∀D ∈ D). Thus, we have
D∈D λD · D,
P
i
Er∼Di [OPT(r)]
n D (r) · OPT(r)
= Pr∈R
i
Er∼Di [ALG(r)]
r∈Rn D (r) · ALG(r)
P
P
λi · D(r) · OPT(r)
n
= Pr∈R PD∈D D
i
D∈D λD · D(r) · ALG(r)
r∈Rn
P
λi · Er∼D [OPT(r)]
= PD∈D D
i
D∈D λD · Er∼D [ALG(r)]
≤ sup

D∈D

Er∼D [OPT(r)]
.
Er∼D [ALG(r)]
8

Hence we obtain
i [OPT(r)]
E
Er∼D [OPT(r)]
Er∼D [OPT(r)]
= lim r∼D
.
≤ sup
i→∞
i
E
[ALG(r)]
E
[ALG(r)]
D∈D Er∼D [ALG(r)]
r∼D
D∈conv(D) r∼D

sup

By taking infimum over ALG ∈ A, we have
Er∼D [OPT(r)]
Er∼D [OPT(r)]
≤ inf sup
,
ALG∈A D∈D Er∼D [ALG(r)]
ALG∈A D∈conv(D) Er∼D [ALG(r)]
inf

sup

which proves the lemma.
Next, we examine relationships between our intended sets of distributions.
Lemma 4.3. For any request-answer game (R, A, f, n), we have
conv(∆i.i.d. ) ⊆ conv(∆r.d. ) = conv(∆r.i. ) ⊆ conv(∆det ) = conv(∆ind ) = ∆dep = conv(∆dep ).
Proof. We first prove that conv(∆det ) = conv(∆ind ) = conv(∆dep ) = ∆dep . By the definition, we have
∆det ⊆ ∆ind ⊆ ∆dep .
P
Also, for D ∈ ∆dep , it holds that D =
r∈Rn D(r)δr and hence ∆dep ⊆ conv(∆det ). Thus, ∆dep =
conv(∆dep ) = conv(∆ind ) = conv(∆det ) holds.
Next, we observe that conv(∆r.d. (Rn )) ⊆ ∆dep (Rn ). As ∆dep (Rn ) = conv(∆dep (Rn )), it is sufficient to
prove that ∆r.d. (Rn ) ⊆ ∆dep (Rn ). Let ψr ∈ ∆r.d. (Rn ). Recall that ψr (r ′ ) = |{σ ∈ Sn | r ′ = r σ }|/n! for
r ′ ∈ Rn . Thus we obtain
ψr =

X |{σ ∈ Sn | r ′ = r σ }|
· δr′ ∈ ∆dep (Rn ).
n!
′
n

r ∈R

Furthermore, we show conv(∆r.d. ) = conv(∆
r.i.
Q).n Since ∆r.d. ⊆ ∆r.i. , it is sufficient to prove that ∆r.i. ⊆
P
conv(∆r.d. ). Let D ∈ ∆r.i. where D(r) = σ∈Sn i=1 Dσ(i) (ri )/n! and Di ∈ ∆(R). Also, let D′ ∈ ∆ind be a
Qn
distribution such that D′ (r) = i=1 Di (ri ). Then we have
X
D=
D′ (r ′ )ψr′ ∈ conv(∆r.d. ).
r ′ ∈Rn

n
n
n
Finally, we show
r.d. (R )). Let D ∈ ∆i.i.d. (R ) and D(r) =
Qn ) ⊆ conv(∆
Qn that′ ∆i.i.d.(R
′
σ
we have D(r) = i=1 D (ri ) = i=1 D (rσ(i) ) = D(r ) for any σ ∈ Sn and hence

D=

X

D(r)δr =

r∈Rn

X 1 X
D(r σ )δrσ
n!
n

σ∈Sn

r∈R

X
X δr σ
X X D(r)δrσ
=
D(r)
=
n!
n!
n
n
r∈R σ∈Sn

=

X

r∈Rn

=

X

r∈Rn

D(r)

σ∈Sn

r∈R

′

X |{σ ∈ Sn | r = r σ }|
· δr ′
n!
′
n

r ∈R

D(r) · ψr ∈ conv(∆r.d. (Rn )),

which proves the claim.

9

!

Qn

i=1

D′ (ri ). Then

We remark that ∆i.i.d. (Rn ) ( conv(∆i.i.d. (Rn )) in general. For example, if R = {0, 1} and n = 2, then
+ 21 δ(1,1) ∈ conv(∆i.i.d. (Rn )) while 21 δ(0,0) + 12 δ(1,1) 6∈ ∆i.i.d. (Rn ).
Now we are ready to prove Theorem 2.4. By Lemmas 4.2 and 4.3, we obtain

1
2 δ(0,0)

CRi.i.d. ≤ CRr.d. = CRr.i. ≤ CRdep = CRdet = CRind = CRdep
since D ⊆ D′ implies CRD ≤ CRD′ . Moreover, CRi.i.d. ≤ CRi.i.d. holds by Lemma 2.2 and CRi.i.d. ≥ 1 (=
CRdet ) by the definition of competitive ratio. Thus, (3) holds. Also, (4) holds by ∆r.d. ⊆ ∆r.i. , (5) holds by
∆i.i.d. ⊆ ∆r.i. , and (6) holds by ∆i.i.d. ⊆ ∆ind ⊆ ∆dep .

4.2

Inequalities for incomparable ratios

We show that the relations (3)–(6) cannot be merged into one sequence. To prove this, we observe some
examples of request-answer games.
Lemma 4.4. For each following statement, there exists a request-answer game (R, A, f, n) that satisfies it:
(a) CRr.i. < CRi.i.d. , (b) CRind < CRi.i.d. , (c) CRr.d. < CRi.i.d. , (d) CRi.i.d. < CRr.d. , and (e) CRr.d. < CRind .
Proof. (a) CRr.i. < CRi.i.d.. This inequality holds for an online selection problem instance since CRr.i. ≤
e/(e − 1) (≈ 1.582) and CRi.i.d. ≥ e (≈ 2.718) when n and m go to infinity (see Section 3.1).
(b) CRind < CRi.i.d.. This inequality holds for an online selection problem instance since CRind ≤ 2 and
CRi.i.d. ≥ e when n and m go to infinity (see Section 3.1).
(c) CRr.d. < CRi.i.d. . This inequality holds for an odds problem instance since CRr.d. → 1 and CRi.i.d. → e
as n goes to infinity (see Section 3.2).
To prove the other cases, we consider request-answer games of the form G = (R, A, fS , n) where S ⊆ Rn ,
A = {0, 1}, and
(
1 ((r ∈ S and a1 = 1) or (r 6∈ S and a1 = 0)),
fS (r, a) =
0 (otherwise).
By the definition of the game, the task of the online algorithm is to predict r ∈ S or not. The prediction
is answered as a1 . The profit is one if the prediction is correct and is zero otherwise. Here, we remark that
OPT(r) = 1 for any r ∈ Rn .
(d) CRi.i.d. < CRr.d. . We consider the game G with
R = {1, 2, . . . , n} and S = {(σ(1), . . . , σ(n)) ∈ Rn | σ ∈ Sn , σ(n) > σ(n − 1)}.
Then, for any i.i.d. distribution, the request sequence does not belong to S with high probability. Thus, by
predicting that the request sequence does not belong to S, one can obtain an expected profit 1 − o(1). On the
other hand, when the input distribution is ψ(1,2,...,n) , we cannot predict that the request sequence belongs to
S or not with probability better than 1/2. Thus, CRi.i.d. = 1 + o(1) and CRr.d. = 2 and hence the inequality
holds.
(e) CRr.d. < CRind . We consider the game G with R = {0, 1} and S = {(0, 0, . . . , 0, 1)}. Then, for any
random order distribution, the request sequence belong to S with probability at most 1/n. Thus, by predicting
that the request sequence does not belong to S, one canQ
get an expected profit 1 − 1/n. On the other hand,
when the input distribution D ∈ ∆ind satisfies D(r) = ni=1 Di (ri ) where D1 (0) = · · · = Dn−1 (0) = 1 and
Dn (0) = Dn (1) = 1/2, we cannot predict that the request sequence belongs to S or not with probability
better than 1/2. Thus, CRr.d. = n/(n − 1) and CRind = 2 and hence the inequality holds.

10

References
[1] M. Abolhassani, S. Ehsani, H. Esfandiari, M. HajiAghayi, R. Kleinberg, and B. Lucier. Beating 1 − 1/e
ordered prophets. In Proceedings of STOC, pages 16–71, 2017.
[2] M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. A knapsack secretary problem with applications. In Proceedings of APPROX and RANDOM, pages 16–28, 2007.
[3] M. Babaioff, N. Immorlica, D. Kempe, and R. Kleinberg. Online auctions and generalized secretary
problems. ACM SIGecom Exchange, 7(2):7:1–7:11, 2008.
[4] M. Babaioff, N. Immorlica, and R. Kleinberg. Matroids, secretary problems, and online mechanisms. In
Proceedings of SODA, pages 434–443, 2007.
[5] S. Ben-David, A. Borodin, R. M. Karp, G. Tardos, and A. Wigderson. On the power of randomization
in on-line algorithms. Algorithmica, 11(1):2–14, 1994.
[6] A. Borodin and R. El-Yaniv. Online computation and competitive analysis. Cambridge university press,
2005.
[7] F. T. Bruss. Sum the odds to one and stop. The Annals of Probability, 28(3):1384–1391, 2000.
[8] F. T. Bruss and D. Paindaveine. Selecting a sequence of last successes in independent trials. Journal of
Applied Probability, 37(02):389–399, 2000.
[9] S. Bubeck and N. Cesa-Bianchi. Regret analysis of stochastic and nonstochastic multi-armed bandit
problems. Foundations and Trends in Machine Learning, 5(1):1–122, 2012.
[10] N. Cesa-Bianchi and G. Lugosi. Prediction, learning, and games. Cambridge university press, 2006.
[11] M. Dinitz. Recent advances on the matroid secretary problem. SIGACT News, 44(2), 2013.
[12] E. B. Dynkin. The optimum choice of the instant for stopping a Markov process. Soviet Mathematics
Doklady, 4:627–629, 1963.
[13] H. Esfandiari, M. Hajiaghayi, V. Liaghat, and M. Monemizadeh. Prophet secretary. In Proceedings of
ESA, pages 496–508, 2015.
[14] T. S. Ferguson. Who solved the secretary problem? Statical Science, 4(3):282–289, 1989.
[15] P. R. Freeman. The secretary problem and its extensions: A review. International Statistical Review,
51(2):189–206, 1983.
[16] M. Hajiaghayi, R. Kleinberg, and D. C. Parkes. Adaptive limited-supply online auctions. In Proceedings
of EC, pages 71–80. ACM, 2004.
[17] M. Hajiaghayi, R. Kleinberg, and T. Sandholm. Automated online mechanism design and prophet
inequalities. In Proceedings of AAAI, volume 7, pages 58–65, 2007.
[18] E. Hazan. Introduction to Online Convex Optimization. Foundations and Trends in Optimization Series.
2016.
[19] T. P. Hill and R. P. Kertz. Comparisons of stop rule and supremum expectations of i.i.d. random
variables. The Annals of Probability, 10(2):336–345, 1982.
[20] T. P. Hill and R. P. Kertz. Stop rule inequalities for uniformly bounded sequences of random variables.
Transactions of the American Mathematical Society, 278(1):197–207, 1983.
[21] T. P. Hill and U. Krengel. A prophet inequality related to the secretary problem. Strategies for Sequential
Search and Selection in Real Time, pages 209–215, 1992.
11

[22] T. Kesselheim, K. Radke, A. Tönnis, and B. Vöcking. An optimal online algorithm for weighted bipartite
matching and extensions to combinatorial auctions. In Proceedings of ESA, pages 589–600, 2013.
[23] R. Kleinberg. A multiple-choice secretary algorithm with applications to online auctions. In Proceedings
of SODA, pages 630–631, 2005.
[24] R. Kleinberg and S. M. Weinberg. Matroid prophet inequalities. In Proceedings of STOC, pages 123–136,
2012.
[25] D. Komm. An Introduction to Online Computation: Determinism, Randomization, Advice. Springer
International Publishing, 2016.
[26] N. Korula and M. Pál. Algorithms for secretary problems on graphs and hypergraphs. In Proceedings
of ICALP, pages 508–520, 2009.
[27] U. Krengel and L. Sucheston. Semiamarts and finite values. Bulletin of the American Mathematical
Society, 83(4):745–747, 1977.
[28] O. Lachish. O(log log rank) completitive-ratio for the matroid secretary problem. In Proceedings of
FOCS, pages 326–335, 2014.
[29] L. H. Loomis. On a theorem of von neumann. In Proceedings of the National Academy of Sciences of
the U.S.A., volume 32, pages 213–215, 1946.
[30] T. Matsui and K. Ano. A note on a lower bound for the multiplicative odds theorem of optimal stopping.
Journal of Applied Probability, 51(03):885–889, 2014.
[31] T. Matsui and A. Katsunori. Lower bounds for bruss’ odds problem with multiple stoppings. Mathematics
of Operations Research, 41(2):700–714, 2016.
[32] A. Mehta. Online matching and ad allocation. Foundations and Trends in Theoretical Computer Science,
8(4):265–368, 2013.
[33] A. Rubinstein and S. Singla. Combinatorial prophet inequalities. In Proceedings of SODA, pages 1671–
1687, 2017.
[34] S. M. Samuels. Secretary problems. In Handbook of Sequential Analysis. Marcel Dekker, 1991.
[35] D. D. Sleator and R. E. Tarjan. Amortized efficiency of list update and paging rules. Communications
of the Association for Computing Machinery, 28(2):202–208, 1985.
[36] T. J. Stewart. Optimal selection from a random sequence with learning of the underlying distribution.
Journal of the American Statistical Association, 73(364):775–780, 1978.
[37] M. Tamaki. Sum the multiplicative odds to one and stop. Journal of Applied Probability, 47(03):761–777,
2010.
[38] J. von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100:295–320, 1928.
[39] A. Yao. Probabilistic computations: Toward a unified measure of complexity. In Proceedings of FOCS,
pages 222–227. IEEE, 1977.

12

A

Omitted Proof

Lemma A.1. No online algorithm can achieve a competitive ratio better than e even if the input is a known
i.i.d. distribution.
√
√
Proof. Let us assume that Pr[Xi = 1] = 1/ n and Pr[Xi = 0] = 1 − 1/ n for each i = 1, . . . , n. Consider
the following linear programming (LP):
max
s.t.

Pn



1−

√1
n

n−i

qi
Pi−1
√
n · qi ≤ 1 − j=1 qj
qi ≥ 0
i=1

(i ∈ [n]),
(i ∈ [n])

where [n] = {1, 2, . . . , n}.
We claim that the optimal value for the LP gives an upper bound of the probability of win for the problem.
Let qi be the probability of selecting the ith random variable as success. Then the probability of win is
n−i
n 
X
1
1− √
qi
n
i=1

because if Xi+1 = · · · = Xn = 0 with probability 1 −

√1
n

n−i

. Also, pij must satisfy the following relation:


pi ≤ Pr[1, . . . , i − 1 are not selected] · Pr[Xi = 1] = 1 −

Thus, the LP present an upper bound of the success probability.
To evaluate the optimal value, now we consider the dual problem:
Pn
min
i=1 ri

n−i
Pn
√
s.t.
n · ri + j=i+1 rj ≥ 1 − √1n
ri ≥ 0

i−1
X



1
qj  · √ .
n
j=1

(i ∈ [n]),
(i ∈ [n]).

√ n−i−1
√ n−i n−i
− n · (1 − 1/ n)
, 0}. Then it is easy to check that ri∗ is a feasible
Let ri∗ = max{ √1n · (1 − 1/ n)
solution for the dual LP.
Thus, the optimal value of the LP (and the dual LP) is upper bounded by
n
X

ri∗

=

n
X

max

i=1

i=1

=

n
X




√ n−i n − i
√ n−i−1
1
√ · (1 − 1/ n)
−
,0
· (1 − 1/ n)
n
n


√ n−i n − i
√ n−i−1
1
√ · (1 − 1/ n)
· (1 − 1/ n)
−
n
n

√
i=n−⌊ n⌋+1

√ ⌊√n⌋
√ ⌊√n⌋
√ ⌊√n⌋
1 1 − (1 − 1/ n)
1 1 − (1 − 1/ n)
− (1 − 1/ n)
√
=√ ·
− ·
n
1 − (1 − 1/ n)
n
1/n
√
√ ⌊ n⌋
1
(n → ∞).
→
= (1 − 1/ n)
e
Hence, 1/e is an upper bound of the probability of win for the problem.
Moreover, since Pr[X1 = · · · = Xn = 0] → 0 as n → ∞, there exists no online algorithm that can achieve
a competitive ratio better than e.

13

