Introduction to Decision Trees

Introduction to Decision Trees, Page 1 of 8

Back

Introduction to Decision Trees

Q:What is the biggest weakness of payoff tables?

A:That they deal with only one decision at a time.

D:Please note that I did not say “one decision alternative at a time.” A decision, as you now know, involves a set of alternatives, from which you select one.

Q:Why is that a weakness?

A:Few decision situations stand apart from everything else.

D:It should be easy for you to see that any present decision depends on choices made in the past, so you can extrapolate from that and realize that any decision you must make now will affect the choices you face in the future. Therefore, we need a tool that will let us show those linkages.

Q:Does that mean payoff tables are worthless?

A:No, just limited.

D:Remember that you really don’t know what is going to happen in the future. That means that it is good, when you start thinking about a decision, to consider how it affects the alternatives you will face later on, but when it comes time to make the decision, a payoff table is your most powerful tool.

Q:What tool looks at more than one decision situation?

A:A decision tree.

Q:How do we start using a decision tree?

A:First you need to know the parts of a decision tree.

D:A decision tree is a type of graph, or flowchart, but it has a very limited set of symbols and is very specific as to the types of situations it can represent. The only symbols used are shown in Figure 1:

Figure 1: Symbols for a Decision Tree

These symbols are given very abstruse names; they are called a square, a circle, and an arrow. The first two symbols (square and circle) are also called nodes, and they serve as road signs.

Q:What is the purpose of a road sign?

A:To tell you what is coming up.

D:When you are driving down a road and see a road sign, it tells you what to expect, an exit or a rest stop, or construction, or whatever.

When my wife and I visited England, we took a ferry over to Ireland. We were late getting to the ferry, so we were about the last on, which made us the first off. As the ferry got in about midnight, this meant we had a couple of hundred very tired Irish folk who wanted to get home, and me in front, blocking their way. I just wanted to get out of their way, let them get past, and then find our hotel. I drove down the ramp, came to a stop sign, and looked left and right. To the left I saw the sign shown in Figure 2:

Figure 2: Irish Road Sign

Apparently they have a lot of experience dealing with tourists. Knowing what was coming up to the left, I very easily decided to turn right, found a parking spot, waited for everyone to pass me, and then took my wife on a tour of the slums of Dublin (she says I could get lost in a phone booth).

The two symbols (nodes) we will use will function in exactly the same way. The way you interpret the road signs is:

the next thing you see will be a set of decision alternatives

the next thing you see will be a set of states-of-nature

We need the two different symbols because we use the same symbol for both decision alternatives and states-of-nature: the arrow.

Q:Why do you use an arrow to show both the decision alternatives and the states-of-nature?

A:The most important thing a decision tree shows is the sequence in which things happen.

D:You may have seen a thing called an “influence diagram” at some point. If not, it a collection of symbols, almost any shape will do, connected by a spider’s web of arrows going all over the place, back and forth from each shape in no particular pattern or order. A decision tree, while somewhat the same, has a much more defined order. A tree is read from left to right, so whatever is furthest to the left comes first, and any node to the left of another node precedes that other node.

Q:What’s a decision tree problem look like?

A:Like this:

D:The following example is adapted from some class notes of mine, which undoubtedly means it was taken from a textbook somewhere, but I have no idea where, so consider this sufficient attribution and thanks to that nameless author.

A company is faced with a good problem: demand for their product has been growing and has now outpaced their production capacity. With further growth in demand anticipated for next year, the company must find some way to expand capacity or risk losing customers when demand cannot be met. Your boss came to you and announced that three options were being considered: to expand the existing plant, to build a whole new plant from the ground up, or simply to subcontract with a another company. You are to analyze the situation and make a recommendation.

Your first step was to find out how much growth in demand was expected next year, so you went to talk to your company’s sales force (who would know the customers better than they would?). Unfortunately, you got several different answers. About 40% of the sales force is predicting high growth, another 40% is predicting moderate growth, and the last 20% is predicting low growth. Nobody thinks demand will decrease. You worked out one-year returns for each combination, as shown in Table 1:

High / Moderate / Low
Expand / 1200 / 500 / -100
Build / 2500 / 1200 / -500
Subcontract / 1500 / 800 / -50

Table 1: First year returns

Obviously, this looks like a payoff table, and it could be solved analyzed that way, but any payoff table can be drawn as a decision tree (it doesn’t necessarily work in reverse), so let’s work it that way.

Q:What’s the first step to drawing a decision tree?

A:Organize the information into groups of decision alternatives or states-of-nature.

D:A group is a set of alternatives or states-of-nature which are mutually exclusive. All that means is that if you pick one decision alternative (or state-of-nature) then no other alternative (of state-of-nature) can be chosen (or occur). If it looks like two or more alternatives could be chosen, then they probably belong in different groups. Usually, there will be more than one group of each type, but this is a simple problem so we have only one of each, as shown in Figure 3:

Figure 3: Groups

I used a circle to indicate the state-of-nature group and a square to indicate the decision alternative group.

Q:How do you know a state-of-nature group from decision alternative group?

A:By looking at what you control.

D:The difference between the two is a question of control. You (or the decision maker) control which of the decision alternatives is chosen; you do not control which of the states-of-nature occurs. In Figure 3, the company can choose which of the expansion options they wish to implement, but cannot choose what the level of growth in demand will be.

Q:What’s the second step to drawing a decision tree?

A:Decide which of the groups comes first.

D:As we have only two groups, there are only two possibilities: make the decision first and wait to see what demand appears, or wait to see what demand appears, then make your decision. While the second option is appealing, in that we would not make a mistake, it simply won’t work. If we wait to see what demand appears, then we will not get the new capacity ready in time to meet that demand. As is usually true with decision-making, we will have to decide first, and then hope for a good outcome. So, we now know what goes first, and we can draw it, as shown in Figure 4:

Figure 4: Decision alternatives start the tree

Q:What’s the third step to drawing a decision tree?

A:Pick any one branch (arrow) and ask, “What comes next?”

D:I recommend a depth-first approach to drawing a tree. This means following a single set of branches further and further to the right, ignoring all the other branches until you reach the end of that path and put a payoff as the closing part. The reason for this is that most trees are too complex to grasp in their entirety just from reading a world problem. If you try to do that, you will get bogged down in a mess of alternatives and states-of-nature, with branches all over the place, and no sense of order. Going depth-first lets you concentrate on one small part of the tree, let’s you draw that part correctly, and then move on to another small part. When all the small parts are drawn correctly, you often find you have drawn the whole tree correctly.

Anyway, we pick one branch. Being excessively orderly, I will start at the top, with the branch labeled “Expand.” Again, because this is a small problem, the answer to, “What comes next?” is rather straightforward: the states-of-nature.

Q:Do squares and circles have to alternate through the tree?

A:No, any order at all can be followed.

D:In this example, they do alternate, but only because there are only two. Drawing in the states-of-nature that follow the “Expand” branch, we get Figure 5:

Figure 5: Depth-first on the “Expand” branch

Things to notice: I added the percentages to the labels on the state-of-nature branches. You don’t have to do this right away when you are drawing a tree by hand, and you may find it inconvenient, because it takes your mind off of the process (drawing the tree) and makes you search through the problem to find the numbers. If you have the numbers to hand, though, then it can’t hurt. For my part, I included them because I already know them (it’s my example) and it is easier than drawing an extra figure just to put in the percentages. Second, I don’t have enough room to draw the states-of-nature for the “Build” branch.

This is a common problem with drawing a tree: you never leave enough room. When drawing a tree by hand, squeeze the branches in wherever you can and then re-draw the tree starting on the right (with the payoffs). The tree gets smaller as you move to the left, so there is plenty of room

Q:What’s the fourth step to drawing a decision tree?

A:Repeat the third step, until you write in the payoff at the end of a branch. When you do that, retreat to the nearest branch that is not finished, and go back to repeating the third step.

D:For our little tree, we pick a branch (High) and when we ask, “What comes next?” the answer is, “A payoff.” So we would write in the payoff of 1200 at the end of that branch and backtrack to the nearest branch (Moderate) that is incomplete, put in the payoff of 500, and then put in the payoff of –100 on the “Low” branch. I have shown all three of these in Figure 6, simply to save room:

Figure 6: Adding the payoffs

Q:How do you draw the rest of the tree?

A:By repeating the pattern we have already used.

D:We are finished with the “Expand” branch, so we do what we did before, which is to backtrack to find the nearest branch that is not complete. This is the “Build” decision alternative. We know the states-of-nature come next, so we would draw the circles and arrows, label them and add the payoffs, as shown in Figure 7 (next page). Notice I had to move things around a bit to make them fit.

Q:Couldn’t we just have the “Build” arrow point into the state-of-nature circle following “Expand?”

A:No.

D:Ignoring for the moment that the payoffs would be different, it is still a bad idea because it is confusing to read. The rule for decision trees is that only one arrow may point into any node (as many as you need may point out).

Figure 7: Finishing the “Build” branch

Q:Are we finished yet?

A:Of course not.

D:We haven’t finished the “Subcontract” branch. You aren’t finished drawing a decision tree until every branch ends in a payoff. Even then you aren’t finished with the decision tree, only with drawing it. Figure 8 repeats the process for the “Subcontract” branch:

Figure 8: Finishing the drawing of the tree

Q:So, what’s left?

A:Calculations.

D:We have payoffs and probabilities, so we can calculate Expected Values for each set of data. Expected Value is not a necessity for payoff tables, but it is the only calculation we make for decision trees. For the sake of convenience, we show the expected values in the nodes. As we calculate the expected values, we move backwards (right to left) through the tree, placing the result in the circle that precedes the state-of-nature arrows. Since you know how to calculate an expected value (sum of the weights times the payoffs, Figure 9 simply shows the results placed in the nodes:

Figure 9: Decision Tree with Expected Values

Q:How do you read these expected values?

A:Follow the branches from left to right.

D:The payoffs that follow the states-of-nature are specific to the decision alternative that preceded the states-of-nature. Therefore, the expected value of 660, listed in the circle node following the “Expand” branch is based on the payoffs for the “Expand” decision alternative. To say it very simply, 660 is the expected value of the decision to expand.

Q:What goes in the square?

A:Whatever you want.

D:That was said somewhat facetiously, but is literally true, within the limits of the tree. A square node indicates decision alternatives, and decision alternatives are things you control. That means you get to pick whichever of the expected values you think is the best. In a practical sense, you will always pick the highest profit or lowest cost. Since we are dealing with profits, we would pick 1380, as shown in Figure 10:

Figure 10: Finished Decision Tree

Q:Now that we have drawn it, what do we do with it?

A:Make a decision.

D:Of course, this is such a small tree you really wouldn’t bother with it. Decision trees are most useful when you several layers of decision alternative nodes and state-of-nature nodes to make things complicated. Before we do that, though, we need to introduce a couple of ideas called Expected Value of Perfect Information (EVPI) and Expected Value of Sample Information (EVSI), but that will be the next set of lecture notes.

Back