#976 - Game Theory I - Operational Research Techniques

Lecture 6: Decision Theory / Game Theory I 12 November 2010 Topics * Tree Diagrams * Decision Trees * Decision Theory * Game Theory Reading Key Points * Tree diagrams * Decision trees * Decision criteria under risk * Decision criteria under uncertainty * Game theory Tree Diagrams * Tree Diagram = A diagrammatic representation used for reviewing the sequential decisions open to decisionmakers * Problems can be attached to different routes through the network * Extensive form games * Normal form games * Perfect information * 2-player zero-sum games Example of a tree diagram Definitions * Decision Nodes = Where the branch is selected by the decision-maker, represented by a square symbol * Decision Theory = Playing against Nature * Decision Tree = A tree diagram where some of the nodes are choice nodes and some are chance nodes * Event Nodes = Where the branch is selected probabilistically, represented by a circle symbol * Folding Back = The decision alternative to be selected is the one with optimal expected pay-off Decision Trees * Decision Tree = A tree diagram where some of the nodes are choice nodes and some are chance nodes * There are rewards associated with each outcome * Decision Nodes = Where the branch is selected by the decision-maker, represented by a square symbol * Event Nodes = Where the branch is selected probabilistically, represented by a circle symbol Example of a decision tree * Game in Extensive Form = An n-person game where a tree represents the moves of the game * Game in Normal Form = AN n-person game consisting of a set of strategies for each player and a set of corresponding pay-off functions * Game Theory = Situations where the decision maker's outcome is affected by an opponent's actions * Hurwicz = If are minimum and maximum pay-offs for strategy I, find where (with ) is your 'optimism-pessimism' index * Laplace = Assume Nature's strategies are equiprobable and maximise expected pay-off * Maximax = Choose the strategy whose maximum pay-off is highest * Maximin = Choose the strategy whose minimum pay-off is highest * Minimax-Regret = Apply minimax to the regret matrix * Perfect Information = A game where all the information sets consist of one vertex only * Regret Matrix = For row i and column j the regret placed in the cell is the amount by which you could have improved your pay-off had you known Nature's strategy Decision Theory * Decision Theory = Playing against Nature * There are two distinct situations: * Those in which we do not know the probabilities where Nature chooses her path * Decisions under uncertainty * Those in which we do know the probabilities where Nature chooses her path * Decisions under risk Decision Criteria Under Risk * Decisions under risk are normally analysed using decision trees * Situations may involve more than one decision so the tree will have more than one decision node * Folding Back = The decision alternative to be selected is the one with optimal expected pay-off * The conditional decisions at each node constitute a complete solution to the problem * The value of chance nodes is the weighted sum of the values of the nodes it leads to (the weights being conditional probability) Example of a decision situation under riskCourse Notes Page 8 * Tree Diagram = A diagrammatic representation used for reviewing the sequential decisions open to decisionmakers * Zero-Sum Two-Person Game = A game in which one player's gain is the other player's loss