On a Class of Optimal Stopping Problems with Mixed Constraints
Thomas Bruss
Abstract
Let X1, X2, ⋯, Xn
be independent, identically distributed uniform random variables on
[0,1]. We can observe the outcomes sequentially and must
select online at least r of them, and, moreover, in
expectation at least µ≥ r. Here
µ need not be integer. We see
Xk as the cost of selecting item
k and want to minimise the expected total cost under the
described combined (r,µ)-constraint. We will see
that an optimal selection strategy exists on the set
Sn of all selection strategies for which
the decision at instant k may depend on the value
Xk, on the number Nk
of selections up to time k and of the number
n-k of forthcoming observations. Let
σr,µ(n) be the corresponding
Sn-optimal selection strategy and
vr,µ(n) its value. The main goal of this
paper is to determine these and to understand the limiting behaviour
of vr,µ(n). After discussion of the
specific character of this combination of two types of constraints we
conclude that the Sn-problem has a recursive
structure and solve it in terms of a double recursion. Our interest
will then focus on the limiting behaviour of n
vr,µ(n) as n →∞. This
sequence converges and its limit allows for the interpretation of a
normalised limiting cost L(r,µ) of the
(r,µ)-constraint. Our main result is that
L(r,µ)=gr((µ-r)2/2)
where gr is the rth iterate of the function
g(x)=1+x+1+2x.
Our motivation to study mixed-constraints problems is indicated by
several examples of possible applications. We also shortly discuss the
intricacy of the expectational part of the constraint if we try to
extend the class of strategies Sn to the
set of full-history-dependent and/or randomized strategies.
Full Text: PDF PostScript