Skeletal Blog for Math 340, Fall 2015 September 9: Classes start. WE BEGIN TOPIC 1: read the supplemental article "Matrix Games and Poker," Sections 1-6 and 8, Appendix B. Later in the course we will cover Section 7 and solve the poker game described in Section 8. Sept 9-11: Sections 1, 2, and Appendix B. The payout matrix for the first poker game is at the beginning of Section 3. Sept 11: We now have a few matrix games: Rock/Paper/Scissors: BETTY Rock Paper Scissors Rock 0 -1 1 ALICE Paper 1 0 -1 Scissors -1 1 0 The above is the payout to Alice Matching Pennies: BETTY (wins on odd number) 1 penny 2 pennies ALICE 1 penny 1 -1 (wins on an 2 pennies -2 2 even number) The above is the payout to Alice Simplified Poker: BETTY calls folds (if given the chance) ALICE Bluff 0 1 Straight 1/2 0 two other suboptimal plays Bluff = Bet on Red, Bet on Black Straight = Bet on Red, Fold on Black Random Example: BETTY 1 2 -10 (the meaning of rows and columns ALICE 3 4 -17 is not important) -------- For simplified poker: Alice announces a pure strategy: value = 0 Alice announces a mixed strategy: value = 1/3 Betty announces a mixed strategy: value = 1/3 Betty announces a pure strategy: value = 1/2 -------- Week of Sept 14-18: We will analyze some 2 x 2 matrix games and make some general observations about matrix games. We begin by analyzing simplified poker, assuming an optimal mixed strategy and using linear algebra to rederive the above values. At this point we are not 100% sure that we have found the best strategies in the two mixed games, but our computations seem to indicate the best answer. --------- The game: BETTY 1 2 ALICE 3 4 Has the following game values: Alice announces a pure strategy: value = 3 Alice announces a mixed strategy: value = 3 Betty announces a mixed strategy: value = 3 Betty announces a pure strategy: value = 3 Here trying to find a mixed strategy for Alice with balanced values does not work: If Alice plays row 1 a fraction a of the time, and row 2 a fraction 1-a of the time, she presents Betty with the choice of a [ 1 2 ] + (1-a) [ 3 4 ] = [ 3 4 ] + a [ -2 -2 ] which can never be balanced, i.e., equal [ v v ] for some value v... -------- Up to Sept 30 : We have described the simplex method (Chapter 2 of Chvatal) and used it to solve linear programs, and in particular to solve matrix games where all the entries are positive; for example, for the game BETTY 1 2 ALICE 3 5 (which is very similar to a game that we analyzed above), we write [ 1 2 ] [ x1 1 - x1 ] [ ] >= [ v v ] [ 3 5 ] and we maximize v subject to the above inequality, and the constraints x1 >= 0 and 1 - x1 >= 0 . Since the simplex method requires v >= 0, and we can see that the value of the game is positive, we can start the simplex method max v subject to 1 - x1 >= 0 x1 + (1-x1) 3 >= v 2 x1 + (1-x1) 5 >= v (and x1,v >= 0). In standard form this becomes max v , s.t. x1 <= 1 2 x1 + v <= 3 3 x1 + v <= 5 x1,v >= 0 Yielding the dictionary z = v x2 = 1 - x1 x3 = 3 - 2 x1 - v x4 = 5 - 3 x1 - v so v enters the basis and x3 leaves, etc. --------- Oct 2: Imagine the matrix game BETTY 33 1 ALICE -1 33 We know the value of the mixed games is positive (if Alice plays 1/2, 1/2, the resulting row vector is [16 17], so the value of the mixed games is at least 16. But the linear program [ 33 1 ] [ x1 1 - x1 ] [ ] >= [ v v ] [ -1 33 ] leads to the first condition 33 x1 + (-1) (1 - x1) >= v , which in standard form looks like - 34 x1 - 1 >= v , i.e., 34 x1 + v <= -1 which leads to the slack variable x3 = -1 - 34 x1 - v which means our simplex method can't even start... So we use the "two-phase" method in Chvatal, Chapter 3. Consider a much simpler linear program with the same problem: max 12 x1 , subject to x1 >= 2, x1 >= 3, x1 <= 7 (and x1 >= 0), which leads to the dictionary z = 12 x1 x2 = -2 + x1 x3 = -3 + x1 x4 = 7 - x1 First phase: add auxilliary x0, pivot to feasibility, and make " min - x0 " the new objective. Such examples are given in class and in Chvatal Chapter 3. --------