Decision Trees & Rollback — Decision trees and rollback...

SECTION 1

Historical Context & Motivation

Making decisions is an inescapable feature of human activity, yet for most of history the process remained largely intuitive and unsystematic. Whether a merchant in Renaissance Florence weighed the risks of financing a sea voyage or a general contemplated alternative battle plans, the reasoning was informal—guided by experience, gut feeling, and heuristic rules of thumb. The modern field of decision analysis arose from the recognition that sequential decisions made under uncertainty could be modeled mathematically, enabling a rigorous comparison of alternatives even when outcomes depend on chance events that have not yet occurred.

The intellectual roots of decision trees reach back to the development of probability theory in the seventeenth century and the formalization of expected value by Blaise Pascal and Pierre de Fermat. However, it was not until the mid-twentieth century that researchers in operations research and management science crystallized these ideas into graphical tools capable of representing entire sequences of decisions and chance events. The timeline below highlights the key milestones that transformed ad hoc reasoning into a structured discipline.

1654

Pascal–Fermat Correspondence

Blaise Pascal and Pierre de Fermat exchanged letters on the Problem of Points, establishing the concept of mathematical expectation—the intellectual ancestor of expected monetary value used in rollback analysis.

1944

Von Neumann & Morgenstern — Game Theory

John von Neumann and Oskar Morgenstern published Theory of Games and Economic Behavior, formalizing strategic decision-making under uncertainty and introducing extensive-form (tree) representations of games.

1964

Howard Raiffa — Decision Analysis

Howard Raiffa's foundational work, including the textbook co-authored with Robert Schlaifer, established decision trees as a standard graphical tool and formalized backward induction (rollback) as the canonical solution method.

1968

Howard's "Decision Analysis" Paper

Ronald A. Howard coined the term decision analysis in a seminal paper, framing the discipline as a prescriptive methodology for choosing among uncertain alternatives using probability, utility theory, and tree-based reasoning.

1980s–Present

Software & Industry Adoption

Decision-tree software (PrecisionTree, TreeAge, and others) brought rollback analysis into everyday business, healthcare, and engineering practice, enabling sensitivity analysis and Monte Carlo simulation on top of the classical tree framework.

The central question this lesson addresses is deceptively simple: When you face a sequence of decisions interleaved with uncertain events, how do you choose the best first move? Decision trees give us a way to lay out every possible path, and rollback analysis (also called backward induction or folding back the tree) provides the algorithmic procedure for evaluating each path and selecting the optimal strategy.

SECTION 2

Core Principles & Definitions

Before constructing a decision tree, it is essential to understand the building blocks from which every tree is assembled. A decision tree is a directed acyclic graph that reads left to right (or top to bottom), with three fundamental types of nodes connected by branches that represent either choices or outcomes. The entire framework rests on the assumption that the decision-maker is rational and seeks to maximize (or minimize) some well-defined objective—most commonly the expected monetary value (EMV) of the strategy.

Decision Node (□)

Represented by a square. The decision-maker controls which branch to follow. Each branch from a decision node corresponds to a distinct alternative or action available at that stage.

Chance Node (○)

Represented by a circle. Nature (chance) determines which branch is taken. Each branch carries a probability, and the probabilities leaving any single chance node must sum to 1.

Terminal Node (△)

Represented by a triangle (or simply a line). This is the end of a path through the tree. Each terminal node carries a payoff value—the net gain or loss if that particular sequence of decisions and events occurs.

Expected Monetary Value (EMV)

The weighted average of payoffs at a chance node, where the weights are the branch probabilities. At a decision node, the EMV equals the best (maximum or minimum) EMV among its branches.

Rollback (Backward Induction)

The procedure of solving a tree from right to left: first calculate EMVs at the rightmost chance nodes, then choose optimal branches at decision nodes, propagating values leftward until the root node receives a single EMV that represents the value of the optimal strategy.

✦ KEY TAKEAWAY

Think of a decision tree as a road map for a cross-country trip with unpredictable weather. At every fork in the road you choose which highway to take (decision node), but the weather that greets you on that highway is up to nature (chance node). Rollback is the act of checking the weather forecasts at each future fork before you leave home, then planning your route so that—on average—you arrive with the shortest travel time, regardless of which weather scenario materializes.

SECTION 3

Anatomy of a Decision Tree

The diagram below illustrates a canonical decision tree for a business scenario: a company must choose between launching a new product or staying with its current product line. If it launches, the market reaction is uncertain—demand could be high or low. Each combination of decision and chance outcome terminates at a payoff. Study the node shapes, probability labels, and payoff placements before moving on to the mathematical framework.

A simple decision tree with one decision node (square), one chance node (circle), and three terminal nodes (triangles). Probabilities on the chance branches sum to 1.0. Payoffs appear at the endpoints.

Notice several structural conventions. First, the tree reads from left to right: the root node at the far left is the first decision you face, and the terminal payoffs at the far right are the final consequences. Second, the branches emerging from the chance node are labeled with both a descriptive event name and a numerical probability; these probabilities must satisfy the axiom Σ P(event) = 1 for every chance node. Third, the payoffs at terminal nodes should represent the same quantity (e.g., net profit) measured in the same units across all endpoints, so comparisons remain valid. With this visual scaffolding in place, we are ready to formalize the mathematics of rollback.

SECTION 4

Mathematical Framework — EMV & Rollback

Rollback analysis is algorithmically straightforward: you begin at the terminal nodes (the rightmost layer of the tree) and work backward, layer by layer, until you reach the root. At each node you encounter along the way, you apply one of two rules depending on the node type. The mathematical foundation is the concept of expected monetary value, which extends the classical notion of expected value from probability theory to the context of sequential decision-making.

EXPECTED MONETARY VALUE AT A CHANCE NODE

EMV = Σᵢ Pᵢ × Vᵢ

where Pᵢ is the probability of the i-th outcome, and Vᵢ is the payoff (or propagated EMV) associated with that branch. The sum runs over all branches leaving the chance node.

OPTIMAL VALUE AT A DECISION NODE

V* = max { EMV(branch₁), EMV(branch₂), … , EMV(branchₖ) }

The decision-maker selects the branch with the highest EMV (if maximizing profit) or the lowest EMV (if minimizing cost). The chosen branch's EMV becomes the value assigned to that decision node.

Rollback Algorithm — Step by Step

Step 1 — Identify terminal nodes. Record the payoff at each endpoint of the tree.
Step 2 — Evaluate the rightmost chance nodes. Compute the EMV at each using the formula above and write it next to the node.
Step 3 — Evaluate the rightmost decision nodes. Choose the branch with the optimal (max or min) EMV. Mark the rejected branches with a double strike-through (‖) to indicate they are pruned.
Step 4 — Repeat. Move one layer to the left and apply Steps 2–3 again, using propagated EMVs from the layer you just solved.
Step 5 — Read the root. The value at the root node is the EMV of the optimal strategy. Trace the unpruned branches from root to terminals to identify the optimal policy.

💡 Why Backward, Not Forward?

Working forward would require evaluating every possible combination of decisions and events simultaneously—an exponential explosion. Rollback exploits the principle of optimality of subproblems: the optimal strategy from any node onward is independent of how you arrived at that node. This is the same principle underlying dynamic programming, and it reduces the computation from exponential to linear in the number of nodes.

SECTION 5

Rollback Illustrated — Solving the Tree

To make the rollback procedure concrete, let us return to the product launch tree from Section 3 and solve it step by step. The diagram below reproduces the tree with the computed EMVs and pruning marks overlaid so you can see exactly how values propagate from right to left.

The solved decision tree. The chance node receives an EMV of $260,000 computed as 0.6 × $500,000 + 0.4 × (−$100,000). The decision node compares $260,000 (Launch) with $150,000 (Stay) and selects Launch. The pruned Stay branch is shown with a dashed line and X marks.

The rollback proceeded in exactly two passes. In the first pass (Step 2), we computed the EMV at the chance node: 0.6 × $500,000 + 0.4 × (−$100,000) = $300,000 − $40,000 = $260,000. In the second pass (Step 3), we arrived at the decision node, compared the Launch path ($260,000) with the Stay path ($150,000), and selected Launch because $260,000 > $150,000. The EMV of $260,000 is therefore the value of the optimal strategy—it is the expected payoff if the decision-maker follows the optimal policy. It is crucial to note that $260,000 is not a guaranteed outcome; in reality, the firm will earn either $500,000 or −$100,000. The EMV represents the long-run average if this decision were repeated many times under identical conditions.

SECTION 6

Worked Example — Investment Decision

Consider a more involved scenario. An investor has $200,000 and must decide between three options: (A) invest in a startup, (B) invest in a mutual fund, or (C) keep the money in a savings account. If the startup is chosen, there is a 0.3 probability of a booming market (payoff $800,000), a 0.5 probability of a stable market (payoff $250,000), and a 0.2 probability of a bust (payoff $20,000). The mutual fund yields $350,000 with probability 0.6 and $180,000 with probability 0.4. The savings account guarantees $210,000. Which option maximizes EMV?

Investment Decision — Rollback Solution

Step 1 — Draw the Tree and Record PayoffsThe root is a decision node with three branches: Startup, Mutual Fund, and Savings. The Startup branch leads to a chance node with three outcomes (Boom, Stable, Bust). The Mutual Fund branch leads to a chance node with two outcomes (Good, Poor). The Savings branch leads directly to a terminal node with payoff $210,000.

Step 2 — EMV at the Startup Chance NodeApply the EMV formula: EMV(Startup) = 0.3 × $800,000 + 0.5 × $250,000 + 0.2 × $20,000 = $240,000 + $125,000 + $4,000.

EMV(Startup) = $369,000

Step 3 — EMV at the Mutual Fund Chance NodeEMV(Mutual Fund) = 0.6 × $350,000 + 0.4 × $180,000 = $210,000 + $72,000.

EMV(Mutual Fund) = $282,000

Step 4 — EMV at the Savings TerminalSince there is no uncertainty, the EMV of the savings option is simply its guaranteed payoff.

EMV(Savings) = $210,000

Step 5 — Decision Node — Select the Optimal BranchCompare the three EMVs at the root decision node: Startup ($369,000), Mutual Fund ($282,000), Savings ($210,000). Since $369,000 is the maximum, the optimal decision is to invest in the startup. The Mutual Fund and Savings branches are pruned.

Optimal strategy: Invest in Startup with EMV = $369,000

⚠️ Risk vs. EMV

Although the startup maximizes EMV, notice it also carries the widest spread of outcomes—from $800,000 to $20,000. A risk-averse investor might prefer the mutual fund or even the savings account despite lower EMVs. Decision trees using EMV assume risk neutrality. To incorporate risk preferences, one replaces monetary payoffs with utility values and maximizes expected utility instead—a topic for a more advanced lesson.

SECTION 7

Strengths & Limitations of Decision Trees

Like any analytical tool, decision trees come with a set of advantages that make them indispensable in certain contexts and a corresponding set of limitations that the practitioner must acknowledge. The table below offers a structured comparison.

Strengths and limitations of decision-tree rollback analysis

Dimension	Strength	Limitation
Clarity	Visual layout makes the logical structure of a problem transparent; all assumptions (probabilities, payoffs, alternatives) are explicit.	Large problems (many stages, many outcomes) produce trees that are impractically wide; clarity deteriorates with complexity.
Optimality	Rollback guarantees the strategy with the highest EMV (or expected utility), given correct inputs.	Optimal in the EMV sense only; does not account for risk aversion unless utilities replace payoffs.
Flexibility	Can model any finite sequence of decisions and chance events; supports multi-stage problems naturally.	Continuous random variables must be discretized; the tree cannot represent infinite or continuous state spaces directly.
Data Sensitivity	Easy to perform sensitivity analysis by varying probabilities or payoffs and re-running rollback.	Garbage in, garbage out: the tree's output quality is only as good as the probability and payoff estimates.
Communication	Excellent for explaining decisions to stakeholders who may not have a mathematical background.	The EMV criterion may not match a stakeholder's intuitive risk preferences, leading to misaligned expectations.

🔍 PUTTING IT IN PERSPECTIVE

Decision trees occupy a middle ground in the analyst's toolkit: more structured than a pros-and-cons list, less computationally demanding than full-scale simulation or Markov decision processes. Think of a decision tree as the architect's blueprint—it captures the essential structure of the decision problem. For routine decisions with well-understood probabilities, the blueprint is all you need. For complex, high-stakes problems, the blueprint is the starting point upon which sensitivity analysis, Monte Carlo simulation, and utility theory are layered.

SECTION 8

Connections to Advanced Decision Theory

The introductory rollback analysis presented here forms the foundation upon which several advanced techniques are built. Understanding where the basic model ends and the extensions begin helps you position this material within the broader landscape of decision science.

Basic decision trees vs. advanced extensions

Feature	Basic Decision Trees (This Lesson)	Advanced Extensions
Objective	Maximize EMV (risk-neutral criterion)	Maximize expected utility (EU), incorporating risk aversion via a utility function u(x)
Probabilities	Fixed, known values assigned to branches	Updated via Bayes' theorem as new information arrives (Bayesian decision analysis)
Information	No option to acquire additional data	Value of information (VOI) analysis quantifies what the decision-maker should pay for perfect or imperfect information
State Space	Finite, discrete outcomes	Influence diagrams and Markov decision processes (MDPs) handle continuous states and infinite horizons
Multiple Agents	Single decision-maker vs. nature	Game trees and mechanism design extend the framework to strategic interactions with rational opponents

In subsequent lessons you will encounter Bayesian revision of probabilities within a decision tree, the computation of the Expected Value of Perfect Information (EVPI), and multi-stage trees where the decision-maker can purchase a market survey or run a clinical trial before committing to the main decision. All of these extensions rely on the same rollback algorithm you learned here—they simply enrich the tree with additional nodes and more nuanced probability assignments.

SECTION 9

Practice Problems

PROBLEM 1 — CONCEPTUAL

Explain the difference between a decision node and a chance node. Why is it important that probabilities at every chance node sum to 1? What would go wrong in the rollback calculation if they did not?

PROBLEM 2 — BASIC CALCULATION

A farmer must decide between planting corn or soybeans. If corn is planted, there is a 0.4 probability of a wet season (profit $80,000) and a 0.6 probability of a dry season (profit $30,000). If soybeans are planted, the wet season yields $60,000 and the dry season yields $50,000 (same probabilities). Using EMV, which crop should the farmer plant?

PROBLEM 3 — INTERMEDIATE

A tech company must decide whether to develop a product in-house or outsource it. If developed in-house, there is a 0.5 chance of on-time completion (net benefit $400,000) and a 0.5 chance of delay (net benefit $100,000). If outsourced, the product is completed on time with probability 0.8 (net benefit $300,000) and delayed with probability 0.2 (net benefit $50,000). However, if the company chooses in-house and completes on time, it then faces a second decision: spend $50,000 on enhanced marketing (which boosts the benefit to $500,000 with probability 0.7 and has no effect with probability 0.3) or skip enhanced marketing and keep the $400,000. Draw the tree and find the optimal strategy using rollback.

PROBLEM 4 — APPLIED

A hospital administrator must choose one of two diagnostic protocols for a rare condition. Protocol A costs $2,000 per patient and correctly identifies the condition 90% of the time, leading to proper treatment (net patient outcome valued at $50,000). If Protocol A misdiagnoses (10%), the patient receives delayed treatment (outcome $15,000). Protocol B costs $800 per patient, identifies correctly 70% of the time (outcome $50,000), and misdiagnoses 30% of the time (outcome $15,000). Using EMV (where value = outcome − cost), which protocol should the administrator select? What is the EMV of the chosen protocol?

PROBLEM 5 — CRITICAL THINKING

Suppose a decision tree has been solved via rollback and the optimal strategy has an EMV of $200,000. A critic points out that none of the terminal payoffs in the tree equals $200,000—the actual outcomes are $500,000, $150,000, and −$50,000. Does this invalidate the analysis? Construct a rigorous argument for or against the use of EMV as a decision criterion when the expected value itself is an outcome that can never actually occur. Under what conditions might an alternative criterion be more appropriate?

SUMMARY

Lesson Summary

A decision tree is a graphical representation of a sequential decision problem composed of three node types: decision nodes (squares) where the decision-maker chooses, chance nodes (circles) where nature determines the outcome according to specified probabilities, and terminal nodes (triangles) where payoffs are recorded. The probabilities on branches leaving any chance node must sum to 1, and all payoffs must be measured in the same units to ensure valid comparisons.

Rollback analysis (backward induction) solves the tree from right to left. At each chance node, compute the expected monetary value (EMV) as EMV = Σ Pᵢ × Vᵢ. At each decision node, select the branch with the highest (or lowest) EMV and prune the rest. The EMV at the root represents the value of the optimal strategy. While this approach assumes risk neutrality, it provides the essential scaffolding upon which Bayesian updating, value-of-information analysis, and expected utility maximization are later built.