American Options and Free Boundaries

A European option can be exercised only at expiry. An American option can be exercised at any time up to expiry, and most traded stock options are American. The holder must now decide when to exercise, and the price is the value of the best decision: an optimal stopping problem. Its solution splits the state space into a region where it is best to continue and a region where it is best to stop, separated by an exercise boundary that is not known in advance and must be found with the solution. The Black–Scholes equation holds only in the continuation region, and on the free boundary two conditions hold: the price equals the payoff, and so does its slope (smooth fit).

This is the parabolic version of the obstacle problem of 6C.1 Regularity of Minimisers and Constraints, with the payoff as the obstacle, and the same mathematics governs melting ice (the Stefan problem), the timing of investments, and when to sell a house. This chapter solves the discrete-time problem completely, solves the perpetual American put in closed form, shows why smooth fit is the optimality condition, and describes the numerical methods used in practice.

By the end of this chapter you will be able to:

• price American options on a binomial tree by backward induction, and characterise the price as the smallest supermartingale above the payoff;
• formulate the continuous-time problem as a linear complementarity problem and a variational inequality;
• solve the perpetual American put in closed form, prove optimality by verification, and derive smooth fit as the condition for the best threshold;
• prove that an American call on a stock without dividends should never be exercised early;
• describe projected SOR and the binomial method for finite-expiry American options.

7.1The value of waiting

7.2Discrete time: the Snell envelope

Consider a binomial model with $N$ steps of length $\Delta t$: at each step the price is multiplied by $u$ or $d = 1/u$, and pricing uses the risk-neutral probability $q = \frac{e^{r\Delta t} - d}{u - d}$ of an up move, which makes the discounted price a martingale (6D.6 Black–Scholes). An American option with payoff $h_n = h(S_n)$ at step $n$ can be exercised at any step.

The recursion is the algorithm: at each node, compare the value of exercising now with the discounted expected value of continuing, and take the larger. John Cox, Stephen Ross and Mark Rubinstein (1979) introduced the binomial model with $u = e^{\sigma\sqrt{\Delta t}}$, under which the prices converge to the continuous-time prices as $\Delta t \to 0$ (statement; for American options this was proved by Amin and Khanna, and Lamberton, in the 1990s).

7.3Continuous time: a free boundary problem

In the Black–Scholes model, the price of an American option with payoff $h(S)$ (for the put, $h(S) = (K - S)^+$) is

the supremum over stopping times, with $dS = rS\,dt + \sigma S\,dW$ under $\mathbb{Q}$. Write $\mathcal L V = \partial_tV + rS\partial_SV + \frac12\sigma^2S^2\partial_{SS}V - rV$ for the Black–Scholes operator. The Snell envelope suggests three properties, the continuous versions of "dominates the payoff", "supermartingale" and "martingale until exercise":

This is a linear complementarity problem: at each point, one of the two inequalities is an equality. The continuation region is $\{V > h\}$, where $\mathcal LV = 0$ (the Black–Scholes equation holds); the exercise region is $\{V = h\}$, where $\mathcal Lh \leq 0$. For the put, the exercise region is $\{S \leq S^*(t)\}$ for an exercise boundary $S^*(t)$, which increases to $K$ as $t \to T$. Equivalently, (LCP) is a parabolic variational inequality: $V$ is the solution of the obstacle problem of 6C.1 Regularity of Minimisers and Constraints for the backward parabolic operator $\mathcal L$ with obstacle $h$.

There is no closed formula for finite $T$. But when $T = \infty$ the time derivative disappears and everything can be computed.

7.4The perpetual American put

For $T = \infty$ the value does not depend on $t$, and (LCP) becomes an ODE problem. In the continuation region $V$ solves

an Euler equation with solutions $S^p$ where $\frac12\sigma^2p(p - 1) + rp - r = 0$, that is, $(p - 1)(\frac12\sigma^2p + r) = 0$: $p = 1$ or $p = -\gamma$ with $\gamma = \frac{2r}{\sigma^2}$. A put is worth little when $S$ is large, so in the continuation region $\{S > b\}$ we take $V = AS^{-\gamma}$; in the exercise region $\{S \leq b\}$, $V = K - S$. Value matching at $b$ gives $A = (K - b)b^\gamma$. So every threshold $b \in (0, K)$ defines a candidate

which is the value of the strategy "exercise when $S$ first falls to $b$" (Exercise 7.6). The best threshold maximises $V_b(S)$ for every $S > b$, and $\frac{d}{db}\big[(K - b)b^\gamma\big] = 0$ gives

At this $b$, $V_b'(b^+) = -\gamma\frac{K - b}{b} = -1 = V_b'(b^-)$: smooth fit is exactly the condition that the threshold is optimal. A threshold that is too high gives a kink pointing down at $b$, one that is too low a kink pointing up.

With $K = 100$, $r = 0.05$ and $\sigma = 0.2$: $\gamma = 2.5$, $S^* = \frac{2.5}{3.5}\times100 \approx 71.43$, and at $S = 100$ the perpetual put is worth $28.57\times1.4^{-2.5} \approx 12.32$ (checked numerically). Exercise is optimal only after a fall of nearly $30\%$: early exercise sacrifices the chance that the price recovers, and is worth it only when the interest earned on the strike, $rK$ per unit time, outweighs that chance.

7.5American calls and dividends

The intuition: exercising a call early means paying the strike early (losing interest on it) and giving up the insurance against a fall that the option provides. If the stock pays dividends, the holder of the stock receives them and the holder of the call does not, and it can be optimal to exercise a call just before a large dividend. For puts, the interest earned on receiving $K$ early can outweigh the insurance value, which is why early exercise of puts is common.

7.6Numerical methods

For finite $T$ there is no formula, and American options are priced numerically.

Binomial and trinomial trees implement the Snell envelope directly (Example 7.2); they converge at rate about $\frac1N$, with oscillations.

Finite differences with projection. Discretise (LCP) in the log-price $x = \log S$ by an implicit or Crank–Nicolson scheme (6D.9 Finite Difference Methods). Each time step requires the solution of a discrete linear complementarity problem

with $A$ tridiagonal. Projected successive over-relaxation (PSOR), introduced by Colin Cryer in 1971, solves it by Gauss–Seidel sweeps in which each new component is projected onto the constraint, $v_i \leftarrow \max\big(h_i, v_i + \omega(\tilde v_i - v_i)\big)$, with $\tilde v_i$ the Gauss–Seidel value and $1 < \omega < 2$ a relaxation parameter. For symmetric positive definite $A$ it converges for $0 < \omega < 2$ (Cryer's theorem, statement); the Black–Scholes matrix is not symmetric, but it is an M-matrix (diagonally dominant with non-positive off-diagonal entries), for which projected Gauss–Seidel also converges. For the put, Michael Brennan and Eduardo Schwartz (1977) observed that a single sweep from the low-price end solves the discrete problem exactly, because the exercise region is an interval at the bottom (a fact later proved under precise conditions by Jaillet, Lamberton and Lapeyre).

Penalty methods replace the constraint by a large penalty: $\mathcal LV_\varepsilon + \frac1\varepsilon(h - V_\varepsilon)^+ = 0$, a semilinear equation whose solutions converge to $V$ as $\varepsilon \to 0$, exactly as in the penalty approach to the obstacle problem.

Monte Carlo methods for American options need an estimate of the continuation value at each simulated state; Francis Longstaff and Eduardo Schwartz (2001) estimated it by least-squares regression on functions of the current price, which made Monte Carlo practical for American options in many dimensions (6D.10 Monte Carlo, Fourier and Finite Element Methods).

7.7History

The theory of optimal stopping began with Abraham Wald's sequential analysis (1940s) and was developed by J. Laurie Snell (1952), whose envelope is the discrete solution. Henry McKean solved the perpetual American put (and related problems) in 1965, in an appendix to a paper of Paul Samuelson on warrant pricing. Brennan and Schwartz (1977) computed American put prices by finite differences, Cox, Ross and Rubinstein (1979) introduced the binomial tree, and Bensoussan and Lions developed the variational inequality theory in the 1970s and early 1980s. McDonald and Siegel's real options model dates from 1986, Dixit and Pindyck's book from 1994, and the Longstaff–Schwartz algorithm from 2001.

7.8Exercises

Solution

(a) By the Feynman–Kac argument of 6D.3 Stochastic Differential Equations and Feynman–Kac (applied to $e^{-rt}f(S_t)$ up to $\tau_b$), the function $f$ solves the Euler equation with these boundary values; the solutions are $AS + BS^{-\gamma}$, and $f \to 0$ forces $A = 0$, $f(b) = 1$ gives $B = b^\gamma$. (b) The payoff at $\tau_b$ is $K - b$, so the value is $(K - b)\mathbb{E}[e^{-r\tau_b}]$.

Solution

At the down node the European value is the continuation value $10.72$; at the up node $0$. At the root, $0.9753\times0.4461\times10.72 \approx 4.66$. The American value is $5.74$, a premium of about $1.07$. At the root, exercising pays $(100 - 100)^+ = 0$, less than the continuation value $5.74$, so the holder continues and exercises at the down node if it is reached.

Solution

$\gamma = \frac{0.1}{0.09} \approx 1.111$, $S^* = \frac{1.111}{2.111}\times100 \approx 52.63$, $V(100) = 47.37\times(100/52.63)^{-1.111} \approx 47.37\times0.4902 \approx 23.2$. Higher volatility makes waiting more valuable (a larger chance of a much lower price later), so the holder waits for a deeper fall, and the option is worth more ($23.2$ versus $12.3$).

Solution

(a) In the continuation region the value $F(P)$ solves $\frac12\sigma^2P^2F'' + (r - \delta)PF' - rF = 0$, with solutions $P^\beta$ for the two roots of the quadratic; $F(0) = 0$ selects the positive root $\beta > 1$ (the quadratic is $-\delta < 0$ at $\beta = 1$). Value matching $AP^{*\beta} = P^* - I$ and smooth fit $\beta AP^{*\beta - 1} = 1$ give $\beta(P^* - I) = P^*$, i.e. $P^* = \frac{\beta}{\beta - 1}I$. (b) $0.02\beta^2 - 0.01\beta - 0.05 = 0$ gives $\beta = \frac{0.01 + \sqrt{0.0041}}{0.04} \approx 1.851$ and $P^* \approx 2.18\,I$.

Solution

On $S < S^*$: $V = h$, and the operator gives $-rK \leq 0$. On $S > S^*$: the operator gives $0$ and $V > h$ (convexity above the tangent). At $S^*$ the product vanishes. If $b > S^*$, then $V_b'(b^+) = -\gamma\frac{K - b}{b} > -1 = V_b'(b^-)$: the slope jumps up at $b$, a convex kink, so $V_b''$ contains a positive multiple of $\delta_b$, the operator applied to $V_b$ is positive there, and $e^{-rt}V_b(S_t)$ is not a supermartingale. If $b < S^*$, then $V_b'(b^+) < -1$: just above $b$, $V_b$ starts at $K - b$ and decreases faster than $K - S$, so it falls below the payoff, violating $V_b \geq h$.

Solution

(a) Differentiate (BS) in $S$: $\Delta = \partial_Sv$ solves $\partial_t\Delta + (r + \sigma^2)S\partial_S\Delta + \frac12\sigma^2S^2\partial_{SS}\Delta = 0$ (the $r\Delta$ terms cancel). Differentiate again: $\partial_t\Gamma + (r + \sigma^2)\Gamma + (r + \sigma^2)S\partial_S\Gamma + \sigma^2S\partial_S\Gamma + \frac12\sigma^2S^2\partial_{SS}\Gamma = 0$. (b) This is a backward Kolmogorov equation with a "creation" term $+(r + \sigma^2)\Gamma$, so $\Gamma(t, S) = e^{(r + \sigma^2)(T - t)}\mathbb{E}[\Gamma(T, X_T)]$ for the diffusion with generator $(r + 2\sigma^2)S\partial_S + \frac12\sigma^2S^2\partial_{SS}$, and $\Gamma(T, \cdot) = h'' \geq 0$ (as a measure). (c) As stated.