Computational complexity of pricing derivatives

Abstract

(Braverman and Pasricha 2014) prove in their paper “The computational hardness of pricing compound options” that pricing a multi-layered option on a single security is in general PSPACE-complete even when the underlying has computationally tractable behaviour. They also prove that, if one uses a Monte Carlo oracle to sample possible futures, then the number of samples required to price the derivative within of its true value is exponential in the depth of derivative layering. In this study, we show that, if there is an upper bound on all possible payoffs of the derivative and if there is an upper bound on the maximum sensitivity of the derivative to the price of the underlying asset (“delta of the derivative”), then with high probability the number of samples required to price the derivative within of its true value is polynomial in the values of the bounds, independent of the depth of derivative layering.