### On a Class of Optimal Stopping Problems with Mixed Constraints

*Thomas Bruss*

#### Abstract

Let X

_{1}, X_{2}, ⋯, X_{n}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 X_{k}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 S_{n}of all selection strategies for which the decision at instant k may depend on the value X_{k}, on the number N_{k}of selections up to time k and of the number n-k of forthcoming observations. Let σ_{r,µ}(n) be the corresponding S_{n}-optimal selection strategy and v_{r,µ}(n) its value. The main goal of this paper is to determine these and to understand the limiting behaviour of v_{r,µ}(n). After discussion of the specific character of this combination of two types of constraints we conclude that the S_{n}-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 v_{r,µ}(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,µ)=g_{r}((µ-r)^{2}/2) where g_{r}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 S_{n}to the set of full-history-dependent and/or randomized strategies.Full Text: PDF PostScript