Polynomial algorithms for pricing path-dependent interest rate instruments

In this paper we study algorithms for pricing of interest rate instruments using recombining
tree (scenario lattice) interest models. The price is defined as expected discounted cash flow. If the
cash-flow generated by the instrument depends on the full or partial history of interest rates (pathdependent
contracts), then pricing algorithms are typically of exponential complexity. We show that
for some models, including product form cash-flows, additive cash-flows, delayed cash-flows and
limited path-dependent cash-flows, polynomial pricing algorithms exist