Linear Programming for Game Theory

Mathematica has several commands for doing linear programming and optimization.  If the problem is already in matrix form, the best is probably LinearProgramming.  Its one drawback is that the variables are put in a way that makes it neither a primal nor a dual LP problem!  We'll get around that with two new commands, PrimalLP and DualLP.  We also have here a few other commands and templates to make our lives easier.

You must run the following commands before using them, or doing any of the examples that follow!

PrimalLP[c_, A_, b_] := 
        LinearProgramming[-c, -A, -b];
DualLP[b_, A_, c_] := 
        LinearProgramming[b, Transpose[A], c];
NOnes[n_] := Table[1, {n}];

Examples

Section 3.1 Primal/Dual Pairs

To use PrimalLP, set c to be the vector of coefficients on the objective function to be maximized, set b to be the constraint vector, and A to be the coefficient matrix.  In other words, PrimalLP will maximize cx subject to Ax ≤ b.  Dually, DualLP will minimize by subject to A'y≥ c (where A' is the transpose of A).  This notation is consistent with our textbook.

The output of PrimalLP or DualLP is (one) optimal solution for the x or y variables.  To find the actual min or max of the objective function, evaluate cx or by.

Problems (3.2) and (3.6)

c = {-3, 2, 1};
A = {{1, 1, 1}};
b = {1};
PrimalLP[c, A, b]

c . PrimalLP[c, A, b]

DualLP[b, A, c]

b . DualLP[b, A, c]

Problems (3.5) and (3.7)

c = {1, 0, 0, -1};
A = {{1, 1, 1, -1}, {-1, -3, -1, 
            2}};
b = {2, -1};
PrimalLP[c, A, b]

c . PrimalLP[c, A, b]

DualLP[b, A, c]

b . DualLP[b, A, c]

Games

In order to use linear programming to solve games, we need to be able to do a few other things.  The constraint and coefficient vectors are all 1's, and we have the command NOnes for that.

Section 4.1

M = {{-2, 2, 1}, {0, -1, 3}, {2, 1, -1}, {-1, 3, 
            0}};
MatrixForm[M]

modifiedM = M + 3;
MatrixForm[modifiedM]

x = PrimalLP[NOnes[3], modifiedM, NOnes[4]]

v = NOnes[3] . x

y = DualLP[NOnes[4], modifiedM, NOnes[3]]

v = NOnes[4] . y

originalv = (1/v) - 3

q = x/v

p = y/v

SPSGW

SPSGW = {{0, -1, 1, 1, -1}, {1, 0, 
            1, -1, -1}, {-1, -1, 0, -1, 1}, {-1, 1, 
            1, 0, -1}, {1, 1, -1, 1, 
            0}};
MatrixForm[SPSGW]

modSPSGW = SPSGW + 2;
MatrixForm[modSPSGW]

x = PrimalLP[NOnes[5], modSPSGW, NOnes[5]]

v = NOnes[5] . x

p = x/v

Three-Finger Morra

Three = {{0, 2, 2, -3, 0, 0, -4, 0, 0}, {-2, 0, 0, 0, 3, 
            3, -4, 0, 0}, {-2, 0, 0, -3, 0, 0, 0, 4, 4}, {3, 0, 
            3, 0, -4, 0, 0, -5, 0}, {0, -3, 0, 4, 0, 4, 
            0, -5, 0}, {0, -3, 0, 0, -4, 0, 5, 0, 5}, {4, 4, 0, 
            0, 0, -5, 0, 0, -6}, {0, 0, -4, 5, 5, 0, 0, 
            0, -6}, {0, 0, -4, 0, 0, -5, 6, 6, 0}};

MatrixForm[Three]

modThree = Three + 7;

x = PrimalLP[NOnes[9], modThree, NOnes[9]]

v = NOnes[9] . x

p = x/v

originalv = (1/v) - 7

Colonel Blotto's Game

Still working on this!

Other tools and tricks for vectors and matrices

Here is an illustration of some of the tools and tricks you can use in Mathematica for vectors and matrices.  Note that a vector is a list of numbers enclosed by curly brackets, and a matrix is a list of vectors enclosed by curly brackets (so matrices begin and end with two curly brackets).

OurMatrix = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}

OurVector = {2, 3, 5}

MatrixForm[OurMatrix]

OurMatrix + 10

OurVector + 10

2*OurMatrix

Matrix multiplication, multiplication of a matrix by a vector, and dot product of two vectors all use "." (the period) between the two objects being multiplied.

OurMatrix . OurMatrix

OurMatrix . OurVector

OurVector . OurMatrix

OurVector . OurVector

Art Duval
October 2, 2005