Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 69

Decision Tree Analysis: The Rollback Method

Recommended resources

Hello! Welcome back.

In our last lesson, we carefully dissected the "anatomy" of a decision tree, identifying its core components: decision nodes for choices, chance nodes for uncertainties, and payoffs for outcomes. We built the map; now it's time to find the best route.

Today, we will learn how to analyze a decision tree by applying the rollback procedure to determine the optimal decision path. This is the method that transforms the tree from a simple diagram of possibilities into a powerful tool for making the best strategic choice under uncertainty. You'll learn the algorithm for "solving" the tree, which will enable you to recommend a course of action with a clear, quantitative justification.

1. The Rollback Procedure: An Overview

The core idea of solving a decision tree is to work backward, from the final outcomes on the right to the initial decision on the left. This process is often called the rollback procedure or backward induction.

The logic is simple: to make the best choice today (at the start of the tree), you first need to know the value of each possible future position you could be in. We determine these future values by "rolling back" the payoffs from the end of the tree.

Let's watch a very short video that demonstrates this process in action.

Decision Analysis 3: Decision Trees

The video 'Decision Analysis 3: Decision Trees' from the Joshua Emmanuel channel provides a quick and clear demonstration of the rollback or 'folding back' process.

Please watch the segment from 01:53 to 03:08. Notice how the presenter calculates a value for each chance node and then uses those values to make a final decision.

This video introduces the two fundamental rules of the rollback procedure, which depend on the type of node you are evaluating.

2. The Two Rules of Rolling Back

The rollback procedure is essentially an algorithm with two rules, applied recursively from the end of the tree to the beginning.

  1. At a Chance Node (◯): Calculate the Expected Value.
    The value of a chance node is the Expected Monetary Value (EMV) of its outcomes. You calculate this by taking a probability-weighted average of the values of all branches emerging from that node.

    You are, in essence, calculating the average outcome you can expect from that point of uncertainty.

  2. At a Decision Node (☐): Choose the Best Alternative.
    The value of a decision node is simply the value of the best single branch emerging from it. You compare the values of all available alternatives and select the one that best meets your objective:

    • If the values represent profits or benefits, you choose the branch with the maximum value.
    • If the values represent costs, you choose the branch with the minimum value.

The branches that are not chosen at a decision node are "pruned" from the tree, visually indicated by drawing parallel lines (//) across them.

3. A Step-by-Step Walkthrough: The DriveTek Problem

Let's apply this algorithm to the DriveTek problem we introduced in the previous lesson. The following reading provides a detailed, step-by-step calculation of the rollback procedure. Given your background in software engineering, you can think of this as executing a recursive algorithm on a tree data structure.

Introduction to Decision Trees

Let's return to the 'Introduction to Decision Trees' PDF. This section is the core of today's lesson, as it meticulously demonstrates the rollback algorithm from start to finish.

Please read Section 14.4 ROLLBACK METHOD very carefully. It starts on page 161. Pay close attention to the two rules for determining rollback values (one for event nodes, one for decision nodes). Follow the calculations in Figures 14.8 through 14.12 as they work backward through the tree. Finally, read the short 'Optimal Strategy' section to see how to state the final decision path once the rollback is complete.

The completed analysis reveals not just a single number, but a full decision policy.

TreePlan Decision Tree Rollback With Probability-Weighted Values
The DriveTek decision tree with all rollback values computed. The optimal path is highlighted by following the branches with the highest value at each decision node.

As the analysis shows, the optimal strategy for DriveTek is:

  1. Decision 1: Choose to "Prepare proposal" (since its EMV of $20,000 is greater than $0 for not preparing one).
  2. Decision 2 (if contract is awarded): Choose to "Try electronic method" (since its EMV of $90,000 is the maximum of the three available options).

The overall expected value of pursuing this optimal strategy is $20,000.

Test your understanding!

Let's look at a different type of problem: cost minimization. The video below analyzes a scenario where a project manager must choose between renting a small or large crane. The goal is to choose the crane that results in the lowest expected total cost.

Decision Trees for Risk Management

The video 'Decision Trees for Risk Management' from PatJHeffernan presents an excellent practical example of using decision trees for cost minimization.

Watch the segment from 05:19 to 07:15. The presenter calculates the expected monetary value for each branch and then rolls back the values to make a final decision.

Based on the video's analysis:

  1. What is the final expected cost associated with choosing the small crane?
  2. What is the final expected cost associated with choosing the large crane?
  3. Why is the "small crane" the optimal choice in this case?
Show answer
  1. The expected cost for the small crane is $17,650.
  2. The expected cost for the large crane is $18,650.
  3. The small crane is the optimal choice because this is a cost minimization problem. At the initial decision node, we choose the alternative with the lowest expected value. Since $17,650 is less than $18,650, choosing the small crane is the optimal decision.

Conclusion

Today you've mastered the core analytical technique for decision trees. By methodically applying the rollback procedure, you can navigate complex scenarios involving both choice and uncertainty to arrive at a logically sound, optimal strategy.

  • Key Takeaways:
    • The rollback procedure (or backward induction) is an algorithm for solving a decision tree by working from the final payoffs back to the initial decision.
    • At chance nodes (◯), you calculate the Expected Monetary Value (EMV) by taking a probability-weighted average of the outcomes.
    • At decision nodes (☐), you select the single best alternative—the one with the maximum value for profits or the minimum value for costs.
    • The final output is an optimal policy that specifies the best choice to make at every decision point you might encounter.

Preview of the Next Lesson

You now have the complete toolkit for decision tree analysis: you know how to build a tree from a problem description and how to solve it using the rollback procedure. In our next lesson, we will put it all together to apply decision tree analysis to a technology investment problem with uncertain outcomes. This will be a case study that directly mirrors the kinds of strategic decisions you face in the software and technology industries.