The decision tree polytope and its application to sequential decision problems

This paper describes a new mathematical programming approach to sequential decision problems that have an underlying decision tree structure. The approach, based upon a characterization of strategies as extreme points of a 0–1 polytope called the ‘decision tree polytope’, is particularly suited to the direct examination of risk–return and other tradeoffs amongst strategies. However, it can also be used for conventional utility maximization if a utility function is available. Further, the approach requires no algorithmic development – it can be implemented using commercially available algebraic modeling software and can solve large problems. A related, and already known, approach can be used for some more general Markov decision problems.