Optimization Methods in Management Science Recitation 6b

Problem 1: Start With the Basics In this first problem, we start to look at the structure of games and develop strategies. This problem is considered very basic; when you are solving the game, make sure you understand what you are doing and not just the mechanics of solving the problem. It will be very important later on when we study more difficult topics. Find the value and optimal minimax and maximin strategies for the game in the table below. Use the graphical approach. ⎡ 2 1⎤ ⎥ ⎢ ⎣1 3⎦ Solution: We let x be the probability that the row player chooses Row 1, and we let y be the probability that the column player chooses column 1. Then 1 – x = Probability that the row player chooses row 2 1 – y = Probability column player chooses column 2 We now compute the cases: Case 1: If the column player chooses column one the if the row player uses a strategy (x,1-x) then the expected payoff to the row player is: 2x+(1-x) = x+1. We can graph the reward as function of x. This is shown below, in red: Payoff to Row x Case 2: If the column player chooses column two, and if the row player uses a strategy (x, 1-x) then the expected payoff to the row player is: x + 3(1-x) = -2x + 3. We can graph the reward as function of x. This is shown below, in green: Payoff to Row Player x The row player can guarantee a payoff of the lower envelope of the above graph, regardless of what the column player chooses. This is shown below: Payoff to Row Player x Thus since the row player wants to maximize his profits, he will choose the highest point on the blue line. This is the point where the red and green lines intersect, and is the point (2/3, 5/3). This shows the optimal strategy for the row player is to choose row one 2/3 of the time and row two 1/3 of the time. To find the optimal strategy for the column player we repeat the same procedure as above: Case 1: If the row player chooses row one and if the column player uses a strategy (y, 1-y) then the expected payoff to the row player is: 2y + (1-y) = y+1 We can graph the reward as function of y. This is shown below, in green: Payoff to Row Player y Case 2: If the row player chooses row two, and if the column player uses a strategy (y, 1-y) then the expected payoff to the column player is: y +3(1-y) = -2y + 3 We can graph the reward as function of y. This is shown below, in plum: Payoff to Row Player (0,1) y The column player can guarantee that the row player gets no more than the upper envelope of the above graph regardless of what the row player does. This is shown below in dark blue: Payoff to Row Player (0,1) y Since the column player wants to minimize the row player’s profits, he will choose the lowest point on the blue line. This is the point where the green and plum lines intersect, which is the point (2/3, 5/3). This shows that the optimal strategy for the column player is to choose column one 2/3 of the time and column two 1/3 of the time. It is important to note the symmetry here is not coincidental, rather we will draw on our knowledge of duality later in the recitation to connect the two. Problem 2. Now that you have practiced with the first problem, we give a second problem with the same flavor. By this point, you should be able to complete this problem without use of a reference. The key here is to eliminate a row for the row player if it is clearly dominated by another row. (One can use the same strategy to eliminate columns for the column player.) Find the value and optimal strategies for the two-person zero-sum game in the table below. ⎡4 ⎢6 ⎢ ⎢5 ⎢ ⎣6 5 7 7 6 5 6 5 5 8⎤ 9 ⎥⎥ 4⎥ ⎥ 5⎦ Solution: This problem can be solved more directly than the first problem. Can you think of the reason why? First of all, the row player would always choose Row 2 since it dominates the other rows. That is, the payoff for Row 2 is at least as large as the payoff for other rows, regardless of what the column player does. Once the column player knows that the row player will choose Row 2, the column player will choose column 1 or column 3. Problem 3: This problem is an extension of the basic theory and also combines the shortest path problem. This is the type of problem we would expect you to solve by extracting the basic knowledge and using some basic reasoning skills. If you get stuck, try to think about the optimal solution using basic methods and then try and use the game theory techniques we have taught you. Email us if you get stuck on this one. Jessica Simpson wants to travel from New York to Dallas by the shortest possible route. She may travel over the routes shown in the table below. Unfortunately, Nick, who is still bitter over having to split the hummer, has gained the ability to block one road leading out of Atlanta or one road leading out of Nashville, but can only block one road in total. Jessica will not know which roads have been blocked until she arrives at Atlanta or Nashville. Draw a 2 x 2 table stating what the travel length will be, where the columns represent Jessica’s choices of going to Atlanta or Nashville, and the rows represent Nick’s best choices of blocking a road from Atlanta or from Nashville. What is Jessica’s best mixed strategy, assuming that she wants to minimize her expected distance to Dallas. Route New York - Atlanta Length of Route (Miles) 800 New York – Nashville 900 Nashville – St. Louis 400 Nashville – New Orleans 200 Atlanta – St. Louis 300 Atlanta – New Orleans 600 St Louis – Dallas 500 New Orleans – Dallas 300 Solution: If Jessica goes through Atlanta, then Nick will block the route from Atlanta to St. Louis since the total travel distance from Atlanta to Dallas is 800 if she travels though St. Louis vs. 900 if she travels through New Orleans. If Jessica goes though Nashville, Nick will block the route from Nashville to New Orleans since the total travel distance from Nashville to Dallas through New Orleans is 500 vs. 900. Hence, we get the following payoff matrix. We make Nick the row player since we are used to the row player being the maximizer and Jessica the column player since she is trying to minimize distance, (Note Payoff to Nick is Total Jessica Travel Distance For Jessica) travels through ATL Nick Blocks ATL-STL 1700 Jessica Row travels Min through NAS 1400 1400 Nick Blocks NAS to MSY 1600 1800 Column Max 1700 1800 1600 From this point on we just use the same method as we did in problem 1, use the graphical method to solve this problem. We let JA be the probability Jessica Travels through Atlanta and let JN be the probability Jessica travels through Nashville. Case 1: If Nick chooses to block ATL-STL and if Jessica uses a strategy (JA, 1-JA) then the expected payoff to the row player is: 1700(JA) + 1400(1-JA) = 300(JA) + 1400 Let JA be measured on the x axis, and the distance traveled be on the y axis. We can graph the reward as function of JA. This is shown below, in green: Distance traveled JA Case 2: If Nick chooses to block NAS-MSY, and if Jessica uses a strategy (JA,1-JA), then the expected payoff to the column player is: 1600JA + 1800(1-JA) = -200JA + 1800 Letting JA be the x axis and the distance traveled be the y axis. We can graph the reward as function of JA. This is shown below, in plum: Distance traveled JA Jessica can guarantee that the expected distance traveled is at most the upper envelope of the above graph, regardless of what Nick does. This is shown below in dark blue: Distance traveled JA Since Jessica wants to minimize the maximum expected distance she travels, she will choose the lowest point on the blue line. This is the point where the green and plum lines intersect or the point (4/5, 1640). This shows that the optimal strategy for Jessica is to choose ATL 4/5 of the time and Nashville 1/5 of the time. Problem 4: Game Theory LP One of the basic skills we ask is that you are able to take a payoff matrix and formulate each player’s strategy as an LP. This is what connects game theory to linear programming. It is important to understand why this works and not just how to do it. It may help to play the game with a friend. Consider the two-person zero-sum game in the table below. ⎡ 1 2 − 1 − 1⎤ ⎢− 1 1 − 1⎥ 2 ⎥ ⎢ ⎢⎣− 1 − 1 1 ⎥⎦ Part A: Write down each player’s LP. Solution: We can find the row player’s LP using the same method we did in class. First we write the row player’s problem as a mathematical program and then convert it to an linear program. max(min(.5 x1 − x2 − x3 , − x1 + .5 x2 − x3 , − x1 − x2 + x3 )) ST : x1 + x2 + x3 = 1 x1 , x2 , x3 ≥ 0 We now convert the above to an LP: Z max ST : Z ≤ .5 x1 − x 2 − x3 Z ≤ − x1 + .5 x 2 − x3 Z ≤ − x1 − x 2 + x3 x1 + x 2 + x3 = 1 x1 , x 2 , x3 ≥ 0 We do the same for the column player: min max(.5 y1 − y2 − y3 , − y1 + .5 y2 − y3 , − y1 − y2 + y3 ) ST : y1 + y2 + y3 = 1 y1 , y2 , y3 ≥ 0 L min ST : L ≥ .5 y1 − y 2 − y 3 L ≥ − y1 + .5 y 2 − y 3 L ≥ − y1 − y 2 + y 3 y1 + y 2 + y 3 = 1 y1 , y 2 , y 3 ≥ 0 Part B: Take the dual of the row player’s LP. What do you find? Solution: The dual of the row player’s LP is that of the column players LP. Part C: Is it always true the dual of the row player’s LP is the column players LP? Does this imply that the maximin value is equal to the minimax value; that is, does it prove that the optimal objective value for both players is the same? Solution: It is always true that the dual of the row player’s LP is the column players LP. By strong duality and the fact that both LPs have feasible solutions, it implies that the objective values of the two LPs are the same. Problem 5: An Exam Problem (2004 Midterm) Students always want to know what they will be tested on, how hard we examine topics and what is likely to appear. The following is a pretty complete problem which should really test your skills and determine if you are ready for an exam level question. After publishing his latest book, Bill earned $500,000, which he wants to invest in stocks. Bill believes the investment will be affected by whoever wins the Presidential election in November. He has narrowed down his investment to three stocks, labeled C, D and E. In this election, the candidates are denoted as B, K, and N. The performance of each stock under each candidate is show in the table below: Stocks C D E B 1.5 1.1 0.9 Candidates K 1.1 1.3 1.2 N 0.7 1.2 1.4 For example, the table says that if Bill invests $1,000 in stock D, and candidate K is elected, then Bill’s position in stock D will be worth $1,300 after one year. Bill is by nature a conservative, and wants to guarantee as much expected return as possible regardless of who wins the election. So, he wants to invest conservatively, so as to maximize his payment over the next year in the worst possible case. We will call his objective the maximin objective, since his goal is to maximize the payment in the worst case. Part A: If Bill were required to invest all his money in one stock, which stock would he invest in? Part B: Let pC, pD, and pE denote the proportion of the money invested in stocks C, D, and E. Formulate an LP to compute the optimal maximin strategy for Bill. It must be in the form of a linear program. Part C: Suppose that the pessimistic Bill decides that candidate N really has no chance whatsoever, and so eliminates that column from consideration. Under this scenario Stock E is dominated by Stock D. Determine what proportion of his $500,000 Bill should allocate to Stocks C and D for his optimal maximin portfolio. Please show your work. Solution: Part A If Bill were to invest $1 in C, he would get $0.7 if N is elected; if Bill were to invest $1 in E, he would get $0.9 if B is elected. Therefore, Bill would invest in D, and get at least $1.1 for each $1 invested. Part B The nonlinear program is max min {1.5 pC + 1.1 pD + 0.9 pE , 1.1 pC + 1.3 pD + 1.2 pE , 0.7 pC + 1.2 pD + 1.4 pE } s.t. pC + pD + pE = 1 pC , pD , pE ≥ 0. After converting to an LP, we obtain the answer: max s.t. z pC + p D + p E = 1 pC , p D , p E ≥ 0 z ≤ 1.5 pC + 1.1 p D + 0.9 p E z ≤ 1.1 pC + 1.3 p D + 1.2 p E z ≤ 0.7 pC + 1.2 p D + 1.4 p E . Part C: Let p be the proportion of money invested in stock C. If B is elected, the payoff is 1.5p + 1.1(1-p). If K is elected, the payoff is 1.1p + 1.3(1-p). The worst case payoff is the lower of these two. The best worst case payoff is when these two payoffs are equal, that is when 1 1.5 p + 1.1(1 − p) = 1.1 p + 1.3(1 − p) ⇔ 0.2 p = 0.6 ⇔ p = . 3 Hence, the answer is to invest 1/3 of $500,000 in stock C, and 2/3 in stock D. The following plot illustrates the reasoning above. return on investment 1.5 1.5 1.4 1.4 1.3 1.3 1.2 1.2 1.1 0 1.1 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 p This is the point when we usually take the last five min to talk about questions, current events, classic TV trivia, and talk about quiz statistics. However, you probably want to get back to what your are doing. We hope you had a great week off. Ollie, isn’t Cancun fun . There are so many single Turkeys on the beach who are going wild for my hat! Who needs game theory when we have beach games! Tim the Turkey Ollie The computationally wise owl Tim, don’t be silly, game theory is an important topic that happens to fall during spring break. We need to learn this material to do well on the quiz, and to further our knowledge of OR. However we should have gone to Hootersville where there are more single owls