Blog for Math 340, Fall 2014
September 3: Classes start.
WE BEGIN TOPIC 1: read the supplemental article "Matrix Games and Poker"
and look at the matrix games in Washburn's book to which "Matrix Games and
Poker" refers.
September 8: How to compute the value of a 2 x 2 matrix game.
Septmeber 10: Minmax and maxmin, Alice announces versus Betty announces,
dominant strategies, irreducible games, second remarkable
theorem and the 2^(52) x 2 game, exchanging Alice and
Betty, symmetric games (their values).
September 19: Begin simplex method
September 22,24: Simplex method: pivots, basic and non-basic variables.
September 24: Shall look at
(1) an unbounded example: max x_1 + x_2 s.t., x_1 <= 6 + x_2 , x_1,x_2>=0;
(2) an infeasible example: max whatever, s.t. x_1 <= -2 , x_1>=0;
(3) a feasible example that requires two phases:
max (whatever), s.t. x_1 >= 2, x_1 <= 6, x_1,x_2>=0.
Examples (2) and (3) illustrate Chapter 2, Section 3: "Initialization."
In all examples: the simplex method should give "proofs" of correctness.
September 29: Dealing with degenerate pivots, via the perturbation or
lexicographical method.
Remark: Game theory solvers usually have degenerate pivots.
The perturbation/lexicographical method takes care of degenerate pivots
and of ties in the leaving variable, and zeta (the objective) always
increases in terms of constant + epsilon1 * constant
+ epsilon2 * constant + ...
October 8: We use the simplex method (which shows that any feasible and
bounded LP has a final, feasible dictionary where the zeta row has all
negative coefficients), to show that in an m by n matrix game with
m > n (we took m=7 and n=2 in class), Alice has an optimal strategy
where she plays at most n rows.
October 10: Begin Chapter 5 of Vanderbei: Duality Theory.
- To every linear program there is a dual linear program
- Namely:
max c.x subject to Ax <= b and x >= 0
(so x,b,c are vectors, A is a matrix, and c.x means the dot product of
c and x)
has dual linear program:
min B.y subject to A^T y >= c and y >= 0 ,
or, in standard form:
max -B.y subject to - A^T y <= -c and y>= 0.
In other words, to change from primal (original) to dual we take
(c,A,b) and substitute (-b,-A^T,-c).
Remark: Vanderbei does not use the above vector notation, which is
conceptually very simple (I have no idea why he omits this...).
Vanderbei's text writes the whole thing out longhand... (See Section 5.2 of
Vanderbei.)
We get some immediate conclusions: any dictionary for the original
problem has a dual dictionary for the dual; the dual of an optimal
dictionary is an optimal dictionary for the dual.
Hence: an LP that is feasible and bounded has a dual which is feasible
and bounded with max c.x equalling min b.y .
Remark: the dual LP expressing Alice's optimal mixed strategy is just the
LP expressing Betty's optimal mixed strategy.
Proof: Assume that all of A's entries are positive. The LP for Alice's
best strategy is
max v subject to p^T A >= [v v ... v], p_1 + ... + p_m <= 1.
In standard form this is
max v s.t. A' x <= b, x >= 0, where
x = [v p_1 p_2 ... p_m], and A' is given in block form by
A' = [ e A^T ]
[ ]
[ 0 1 1 ... 1 ]
e is all 1's, and b is all 0's except a 1 in the final row. Now we
dualize.
We remark that if A does not have all positive entries, then we have to
use v_1 - v_2 instead of v, and have to write p_1 + ... + p_m is both
>= 1 and <= 1. This works similarly.
---------
Complementary slackness: The dual problem gives an upper bound for the
LP:
max c.x s.t. Ax <= b and x >= 0
essentially by multiplying by a non-negative column vector, y, on the right:
Ax <= b implies that (Ax).y <= b.y for any y.
It follows that if y* is an optimal solution for the dual problem, then
(Ax).y* <= b.Y* must hold with equality when x=x* is optimal; hence
(Ax*-b).y* = 0.
For any optimal solution, x* and y*. In other words:
If x* and y* are optimal solutions, then (Ax*-b).y* = 0, and hence if a
y* entry is positive, then then corresponding slack variable entry of
w* = Ax*-b must be zero; similarly if a value of w* is positive, then
the corresponding entry of y* must be zero. Similarly for x and the
slack variables of the dual linear program.
Conversely: if these "complementary slackness" conditions hold, then x* and
y* are optimal solutions.
Note: We can use "complementary slackness" (in "non-degenerate cases")
to determine the optimal dual strategy from a guess for the optimal
primal strategy.
Special cases:
(1) Our standard LP: max 4x_1 + 5x_2 s.t. x_1+x_2 <= 5, x_1 + 2x_2 <= 8,
2x_1 + x_2 <= 8, and x_1,x_2 >= 0.
(2) Game theory: if Alice has a mixed strategy p, such that
p^T A >= [v v ... v] for some v, and if Betty has a mixed strategy q
such that A q >= [w w ... w]^T for some w, and if v=w, then p and
q are, indeed, optimal mixed strategies.
Example:
(1) Let's say we guess that x_1=2, x_2=3 is an optimal solution for
our standard LP. Then we have x_1,x_2, and w_3 > 0 in this optimal
solution (w_3 being the slack variable w_3 = 8 - 2x_1 - x_2 , which
at our guess has the value 8 - 2(2) - (3) = 1 > 0 ). Hence for the
dual we expect that z_1=z_2=0 and y_3=0, for the dual LP
min 5 y_1 + 8 y_2 + 8 y_3 s.t. 4 <= y_1 + y_2 + 2 y_3 , and
5 <= y_1 + 2 y_2 + y_3 (and y_1,y_2,y_3 >= 0, as usual) (and where
z_1, z_2 are the slack variables corresponding to the two inequalities
in the usual fashion.)
So z_1 = 0 means that 4 = y_1 + y_2 + 2 y_3 ,
z_2 = 0 means that 5 = y_1 + 2 y_2 + y_3 ,
and y_3 = 0 means that we have 4 = y_1 + y_2, 5 = y_1 + 2 y_2.
Solving the last part gives y_1 = 3, y_2 = 1. We can check that this
is dual feasible, so we are done.
(2) Let's say we think Alice will play [ 1/2 1/2 ] in the game
[ 1 4 9 16 ]
A = [ ]
[ 16 9 4 1 ]
Then we see that Betty will choose columns 2 and 3. Is this complementary
slackness?
----------------------
LATER:
WE BEGIN TOPIC 3:
Read Chapter 5 of Vanderbei: Duality
- Duality Theory (5.1-5.4)
- Complementary Slackness (5.5)
- The Dual Simplex Method (5.6)
WE BEGIN TOPIC 4: