Methods for Evaluating Multi-level Decision Trees in Imprecise Domains

All Papers

Over the years numerous decision analytical models based on interval estimates of probabilities and utilities have been developed, and a few of these models have also been implemented into software. However, only one software, the Delta approach, are capable of handling probabilities, values and weights simultaneously, and also allow for comparative relations, which are very useful where the information quantity is limited. A major disadvantage with this method is that it only allows for single-level decision trees and cannot non-trivially be extended to handle multi-level decision trees. This paper generalizes the Delta approach into a method for handling multi-level decision trees. The straight-forward way of doing this is by using a multi-linear solver; however, this is very demanding from a computational point of view. The proposed solutions are instead to either recursively collapse the multi-level decision tree into a single-level tree or, preferably, use backward induction, thus mapping it to a bilinear problem. This can be solved by LP-based algorithms, which facilitate reasonable computational effort.