Decision Tree Calculation Algorithm

Q: How are the values displayed decision trees calculated?

A: The following algorithm is used:

1. Expand all reference nodes (internal and external).
2. Enumerate all the possible paths through the tree.
3. For each path calculate the end value associate with this path.

   Cumulative Trees: The end value is the sum of all the branch values on that path. If a payoff function is specified for any of the nodes, this is applied to the branch before the summation.

   Formula Trees: The end value is calculated by evaluating either the default formula specified at the tree root or the custom formula specified at the end node.

   Linked Trees: Walking through the tree along the path, from left to right, substitute each branch value into the cell specified as the linked cell for the parent node (i.e. the node which the branches originate from). The old contents of the cells which are replaced by these branch values are stored internally so they can be restored at the end of the calculation. When an end node is reached, the spreadsheet is recalculated, and the end value for that particular node is taken from the cell specified for the end node. Notice, if two branch values along a path are sent to the same cell, the first one is overwritten by the second, and thus the first value will have no effect.

4. If a utility function was specified, convert each of the end values into their corresponding utility.
5. Now "Rollback" the tree by following these steps
   1. For each node which only has end nodes as successors, determine the expected value (or expected utility) by

      Chance Nodes: Take the average of the end values weighted by their corresponding probabilities.

      Decision Nodes: Use the value of the optimal branch (maximum or minimum). Ties are always broken by selecting the topmost branch.

      Logic Nodes: Use the expected value of the path specified as "TRUE" by the branch logic statements. If no branches are "TRUE", an error value is returned. If more than one logic statement evaluates to "TRUE", then the expected value is the average of all the branches that are "TRUE" (in other words, the logic node is treated like a Chance Node with probabilities equally distributed among all the branches that evaluate to "TRUE").

   2. The value (or utility) calculated in A) is displayed next to the node. The optimal branch chosen for any Decision Nodes is indicated by a "TRUE" or "FALSE" statement next to the branches.
   3. Once all such nodes have been resolved, conceptually convert the calculated nodes into end nodes, with end values (or utilities) equal to the values determined in A).
   4. Repeat Step A) until there is only a single end node left in the tree.

6. If a utility function is used and the output display is set to "Certainty Equivalent", the expected utilities are mapped back into "value units" before being displayed by using the inverse utility function.
7. For each path, determine the end probabilities by multiplying all the probabilities of each branch along that path. If a branch emanated from a decision or logic branch which was not taken, the probability is zero.