Optimal multiple stopping: theory and applications
Analytics
85 views ◎45 downloads ⇓
Abstract
The classical secretary problem was an optimal selection thought experiment for a decision process where candidates with independent and identically distributed values to the observer appear in a random order and the observer must attempt to choose the best candidate with limited knowledge of the overall system. For each observation (interview) the observer must choose to either permanently dismiss the candidate or hire the candidate without knowing any information on the remaining candidates beyond their distribution. We sought to extend this problem into one of sequential events where we examine continuous payoff processes of a function of continuous stochastic processes. With the classical problem the goal was to maximize the probability of a desired occurrence. Here, we are interested in maximizing the expectation of integrated functions of stochastic processes. Further, our problem is not one of observing and discarding, but rather one where we have a job or activity that must remain filled by some candidate for as long as it is profitable to do so. After posing the basic problem we then examine several specific cases with a single stochastic process providing explicit solutions in the infinite horizon using PDE and change of numeraire approaches and providing limited solutions and Monte Carlo simulations in the finite horizon, and finally we examine the two process switching case in both finite and infinite horizon.As our general model will include supremum of the expected value of integrated stochastic processes, we will make use of techniques that allow us to rewrite the problem into a form without integrals. In the infinite horizon cases we will make use of a method developed by Ciss\'{e}, Patie, and Tanr\'{e} \cite{cpt} and change of numeraire before taking standard PDE-approaches to solving the resulting variational inequality. In finite horizon cases, we will use a portfolio method developed by Ve\u{c}e\u{r} \cite{vecer} to rewrite the problem. For optimal stopping problems with integrated processes, the resulting PDE before transforming the problem will have two dimensions for every integral process. The strength of Ve\u{c}e\u{r}'s approach is that it effectively reduces the dimension of the problem, although it does introduce a portfolio term that has complicated dynamics. This makes the approach unsuited to finding closed form solutions in general, but it does offer advantages in Monte Carlo simulations. In a general model, a numerical simulation of the integrals will require simulations of the variables themselves, then integration, then examinations over all possible (discrete) stopping times in the limits of integration. With the portfolio approach, however, we only need to simulate each variable and the portfolio itself.