Introduction to Optimization 2-person Game Theory

z 2-person 0-sum (or constant sum) game theory – 2-dimensional – multi-dimensional – Comments on first midterm: • • • • practice test will be on line coverage: every lecture prior to game theory quiz difficulty < midterm difficulty < homework difficulty closed book, no calculator 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. 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. z Talk with your neighbor to see if you can guess if one person has an advantage in the previous game, and if so, who does? We will return to this game at the end of the lecture. z Incidentally, Marilyn vos Savant answered the question incorrectly. 2-person 0-sum game theory 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 We will run the game for 5 trials. R -2 1 2 2 -1 0 1 0 -2 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? Suppose that R and C are both brilliant players and they play a VERY LONG TIME. -2 1 2 2 -1 0 1 0 -2 We will find a the best guaranteed payoff to R using linear programming. Will R’s payoff be positive in the long run, or will it be negative, or will it converge to 0? 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. 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 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. Another example: Player R randomizes between row 1 and row 2. Prob. .5 × -2 -2 1 2 .5 + .5 × 2 2 -1 0 .5 + 0× 1 1 0 -2 0 Expected Payoff Exercise. Determine the expected payoffs. What can R guarantee? Optimizing for player R z Whatever random strategy (x1, x2, x3) that R chooses, we can quickly compute the payoff for each column. z We will let (x1, x2, x3) be decision variables, and we will write an LP that guarantees the maximum payoff. What is R’s best random strategy? Prob. x1 × -2 -2 1 2 x1 + x2 × 2 2 -1 0 x2 + x3 × 1 1 0 -2 x3 A B C Expected Payoff PA = -2 x1 + 2 x2 + x3 PB = PC = x1 2 x1 x2 - 2 x3 x1 + x2 + x3 = 1 R’s strategic problem, as an optimization problem. Expected Payoff Maximize -2 1 2 x1 2 -1 0 x2 1 0 -2 x3 A B C min (PA, PB, PC) PA = -2 x1 + 2 x2 + x3 PB = x1 - x2 PC = 2 x1 - 2 x3 x1 + x2 + x3 = 1 x1 , x2 , x3 ≥ 0 R’s strategic problem, as an LP Maximize min (PA, PB, PC) PA = -2 x1 + 2 x2 + x3 PB = x1 - x2 PC = 2 x1 - 2 x3 x1 + x2 + x3 = 1 x1 , x2 , x3 ≥ 0 Maximize z (the payoff to R) A: B: C: z ≤ -2 x1 + 2 x2 + x3 z ≤ x1 - x2 z ≤ 2 x1 - 2 x3 x1 + x2 + x3 = 1 x1 , x2 , x3 ≥ 0 2-person 0-sum game 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 An optimal random 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 payoff to R for Game 2R is 1/9. So, R can guarantee at least 1/9 for Game 1. On the payoff guarantee for R z R can guarantee a payoff of 1/9. – But R does not need to reveal a strategy to C. – Can R do better? z We will later show that C can guarantee that R gets at most 1/9. z But first … A 2-dimensional Example 0 4 2 1 The payoff matrix Game 2R: the row player declares his or her randomized strategy as follows: p = prob of selecting row 1 1-p = prob of selecting row 2 For each fixed value of p, the row player R can determine payoff for each column. In 2-dimensions, graph the payoff as a function of p, and then choose the best value of p. Graphing the payoff function: Step 1 Prob p × 0 0 4 p + (1-p) × 2 2 1 1-p payoff to R Payoff for Column 1: 2 – 2p 4 3 2 1 0 4 3 2 1 0 Column 1 0 .1 .2 .3 .4 .5 p .6 .7 .8 .9 1 Graphing the payoff function: Step 2 Prob p × 4 0 4 p + (1-p) × 1 2 1 1-p payoff to R Payoff for Column 2: 1 + 3p 4 3 2 1 0 4 3 2 1 0 Column 2 0 .1 .2 .3 .4 .5 p .6 .7 .8 .9 1 Graphing the payoff function: Step 3 4 Combine the two lines. 2 1 The blue line is the best that R can guarantee. payoff to R 0 4 3 2 1 0 4 3 2 1 0 Column 2 Column 1 0 .1 .2 .3 .4 .5 p .6 .7 .8 .9 1 Step 4. Player R chooses the best p. 0 4 2 1 The maximum guarantee can be chosen by selecting the best value of p. payoff to R payoff = 1.6 4 3 2 1 0 4 3 2 1 0 0 .1 .2 .3 .4 .5 p .6 .7 .8 .9 1 The column player’s viewpoint Prob q q × 0 + (1-q) × 4 1-q 0 4 2 1 Consider the best that the column player can guarantee. payoff to R Payoff for Row 1: 4 – 4q Row 1 4 3 2 1 0 0 .1 4 3 2 1 0 .2 .3 .4 .5 q .6 .7 .8 .9 1 The column player’s viewpoint Prob q q × 2 + (1-q) × 1 1-q 0 4 2 1 payoff to R Payoff for Row 2: 1 + q 4 3 2 1 0 4 3 2 1 0 Row 2 0 .1 .2 .3 .4 .5 q .6 .7 .8 .9 1 Graphing the payoff function: Step 3 4 Combine the two lines. 2 1 For each q, the column player can guarantee a payoff to R of at most the blue line. payoff to R 0 Row 1 4 3 2 1 0 4 3 2 1 0 Row 2 0 .1 .2 .3 .4 .5 q .6 .7 .8 .9 1 Determining the payoff 0 4 2 1 Player C looks at the payoff function and chooses the value of q that minimizes the payoff to R. payoff to R payoff = 1.6 Row 1 4 3 2 1 0 4 3 2 1 0 Row 2 0 .1 .2 .3 .4 .5 q .6 .7 .8 .9 1 Amazing Result z The lower bound for the value of the game for R and the upper bound are the same for all 2 person zero sum games. z That is, linear programming will give you the “value” of the game. This is the best the Row player can guarantee, and the column player can guarantee that no more is obtained. Summary so far z Game 2R: Player R chooses a random strategy and announces it. Then player C goes next. – lower bound on the payoff to R for the original game – LP-based approach – graph based approach z Game 2C: Player C chooses a random strategy and player R goes next. – This gives us an upper bound on the payoff to R for the original game – The upper and lower bounds will be the same Comments on announcing strategies z In reality, players do not announce strategies. z But the point is this: you can choose a mixed strategy that yields a maximum payoff P*, and your opponent can choose a mixed strategy that guarantees you earn no more than P*. z Playing against an opponent who is not perfect, you may do even better. But you can’t do worse if you choose your best mixed strategy. C chooses a random (mixed) strategy Prob. y1 y2 y3 -2 y1 + y2 + 2 y3 -2 1 2 2 y1 - y2 2 -1 0 1 0 -2 Exp. payoff y1 - 2 y3 Minimize v (the payoff to R) A: B: C: v ≥ -2 y1 + y2 + 2 x3 v ≥ 2 y1 - y2 v≥ y1 - 2 y3 y1 + y2 + y3 = 1 y1 , y2 , y3 ≥ 0 The best strategy for the column player for Game 2C 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 strategy for Game 2C, then R gets at most 1/9. A Fundamental Theorem of 0-sum Game Theory z Game 2R and Game 2C always produce the same optimal payoff to the R player. Let us call this optimal payoff P*. z The optimal mixed strategy for R always guarantees a payoff of at least P*, regardless of what C does. z The optimal mixed strategy for C always guarantees a payoff to R of at most P*, regardless of what R does. z This is a special case of Linear Programming Duality. The Fundamental Theorem in 2-dimensions. z We return to the 2-dimensional example z Review: In Game 2R, the Row Player could guarantee a payoff of 1.6 by setting p = .2 z We will see that in Game 2C, the Column Player can guarantee that the Row Player gets no more than 1.6 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? Determining the optimal strategy B. S. H T H T 3 -2 Prob -2 1 You are the row player. What is your best randomized strategy? p Payoff for Column 1: 3p + -2(1-p) = -2 + 5p 1-p payoff to you. 3 2 1 0 -1 -2 0 Column 1 .1 .2 .3 .4 .5 p .6 .7 .8 .9 3 2 1 0 -1 -2 1 Determining the optimal strategy B. S. H T H payoff to you. T 3 -2 Prob -2 1 p Payoff for Column 2: -2p + 1(1-p) = 1 - 3p 1-p 3 Column 1 2 1 0 -1 -2 0 Column 2 .1 .2 .3 .4 .5 p .6 .7 .8 .9 3 2 1 0 -1 -2 1 Determining the optimal strategy B. S. H T H 3 -2 p T -2 1 1-p payoff to you. The blue line is the guaranteed payoff. Prob Player R chooses the value of p that maximizes the payoff. 3 Column 1 2 1 0 -1 -2 0 Column 2 .1 .2 .3 .4 .5 p .6 .7 .8 .9 3 2 1 0 -1 -2 1 The payoff Payoff for Column 1: = -2 + 5p Payoff for Column 2: = 1 - 3p The payoffs are the same when p = 3/8 optimal payoff to row player = -1/8 Determining the optimal strategy B. S. H T What is your best randomized strategy for the Beautiful Stranger? H 3 -2 T -2 1 Marilyn vos Savant chose q = 1/3, which would given the B.S. a payoff of 0. payoff to You 3 2 1 0 -1 -2 0 3 2 1 0 -1 -2 .1 .2 .3 .4 .5 q .6 .7 .8 .9 1 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.