Definition:Decision Tree
Definition
A decision tree is a form of tree diagram which can be used to determine the optimum move when there are alternative strategies with uncertain outcomes.
To determine the maximum expected gain, the expected gain is calculated at each random node, and is conventionally written inside or below each such node.
Decision Node
A decision node in a decision tree is a node representing a decision which the player has control over.
It is denoted on the decision tree by a square.
Random Node
A random node in a decision tree is a node representing a consequence over which the player has no control over, but is the result of a random process.
It is denoted on the decision tree by a circle.
Terminal Node
A terminal node in a decision tree is a node representing the outcome of the path taken.
It is denoted on the decision tree by a vertical line segment.
Examples
Arbitrary Example
Consider the case of a builder who is allowed to tender for only one of two contracts.
If he tenders for contract $A$, there is a $70 \%$ probability of winning the contract, and thereby making a profit of $\$10\,000$.
If he tenders for contract $B$, there is only a $20 \%$ probability of winning the contract, but his profit will be $\$30\,000$.
If he fails to win either contract, he will do other work instead and make a profit of $\$5000$.
The decision tree for making the decision as to which contract to bid for is shown here:
Here, the expected gains for contracts $A$ and $B$ are calculated as follows:
- For contract $A$: $\$10\,000 \times 0.7 + \$5000 \times 0.3 = \$8500$
- For contract $B$: $\$30\,000 \times 0.2 + \$5000 \times 0.8 = \$10\,000$
Hence, for a maximum expected gain, the builder should tender for contract $B$.
Also see
- Results about decision trees can be found here.
Sources
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): decision tree
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): decision tree