A New Pruning Method for Solving Decision Trees and Game Trees
This work addresses efficiency issues in decision-making and game theory applications, but it appears incremental as it builds on existing pruning techniques with a variant tree representation.
The paper tackles the problem of solving decision and game trees by introducing a new pruning method that uses scenario trees, which require joint probabilities for paths rather than conditional probabilities at chance nodes, resulting in improved efficiency over the traditional rollback method for problems involving Bayesian revision and game trees.
The main goal of this paper is to describe a new pruning method for solving decision trees and game trees. The pruning method for decision trees suggests a slight variant of decision trees that we call scenario trees. In scenario trees, we do not need a conditional probability for each edge emanating from a chance node. Instead, we require a joint probability for each path from the root node to a leaf node. We compare the pruning method to the traditional rollback method for decision trees and game trees. For problems that require Bayesian revision of probabilities, a scenario tree representation with the pruning method is more efficient than a decision tree representation with the rollback method. For game trees, the pruning method is more efficient than the rollback method.