Parallel Binomial Lattices for American Option Pricing
Summary
The document describes a question about extending a GPU-oriented parallel binomial option-pricing method from European options to American options. In a standard binomial lattice, an American option's value at each node is the greater of its immediate exercise value and its discounted continuation value. The cited parallel approach partitions the lattice, propagates prices between partition boundaries, and can fill partition interiors in parallel.
The central issue is that early exercise adds a decision at every node, while the paper's accelerated boundary relation is described as if it can skip intermediate steps. The post asks whether that relation must change and how exercise decisions fit into the partitioned computation, but it provides no answer or performance evidence. It is useful as a framing of the computational challenge, while leaving the actual recurrence, boundary handling, and correctness conditions unresolved.
Key ideas
- An American option's node value accounts for both immediate exercise and continuation.
- The described parallel method partitions the lattice and propagates values across partition boundaries.
- Early-exercise checks at intermediate nodes complicate skipping calculations between boundaries.
- The document poses the implementation question but does not provide a resolution.
Tags
Full text
# Modifying a parallel binomial option pricing algorithm to work for American-style options? # Modifying a parallel binomial option pricing algorithm to work for American-style options? I am writing about GPU-accelerated option pricing algorithms for a Bachelor's thesis, and have found this paper: https://www.ccrc.wustl.edu/~roger/papers/gcb09.pdf I do understand the outline of this algorithm for European-style options, where no early-exercise is possible. But for American-style options where this is a possibility, the standard sequential binomial model calculates the value of the option at the current node as a maximum of either the discounted continuation value of holding it to the next period (so just like for a European option) or the value of exercising it immediately on the spot (i.e. the difference of the current asset price and the specified strike price). This algorithm uses a recursive formula to establish relative option prices between nodes over several time-steps. This is then utilized by splitting the entire lattice into partitions, calculating relative option prices between every partition boundary, and finally, propagating the option values over these partitions from the terminal nodes back to the initial node. This allows us to skip many intermediate calculations. The paper then states that "Now, the option prices could be propagated from one boundary to the next, starting from the last with the dependency relation just established, with a stride of T /p time steps until we reach the first partition, which bears the option price at the current moment, thus achieving a speed-up of p, as shown in figure (3). Now, with the knowledge of the option prices at each boundary, the values in the interior nodes could be filled in parallel for all the partitions, if needed(as in American options)." I feel like this is quite vague, and I don't really get how to modify this to work with American options. I feel like the main recursive equation must be changed to incorporate the early-exercise possibility at every step, and I am not convinced that we have such a simple equation for relating option prices across several time steps like before. Could someone explain the gaps in my knowledge here, or shed some light on how exactly you tailor this to work for American options? Thanks!
Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.