A state-space partitioning method for pricing high-dimensional American-style options

The pricing of American-style options by simulation-based methods is an important but difficult task primarily due to the feature of early exercise, particularly for high-dimensional derivatives. In this paper, a bundling method based on quasi-Monte Carlo sequences is proposed to price high-dimensional American-style options. The proposed method substantially extends Tilley's bundling algorithm to higher-dimensional situations. By using low-discrepancy points, this approach partitions the state space and forms bundles. A dynamic programming algorithm is then applied to the bundles to estimate the continuation value of an American-style option. A convergence proof of the algorithm is provided. A variety of examples with up to 15 dimensions are investigated numerically and the algorithm is able to produce computationally efficient results with good accuracy