Today I want to work through some stuff I struggled with in my current class. I haven’t done linear programming before in my life (college was a long time ago). Well, that changed a few weeks ago while trying to replicate a graph for Foe-Q and a graph for Correlated Equilibrium (CE-Q) of a zero sum game. In order to work my way through the assignment I started small and used the game of Rock, Paper, Scissors. The “trick” is adding the ‘U’ variable that you will minimize.

For the solver, I went with cvxopt and glpk since it was an order of magnitude faster than anything else. But, since I was on Windows it was a pain to get installed and I didn’t get nearly the speed up that Linux users got.

[python]

from cvxopt import matrix, solvers

glpksolver = ‘cvxopt_glpk’

[/python]

For the ‘c’ matrix we need to set the first column to -1 since we need to minimize the U variable to get the correct value.

[python]

#Minimize: U + R + P + S

c = matrix([-1.,0.,0.,0.])

[/python]

For the G matrix we need to build our equations. The first 3 set up the results. The first row is throwing Rock where you lose (-1) to Paper but win (+1) to Scissors. Row 2 is Paper’s results and row 3 is Scissors.

[python]

#1. U – P + S <= 0 => [1, 0,-1, 1]

#2. U + R – S <= 0 => [1, 1, 0,-1]

#3. U – R + P <= 0 => [1,-1, 1, 0]

[/python]

The second set of 3 rows is to ensure you can only throw a single play. Not, since we are using cvxopt we need to negate these. So, instead of R greater than or equal to 0 we need -R less than or equal to 0.

[python]

#4. -R <= 0 => [0,-1, 0, 0]

#5. -P <= 0 => [0, 0,-1, 0]

#6. -S <= 0 => [0, 0, 0,-1]

[/python]

The last set are the equality parameters. This ensure that we get a total 1 when the game is over. You can’t throw more than 1 play.

[python]

#7. R + P + S <= 1 => [0, 1, 1, 1]

#8. -R – P – S <=-1 => [0,-1,-1,-1]

[/python]

The h matrix is the results of the previous 8 equations.

[python]

h = matrix([0.,0.,0.,0.,0.,0.,1.,-1.])

[/python]

Here is the code:

[python]

from cvxopt import matrix, solvers

glpksolver = ‘cvxopt_glpk’

#Minimize: U + R + P + S

c = matrix([-1.,0.,0.,0.])

#1. U – P + S <= 0 => [1, 0,-1, 1]

#2. U + R – S <= 0 => [1, 1, 0,-1]

#3. U – R + P <= 0 => [1,-1, 1, 0]

#4. -R <= 0 => [0,-1, 0, 0]

#5. -P <= 0 => [0, 0,-1, 0]

#6. -S <= 0 => [0, 0, 0,-1]

#7. R + P + S <= 1 => [0, 1, 1, 1]

#8. -R – P – S <=-1 => [0,-1,-1,-1]

G = matrix([[1.,1.,1.,0.,0.,0.,0.,0.],[0.,1.,-1.,-1.,0.,0.,1.,-1],[-1.,0.,1.,0.,-1.,0.,1.,-1.],[1.,-1.,0.,0.,0.,-1.,1.,-1.]])

h = matrix([0.,0.,0.,0.,0.,0.,1.,-1.])

sol = solvers.lp(c,G,h, solver=glpksolver)

print(sol[‘status’])

print(sol[‘x’])

[/python]

To wrap this up, I was able to get the Foe-q graph replicated by setting up the linear equation to solve for minimax. But, CE-Q defeated me.