Optimal stopping

Solution methods

There are generally two approaches to solving optimal stopping problems. When the underlying process (or the gain process) is described by its unconditional finite-dimensional distributions, the appropriate solution technique is the martingale approach, so called because it uses martingale theory, the most important concept being the Snell envelope. In the discrete time case, if the planning horizon ${\displaystyle T}$ is finite, the problem can also be easily solved by dynamic programming.

When the underlying process is determined by a family of (conditional) transition functions leading to a Markov family of transition probabilities, powerful analytical tools provided by the theory of Markov processes can often be utilized and this approach is referred to as the Markov method. The solution is usually obtained by solving the associated free-boundary problems (Stefan problems).

A jump diffusion result

Let ${\displaystyle Y_t}$ be a Lévy diffusion in ${\displaystyle {\mathbb{R}}^k}$ given by the SDE

${\displaystyle d{Y}_t=b(Y_t)dt+\sigma (Y_t)d{B}_t+{\int }_{{\mathbb{R}}^k}\gamma (Y_{t-},z)\overline{N}(dt,dz),Y_0=y}$

where ${\displaystyle B}$ is an ${\displaystyle m}$-dimensional Brownian motion, ${\displaystyle \overline{N}}$ is an ${\displaystyle l}$-dimensional compensated Poisson random measure, ${\displaystyle b:{\mathbb{R}}^k\to {\mathbb{R}}^k}$, ${\displaystyle \sigma :{\mathbb{R}}^k\to {\mathbb{R}}^{k\times m}}$, and ${\displaystyle \gamma :{\mathbb{R}}^k\times {\mathbb{R}}^k\to {\mathbb{R}}^{k\times l}}$ are given functions such that a unique solution ${\displaystyle (Y_t)}$ exists. Let ${\displaystyle \mathcal{S}\subset {\mathbb{R}}^k}$ be an open set (the solvency region) and

${\displaystyle {\tau }_{\mathcal{S}}=inf\{t>0:Y_t\notin \mathcal{S}\}}$

be the bankruptcy time. The optimal stopping problem is:

${\displaystyle V(y)=\underset{\tau \le {\tau }_{\mathcal{S}}}{sup}{J}^{\tau }(y)=\underset{\tau \le {\tau }_{\mathcal{S}}}{sup}{\mathbb{E}}_y\left[M(Y_{\tau })+{\int }_0^{\tau }L(Y_t)dt\right].}$

It turns out that under some regularity conditions, the following verification theorem holds:

If a function ${\displaystyle \varphi :\overline{\mathcal{S}}\to \mathbb{R}}$ satisfies

• ${\displaystyle \varphi \in C(\overline{\mathcal{S}})\cap C^1(\mathcal{S})\cap C^2(\mathcal{S}\setminus \mathrm{\partial }D)}$ where the continuation region is ${\displaystyle D=\{y\in \mathcal{S}:\varphi (y)>M(y)\}}$,
• ${\displaystyle \varphi \ge M}$ on ${\displaystyle \mathcal{S}}$, and
• ${\displaystyle \mathcal{A}\varphi +L\le 0}$ on ${\displaystyle \mathcal{S}\setminus \mathrm{\partial }D}$, where ${\displaystyle \mathcal{A}}$ is the infinitesimal generator of ${\displaystyle (Y_t)}$

then ${\displaystyle \varphi (y)\ge V(y)}$ for all ${\displaystyle y\in \overline{\mathcal{S}}}$. Moreover, if

• ${\displaystyle \mathcal{A}\varphi +L=0}$ on ${\displaystyle D}$

Then ${\displaystyle \varphi (y)=V(y)}$ for all ${\displaystyle y\in \overline{\mathcal{S}}}$ and ${\displaystyle {\tau }^{\ast }=inf\{t>0:Y_t\notin D\}}$ is an optimal stopping time.

These conditions can also be written is a more compact form (the integro-variational inequality):

• ${\displaystyle max\left\{\mathcal{A}\varphi +L,M-\varphi \right\}=0}$ on ${\displaystyle \mathcal{S}\setminus \mathrm{\partial }D.}$

Examples

Coin tossing

(Example where ${\displaystyle \mathbb{E}(y_i)}$ converges)

You have a fair coin and are repeatedly tossing it. Each time, before it is tossed, you can choose to stop tossing it and get paid (in dollars, say) the average number of heads observed.

You wish to maximise the amount you get paid by choosing a stopping rule. If X_i (for i ≥ 1) forms a sequence of independent, identically distributed random variables with Bernoulli distribution

${\displaystyle \text{Bern}\left(\frac{1}{2}\right),}$

and if

${\displaystyle y_i=\frac{1}{i}\sum _{k=1}^i{X}_k}$

then the sequences ${\displaystyle (X_i{)}_{i\ge 1}}$, and ${\displaystyle (y_i{)}_{i\ge 1}}$ are the objects associated with this problem.

House selling

(Example where ${\displaystyle \mathbb{E}(y_i)}$ does not necessarily converge)

You have a house and wish to sell it. Each day you are offered ${\displaystyle X_n}$ for your house, and pay ${\displaystyle k}$ to continue advertising it. If you sell your house on day ${\displaystyle n}$, you will earn ${\displaystyle y_n}$, where ${\displaystyle y_n=(X_n-nk)}$.

You wish to maximise the amount you earn by choosing a stopping rule.

In this example, the sequence (${\displaystyle X_i}$) is the sequence of offers for your house, and the sequence of reward functions is how much you will earn.

Secretary problem

(Example where ${\displaystyle (X_i)}$ is a finite sequence)

You are observing a sequence of objects which can be ranked from best to worst. You wish to choose a stopping rule which maximises your chance of picking the best object.

Here, if ${\displaystyle R_1,\dots ,R_n}$ (n is some large number) are the ranks of the objects, and ${\displaystyle y_i}$ is the chance you pick the best object if you stop intentionally rejecting objects at step i, then ${\displaystyle (R_i)}$ and ${\displaystyle (y_i)}$ are the sequences associated with this problem. This problem was solved in the early 1960s by several people. An elegant solution to the secretary problem and several modifications of this problem is provided by the more recent odds algorithm of optimal stopping (Bruss algorithm).

Search theory

Economists have studied a number of optimal stopping problems similar to the 'secretary problem', and typically call this type of analysis 'search theory'. Search theory has especially focused on a worker's search for a high-wage job, or a consumer's search for a low-priced good.

Parking problem

A special example of an application of search theory is the task of optimal selection of parking space by a driver going to the opera (theater, shopping, etc.). Approaching the destination, the driver goes down the street along which there are parking spaces – usually, only some places in the parking lot are free. The goal is clearly visible, so the distance from the target is easily assessed. The driver's task is to choose a free parking space as close to the destination as possible without turning around so that the distance from this place to the destination is the shortest.

Option trading

In the trading of options on financial markets, the holder of an American option is allowed to exercise the right to buy (or sell) the underlying asset at a predetermined price at any time before or at the expiry date. Therefore, the valuation of American options is essentially an optimal stopping problem. Consider a classical Black–Scholes set-up and let ${\displaystyle r}$ be the risk-free interest rate and ${\displaystyle \delta }$ and ${\displaystyle \sigma }$ be the dividend rate and volatility of the stock. The stock price ${\displaystyle S}$ follows geometric Brownian motion

${\displaystyle S_t=S_0\exp \left\{\left(r-\delta -\frac{{\sigma }^2}{2}\right)t+\sigma B_t\right\}}$

under the risk-neutral measure.

When the option is perpetual, the optimal stopping problem is

${\displaystyle V(x)=\underset{\tau }{sup}{\mathbb{E}}_x\left[e^{-r\tau }g(S_{\tau })\right]}$

where the payoff function is ${\displaystyle g(x)=(x-K{)}^{+}}$ for a call option and ${\displaystyle g(x)=(K-x{)}^{+}}$ for a put option. The variational inequality is

${\displaystyle max\left\{\frac{1}{2}{\sigma }^2{x}^2{V}^{″}(x)+(r-\delta )x{V}^{\prime }(x)-rV(x),g(x)-V(x)\right\}=0}$

for all ${\displaystyle x\in (0,\mathrm{\infty })\setminus \{b\}}$ where ${\displaystyle b}$ is the exercise boundary. The solution is known to be

• (Perpetual call) ${\displaystyle V(x)=\{\begin{array}{ll}(b-K)(x/b{)}^{\gamma }& x\in (0,b)\\ x-K& x\in [b,\mathrm{\infty })\end{array}}$ where ${\displaystyle \gamma =(\sqrt{{\nu }^2+2r}-\nu )/\sigma }$ and ${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,b=\gamma K/(\gamma -1).}$
• (Perpetual put) ${\displaystyle V(x)=\{\begin{array}{ll}K-x& x\in (0,c]\\ (K-c)(x/c{)}^{\tilde{\gamma }}& x\in (c,\mathrm{\infty })\end{array}}$ where ${\displaystyle \tilde{\gamma }=-(\sqrt{{\nu }^2+2r}+\nu )/\sigma }$ and ${\displaystyle \nu =(r-\delta )/\sigma -\sigma /2,c=\tilde{\gamma }K/(\tilde{\gamma }-1).}$

On the other hand, when the expiry date is finite, the problem is associated with a 2-dimensional free-boundary problem with no known closed-form solution. Various numerical methods can, however, be used. See Black–Scholes model#American options for various valuation methods here, as well as Fugit for a discrete, tree based, calculation of the optimal time to exercise.