Optimization Methods in Management Science Game Theory

2-person 0-sum (or constant sum) game theory Quotes of the Day My work is a game, a very serious game. -- M. C. Escher (1898 - 1972) Conceal a flaw, and the world will imagine the worst. -- Marcus Valerius Martialis (40 AD - 103 AD) Reveal your strategy in a game, and your outcome will be the worst. -- Professor Orlin (for the lecture on game theory) From Marilyn Vos Savant’s column. Say you’re in a public library, and a beautiful stranger strikes up a conversation with you. She says: ‘Let’s show pennies to each other, either heads or tails. If we both show heads, I pay you $3. If we both show tails, I pay you $1. If they don’t match, you pay me $2.’ At this point, she is shushed. You think: ‘With both heads 1/4 of the time, I get $3. And with both tails 1/4 of the time, I get $1. So 1/2 of the time, I get $4. And with no matches 1/2 of the time, she gets $4. So it’s a fair game.’ As the game is quiet, you can play in the library. But should you? Should she? Marilyn Vos Savant has a weekly column in Parade. She has the highest recorded IQ on record. I read Marilyn Vos Savant’s column on a regular basis. Some of my favorite columns of hers are ones that deal with elementary probability or mathematics. 2-person 0-sum Game Theory z Two people make decisions at the same time. z The payoff depends on the joint decisions. z Whatever one person wins the other person loses. – Marilyn vos Savant answered the question incorrectly. Payoff Matrix for Vos Savant’s Game You choose heads or tails The beautiful stranger chooses heads or tails Beautiful Stranger Heads Heads You Tails Tails 3 -2 -2 1 This matrix is the payoff matrix for you, and the beautiful stranger gets the negative. Payoff Matrix for Rock-Paper-Scissors Person R chooses a row: either 1, 2, or 3 Person C chooses a column: either 1, 2, or 3 Rock R C Paper Scissors Rock 0 -1 1 Paper 1 0 -1 Scissors -1 1 0 This matrix is the payoff matrix for player R. (And player C gets the negative.) Another Payoff Matrix Person R chooses a row: either 1, 2, or 3 Person C chooses a column: either 1, 2, or 3 e.g., -2 1 2 2 -1 0 1 0 -2 This matrix is the payoff matrix for player R. (And player C gets the negative.) R chooses row 3; C chooses column 1 R gets 1; C gets –1 (zero sum) Some more examples of payoffs R chooses 2, C chooses 3 R gets 0; C gets 0 -2 1 2 2 -1 0 1 0 -2 (zero sum) R chooses row 3; C chooses column 3 R gets -2; C gets +2 (zero sum) Next: 2 volunteers Player R puts out 1, 2 or 3 fingers Player C simultaneously puts out 1, 2, or 3 fingers -2 1 2 2 -1 0 1 0 -2 -2 We will run the game for 5 trials. R Total R tries to maximize his or her total C tries to minimize R’s total. Next: Play the game with your partner (If you don’t have one, then watch) Player R puts out 1, 2 or 3 fingers Run the game for 5 trials. Player C simultaneously puts out 1, 2, or 3 fingers -2 1 2 2 -1 0 1 0 -2 R tries to maximize his or her total C tries to minimize R’s total. R Total R C Tie Who has the advantage: R or C? Here we will take a very conservative viewpoint? What can player R guarantee in return, regardless of what C chooses? -2 1 2 2 -1 0 1 0 -2 Most students guess correctly that R has an advantage. But to determine who has an advantage in general is a much more difficult problem than it seems, and relies on linear programming. Can R guarantee an expected return independent of what C does? (a lower bound on the opt for R). Suppose R chooses row j. What can R guarantee? -2 1 2 2 -1 0 1 0 -2 What row offers R the best guaranteed “return”? A strategy that consists of selecting the same row over and over again is a “pure strategy.” R can guarantee a payoff of at least –1. What column offers C the best guaranteed “return”? Random (mixed) strategies Suppose we permit R to choose a random strategy. What can R guarantee. -2 1 2 2 -1 0 1 0 -2 Suppose R will flip a coin, and chooses: Row 1 if Heads, and Row 3 if tails. That is, .5 for Row 1 .5 for Row 3 The idea of a randomized strategy is one of the most important concepts of game theory. A good example occurs in sporting events, such as baseball. If a batter knows what a pitcher is going to throw, then the batter has an advantage. So the pitcher will try to “mix it up” so that the batter cannot know for sure what kind of pitch he will receive. In fact, it is optimal for the pitcher to randomize. Similarly, the batter often has to decide in advance what kind of pitch to swing at. If he were to let the pitcher know what he is expecting, then the batter is at a disadvantage. So, the batter is better off randomizing on what he will be looking for. Prob. .5 × -2 1 2 -2 1 2 .5 + 0 × -1 2 0 2 -1 0 0 + .5 × -2 1 0 1 0 -2 .5 -.5 .5 0 Expected Payoff So, with a random strategy R guarantees at least -.5 regardless of what column C chooses. That is, the minimum expected payoff over all three columns is -.5. In two person game theory, we will often talk in terms of guarantees. Of course, the guarantee is not a real guarantee in the usual sense. It is a guarantee in terms of expected value. If the row player chose this strategy a large number of times, then he or she would receive at least -.5 on average. This is not a particularly good guarantee, but it is better than the -1 from before. We shall see that the row player can do much better. Another example: Player R chooses each row with probability of 1/3. Prob. 1/3 × -2 -2 1 2 1/3 + 1/3 × 2 2 -1 0 1/3 + 1/3 × 1 1 0 -2 1/3 1/3 0 0 Expected Payoff Thus R can guarantee a payoff of at least ______ . It is a lower bound on what R will get. This is better. With this simple mixed strategy, the row player can guarantee at least 0 regardless of what the column player does. Moreover, if the column player were to occasionally choose column 1, then the row player would do even better. Player C can also do this. Suppose that Player C chooses each column with probability of 1/3. Prob. 1/3 1/3 1/3 Expected Payoff -2 1 2 1/3 Row 1 2 -1 0 1/3 Row 2 1 0 -2 -1/3 Row 3 Thus C can limit R’s payoff to at most ______ . This is the maximum expected payoff over all three rows This gives an upper bound on what R would get. Previously we were focusing on guarantees that the row player can achieve. Of course, this is a two person game, and so we can carry out similar analysis for the column player. In this case, the column player can guarantee that the row player receives at most 1/3, which is what would happen if the row player selected row 1 or row 2. The payoff to the row player could be less than 1/3 in this case if the row player occasionally chose row 3. Challenge to Class -2 1 2 2 -1 0 1 0 -2 Left half of class: row players. Choose probabilities for each row so that you are guaranteed more than 0, regardless of what the column player does Right half of class: column players. Choose probabilities for each column so that the row player can get no more than .3 regardless of what the row player does. Even though this is a tiny problem, it is extremely hard to come up with the optimum probabilities for the row player or for the column player. It is a challenge enough to do better than 0 for the row player or for the column player to guarantee a payoff to R of less than .3. Row Player’s Problem Prob. -2 1 2 x1 2 -1 0 x2 1 0 -2 x3 Maximize z = min{ -2 x1 + 2 x2 + x3, x1 - x2, 2 x1 - 2 x3 s.t. x1 + x2 + x3 = 1 Let z be a lower bound on what R will get. } This is the maximin payoff. x1, x2, x3 ≥ 0 We finally see the connection between two person 0-sum games and optimization. The Row Player’s problem is to develop probabilities so that the guaranteed payoff is as large as possible. The column player can choose column 1 or column 2 or column 3, each leading to its own expected payoff. The guaranteed payoff is the least of these three expected payoffs. And we need x1, x2, and x3 to correspond to probabilities. So, they are nonnegative and they sum to 1. We call this the maximin payoff because we are maximizing the minimum of three payoff values. Row Player’s Problem Maximize z = min{ -2 x1 + 2 x2 + x3, x1 - x2, 2 x1 - 2 x3 s.t. x1 + x2 + x3 = 1 Recall: } min(1, 0, 2) is the same as x1, x2, x3 ≥ 0 max z Maximize z s.t. z ≤ -2 x1 + 2 x2 + x3 z≤ x1 - x2, z ≤ 2 x1 - 2 x3 s.t z≤1 z≤0 z≤2 x1 + x2 + x3 = 1 x1, x2, x3 ≥ 0 We learned how to convert a maximin problem into a linear program. We carry out the same transformation here. So, the optimum strategy for the row player (in the maximin sense) can be determined by solving a linear program. The Row Player’s LP, in general x1 × a11 a11 a12 a13 … a1m x1 + x2 × a21 … a21 a22 a23 … a2m x2 + xn × an1 an1 an2 an3 … anm xn Expected Payoff P1 P2 … Pm Maximize z (the payoff to x) Pj: z ≤ a1j x1 + a2j x2 +… + anjxn for all j … P3 x1 + x2 + … + xn = 1 xj ≥ 0 for all j This is what happens in 2-person 0-sum games in general. Instead of a 3 by 3 payoff matrix, there is an m by n payoff matrix. The row player will select probabilities for m rows. This vector x of probabilities leads to a payoff for each column. The row player wants to choose x so that the minimum payoff of a row is maximized. The Column Player’s Problem Prob. Min v y1 y2 y3 -2 1 2 Row 1 2 -1 0 Row 2 1 0 -2 Row 3 Let v be an upper bound on what R will get. = max{ -2 y1 + y2 + 2 y3, 2 y1 - y2 y1 y1 - 2 y3 + y2 } This is the minimax payoff. + y3 = 1 y1 , y2 , y3 ≥ 0 A similar analysis can be carried out for the column player. In this case, the column players chooses probabilities associated with each column. If the row player chooses row 1, then the associated payoff is -2y1 + y2 + 2y3. There are also payoffs for the other two rows. The column player wants to minimize the guaranteed payoff to the row player which is the max of those three payoffs. For this reason, the column player’s problem is a minimax problem. The Column Player’s Problem Min v = max{ -2 y1 + y2 + 2 y3, 2 y1 - y2 y1 - 2 y3 y1 + y2 + y3 = 1 y1 , y2 , y3 Min v } ≥ 0 (the payoff to R) v ≥ -2 y1 + y2 + 2 y3 v≥ v≥ 2 y1 - y2 y1 y1 - 2 y3 + y2 + y3 = 1 y1 , y2 , y3 ≥ 0 Similar to before, we translate the column player’s problem into a linear program. An optimal randomized strategy for R. Prob. Expected Payoff -2 1 2 7/18 2 -1 0 5/18 1 0 -2 1/3 1/9 1/9 1/9 The optimal maximin payoff to R is 1/9. That is, R can play to guarantee at least 1/9. The optimal strategy for R (in terms of maximin optimization) is to choose Row one 7/18 of the time, to choose row two 5/18 of the time, and to choose row three 1/3 of the time. Under these circumstances, the row player will receive an expected payoff of 1/9 regardless of what the column player does. A natural question is: does the optimal strategy for the row player always lead to a payoff that that is the same for all columns. The answer is no. For example, if you added a fourth column of (0, 0, .5), you would find that the expected payoff of that column is 1/6. And it would also be true that the optimum strategy for the row player would be the same as above, with an expected maximin payoff of 1/9. The difference in this case is that the row player could possibly get more than 1/9 if the column player occasionally selected the fourth column. An optimal randomized strategy for C. Prob. 1/3 5/9 1/9 Exp. payoff -2 1 2 1/9 2 -1 0 1/9 1 0 -2 1/9 So, if C plays the optimal minimax strategy, then R gets at most 1/9. If we carry out the analysis for the column player, the optimal minimax strategy is for the column player to choose column one with probability 1/3, column two with probability 5/9, and column three with probability 1/9. In this case, the column player can guarantee a payoff of at most 1/9 to the row player regardless of what row the row player selects. It turns out that the maximin payoff is the same as the minimax payoff, which is remarkable. After all, the maximin payoff is a very conservative strategy. Rather than trying to take advantage of knowledge of his or her opponent, the row player chooses probabilities that are absolutely guaranteed to return an expected payoff of 1/9 regardless of what the column player does. It seems plausible that if one takes into account lots of information about the column player, possibly the row player would do even better. But no. The row player cannot do better if the column player is also playing conservatively. In this case, the column player can guarantee a payoff of at most 1/9 to the row player, regardless of what the row player does. To see how extreme and unintuitive this result is, imagine that you are the row player and you have to announce in advance of playing what your mixed (randomized) strategy is. You may think that announcing your strategy prior to the column player selecting a column has to be a bad idea, and will cost you. But if you announce the optimum maximin strategy, you will still guarantee an expected payoff of 1/9. Announcing the strategy does not cost you int his case. Fundamental Theorem of 2-person 0-sum Game Theory. For any two person game, let RPay(x) be the guaranteed payoff to R if the row player chooses probability vector x. Let CPay(y) be the upper bound on what R can get if the column player chooses probability vector y. Then RPay(x) ≤ CPay(y) “Weak Duality” There exists x* and y* so that RPay(x*) = CPay(y*) “Strong Duality” That is, maximin payoff = minimax payoff. Proof: The column player’s LP is the dual of the row player’s LP. Max z s.t. 2 x1 - 2 x2 - x3 + z +z - x1 + x2 2 x3 + z - 2 x1 + x1 + x2 + x3 Dual variables (the payoff to R) ≤ 0 ≤ 0 ≤ 0 = 1 y1 y2 y3 v x1, x2, x3 ≥ 0 Min v (the payoff to R) 2 y1 - y2 - 2 y3 + v ≥ 0 + v ≥ 0 y1 + 2 y3 + v ≥ y1 + y2 + y3 = 0 1 - 2 y1 + y2 - y1 , y2 , y3 ≥ 0 The two linear programs given before do not seem to be duals of each other. But if we rewrite them, we can see that they are duals. Using the SOB technique, one can easily see that the second LP is the dual of the first. From Marilyn Vos Savant’s column. Say you’re in a public library, and a beautiful stranger strikes up a conversation with you. She says: ‘Let’s show pennies to each other, either heads or tails. If we both show heads, I pay you $3. If we both show tails, I pay you $1. If they don’t match, you pay me $2.’ At this point, she is shushed. You think: ‘With both heads 1/4 of the time, I get $3. And with both tails 1/4 of the time, I get $1. So 1/2 of the time, I get $4. And with no matches 1/2 of the time, she gets $4. So it’s a fair game.’ As the game is quiet, you can play in the library. But should you? Should she? We now return to Marilyn vos Savant’s problem. Determining the optimal strategy B. S. H T Prob H 3 -2 p T -2 1 1-p Choose the value of p that maximizes the minimum payoff. Col 2 Col 1 maximize subject to z = min {3p + -2(1-p), -2p + 1(1-p) } 0≤p≤ 1 Col 1 maximize subject to Col 2 z = min {5p – 2, -3p + 1 } 0≤p≤ 1 Note that the row player only has to choose one variable, that is, p. If we write the maximin problem, it is a problem involving two variables: p and z. We can express this as a linear program, but we will leave it in the maximin form instead. The second optimization problem is a simplification of the first one. Determining the optimal strategy Col 1 maximize z = min {5p – 2, -3p + 1 } subject to payoff to you. Col 2 0≤p≤ 1 3 Column 1 2 1 0 -1 -2 0 Column 2 5p – 2 -3p + 1 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 p If we write the min of two linear functions (as p varies), we will see that it is the blue line given in the graph. If we then find the maximum of the blue line, it is the black dot. The beautiful stranger’s viewpoint B. S. H T Choose the value of y that minimizes that maximum payoff. H 3 -2 T -2 1 Prob y 1-y Row 1 minimize subject to z = max {3y + -2(1-y), -2y + 1(1-y) } 0≤y≤ 1 Row 1 minimize subject to Row 2 Row 2 z = max {5y – 2, -3y + 1 } 0≤y≤ 1 We can carry out the same analysis from the beautiful stranger’s view point. In this case, we let y be the probability of the column player choosing heads. The Beautiful Stranger’s Viewpoint Row 1 minimize z = max {5y – 2, -3y + 1 } subject to payoff to you. Row 2 0≤y≤ 1 3 Row 1 2 1 0 -1 -2 0 Row 2 5y – 2 -3y + 1 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 y The payoff as a function of y is the max of two linear functions, which is represented as the blue line. The beautiful stranger chooses the minimum of the blue line, which is at the black dot. It turns out that this is when y = 3/8. The payoff to the row player (that is, you) is -1/8, and thus the beautiful stranger wins. The payoffs are the same when y = 3/8 optimal payoff to row player = -1/8 payoff to you. Marilyn vos Savant chose y = 1/3, which would given the B.S. a payoff of 0. 3 Row 1 2 1 0 -1 -2 0 Row 2 5y – 2 -3y + 1 .1 .2 .3 .4 .5 .6 .7 .8 .9 1 y But inexplicably, Marilyn vos Savant chose y = 1/3, which is not optimal. Summary z 2-person 0 sum game theory z Can be solved using LP z 2-dimensional version can be solved graphically z Fundamental theorem z Marilyn vos Savant may be the person with the highest measured IQ, but she does not seem to know her game theory.