Linear programming in Python: CVXOPT and game theory
CVXOPT is an excellent Python package for linear programming. However, when I was getting started with it, I spent way too much time getting it to work with simple game theory example problems. This tutorial aims to shorten the startup time for everyone trying to use CVXOPT for more advanced problems.
All code is available here.
Installation of dependencies:
- Using Docker is the fastest way to run the code. In only 5 commands you can replicate my environment and run the code.
- Alternatively, the code has the following dependencies: Python (3.5.3), numpy (1.12.1), cvxopt (1.1.9), glpk optimizer (but you can use the default optimizer, glpk is better for some more advanced problems)
Please review how CVXOPT solves simple maximization problems. While this article focuses on game theory problems, it is critical to understand how CVXOPT defines optimization problems in general.
The first problem we will solve is a 2-player zero-sum game.
The constraints matrix A is defined as
A = [[3, -2, 2], [-1, 0, 4] ,[-4, -3, 1]]
Next, we define a maxmin helper function
def maxmin(self, A, solver="glpk"):
num_vars = len(A)
minimize matrix c
c = [-1] + [0 for i in range(num_vars)]
c = np.array(c, dtype="float")
c = matrix(c)
constraints G*x <= h
G = np.matrix(A, dtype="float").T reformat each variable is in a row
G *= -1 minimization constraint
G = np.vstack([G, np.eye(num_vars) * -1]) > 0 constraint for all vars
new_col = [1 for i in range(num_vars)] + [0 for i in range(num_vars)]
G = np.insert(G, 0, new_col, axis=1) insert utility column
G = matrix(G)
h = ([0 for i in range(num_vars)] +
[0 for i in range(num_vars)])
h = np.array(h, dtype="float")
h = matrix(h)
contraints Ax = b
A = [0] + [1 for i in range(num_vars)]
A = np.matrix(A, dtype="float")
A = matrix(A)
b = np.matrix(1, dtype="float")
b = matrix(b)
sol = solvers.lp(c=c, G=G, h=h, A=A, b=b, solver=solver)
return sol
Last, we use the maxmin helper function to solve our example problem:
sol = maxmin(A=A, solver=”glpk”) probs = sol[“x”] print(probs) [ 1.67e-01] [ 8.33e-01] [ 0.00e+00]
In other words, player A chooses action 1 with probility 1/6 and action 2 with probability 5/6.
Next we will solve a Correlated Equilibrium problem called Game of Chicken as defined on page 3 of this document. The constraints matrix A is defined as
A = [[6, 6], [2, 7], [7, 2], [0, 0]]
Next, we define a ce and build_ce_constraints helper functions:
def ce(self, A, solver=None):
num_vars = len(A)
maximize matrix c
c = [sum(i) for i in A] sum of payoffs for both players
c = np.array(c, dtype="float")
c = matrix(c)
c *= -1 cvxopt minimizes so *-1 to maximize
constraints G*x <= h
G = self.build_ce_constraints(A=A)
G = np.vstack([G, np.eye(num_vars) * -1]) > 0 constraint for all vars
h_size = len(G)
G = matrix(G)
h = [0 for i in range(h_size)]
h = np.array(h, dtype="float")
h = matrix(h)
contraints Ax = b
A = [1 for i in range(num_vars)]
A = np.matrix(A, dtype="float")
A = matrix(A)
b = np.matrix(1, dtype="float")
b = matrix(b)
sol = solvers.lp(c=c, G=G, h=h, A=A, b=b, solver=solver)
return sol
def build_ce_constraints(self, A):
num_vars = int(len(A) ** (1/2))
G = []
row player
for i in range(num_vars): action row i
for j in range(num_vars): action row j
if i != j:
constraints = [0 for i in A]
base_idx = i * num_vars
comp_idx = j * num_vars
for k in range(num_vars):
constraints[base_idx+k] = (- A[base_idx+k][0]
+ A[comp_idx+k][0])
G += [constraints]
col player
for i in range(num_vars): action column i
for j in range(num_vars): action column j
if i != j:
constraints = [0 for i in A]
for k in range(num_vars):
constraints[i + (k * num_vars)] = (
- A[i + (k * num_vars)][1]
+ A[j + (k * num_vars)][1])
G += [constraints]
return np.matrix(G, dtype="float")
Using the helper functions, we solve the Game of Chicken
sol = ce(A=A, solver="glpk") probs = sol["x"] print(probs) [ 5.00e-01] [ 2.50e-01] [ 2.50e-01] [ 0.00e+00]
In other words, the optimal strategy is for both players to select actions [6, 6] 50% of the time, actions [2, 7] 25% of the time, and action [7, 2] also 25% of the time.
Hopefully this overview helps in getting you started with linear programming and game theory in Python.
Credits: cvxopt.org/examples/tutorial/lp.html, cs.duke.edu/courses/fall12/cps270/lpandgames.pdf, en.wikipedia.org/wiki/Minimax#Example, https://www3.ul.ie/ramsey/Lectures/Operations_Research_2/gametheory4.pdf, cs.rutgers.edu/~mlittman/topics/nips02/nips02/greenwald.ps, cs.duke.edu/courses/fall16/compsci570/LPandGames.pdf