In this article we propose a novel approach to reduce the computational
complexity of the dual method for pricing American options.
We consider a sequence of martingales that converges to a given
target martingale and decompose the original dual representation into a sum of
representations that correspond to different levels of approximation to the
target martingale. By next replacing in each representation true conditional expectations with their
Monte Carlo estimates, we arrive at what one may call a multilevel dual Monte
Carlo algorithm. The analysis of this algorithm reveals that the computational
complexity of getting the corresponding target upper bound, due to the target martingale,
can be significantly reduced. In particular, it turns out that using our new
approach, we may construct a multilevel version of the well-known nested Monte
Carlo algorithm of Andersen and Broadie (2004) that is, regarding complexity, virtually
equivalent to a non-nested algorithm. The performance of this multilevel
algorithm is illustrated by a numerical example. (joint work with Denis Belomestny)