Improved Algorithms and Analysis for Secretary Problems and Generalizations.
In the classical secretary problem, n objects from an ordered set arrive in random order, and one has to accept k of them so that the final decision about each object is made only on the basis of its rank relative to the ones already seen. Variants of the problem depend on the goal: either maximize the probability of accepting the best k objects, or minimize the expectation of the sum of the ranks (or powers of ranks) of the accepted objects. The problem and its generalizations are at the core of tasks with a large data set, in which it may be impractical to backtrack and select previous choices.Optimal algorithms for the special case of are well known. Partial solutions for the first variant with general k are also known. In contrast, an explicit solution for the second variant with general k has not been known. It seems that the fact that the expected sum of powers of the ranks of selected items is bounded as n tends to infinity has been known to follow from standard results. We derive our results by obtaining explicit algorithms. For each $z \geq 1$, the resulting expected sum of the zth powers of the ranks of the selected objects is at most $k^{z the best possible value at all is kz O(kz). Our methods are very intuitive and apply to some generalizations. We also derive a lower bound on the trade-off between the probability of selecting the best object and the expected rank of the selected object.
Introduction
In the classical secretary problem, n items or options
are presented one by one in random order (i.e., all
n! possible orders being equally likely). If we could
observe them all, we could rank them totally with no
ties, from best (rank 1) to worst (rank n). However,
when the ith object appears, we can observe only
its rank relative to the previous the
relative rank is equal to one plus the number of the
predecessors of i which are preferred to i. We must
accept or reject each object, irrevocably, on the basis
of its rank relative to the objects already seen, and we
are required to select k objects. The problem has two
main variants. In the first, the goal is to maximize
the probability of obtaining the best k objects. In
the second, the goal is to minimize the expectation of
the sum of the ranks of the selected objects or, more
generally, for a given positive integer z, minimize the
expectation of the sum of the zth powers of the ranks.
Solutions to the classical problem apply also in variety
of more general situations. Examples include (i)
the case where objects are drawn from some probability
distribution; the interesting feature of this variant
is that the decisions of the algorithms may be based
not only on the relative rank of the item but also on
an absolute "grade" that the item receives, (ii) the
number of objects is not known in advance, (iii) objects
arrive at random times, (iv) some limited back-tracking
is allowed: objects that were rejected may
be recalled, (v) the acceptance algorithm has limited
memory, and also combinations of these situations. In
addition to providing intuition and upper and lower
bounds for the above important generalizations of the
problem, solutions to the classical problem also provide
in many cases very good approximations, or even
exact solutions (see [4, 13, 14] for survey and also [8]).
Our methods can also be directly extended to apply
for these generalizations.
The obvious application to choosing a best applicant
for a job gives the problem its common name,
although the problem (and our results) has a number
of other applications in computer science. For
any problem with a very large data set, it may be
impractical to backtrack and select previous choices.
For example, in the context of data mining, selecting
records with best fit to requirements, or retrieving images
from digital libraries. In such applications limited
backtracking may be possible, and in fact this is
one of the generalizations mentioned above. Another
important application is when one needs to choose an
appropriate sample from a population for the purpose
of some study. In other applications the items may
be jobs for scheduling, opportunities for investment,
objects for fellowships, etc.
1.1 Background and Intuition
The problem has been extensively studied in the
probability and statistics literature (see [4, 13, 14]
for surveys and also [10]).
The case of k = 1. Let us first review the case of
one object has to be selected. Since
the observer cannot go back and choose a previously
presented object which, in retrospect, turns out to be
the best, it clearly has to balance the risk of stopping
too soon and accepting an apparently desirable object
when an even better one might still arrive, against the
risk of waiting for too long and then find that the best
item had been rejected earlier.
It is easy to see that the optimal probability of selecting
the best item does not tend to zero as n tends
to infinity; consider the following stopping rule: reject
the first half of the objects and then select the first
relatively best one (if any). This rule chooses the best
object whenever the latter is among the second half
of the objects while the second best object is among
the first half. Hence, for every n, this rule succeeds
with probability greater than 1=4. Indeed, it has been
established ([7, 5, 2]) (see below) that there exists an
optimal rule that has the following form: reject the
first objects and then select the first relatively
best one or, if none has been chosen through the end,
accept the last object. When n tends to infinity, the
optimal value of r tends to n=e, and the probability
of selecting the best is approximately 1=e. (Lind-
ley showed the above using backward induction [7].
Later, Gilbert and Mosteller provided a slightly more
accurate bound for r [5]. Dynkin established the result
as an application of the theory of Markov stopping
times [2].)
It is not as easy to see that the optimal expected
rank of the selected object tends to a finite limit as n
tends to infinity. Observe that the above algorithm
(for maximizing the probability of selecting the best
object) yields an expected rank of n=(2e) for the selected
item; the argument is as follows. With probability
1=e, the best item is among the first n=e items,
and in this case the algorithm selects the last item.
The conditional expectation of the rank of the last
object in this case is approximately n=2. Thus, the
expected rank for the selected object in this algorithm
tends to infinity with n. Indeed, in this paper
we show that, surprisingly, the two goals are in fact
in conflict (see Section 1.2).
It can be proven by backward induction that there
exists an optimal policy for minimizing the expected
rank of selected item that has the following form: accept
an object if and only if its rank relative to the
previously seen objects exceeds a certain threshold
(depending on the number of objects seen so far).
Note that while the optimal algorithm for maximizing
the probability of selecting the best has to remember
only the best object seen so far, the threshold
algorithm has to remember all the previous objects.
(See [11] for solutions where the observer is allowed
to remember only one of the previously presented
items.) This fact suggests that minimizing the expected
rank is harder. Thus, not surprisingly, finding
an approximate solution for the dynamic programming
recurrence for this problem seems significantly
harder than in the case of the first variant of the prob-
lem, i.e., when the goal is to maximize the probability
of selecting the best. Chow, Moriguti, Robbins, and
Samuels, [1] showed that the optimal expected rank
of the selected object is approximately 3:8695. The
question of whether higher powers of the rank of the
selected object tend to finite limits as n tends to infinity
was resolved in [11]. It has also been shown that
if the order of arrivals is determined by an adversary,
then no algorithm can yield an expected rank better
than n=2 [12].
The case of a general k. There has been much interest
in the case where more than one object has to
be selected. It is not hard to see that for every fixed
k, the maximum probability of selecting the best k
objects does not tend to zero as n tends to infinity.
The proof is as follows. Partition the sequence of n
objects into k disjoint intervals, each containing n=k
consecutive items. Apply the algorithm for maximizing
the probability of selecting the best object to each
set independently. The resulting algorithm selects the
best item in each interval with probability e \Gammak . The
probability that the best k objects belong to distinct
intervals tends to k!=k k as n tends to infinity. For
this first variant of the problem, the case of
was considered in [9]; Vanderbei [16], and independently
Glasser, Holzager, and Barron [6], considered
the problem for general k. They showed that there is
an optimal policy with the following threshold form:
accept an object with a given relative rank if and only
the number of observations exceeds a critical number
that depends on the number of items selected so
in addition, an object which is worse than any of
the already rejected objects need not be considered.
Notice that this means that not all previously seen
items have to be remembered, but only those that
were already selected and the best among all those
that were already rejected. This property is analogous
to what happened in the case, where the
goal was to maximize the probability of selecting the
best item. Both papers derive recursive relations using
backward induction. General solutions to their
recurrences are not known, but the authors give explicit
solutions (i.e., critical values and probability)
for the case of
[16] also presents certain asymptotic results as
n tends to infinity and k is fixed and also as both k
and n tend to infinity so that (2k \Gamma n)=
remains
finite.
In analogy to the case of bounding the optimal
expected sum of ranks of k selected items appears
to be considerably harder than minimizing the probability
of selecting the best k items. Also, here it is
not obvious to see whether or not this sum tends to
a finite limit when n tends to infinity. Backward induction
gives recurrences that seem even harder to
solve than those derived for the case of maximizing
the probability of selecting the best k. Such equations
were presented by Henke [8], but he was unable
to approximate their general solutions.
Thus, the question of whether the expected sum of
ranks of selected items tends to infinity with n has
been open. There has not been any explicit solution
for obtaining a bounded expected sum. Thus the sec-
ond, possibly more realistic, variant of the secretary
problem has remained open.
1.2 Our Results
In this paper we present a family of explicit algorithms
for the secretary problem such that for each
positive integer z, the family includes an algorithm
for accepting items, where for all values of n and k,
the resulting expected sum of the zth powers of the
ranks of the accepted items is at most
where C(z) is a constant. 2
kg.
Clearly, the sum of ranks of the zth powers of the
best k objects is k z+1 =(z Thus, the
sum achieved by our algorithms is not only bounded
by a value independent of n, but also differs from the
best possible sum only by a relatively small amount.
For every fixed k, this expected sum is bounded by a
constant. Thus we resolve the above open questions
regarding the expected sum of ranks and, in general,
zth powers of ranks, of the selected objects.
Our approach is very different from the dynamic
programming approach taken in most of the papers
mentioned above. In addition to being more successful
in obtaining explicit solution to this classical prob-
lem, it can more easily be used to obtain explicit solutions
for numerous generalizations, because it does
not require a completely new derivation for each objective
function.
We remark that our approach does not partition
the items into k groups and select one item in each.
Such a method is suboptimal since with constant
probability, a constant fraction of the best k items
appear in groups where they are not the only ones
from the best k. Therefore, this method rejects a
constant fraction of the best k with constant prob-
ability, and so the expected value of the sum of the
ranks obtained by such an algorithm is greater by at
least a constant factor than the optimal.
Since the expected sums achieved by our algorithms
depend only on k and z and, in addition, the
probability of our algorithms to select an object does
not decrease with its rank, it will follow that the probabilities
of our algorithms to actually select the best
objects depend only on k and z, and hence for fixed
k and z, do not tend to zero when n tends to infin-
ity. In particular, this means that for our
algorithms will select the best possible object with
probability bounded away from zero.
In contrast, for any algorithm for the problem, if
the order of arrival of items is the worst possible (i.e.,
generated by an oblivious adversary), then the algorithm
yields an expected sum of at least kn z 2 \Gamma(z+1)
for the zth powers of the ranks of selected items. Our
lower bound holds also for randomized algorithms.
Finally, in Section 1.1 we observed that an optimal
algorithm for maximizing the probability of selecting
the best object results in an unbounded expected
rank of the selected object. As a second part of this
work we show that this fact is not a coincidence: the
two goals are in fact in conflict. No algorithm can
simultaneously optimize the expected rank and the
probability of selecting the best. We derive a lower
bound on the trade-off between the probability of accepting
the best object and the expected rank of the
accepted item.
Due to lack of space, most proofs are omitted or
only sketched.
2. The Algorithms
In this section we describe a family of algorithms for
the secretary problem, such that for each positive integer
z, the family includes an algorithm for accepting
objects, where the resulting expected sum of the zth
powers of the ranks of accepted objects is
In addition, it will follow that the algorithm accepts
the best k objects with positive probability that depends
only on k and z. Let z be the positive integer
that we are given. Denote
For the convenience of exposition, we assume without
loss of generality that n is a power of 2. We partition
the sequence [1; . ; n] (corresponding to the
objects in the order of arrival) into
consecutive intervals I i m), so that
I
fng if
In other words, the first are [1; n
4 ]; . ; each containing a half of the remaining
elements. The mth interval contains the last element.
Note that jI
Let us refer to the first
intervals as the opening ones, and let the rest be the
closing ones. Note that since p - 64, the last five
intervals are closing. For an opening I i , the expected
number of those of the top k objects in I i is
(The latter is not necessarily an integer.) Further-
more, for any d -
(i.e., d is in one of the
opening intervals), the expected number of those of
the top k objects among the first d to arrive is d \Delta k
n .
Let
Observe that pm 0
We will refer to p i as the minimum number of acceptances
required for I i m). Observe that
On the other hand,
Intuitively, during each interval the algorithm attempts
to accept the expected number of top k objects
that arrive during this interval, and in addition
to make up for the number of objects that should
have been accepted prior to the beginning of this
interval but have not. Note that since p
during such intervals the algorithm
only attempts to make up for the number of objects
that should have been accepted beforehand and have
not.
Let us explain this slightly more formally. During
each execution of the algorithm, at the beginning
of each interval, the algorithm computes a threshold
for acceptance, with the goal that by the time the
processing of the last object of this interval is com-
pleted, the number of accepted objects will be at least
the minimumnumber of acceptances required prior to
this time. In particular, recall that for
denotes the minimum number of acceptances required
for I i . Given a "prefix" of an execution prior
to the beginning of I i
1), be the number of items accepted
in I j . Let D
Roughly speaking, D i\Gamma1 is the difference between the
minimumnumber of acceptances required prior to the
beginning of I i and the number of items that were
actually accepted during the given prefix. Note that
Given a prefix of an execution prior to the beginning
of I i , let
ae
We refer to A i computed at the beginning of I i as the
acceptance threshold for I i in this execution. Loosely
stated, given a prefix of execution of the algorithm
prior to the beginning of I i , A i is the number of objects
the algorithm has to accept during I i in order to
meet the minimum number required by the end of I i .
The algorithm will aim at accepting at least A i objects
during I i . To ensure that it accepts that many, it
attempts to accept a little more. In particular, during
each opening interval I i , the algorithm attempts to
accept an expected number of A i +6(z +1) p
A i log k.
As we will see, this ensures that the algorithm accepts
at least A i objects during this interval with probability
of at least k \Gamma5(z+1) . During each closing interval
I i , the algorithm attempts to accept an expected
number of 32(z This ensures that the algorithm
accepts at least A i objects during this interval
with probability of at least 2 \Gamma5(z+1)(a i +1) .
We make the distinction between opening and closing
intervals in order to restrict the expected rank of
the accepted objects. If I i is closing, then A i may be
much smaller than p
A i log k. Let
ae
A i log k if I i is opening
closing.
In order to accept an expected number of B i objects
during interval I i , the algorithm will accept the dth
item if it is one of the approximately
ones among the first d. Since the order of arrival
of the items is random, the rank of the dth object
relative to the first d ones is distributed uniformly
in the set f1; . ; dg. Therefore, the dth object will
be accepted with probability of B
since jI e, the expected number of objects
accepted during I i is indeed B i .
If at some point during the execution of the algo-
rithm, the number of slots that still have to be filled
equals the number of items that have not been processed
yet, all the remaining items will be accepted
regardless of rank. Analogously, if by the time the
dth item arrives all slots have already been filled, this
item will not be accepted.
Finally, the algorithm does not accept any of the
first dn=(8
k)e items except in executions during
which the number of slots becomes equal to the number
of items before dn=(8
k)e items have been pro-
cessed. Roughly speaking, this modification will allow
to bound the expected rank of the dth item in
terms of its rank relative to the first d items.
The above leads to our algorithm, which we call
Select.
Algorithm Select: The algorithm processes the
items, one at a time, in their order of arrival. At the
beginning of each interval I i , the algorithm computes
A i as described above. When the dth item (d 2 I i )
arrives, the algorithm proceeds as follows.
(i) If all slots have already been filled then the object
is rejected.
(ii) Otherwise, if d ? dn=(8
k)e, then
(a) If the dth item is accepted if it is one
of the top
items among the first d.
(b) If the algorithm accepts the dth item
if it is one of the top b32(z
items among the first d.
(iii) Otherwise, if the number of slots that still have
to be filled equals the number of items left (i.e.,
1), the dth item is accepted.
We refer to acceptances under (3) , i.e., when the
number of slots that still have to be filled equals the
number of items that remained to be seen, as manda-
tory, and to all other acceptances as elective. For
example, if the dth item arrives during I 1 , and the
latter is opening, then the item is accepted electively
if and only if it is one of the approximately
k=2 log
k=2 log
top objects among the first d. In general, if the dth
object arrives during an opening I i , then the object
is accepted electively if and only if it is one of the
approximately
top objects among the first d.
3. Analysis of Algorithm Select
Very loosely stated, the proof proceeds as follows.
In Section 3.1 we show that for
Observe that this implies that for
high probability, A i is approximately p i , i.e.,
In Section 3.2 we show that if the dth object arrives
during an opening I i , then the conditional expectation
of the zth power of its rank, given that it is
accepted electively, is not greater than 2 iz 1
z+1 A z
c 4 (z)2 iz A z\Gamma0:5
log k, for some constant c 4 (z) (depend-
ing on z); if I i is closing, this conditional expectation
is not greater than c 6 (z)2 iz A z
c 6 (z). In Section 3.3 these results of Sections 3.1 and
3.2 are combined and it is established that if the dth
object arrives during an opening I i , then its conditional
expected zth power of rank, given that it is
accepted electively, is at most
k z
for some constant c(z). If I i is closing, that conditional
expected zth power of rank is at most c 0 (z)k z ,
for some constant c 0 (z), if approximately
otherwise. From this it will follow that the
expected sum of the zth powers of ranks of the elec-
tively accepted objects is 1
In addition we use the result of Section 3.1 to show
that the expected sum of the zth powers of ranks of
mandatorily accepted objects is O(k z+0:5 log k). Thus
the expected sum of the zth powers of ranks of the
accepted objects is 1
In addition, from the fact that the expected sum
of the zth powers of ranks of the accepted objects is
bounded by a value that depends only on k and z, it
will also follow that the algorithm accepts the top k
objects with probability that depends only on k and
z.
3.1 Bounding the A i s
In this section we show that for
high probability, A i is very close to p i . To this end
we distinguish between 'smooth' and `nonsmooth' executions
(see below).
3.1.1 Smooth Prefixes. Denote by E i the prefix
of an execution E prior to the end of I i . Note that Em
is E. We say that
computed in E i is - jI j j. Denote by ME i
the event
in which E i is smooth.
In this section we show that for an opening interval
I i , in executions whose prefix prior to the end of
the 1th interval is smooth, the probability that
exponentially with j (Part 1 of
Lemma 3.3). For a closing I i , in executions whose
prefix prior to the end of the i\Gamma1th interval is smooth,
the probability that A i exponentially
both with j and with i (Part 2 of Lemma 3.3).
Part 1 and Part 2 of Lemma 3.3 will follow, respec-
tively, from Lemmas 3.1 and 3.2 that show that in
executions whose prefix prior to the end of the ith
interval is smooth, in I i the algorithm accepts A i objects
with high probability (where A i is computed for
the prefix of the execution). Intuitively, the restriction
to smooth executions is necessary since at most
objects can be selected in I i .
Lemma 3.1 For every any value a i
of A i ,
Sketch of Proof: Note that D i ? 0 only if the
number of objects accepted in I i is less than a i .
Loosely stated, the algorithm accepts the dth object
electively if it is one of the top
A i log
objects among the first d. Since the
objects arrive in a random order, the rank of the dth
object within the set of first d is distributed uniformly
and hence it will be accepted electively with probability
not less than b(a
a i log
c=d.
Moreover, the rank of the dth object within the set
of the first d is independent of the arrival order of the
first d \Gamma 1, and hence is independent of whether or
not any previous object in this interval, say the th
one, is one of the top
objects among the first d 1 . The rest of the proof
follows from computing the expected number of accepted
candidates and Chernoff inequality.
Analogously,
Lemma 3.2 If n - 16, then for every
Lemma 3.3
(i) For
(ii) If n - 16, then for
Sketch of Proof: We outline the proof for Part
(1). Recall that the minimum number of acceptances
required for an opening interval I i is
Thus if A i ? k2 \Gammai , then D
are positive. These events are
dependent and their probabilities are conditioned on
however, it can be shown that both the dependency
and the conditioning are working in our
favour. Lemma 3.1 thus implies that each of the
underlying events fD q ? 0g
with probability less than k \Gamma5(z+1) . Hence,
3.1.2 Nonsmooth Executions. Lemma 3.3 implies
that in smooth executions, with high probability,
A i is very close to p i . To complete the proof that A i
is close to p i , we now show that nonsmooth executions
are rare. In particular, Part (1) of Lemma 3.3
is used to show:
Lemma 3.4 If
Analogously,
Lemma 3.5 If n - 16, k - 1
The case of k - n=2 is excluded (Lemma 3.5) and
thus handled separately later (Section 3.3).
3.2 Expected zth powers of Ranks
Let us denote by R d the random variable of the rank
of the dth object. We define the arrival rank of the
dth object as its rank within the set of the first d
objects, i.e., one plus the number of better objects
seen so far. Denote by S d the random variable of the
arrival rank. Denote by NA d the event in which the
dth object is accepted electively.
Lemma 3.6 There exist constants c 2 (z), c 3 (z) and
c (z) such that for all d - n
k and s,
E(R z
d
d
s z
d
d
Combining the result of Lemma 3.6 with the fact
that given that the object is accepted electively during
an opening interval I i and A
distributed uniformly in the set f1; 2; . ; b(a
a i log k)2 i d=ncg, we will get:
Lemma 3.7 There exist constants c 4 (z) and c 5 (z)
such that for all opening intervals I i (i.e.,
every value a i of A i , if the dth object arrives during
I i and d - n
E(R z
r
d
Analogously,
Lemma 3.8 There exists a constant c 6 (z), such that
for all closing intervals I i (i.e.,
a i of A i , if the dth object arrives during I i , and d -
, then
E(R z
3.3 Expected Sum of Ranks
In this section we show that the expected sum of the
zth powers of ranks of the k accepted objects isz
(Theorem 3.1). This will follow by adding up the expected
sum of the zth powers of ranks of electively
accepted objects (Lemmas 3.13), and the expected
sum of the zth powers of ranks of mandatorily accepted
objects (Lemma 3.15).
3.3.1 Elective Acceptances. Denote by SUMZ i
the sum of the zth powers of ranks of objects that are
accepted electively during I i .
Lemma 3.9 There exists a constant c 7 (z) such that
for all opening intervals I i and for all values a i of A i ,
a z+1
Lemma 3.10 There exists a constant c 8 (z) such that
for all closing intervals I i , for all acceptance thresholds
a i computed for I i ,
Lemma 3.9 is combined with Part 1 of Lemma 3.3
and with Lemma 3.4 to show:
Lemma 3.11 There exists a constant c 9 (z) such that
for all opening intervals I i ,
Analogously,
Lemma 3.12 If n - 16, then there exists a constant
such that for any closing interval I i ,
The following lemma completes the proof of the
upper bound on the sum of the ranks of the electively
accepted objects. It sums up the expected sum of
ranks of electively accepted objects over all intervals.
Lemma 3.13
3.3.2 Mandatory Acceptances. This section
bounds the expected sum of mandatorily accepted
objects. We first observe:
Lemma 3.14 If the dth object is mandatorily accepted
in execution E during I i , then :ME i+1
Denote by SUMDZ i the sum of the zth powers of
ranks of objects that are accepted mandatorily during
I i .
Lemmas 3.4 and 3.5 of Section 3.1.2 imply that,
for each I i , the probability that a prefix of execution
prior to the end of I i is not smooth, is at
most c(z)n \Gamma2:5(z+1) log n, where c(z) is a constant.
(The case of k - 1
2 n is handled without the use of
Lemma 3.5, since this lemma excludes it.) Clearly,
this bound applies also for the probability that objects
will be mandatorily accepted in I i . We combine
this bound with the facts that the rank of an object
never exceeds n, and the number of accepted objects
is at most k - n, to show:
Lemma 3.15 There exist constants c 21 (z) and
c 22 (z) such that
Lemmas 3.13 and 3.15 imply:
Theorem 3.1 The expected sum of ranks of accepted
objects is at
Corollary 3.1 Algorithm Select accepts the best k
objects with positive probability that depends only on
k and z.
4. Trade-Off between Small Expected
Rank and Large Probability of Accepting
the Best
Theorem 4.1 Let p 0 be the maximum possible probability
of selecting the best object. There is a c ? 0 so
that for all ffl ? 0 and all sufficiently large n, if A is an
algorithm that selects one of n objects, and the probability
pA that A selects the best one is greater than
then the expected rank of the selected object is
at least c=ffl.
Proof: Suppose that contrary to our assertion there
is an algorithm A that selects the best object with
probability of at least p yet the expected
value of the rank of the selected object is less than
c=ffl.
Starting from A, we construct another algorithm R
so that R selects the best object with a probability
Denote by OPT the following algorithm: Let n=e
objects pass, and then accept the first object that is
better than anyone seen so far. If no object was accepted
by the time the last object arrives, accept the
last object. For n sufficiently large, this algorithm accepts
the best object with the highest possible prob-
ability, and hence with probability p 0 [7]. 3
In better approximation to
r than ne \Gamma1 although the difference is never more than 1 [5].
We ignore this difference for the sake of simplicity.
We define R by modifying A. The definition will
depend on parameters c 1 ? d ? 0. We will assume
that d is a sufficiently large absolute constant and c 1
is sufficiently large with respect to d. R will accept
an object if at least one of the following conditions is
(i) A accepts the object after time n=d and by time
and the object is better than anybody
else seen
(ii) OPT accepts the object whereas A accepted earlier
somebody who, at the time of acceptance,
was known not to be the best one (that is there
was a better one before);
(iii) OPT accepts the object and A has already accepted
somebody by time n=d;
(iv) the object comes after time it is better
than anybody else seen before and R has not yet
accepted anybody based on the rules (1), (2),
(v) the object is the nth object and R has not accepted
yet any object.
Notation: Denote by BA, BR, and BOPT the
events in which A, R and OPT, repectively, accept
the best object. Denote by B1, B2, and B3 the
events in which the best object appears in the intervals
spectively. Denote by IA1, IA2 and IA3 the events
in which A makes a selection in the intervals [1; n=d],
We distinguish between two cases.
Case I: ProbfIA1g -
4.1
Proof: Suppose that A made a selection by time
n=d. According to rule (3), in this case R will accept
an object that arrives after time n=d if and only if
OPT accepts this object. By choosing d sufficiently
large, we have that objects are accepted by OPT only
after time n=d. Thus, if A made a selection by time
n=d, R will accept the object if and only if OPT accepts
it. Thus,
The second inequality follows since the probability
that OPT accepts the best object is independent of
the order of arrival of the first n=d objects, and hence
independent of whether or not A makes a selection by
time n=d.
On the other hand,
Thus, by choosing d to be sufficiently large the claim
follows.
4.2
Proof: The claim follows immediately from the fact
that if A picks the best object between n=d and t 0 ,
then this object must be the best seen so far, and
hence by rule (1), R picks the same object.
4.3
Proof: If IA3 holds then neither A nor R have accepted
anybody till time t 0 . Let X be the event when
A chooses no later than R. By the definition of R we
have that if X " IA3 holds then either A accepts an
object that already at the moment of acceptance is
known not to be the best, or A and R accept the same
object. Thus,
To complete the proof, it suffices to show that
Suppose that IA3 " :X holds and R accepts an object
at some time t ? t 0 . By definition, A has not
accepted anybody yet, and the object accepted by R
at t is better than anyone else seen earlier. Thus, if a
better object than the one accepted by R arrives after
time t, this means that the best object arrives after
time t. Since the objects arrive in a random order,
the rank of each dth arriving object within the set
of first d is distributed uniformly. Hence, the probability
that the best object will arrive after time t
is at most (n \Gamma t)=n - c 1 ffln. Notice that this probability
is independent of the ordering of the first t
objects, and hence is independent of the fact that
R has accepted the tth object. Therefore the probability
that the object accepted by R is indeed the
best object is at least 1 \Gamma c 1 ffln, while the probability
that A accepts the best one later is smaller than
ffln. Thus, for any fixed choice of t and fixed order
of the first t objects (with the property IA3 " :X),
the probability of BR is larger than BA, and hence
Now we can complete the proof of Case I:
ProbfBRg
The second inequality follows from Claims 4.1, 4.2
and 4.3. The fourth inequality follows from (i)
by the theorem assumption and
(ii) ProbfIA1g - 3ffl=p 0 by Case I assumption.
Case II: ProbfIA1g ! 3ffl=p 0 . Denote by BR1,
BR2, and BR3 the events when R picks the
best object and its selections are in the interval
respectively. Denote by
BA1, BA2, and BA3 the corresponding events for A.
Since by the assumption of this case ProbfIA1g !
If A picks the best object between n=d and t 0 , then
this object must be the best seen so far, and hence
by rule (1), R picks the same object. Thus
By choosing d sufficiently large, we have that objects
are accepted by OPT only after time n=d. Observe
that in that case, if the second best comes by
time n=d and the best comes after time t 0 , then R
accepts the best object. The probability that the second
best object arrives by time n=d is 1=d, and the
conditional probability that the best object comes after
given that the second best comes by time
n=d, is at least c 1 ffl. It thus follows:
For bounding ProbfBA3g, we first use the assumption
that the expected rank of the object selected by
A is less than c=ffl, to show:
Proof: Each of the 1=(10dc 1 ffl) objects with a rank
smaller than 1=(10dc 1 ffl) arrives after time t
probability of at most c 1 ffl. Therefore, with
probability of at least 1 \Gamma 1=(10d), all objects that
arrive after time t 0 are of rank larger than 1=(10dc 1 ffl).
Hence, if the probability of IA3 had been greater than
1=(2d), then the expected value of the rank would
have been larger than c 0 =ffl for some absolute constant
the c of the theorem to be equal to c 0 ,
and we get a contradiction to the assumption that the
expected rank of the selected object is at most c=ffl.
Recall that B3 denotes the event in which the best
object arrives in interval
IA3g. But B3 is independent
of the order of arrival of the first t 0 objects
and hence independent on whether or not A has accepted
an object by time t 0 . Thus, Claim 4.4 implies
that ProbfIA3g \Delta ProbfB3
Equations (1) to (4) imply
(The last inequality follows from our assumption that
c 1 is sufficiently large with respect to d.) Therefore

Acknowledgements

We are indebted to James Aspnes, Eugene Dynkin,
John Preater, Yossi Rinott, Mike Saks, Steve
Samuels, and Robert Vanderbei for helpful references.



--R

"secretary problem"
The optimum choice of the instant for stopping a Markov process.
Who solved the secretary prob- lem? Statistical Science <Volume>4</Volume>
The secretary problem and its ex- tensions: A review
Recognizing the maximum of a sequence.
The d Choice secretary problem.
Dynamic programming and decision theory.
Sequentialle Auswahlprobleme bei Unsicherheit.
A generalization of the best choice problem.
On multiple choice secretary prob- lems
The finite memory secretary problem.
Optimal counter strategies for the secretary problem.
Secretary problems.
Secretary problems as a source of benchmark sounds.
Amortized efficiency of list updates and paging rules.
The optimal choice of a sub-set of a population
--TR

--CTR
Andrei Broder , Michael Mitzenmacher, Optimal plans for aggregation, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California
Robert Kleinberg, A multiple-choice secretary algorithm with applications to online auctions, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA
optimal stopping;expected rank maximization;dynamic programming