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.
--------