Optimal sequential selection of a gambler assessed by the prophet (Q2734507)

This dissertation deals with the following optimal stopping problem: let \(X_1,\dots, X_n\) be i.i.d. real-valued random variables with maximum \(M_n\); find a stopping rule \(S\) maximizing \(E(f(X_S\), \(M_n))\), where \(f(x,y)\) is some function having certain monotonicity properties. For example, one may want to stop so as to maximize the probability that \(X_S\) is greater than 90 \% of the maximum. The problem is first reduced to the case of uniformly distributed \(X_i\), and then the general structure of the optimal stopping rule is derived in terms of the boundaries of the stopping regions. The case \(f= 1_{\{x\geq r(y)\}}\), in which \(P(X_S\geq r(M_n))\) is to be maximized, is considered in detail. Here \(r(y)\) is a continuous, increasing function satisfying \(r(y)\leq y\). If \(r(1)= 1\), the limiting behavior as \(n\to\infty\) is shown to depend only on \(r'(1-)\); many asymptotic relations for threshold strategies are presented in this case. The case of random arrival times of the ``offers'' \(X_i\) within a finite horizon is also treated, and simple rules are shown to be optimal for geometric and for exponential arrival processes. A Poisson limit theorem is also proved.NEWLINENEWLINENEWLINEThe \(k\)th offer \(X_k\) is called a temporary \(r\)-candidate at time \(j\geq k\) if \(X_k\geq r(M_j)\), and an overall \(r\)-candidate if \(X_k\geq r(M_n)\). In the duration problem the objective is either (i) to stop at an \(X_k\) that remains an \(r\)-candiate for a maximum time, or (ii) to stop at an overall \(r\)-candidate as early as possible: Both problems can be treated with or without recall option, and also with discounting. Several exact and asymptotic results are derived for all these variations, including the continuous-time case with Poisson arrivals within a fixed or random (exponential) horizon.