treeplan

Decision Trees Using TreePlan Add-In for Microsoft Excel Contents Chapter 1 Quick Start........................................................................................2 TreePlan Installation.............................................................................................2 Occasional Use....................................................................................................2 Selective Use.......................................................................................................2 Steady Use..........................................................................................................2 Building a Decision Tree in TreePlan.....................................................................3 The Anatomy of a TreePlan Decision Tree............................................................5 Chapter 2 Step-by-Step TreePlan Tutorial ....................................................6 DriveTek Problem................................................................................................6 Nodes and Branches ............................................................................................7 Terminal Values...................................................................................................7 Building the Tree Diagram....................................................................................8 Interpreting the Results....................................................................................... 13 Formatting the Tree Diagram.............................................................................. 14 Displaying Model Inputs ..................................................................................... 16 Printing the Tree Diagram.................................................................................. 17 Alternative Model.............................................................................................. 19 Chapter 3 Decision Tree Solution.................................................................20 Strategy............................................................................................................. 20 Payoff Distribution ............................................................................................. 20 DriveTek Strategies ........................................................................................... 20 Strategy Choice ................................................................................................. 25 Certainty Equivalent ........................................................................................... 25 Rollback Method................................................................................................ 27 Optimal Strategy ................................................................................................ 28 Chapter 4 Sensitivity Analysis........................................................................30 One-Variable Sensitivity Analysis using an Excel data table .................................. 30 Two-Variable Sensitivity Analysis using an Excel data table .................................. 32 2 Chapter 1 Quick Start TreePlan is an Excel add-in that allows you to build decision trees in Excel. It was developed by Professor Michael R. Middleton at the University of San Francisco and modified for use at Fuqua (Duke) by Professor James E. Smith. TreePlan Installation All of TreePlan’s functionality is in a single file, TreePlan.xla. Depending on your preference, there are three ways to install TreePlan. (These instructions also apply to the other Decision ToolPak add-ins: SensIt.xla and RiskSim.xla.) Occasional Use If you plan to use TreePlan on an irregular basis, simply use Excel’s File | Open command to load TreePlan.xla each time you want to use it. You may keep the TreePlan.xla file on a floppy disk, your computer’s hard drive, or a network server. Selective Use You can use Excel’s Add-In Manager to install TreePlan. First, copy TreePlan.xla to a location on your computer’s hard drive. Second, if you save TreePlan.xla in the Excel or Office Library subdirectory, go to the third step. Otherwise, run Excel, choose Tools | Add-Ins; in the Add-Ins dialog box, click the Browse button, use the Browse dialog box to specify the location of TreePlan.xla, and click OK. Third, in the Add- Ins dialog box, note that TreePlan is now listed with a check mark, indicating that its menu command will appear in Excel, and click OK. If you plan to not use TreePlan and you want to free up main memory, uncheck the box for TreePlan in the Add-In Manager. When you do want to use TreePlan, choose Tools | Add-Ins and check TreePlan’s box. To remove TreePlan from the Add-In Manager, use Windows Explorer or another file manager to delete TreePlan.xla from the Library subdirectory or from the location you specified when you used the Add-In Manager’s Browse command. The next time you start Excel and choose Tools | Add-Ins, a dialog box will state “Cannot find add-in … treeplan.xla. Delete from list?” Click Yes. Steady Use If you want TreePlan’s options immediately available each time you run Excel, use Windows Explorer or another file manager to save TreePlan.xla in the Excel XLStart directory. Alternatively, in Excel you can use Tools | Options | General to specify an alternate startup file location and use a file manager to save TreePlan.xla there. When you start Excel, it tries to open all files in the XLStart directory and in the alternate startup file location. For additional information visit “TreePlan FAQ” at www.treeplan.com. 3 After opening TreePlan.xla in Excel, the command "Decision Tree" appears at the bottom of the Tools menu (or, if you have a customized main menu, at the bottom of the sixth main menu item). Building a Decision Tree in TreePlan You can start TreePlan either by choosing Tools | Decision Tree from the menu bar or by pressing Ctrl+t (hold down the Ctrl key and press t). If the worksheet doesn't have a decision tree, TreePlan prompts you with a dialog box with three options; choose New Tree to begin a new tree. TreePlan draws a default initial decision tree with its upper left corner at the selected cell. For example, the figure below shows the initial tree when $B$2 is selected. (Note that TreePlan writes over existing values in the spreadsheet: begin your tree to the right of the area where your data is stored, and do not subsequently add or delete rows or columns in the tree-diagram area.) In Excel 5 and 95 a terminal node is represented by a triangle instead of a vertical bar. 1 2 3 4 5 6 7 8 9 10 11 A B C D E F G H I Decision 1 0 0 0 1 0 Decision 2 0 0 0 Build up a tree by adding or modifying branches or nodes in the default tree. To change the branch labels or probabilities, click on the cell containing the label or probability and type the new label or probability. To modify the structure of the tree (e.g., add or delete branches or nodes in the tree), select the node or the cell containing the node in the tree to modify, and choose Tools | Decision Tree or press Ctrl+t. TreePlan will then present a dialog box showing the available commands. For example, to add an event node to the top branch of the tree shown above, select the square cell (cell G4) next to the vertical line at the end of a terminal branch and press Ctrl+t.. TreePlan then presents this dialog box. To add an event node to the branch, we change the selected terminal node to an event node by selecting Change to event node in the dialog box, selecting the number of branches (here two), and pressing OK. TreePlan then redraws the tree with a chance node in place of the terminal node. 4 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A B C D E F G H I J K L M 0.5 Event 3 0 Decision 1 0 0 0 0 0.5 Event 4 0 1 0 0 0 Decision 2 0 0 0 The dialog boxes presented by TreePlan vary depending on what you have selected when you choose Tools | Decision Tree or press Ctrl+t. The dialog box shown below is presented when you press Ctrl+t with an event node selected; a similar dialog box is presented when you select a decision node. If you want to add a branch to the selected node, choose Add branch and press OK. If you want to insert a decision or event node before the selected node, choose Insert decision or Insert event and press OK. To get a description of the available commands, click on the Help button. The Copy subtree command is particularly useful when building large trees. If two or more parts of the tree are similar, you can copy and paste "subtrees" rather than building up each part separately. To copy a subtree, select the node at the root of the subtree and choose Copy subtree. This tells TreePlan to copy the selected node and everything to the right of it in the tree. To paste this subtree, select a terminal node and choose Paste subtree. TreePlan then duplicates the specified subtree at the selected terminal node. Since TreePlan decision trees are built directly in Excel, you can use Excel's commands to format your tree. For example, you can use bold or italic fonts for branch labels: select the cells you want to format and change them using Excel's formatting commands. To help you, TreePlan provides a Select dialog box that appears when you choose Tools Decision Tree or press Ctrl+t without a node selected. You can also bring up this dialog box by pressing the Select button on the Node dialog box. From here, you can select all items of a particular type in the tree. For example, if you choose Probabilities and press OK, TreePlan selects all cells containing probabilities in the tree. You can then format all of the probabilities simultaneously using Excel's formatting commands. (Because of limitations in Excel, the Select dialog box will not be available when working with very large trees.) 5 The Anatomy of a TreePlan Decision Tree An example of a TreePlan decision tree is shown below. In the example, a firm must decide (1) whether to prepare a proposal for a possible contract and (2) which method to use to satisfy the contract. The tree consists of decision nodes, event nodes and terminal nodes connected by branches. Each branch is surrounded by cells containing formulas, cell references, or labels pertaining to that branch. You may edit the labels, probabilities, and partial cash flows associated with each branch. The partial cash flows are the amount the firm "gets paid" to go down that branch. Here, the firm pays $50,000 if it decides to prepare the proposal, receives $250,000 up front if awarded the contract, spends $50,000 to try the electronic method, and spends $120,000 on the mechanical method if the electronic method fails. Use mechanical method $80,000 0.5 -$120,000 $80,000 Awarded contract 2 0.5 $250,000 $90,000 Electronic success $150,000 Try electronic method $0 $150,000 Prepare proposal -$50,000 $90,000 0.5 Electronic failure -$50,000 $20,000 $30,000 -$120,000 $30,000 0.5 1 Not awarded contract $20,000 -$50,000 $0 -$50,000 Don't prepare proposal $0 $0 $0 BRANCH LABELS: Type text in these cells. DECISION NODES: TreePlan formula for which alternative is optimal. PARTIAL CASH FLOWS: Enter numbers or formulas in these cells. PROBABILITIES: Enter numbers or formulas in these cells. ROLLBACK EVs: TreePlan formula for expected value at this point in the tree. TERMINAL NODES EVENT NODES TERMINAL VALUES: TreePlan formula for sum of partial cash flows along path. The trees are "solved" using formulas embedded in the spreadsheet. The terminal values sum all the partial cash flows along the path leading to that terminal node. The tree is then "rolled back" by computing expected values at event nodes and by maximizing at decision nodes; the rollback EVs appear next to each node and show the expected value at that point in the tree. The numbers in the decision nodes indicate which alternative is optimal for that decision. In the example, the "1" in the first decision node indicates that it is optimal to prepare the proposal, and the "2" in the second decision node indicates the firm should try the electronic method because that alternative leads to a higher expected value, $90,000, than the mechanical method, $80,000. TreePlan has a few options that control the way calculations are done in the tree. To select these options, press the Options button in any of TreePlan's dialog boxes. The first choice is whether to Use Expected Values or Use Exponential Utility Function for computing certainty equivalents. The default is to rollback the tree using expected values. If you choose to use exponential utilities, TreePlan will compute utilities of endpoint cash flows at the terminal nodes and compute expected utilities instead of expected values at event nodes. Expected utilities are calculated in the cell below the certainty equivalents. You may also choose to Maximize (profits) or Minimize (costs) at decision nodes; the default is to maximize profits. If you choose to minimize costs instead, the cash flows are interpreted as costs, and decisions are made by choosing the minimum expected value or certainty equivalent rather than the maximum. See the Help file for details on these options. 6 Chapter 2 Step-by-Step TreePlan Tutorial A decision tree can be used as a model for a sequential decision problems under uncertainty. A decision tree describes graphically the decisions to be made, the events that may occur, and the outcomes associated with combinations of decisions and events. Probabilities are assigned to the events, and values are determined for each outcome. A major goal of the analysis is to determine the best decisions. Decision tree models include such concepts as nodes, branches, terminal values, strategy, payoff distribution, certainty equivalent, and the rollback method. The following problem illustrates the basic concepts. DriveTek Problem DriveTek Research Institute discovers that a computer company wants a new tape drive for a proposed new computer system. Since the computer company does not have research people available to develop the new drive, it will subcontract the development to an independent research firm. The computer company has offered a fee of $250,000 for the best proposal for developing the new tape drive. The contract will go to the firm with the best technical plan and the highest reputation for technical competence. DriveTek Research Institute wants to enter the competition. Management estimates a cost of $50,000 to prepare a proposal with a fifty-fifty chance of winning the contract. However, DriveTek's engineers are not sure about how they will develop the tape drive if they are awarded the contract. Three alternative approaches can be tried. The first approach is a mechanical method with a cost of $120,000, and the engineers are certain they can develop a successful model with this approach. A second approach involves electronic components. The engineers estimate that the electronic approach will cost only $50,000 to develop a model of the tape drive, but with only a 50 percent chance of satisfactory results. A third approach uses magnetic components; this costs $80,000, with a 70 percent chance of success. DriveTek Research can work on only one approach at a time and has time to try only two approaches. If it tries either the magnetic or electronic method and the attempt fails, the second choice must be the mechanical method to guarantee a successful model. The management of DriveTek Research needs help in incorporating this information into a decision to proceed or not. [Source: The tape drive example is adapted from Spurr and Bonini, Statistical Analysis for Business Decisions, Irwin.] 7 Nodes and Branches Decision trees have three kinds of nodes and two kinds of branches. A decision node is a point where a choice must be made; it is shown as a square. The branches extending from a decision node are decision branches, each branch representing one of the possible alternatives or courses of action available at that point. The set of alternatives must be mutually exclusive (if one is chosen, the others cannot be chosen) and collectively exhaustive (all possible alternatives must be included in the set). There are two major decisions in the DriveTek problem. First, the company must decide whether or not to prepare a proposal. Second, if it prepares a proposal and is awarded the contract, it must decide which of the three approaches to try to satisfy the contract. An event node is a point where uncertainty is resolved (a point where the decision maker learns about the occurrence of an event). An event node, sometimes called a "chance node," is shown as a circle. The event set consists of the event branches extending from an event node, each branch representing one of the possible events that may occur at that point. The set of events must be mutually exclusive (if one occurs, the others cannot occur) and collectively exhaustive (all possible events must be included in the set). Each event is assigned a subjective probability; the sum of probabilities for the events in a set must equal one. The three sources of uncertainty in the DriveTek problem are: whether it is awarded the contract or not, whether the electronic approach succeeds or fails, and whether the magnetic approach succeeds or fails. In general, decision nodes and branches represent the controllable factors in a decision problem; event nodes and branches represent uncontrollable factors. Decision nodes and event nodes are arranged in order of subjective chronology. For example, the position of an event node corresponds to the time when the decision maker learns the outcome of the event (not necessarily when the event occurs). The third kind of node is a terminal node, representing the final result of a combination of decisions and events. Terminal nodes are the endpoints of a decision tree, shown as the end of a branch on hand-drawn diagrams and as a triangle on computer-generated diagrams. The following table shows the three kinds of nodes and two kinds of branches used to represent a decision tree. Type of Node Written Symbol Computer Symbol Node Successor Decision square square decision branches Event circle circle event branches Terminal endpoint triangle or bar terminal value 8 Terminal Values Each terminal node has an associated terminal value, sometimes called a payoff value, outcome value, or endpoint value. Each terminal value measures the result of a scenario: the sequence of decisions and events on a unique path leading from the initia l decision node to a specific terminal node. To determine the terminal value, one approach assigns a cash flow value to each decision branch and event branch and then sum the cash flow values on the branches leading to a terminal node to determine the terminal value. In the DriveTek problem, there are distinct cash flows associated with many of the decision and event branches. Some problems require a more elaborate value model to determine the terminal values. The following diagram shows the arrangement of branch names, probabilities, and cash flow values on an unsolved tree. Use mechanical method -$120,000 0.5 Electronic success 0.5 Try electronic method $0 Awarded contract -$50,000 0.5 $250,000 Electronic failure -$120,000 0.7 Magnetic success Prepare proposal Try magnetic method $0 -$50,000 -$80,000 0.3 Magnetic failure -$120,000 0.5 Not awarded contract $0 Don't prepare proposal $0 To build the decision